基于实时栅格法的多机器人协作建图

王曙光，唐浩漾

(西安邮电大学自动化学院，陕西西安710121)

用于协作定位、环境探索、地图构建的分布式多智能体系统成为研究的热点［1－2］。多机器人同步定位与地图构建(SLAM)要解决控制结构、协作模式、局部子地图融为全局地图的融合算法等问题。栅格地图是一种比较成功的地图标示方法，它简单、易扩展。二维栅格地图是把环境分割成若干正方形小区域，即栅格［3］，被障碍物占据的栅格赋值为1，无障碍物的栅格赋值为0。但栅格地图需要较大的存储空间，定位时计算量也很大。目前机器人对环境的探测，往往用激光雷达、GPS 定位仪等昂贵的传感器。文中提出一种实时栅格建图方法，依靠多机器人编队，进行定位建图，使用简单的传感器即可实时生成地图，不需要局部地图融合的过程，减少了计算量和存储空间［4］。

1 实时栅格法基本原理

1.1 原理

传统的栅格法，最初用于单个机器人建图，后来推广到多机器人协作，也只是各自划分一个小区域，独立探索，最后把局部地图融合成全局地图。而实时栅格法，栅格的划分是由机器人编队直接完成的，栅格也不再局限于正方形。

在机器人编队区域内，如果有障碍物的话，会遮挡机器人之间的“视线”，可以认为，被挡住的视线两侧的区域内存在障碍物，而未被遮挡的视线所围成的区域无障碍。如果机器人自身的位置已知，根据遮挡视线的情况，可以按照栅格法的原理确定障碍物的位置。假设有A、B、C、D 4 个机器人，排成正方形，如图1所示。X部分为障碍物。

图1 实时栅格法示意图

在图1所示情况下，机器人之间的视线“B－C”和“A－B”被遮挡，则AOB 和BOD 这两个三角形区域内，存在部分障碍。由视线“A－C”、“B－D”和“C－D”围成的区域无障碍。显然，图1 的探测结果误差太大。如果能把检测区域分割得较小，就能使检测误差变小。假定机器人在运动过程中，能一直保持正方形编队进行障碍探索。机器人编队在行进过程中，连续快速探测障碍，理论上应该能得出障碍物的基本形状。但连续检测，需要处理的数据多，通信协调也需要不断进行，效率很低，需要进行简化。

1.2 检测步距的确定

机器人编队每行进一段距离，进行一次“对视”检测，这个距离称为检测步距。对图1 的机器人编队，如果取检测步距为正方形边长的一半，将得到图中所示的检测效果。

若以C 为坐标原点，图1 中关于障碍的检测可以看成是3 次检测的合成:机器人C 在原点，初始位置的检测;编队沿x 轴平移1 个步距，C 到C1处，进行一次检测;编队沿y 平移，C 到C2处，进行一次检测。综合3 次的检测结果，图1 中，右上角的小正方形部分，表示有障碍的区域。与编队初始的一次检测结果比较，障碍物区域缩小了1 倍。如果要更加精确地描述障碍物区域，则需进一步减小步距。如果大正方形边长分成m 步，推算可知，对某一区域，最终结果是(2m－1)次检测的叠加，即(2m－1)个阴影的重叠部分。

由图可见:理论上，障碍物尺寸的最大误差是步距的一半，由实际误差要求，反推可得步距的大小。

1.3 计算

可以认为机器人对视的视线把检测区域分割成了一种特殊的栅格地图，参照栅格地图的处理方法，用一个2m×2m 的矩阵H 来表示，m 为步数。有障碍的栅格用1 表示，无障碍的栅格用0 表示。

每次检测，由于编队位置的变化，需要作坐标平移变换。设初始检测区域的矩阵为。多步平移后的检测，在始检测区域内的矩阵为Hx1，Hx2，……Hxm，及Hy1，Hy2，……Hym。

^表示矩阵对应元素相与。

2 编队控制

实时栅格法检测障碍，具有计算简单的特点，不需要进行局部地图的拼接。但是前提是机器人的编队必须保持相对位置不变。实际上，机器人运行中，队形肯定会有偏差;地面有起伏等环境因素也影响队形。队列的偏差，会造成栅格位置的误差，影响检测结果。所以，编队控制是实时栅格法的关键技术［5］。

机器人之间，采用定向红外器件进行障碍检测，同时测量机器人间的距离。由此，可检测机器人编队间的障碍遮挡情况，判断障碍物位置。机器人间使用无线传感器网络作为通信方式［6］。

