基于随机行走的群机器人二维地图构建

陆国庆，孙 昊

（河北工业大学人工智能与数据科学学院，天津 300130）

0 引言

群机器人系统是由数量众多、具有简单结构和功能一致的机器人组成的，群体机器人是研究通过使用局部规则协调大量相对简单机器人的群体［1］。它不同于单机器人或者多机器人系统，群机器人系统自身具有高度灵活性和较强的容错性，能适应各种未知环境和高效率执行单个及多个任务。因此，群机器人广泛应用于大规模侦察搜救、探索等领域。

目前移动机器人地图所用到的传感器主要有激光雷达和视觉传感器。视觉传感器主要有单目摄像头和双目摄像头，所采集的图像信息量大，但同时造成了很大的计算量；激光雷达的测量精确，虽然价格较昂贵，但应用场景十分广泛，例如可以在黑暗环境下进行测量。由于传感器的差异和环境中噪声的影响，地图构建技术主要存在的问题是测量误差和信息的不完整［1］。单个机器人在构建环境地图时，由于其自身的搜索范围局限和自身发生故障等情况，对未知环境的地图构建效率较低。群机器人的数量优势以及较强的鲁棒性，比单个机器人地图构建的效率更高。

地图构建作为同步定位与建图（Simultaneous Localization and Mapping，SLAM）技术的一部分，目前大部分研究多集中于单个机器人，对于多个机器人构建未知环境地图的研究较少。文献［2］中利用多个搭载单目摄像头的微型飞行器进行未知环境的地图构建，设置地面固定站估计机器人位姿，然后构建每个机器人的地图，最后再融合所有地图，但是该方法采用视觉进行地图构建，相较于激光雷达应用场景较为有限。文献［3］中将粒子群算法应用到多机器人SLAM 中，计算两个“相撞”机器人的相对位姿，将两个机器人的先前和接下来的地图信息融合成一个共同地图；但是该算法两个机器人之间的位姿计算相较于随机行走算法较为复杂。文献［4］中利用粒子群优化算法进行局部地图间的配准，然后融合成全局地图。文献［5］中将未知环境划分成4 个区域来避免多移动机器人陷入障碍物区域，对障碍物区域的地图构建不够准确，有一定的局限性。

随机行走算法在群机器人中实现简单，自由度和容错性较高，与其他复杂的SLAM 算法相比，机器人之间不需要太多的交流以及机器人实时的定位，大大减少了算法计算的复杂度和时间。群机器人地图构建中用到的随机行走算法主要有布朗运动、相关随机游走、Lévy flight、弹道运动等，这些随机运动算法可以概述为：机器人随机选择一个运动方向，然后朝着该方向运动直到新的运动方向产生［6］。文献［6］中对群机器人随机行走构建地图，对比了多种随机行走算法进行小范围的地图构建，其中机器人运动采用弹道运动时效果较好；但机器人重复在小范围内的随机运动必然导致过多的重复搜索，降低了构建地图的精确度，并且采用弹道运动的方法构建完整的小范围地图中残留了过多的机器人的轨迹，影响了地图构建的准确性。Pang等［7］提出了一种基于布朗运动和Lévy flight 的改进随机行走方法，该方法将机器人分散在不同的区域并通过控制群机器人的搜索区域和搜索步长来减小搜索的重复区域，提高了搜索效率。该方法虽然能够提高搜索效率，但需要根据环境的变化去频繁调整机器人的搜索区域面积和步长，并且在未知的大环境中并不能很好地调整合适每个机器人的搜索面积的大小以及解决如何分散放置的问题，设置过大的搜索步长容易错失较多的区域地图信息。Ramachandran 等［8］提出了一种只需依赖局部机器人间交流的分布式构建地图方法，每个机器人都装备激光雷达传感器，通过自身的距离测量和相邻机器人传递的地图信息来构建地图，机器人的运动采用基于机器人间相互信息影响的Lévy flight，该算法中传递地图信息需要机器人之间良好的沟通，机器人随机行走可能会出现接收其他机器人信息不完全的情况。本文中所有机器人产生的局部地图由固定节点的地图融合算法进行融合，避免了机器人间传递地图信息导致的误差和复杂度。在利用随机行走及其相关改进算法进行多机器人建图的相关研究中，虽然都可以进行一定范围的未知环境地图构建，但是由于随机行走的随机性，难以避免多个机器人重复搜索某个区域的问题，降低了多个机器人的地图构建效率，机器人搜索过程中频繁的大范围的角度旋转也会增大地图构建的准确性。对于未知环境，如何简单高效地构建出更大范围的环境地图仍是一个研究热点。