在编队中，指定A 为主机器人，作为基准参考，B、C、D 跟随A 运动，并依次进行队形位置校正。A安装3 套红外收发器，分别指向B、C、D。机器人B向C、D 定向发射;C 向D 定向发射，D 只安装红外接收电路。红外接收器做成一个接收阵列，接收定向发来的信息。当机器人位置偏移时，接收阵列会检测到偏移的方向，据此来调整机器人的位置，保持队形。每个机器人的位置都由另外两个机器人的光束定位。当出现偏移时，按顺序依次校正，防止循环出现误差。为防止队形出现向心或离心的缩放，机器人A同时利用红外传感器测距，保持机器人的相对距离也不发生变化。机器人A 的运动方向靠电子罗盘来检测并保持。假定编队以机器人AB 为前方，程序处理流程如图2 和图3所示。

图2 机器人A 的工作流程

图3 其他机器人的工作流程

还有一种情况，就是机器人的行进路径上存在障碍物，它必须绕行，这会破坏编队的队形。采用基于观察者的多机器人编队控制方法，结合领导－跟随法和VHF+避障法，能够有效地绕过障碍。指定被阻挡的机器人作为观察者，利用VFH + 避障法绕过障碍;领导者根据观察者的运动轨迹和传感器信息，并根据队形的可通过性控制跟随者绕过障碍［7］。通过障碍后，编队要初始化，重新组织队形。

文献［8］指出:当运动速度不高，一个采样周期内，机器人编队可以稳定保持。

当环境探索结束时，可以测量机器人的相对位置，看是否出现较大偏差。如果有，进行一定的反演补偿。

3 硬件结构

在此编队中，4 个机器人的结构和功能是相似的。A 起领导作用，功能稍强。图4 是机器人A 的结构，主要包括处理器、电池及电机驱动模块、光电编码器、定向红外发射电路、短距离无线通信模块、外侧障碍检测模块等部分。

图4 机器人A 的结构框图

处理器采用ARM7;定向红外发射器有3 组，分别指向B、C 和D;红外避碰检测传感器安装在编队外侧，用来判断机器人是否遇到障碍或到达环境边界;光电编码器用来计算编队行进距离。

机器人B、C 和D 不安装电子罗盘和光电编码器。机器人A 依靠角度和里程计算确定编队的位置［9］，进而划分栅格的位置。

4 实验验证

在博创InnoSTAR 机器人平台上，安装传感器及通信模块，进行了验证。实验中，取机器人正方形编队的边距为1.6 m，检测步距为0.4 m，障碍物为一直径约0.3 m的圆柱形物体。实验结果如图5所示，圆形阴影部分所占据的栅格为理想检测状态，即用圆点表示的栅格。实验表明，编队在运动10 个步距后，对图中所示位置的检测，出现误差的概率小于2%。运动15 个步距后，出现误差的概率显著增大，在“－”或“+”标注的栅格检测到障碍的概率达到30%以上。

实验表明:在误差允许的范围内，此方法能够保持机器人编队基本稳定，能够按照实时栅格法对有障碍的区域进行探索建图。

对于检测误差，根本原因还是机器人行进距离累积误差造成的。减小这个误差，能够提高建图的准确性，增大有效探测范围。

图5 实验检测结果

5 结论

实时栅格法是综合了机器人编队控制的栅格建图法，方法简单，不需要精密昂贵的探测仪器和设备，能够在低成本的小型机器人上实现，缺点是探测速度较慢。由于编队的特点，实时栅格法最适合检测孤立的“岛型”障碍物，不适合检测尺寸庞大的障碍物或迷宫走廊式环境。对编队控制还可以进一步研究，使其环境适应性更好，能及时调整机器人的位置，减小误差。

【1】SIM R，ROY N.Global A-Optimal Robot Exploration in SLAM［C］// Proceedings of the 2005 IEEE International Conference on Robotics and Automation，2005:661－666.

【2】AMIGONI F，CAGLIOTI V.An Information-based Exploration Strategy for Environment Mapping with Mobile Robots［J］.Robotics and Autonomous Systems，2010，58(5):684－699.

【3】于金霞，王璐，蔡自兴.未知环境中移动机器人自定位技术［M］.北京:电子工业出版社，2011:7，56.

【4】蔡自兴.多移动机器人协调原理与技术［M］.北京:国防工业出版社，2011:126，137.

【5】杨甜甜，刘志远，陈虹.移动机器人编队控制的现状与问题［J］.智能系统学报，2007(2):21－27.

【6】冯国栋，刘敏，王国利.实现机器人随动的红外感知方法［J］.机器人，2012，34(1):104－109.

【7】雷斌，曾良才.未知环境中基于观察者的多机器人编队控制方法［J］.武汉科技大学学报，2011，34(6):195－197.

【8】吴俊，陆宇平.基于网络通信的多机器人系统的稳定性分析［J］.自动化学报，2010，36(12):1706－1710.

【9】ZHU Yanping，HUANG Daqing.Location Algorithm Using Distance and Angle Information in Wireless Sensor Networks［J］.Transactions of Nanjing University of Aeronautics ＆ Astronauti，2009，26(1):58－64.