本文对布朗运动进行改进，提出了一种适合群机器人快速搜索和精确构建环境地图的改进布朗运动随机行走算法，通过改进的布朗运动，使机器人在不进行局部沟通的情况下也能搜索到更多的区域，并且通过限制机器人随机行走的旋转角度使机器人相同时间内可以搜索到更多的区域，机器人随机行走中旋转次数的减少也提高了构建地图的精度。本文算法计算简单，降低了复杂度。该算法中个体机器人的移动是随机向前运动随机距离，然后旋转随机角度来模拟分子的布朗运动，对机器人旋转角度进行了限制，使群体中的单个机器人能够在初始运动方向的具体范围内随机向前运动，降低搜索区域的重复度，避免了因为运动方向突变导致机器人构建地图的面积和准确度的下降。机器人在搜索过程中利用激光雷达传感器构建环境地图。在仿真实验中，搭载激光雷达的多个移动机器人依靠改进布朗运动随机行走算法自主地进行搜索和搜索区域建图，并且在仿真环境中加入一些障碍物，在单个机器人随机行走算法中加入避障算法。地图构建算法和地图融合算法分别采用了GMapping 算法和Multirobot_map_merge算法。

1 随机行走算法

随机行走又称为随机漫步、随机游走等，这类运动的特征是无法根据前一步的运动去预测下一步的运动方向，“随机游走”一词最早由卡尔·皮尔森于1905 年提出。随机游走可应用于许多科学领域，包括生态学、心理学、计算机科学、物理学、化学、生物学以及经济学。

布朗运动{B(t)，t≥0}是一个非负实域连续的随机过程，它满足B(0)=0，并且{B(t)-B(s)}～N(0，t-s)。应用在机器人随机行走中，机器人向前移动由正态分布函数随机产生的给定步长，然后转向从搜索空间随机选择的方向，依次重复这个过程。

本文提出了一种基于改进布朗运动的随机行走算法。在该算法中，群机器人初始位置固定，机器人群数量为N，机器人步长α为标准正态分布中的任意正数取值，保证机器人始终向前运动，因此每一步的步长任意变化，单个机器人初始速度为V，单个机器人的初始位置已知。假定地图中心点为全局坐标系原点，可以得到第n个机器人初始坐标和初始运动方向，则单个机器人初始位姿可以用（xn0，yn0，θn0）表示。单个机器人的随机行走算法如图1 所示。初始时，机器人在初始位置在某个范围内随机选择转角增量，前进一个步长，然后重复此过程，运动过程中机器人的速度恒定。改进布朗运动随机行走算法的数学模型如下：

图1 单个机器人模拟布朗运动示意图Fig.1 Schematic diagram of single robot simulating Brownian motion

其中：Sn表示第n个机器人在M步长里运动的总里程，αi表示机器人第i步的步长，P为标准正态分布函数的值域；（xn，yn）表示机器人第n个机器人在第i步长的坐标，θni表示第n个机器人在第i步长的运动方向，l为[-1，1]区间的随机数，β表示单位转角增量。

为了使群机器人在最短时间内提取到更多环境特征，本文提出的随机行走算法与其他随机行走不同之处在于机器人随机行走时角度变化被限定在固定范围内，每前进一个步长都要进行运动方向的角度调整，角度调整的可变范围是一定的，这样就保证了每个机器人能够依照初始运动方向在某个梯形区域内运动，避免了因为大幅度旋转角度变化造成的某个区域的缺失，运动过程中依靠机器人里程计可以实时得到机器人位置。环境范围越大，机器人个体的数量越多，机器人可扫描到的区域越大，构建的地图越精确。

本文使用Matlab分别对布朗运动和本文提出的改进布朗运动随机行走进行了简单的无障碍物群机器人的运动轨迹仿真，初始坐标点为（0，0），机器人数量为10，二者的运动步数均设置为100，单位转角增量β设置为30°。布朗运动的仿真结果如图2（a）所示，本文提出的算法的仿真结果如图2（b）所示。从机器人运动轨迹仿真结果可以看出，相同步数下，机器人布朗运动搜索到的区域重复性很高，相较于本文提出的改进布朗运动随机行走算法小得多；本文提出的改进布朗运动随机行走算法覆盖的区域较大，而且减小了搜索区域的重复度，提高了群机器人地图构建的效率。

在实际实验过程中，由于在实验环境中添加了障碍物，所以为了避免与障碍物相撞使机器人无法运动，本文采用了简单的避障算法，如图3 所示。该算法通过激光雷达采集到的数据判断与障碍物的距离，设置最小距离D，当机器人激光雷达采集到的距离数据最小值小于D时，停止随机行走，机器人的旋转γ设置为60°。

图3 避障过程Fig.3 Obstacle avoidance process

2 群机器人地图构建

2.1 GMapping算法

机器人构建的地图一般分为栅格地图、拓扑地图、特征地图，本次介绍的GMapping 算法［9］，所构建的是二维栅格地图。在本文中，搭载激光雷达传感器的单个机器人对环境进行地图构建采用了GMapping 算法。GMapping 为2007 年在机器人操作系统（Robot Operating System，ROS）中开源的SLAM 软件包，是目前使用最广泛的软件包。它可用于室内和室外，应用改进的自适应Rao-Blackwellized 粒子滤波算法来进行定位与建图。GMapping 可以实时构建室内地图，在构建小场景地图时所需的计算量较小且精度较高，并有效利用了车轮里程计信息，相较于Hector 和Cartographer 算法，对激光雷达频率要求低、鲁棒性高，不需要太多的粒子且没有回环检测，因此计算量小于Cartographer而精度相差不大。该算法基于RBPF粒子滤波算法，即将定位和建图过程分离，先进行定位再进行建图。GMapping 在RBPF 算法上做了两个主要的改进：改进提议分布和选择性重采样。ROS中GMapping框架如图4所示。

图4 ROS中GMapping框架Fig.4 GMapping framework in ROS

2.2 Multirobot_map_merge算法

Multirobot_map_merge 算法的实现基于ROS 框架，主要解决了运动的机器人识别、初始位姿估计和地图合成问题［10］。借助ROS 的通信机制，机器人的内部交流只需要依赖ROS 的话题机制和服务机制。该算法可以合成任意数量机器人的地图，并且可以在实验环境下改变机器人的数量，因此特别适合大规模数量的机器人地图合成。ROS 中Multirobot_map_merge 框架图如图5 所示。本文的群机器人中的每个机器人在运动过程中通过话题机制向Multirobot_map_merge 节点发布话题，通过订阅每个机器人的话题将局部地图合成为全局地图。

图5 ROS中multirobot_map_merge框架图Fig.5 multirobot_map_merge framework in ROS

机器人的局部地图融合成全局地图过程中，首先需要计算机器人和全局坐标系之间的坐标变换，假定机器人的坐标系相对于全局坐标系的变换需要分别在X轴和Y轴平移a、b个单位，然后旋转φ，则机器人坐标系在全局坐标系下的变换关系可以表示为：

在对局部地图进行平移旋转变换后，再对局部地图中的关键特征（黑色所表示的障碍物部分）进行检测，对局部地图中相互重合的部分进行特征匹配，保留每个局部地图重叠部分的特征，最后在地图重合部分对关键特征进行校准，校准中需要对重叠区域黑色栅格所占据的部分进行统一化校对，即采取“求同去异”原则。只处理每个机器人的局部地图重合区域的关键特征一定程度降低了计算的复杂度。

3 仿真实验

3.1 实验环境

本次实验在Linux 系统下基于ROS 通信框架进行，Stage是ROS 中的一个实现物理仿真的工具包，可以模拟机器人以及环境中的很多物理特性。通过Stage搭建了一个20 m×20 m的环境，在环境中添加障碍物，如图6 所示。仿真实验所用的机器人为TurtleBot，TurtleBot 配备了一个激光雷达用于地图构建，可以很好地采集周围环境特征用于更精确的建图。实验中采用Rviz 显示机器人的运动状态和地图信息，Rviz 是一款显示多种数据的三维可视化工具，能够实时显示机器人传感器的信息、机器人的运动状态、周围环境的变化等。图7 是群机器人在仿真中的通信结构，包括各节点发布及订阅的话题和消息。图8是各个机器人坐标之间的关系。

图6 Stage中的仿真环境Fig.6 Simulation environment created in Stage

图7 ROS下机器人的节点和话题Fig.7 Nodes and topics of robots under ROS

图8 ROS下机器人坐标之间的关系Fig.8 Coordinates relationship of robots under ROS

3.2 实验过程和结果

群机器人随机行走进行建图，不同机器人数量、最大转角增量的大小、随机行走的步数都是影响地图构建的重要因素，为了探究本文提出的改进布朗运动随机行走算法的优越性，分别从机器人数量、最大转角增量、行走步数等方面与布朗运动进行对比验证。实验仿真环境的完整地图如图9所示。

图9 仿真环境完整地图Fig.9 Complete map of simulation environment

3.2.1 不同最大转角增量

实验开始时将机器人组成的群体放置于地图固定区域，初始运动方向随机设置，机器人激光雷达的扫描角度为120°，机器人的最大转角增量分别设置为β=30°，β=90°，β=180°。机器人数量设置为3，初始位姿分别为（0，0，0）、（0，1，0）、(0，-1，0)，运动步数设置为100。不同最大转角增量重复进行10 次实验，选取最优地图进行对比，实验结果如图10所示。

3.2.2 不同机器人数量

实验开始时将机器人组成的群体放置于地图固定区域，初始运动方向随机设置，机器人激光雷达的扫描角度为120°，群机器人初始最大转角增量为30°，运动步数设置为100。机器人数量分别设置为3和5，如图6所示，初始位姿分别设置为（0，0，0）、（0，1，0）、(0，-1，0)和（0，0，0）、（0，1，0）、(0，-1，0)、（2，0，0）、(-2，0，0)。不同机器人数量重复进行10 次实验，选取最优地图进行对比，实验结果如图11所示。

3.2.3 不同运动步数

实验开始时将机器人组成的群体放置于地图固定区域，初始运动方向固定，机器人激光雷达的扫描角度为120°，群机器人初始最大转角增量为30°，机器人数量设置为3，初始位姿分别为（0，0，0）、（0，1，0）、(0，-1，0)，运动步数设置分别为50、100、200。不同运动步数重复进行10 次实验，选取最优地图进行对比，实验结果如图12所示。

图12 群机器人不同运动步数地图构建Fig.12 Mapping of swarm robots with different movement steps

3.2.4 不同方法

本文提出的改进布朗运动与文献［6］中提出的弹道运动方法进行了相同运动步数下建图效果的对比，包括最后建图的实际仿真效果图以及机器人的运动轨迹图的对比。机器人搜索时间设置为60 s，改进布朗运动的最大转角增量设置为30°，机器人数量设置为3，初始位姿分别为（0，0，0）、（0，1，0）、（0，-1，0）。最终实验结果如图13和表4所示。

表4 不同机器人运动方法覆盖率对比Tab.4 Comparison of coverage ratio with different robot movement methods

图13 群机器人不同方法地图构建Fig.13 Mapping of swarm robots with different methods

3.2.5 实验结果分析

移动机器人激光雷达采用GMapping 算法所构建的是二维栅格地图，地图的灰色区域代表未知区域，白色区域代表已搜索区域，黑色线条表示障碍物。对群机器人随机行走构建的地图结果与仿真环境地图比较，从搜索区域大小和准确度两方面进行定性分析。

如图10 所示，在机器人数量、运动步数相同，不同最大转角增量情况下，最大转角增量越大，机器人随机运动方向的选择范围越大，机器人搜索区域的重复面积也越大，机器人运动可旋转的角度越大，导致运动方向大幅度的随机变化，使得激光雷达构建的地图的准确性下降，群机器人采取布朗运动构建地图面积最小，地图准确度也最差。

图10 群机器人不同最大转角增量地图构建Fig.10 Mapping of swarm robots under different maximum rotation angle increments

如图11 所示，在最大转角增量、运动步数相同，机器人数量不同的情况下，机器人数量由3 个增加到5 个时，相同运动步数下，群机器人的搜索区域面积明显增加，相较布朗运动，改进布朗运动所构建地图的精度更高；但是受限于激光雷达的仿真精确性，理论上机器人数量越多，所需要的计算能力越高，所以在准确性上会出现构建地图的准确度略微下降的情况。在本次仿真实验中，受限于自身实验电脑的配置，只进行了3个和5个机器人的仿真实验，但是从仿真中也可以明显看出本文提出的改进布朗运动随机行走的优越性。

图12 展示本文提出的改进布朗运动随机行走和布朗运动在不同运动步数下机器人构建地图的面积和准确性。与布朗运动相比，随着运动步数的增加，群机器人构建地图的面积也在增加，本文改进布朗运动随机行走能够搜索到更大区域，构建的地图面积和地图精确性更高。布朗运动构建的地图发生整体歪斜的情况，这是由于在大范围旋转时过多重复搜索区域导致地图准确度下降。

表1～4 分别从机器人构建的地图覆盖率的平均值、标准差、建图效率定量分析了最大转角增量、机器人数量和运动步数对地图构建的影响。地图覆盖率是指已构建的地图面积与总的环境地图面积的比值，地图覆盖率的平均值反映了地图构建的区域的面积；标准差反映了建图的准确度，标准差的衡量主要通过真实地图与所构建地图重合度的计算，标准差越大，地图的准确度越高。为了从时间和空间角度定量评价建图的可靠性，通过计算所构建地图的覆盖面积与搜索时间的比值以及标准差的关系来综合评价建图效率，建图效率的值越大，建图效率越高。

表1 不同最大转角增量覆盖率对比Tab.1 Comparison of coverage ratio with different maximum rotation angle increments

表2 不同数量机器人覆盖率对比Tab.2 Comparison of coverage ratio with different numbers of robots

表3 不同运动步数覆盖率对比Tab.3 Comparison of coverage ratio with different movement steps

在改进布朗运动与采用弹道运动进行建图的对比中，通过图13 的相同时间下最终建图结果与机器人的运动轨迹中可以看出，改进后的布朗运动能够搜索到更多的区域，在表4的定量分析中，改进布朗运动在地图覆盖率以及地图构建准确度方面都要优于弹道运动。

从仿真实验的结果中可以看出，本文提出的改进布朗运动随机行走算法通过限制机器人随机运动时的旋转角度范围减少了重复区域的搜索，提高了未知环境下地图构建效率。在相同环境下，机器人数量和运动步数都会对所构建地图产生影响，通过对机器人旋转角度的限制可以很好地避免由于大范围旋转造成的偏差，提高群机器人构建的地图的精度。

4 结语

未知环境的地图构建作为机器人领域的重要部分，对机器人发展有着深远的影响，本文针对机器人在未知环境快速和准确地构建环境地图进行了研究，提出了一种基于布朗运动的群机器人改进布朗运动随机行走算法，该算法在群机器人地图构建中的应用使机器人能在不进行复杂沟通情况下快速构建未知环境地图，提高了地图构建效率。受限于激光雷达和里程计的准确性，机器人构建地图时不可避免存在一定的误差，导致构建的地图准确度略有下降，未来会通过相关算法对误差进行补偿和构建地图的校正。另外，群机器人在未知环境探索领域的应用相较复杂结构的单个机器人具有更大的优势，以后的研究工作应该致力于实现复杂未知场景下精确地图的构建等相关工作。