未知环境中自主机器人环境探索与地图构建

王东署， 王海涛

(郑州大学电气工程学院 河南郑州450001)

0 引言

自主移动机器人是机器人技术的一个重要研究领域，已广泛应用于工农业生产、交通、服务、医疗和军事等领域.随着应用环境的复杂化，人类对移动机器人的自主性和智能性提出了更高的要求，特别是在大规模未知极限或复杂环境下，如深海探索、太空探索及核事故处理等领域，人类期望机器人能自主完成环境的探索，并创建环境地图.因此，在未知环境中进行环境探索，并根据任务的不同同时构建相应的环境地图是自主移动机器人应具备的基本能力.

机器人对环境的探索通常看作是NBV(next best view)问题［1］，即在已探测的环境中选取一个最好的观测点作为目标点，并驶向该观测点，然后通过多次迭代，直到完成对整个工作环境的遍历.在探索过程中，机器人必须解决如下3个关键问题:如何根据传感器提供的信息来产生一系列候选观测点;如何从机器人当前位置运动到下一最优观测点;如何对获得的传感器信息进行相应处理以构建出机器人能理解的环境地图.其中前两步可归为环境探索，第三步可归为地图构建，环境探索又可进一步细分为候选观测点的选取和评估.

早期候选观测点的选取主要采用随机算法［2］，该方法具有很大的随机性，研究人员必须考虑对随机点的过滤和环境遍历等问题.为了提高机器人环境探索的效率，Yamauchi［1］提出了前沿探测理论，其基本思想是将已知区域与未知区域的交界定义为前沿，探索过程中使机器人尽可能地驶向未知区域，并使期望的信息增益最大，同时能快速降低地图信息中的不确定性因素，该探索策略具有一定的趋向性，是目前探索策略的核心思想，被广泛采用［3-6］.除此之外，Freda等［7］提出了利用前沿理论随机生成观测位置，并使候选位置趋向于未探测区域的混合算法.该算法的核心思想是创建一个结构树，为树中的节点生成随机探测方向，在该探测方向上选择候选观测点.这种方法可以使候选观测点分布于信息增益较大的边界上，提高了探测效率.

候选观测点的评估则主要通过建立一个效用函数［3-6，8-11］来衡量候选观测点的效用值，效用函数中一般包括机器人的转向角度、机器人与目标点间的运动距离、探测未知区域面积(信息增益)、机器人运动损耗等信息.早期的效用函数采用单一指标，如文献［1］采用最小运行距离作为评价候选观测点的参考指标.现在更多的效用函数采用两个或多个指标的组合，如最小运行距离与信息增益的线性组合［8］及非线性组合［9］，最小运行距离、信息增益和重叠率的加权平均［10］等.

机器人在对环境进行探索的过程中需要将对外界环境的感知以地图的形式存储起来.目前常用的地图表示方法分为三类:度量地图、拓扑地图和混合地图［12］.自主机器人未知环境探索与地图创建是两个相辅相成的研究内容，应该是在同一过程中同时进行的.但很多研究将二者分开进行，在设计环境探索策略时很少考虑地图构建算法的实现.作者将自主环境探索与地图构建的研究相结合，提出了可同时实现环境探索与地图创建的方法.在环境探索阶段，基于前沿探测理论，提出了具有避障功能的环境探索策略;在地图构建阶段，提出了基于增长的神经气网络的地图构建方法，该方法以神经气网络的节点作为拓扑网络的网络节点，以少量的神经气网络节点分布来描述具有大量特征信息的未知环境，建立了能准确描述环境的且易于机器人理解、规划与决策的拓扑网络地图.

1 未知环境中的探索

移动机器人在完全未知的环境中，必须通过自身配带的传感器对当前所处的环境进行扫描而获取环境信息，并且根据所获得的环境信息选取合适的位置点作为探索的目标点，进而指导机器人在未知环境中不断探索，直到对整个未知环境进行完全遍历.

1.1 坐标转换

移动机器人环境探索的目的是为了建立环境地图，环境探索也是未知环境中构建环境地图的必要手段，因此，将移动机器人探索的信息转换成环境地图的坐标信息，对于环境认知研究是一个必不可少的步骤.图1所示为机器人探索点的坐标与环境地图绝对坐标之间的转换示意图.公式如下:

式中，(X，Y)表示探索目标点在环境地图中的坐标，(Xr，Yr)表示移动机器人在环境地图中的位置坐标，DL表示目标点与移动机器人的距离，α表示移动机器人的航向角，β表示目标点的激光束与激光雷达的夹角．

1.2 探索策略

根据前沿探测理论，假设激光传感器探测的边缘均分为19个探测点.从中筛选出合适的候选观测点，从而得到最佳的观测点作为该步骤目标点，并且驶向该目标点.该方法简单实用，可以快速有效地对未知环境进行探索，并且具有避障功能.具体的探索策略步骤如下:

(1)初始化移动机器人位置与航向角.

(2)移动机器人利用传感器扫描获取环境信息，筛选符合以下条件的点为候选观测点:①该点必须是探测的前沿点，不被障碍物遮挡;②该点处于未探索环境中.

(3)若筛选出来的候选观测点被障碍物分为M组，则按以下准则选出最优观测点:①从M组中选取包含候选观测点最多的一组，若同时有两组或两组以上含有最多候选观测点，则选取与机器人航向角偏向角度最小的一组;②选择该组N个候选观测点中处于中间位置的点作为最优观测点.

被选择的候选组中所有候选探测点标记为已知，未被选中组的候选观测点标记为未知，当下次被探测到时才标记为已知.

图2中用小圆圈表示移动机器人当前位置，方块表示障碍物，星号点表示激光传感器19个探测点，其中被障碍物占据了6个.探测点被分成两组，第一组包含9个探测点，第二组包含4个探测点.首先选择具有9个探测点这组，然后选择9个探测点处于中间位置的探测点为最优观测点.同时，第一组的9个探测点标记为已知点，第二组的4个探测点标记为未知点.

(4)移动机器人在驶向目标节点的过程中，移动设定步长后要对环境信息进行更新，具体更新过程详见环境地图的构建部分.

(5)移动机器人到达目标节点后，如果有符合候选观测点的条件则重复步骤(2)、(3)、(4);否则，机器人自转设定的角度后再次查看.

(6)检测已探测环境中所有候选探测点的标记值，如果有未知候选观测点，则驱动机器人行驶到该点进行探测.

图1 探索点的坐标与环境地图绝对坐标的转换Fig．1 Transition between coordinate of exploration pointand absolute coordinate of environment map

图2 候选观测点的选取Fig．2 Choices of candidate observation point

(7)当所有的候选观测点标记值都为已知，则认为移动机器人完成了整个环境空间遍历，停止工作.该过程的流程图如图3所示.

图3 环境探索流程图Fig．3 Flowchart of environment exploration

2 基于GNG网络的拓扑环境地图的构建

GNG(growing neural gas)是由Fritzke［13］提出的一种生长的神经气网络，是一种非监督的、生长型的聚类算法，其神经网络的规模具有可增减特性.GNG算法不必预先知道输入空间的分布特点，但是在实际系统当中，需要预先估计输入空间的大小等情况来估计网络大小、生成速度及其他参数.GNG网络是由网络节点(node)和网络节点之间的连接线(edge)两部分构成.

机器人对环境的探索是个动态递增的过程，该探索过程可通过GNG网络在动态的输入空间中不断地学习生成拓扑网络节点来实现.GNG网络的可增长性体现在规模可增长和结构可增长，即随着输入空间的不断增长，用来表示输入空间的网络映射图不断增长.随着网络节点不断自我学习，自组织地发现输入空间中数据的分布特性，并将这种特性反映在映射输出空间中.输入空间中数据密集的地方在映射空间中占据较多的网络节点，能准确地实现输入空间的模式聚类和模式分类［14］.

基于GNG网络的拓扑地图构建算法步骤如下:

(1)初始化节点空间N，具有两个已知节点N1，N2，对应的向量为

(2)初始化信号输入空间S，随机生成一个输入信号s，且s的概率为1/S，对应的向量为

(3)分别计算输入信号s与节点N1和N2的距离，以区分最近点和次近点，假设N1为最近点．

(4)若N1和N2之间没有连接边，则连接两点，且设置该连接边的老化度为0．

(6)更新最近点N1以及与之有连接的节点的位置:

(7)最近节点N1的连接边老化度加1，如果老化度＞Agemax，则删除该连接边，同时删除没有连接边的节点．

(8)返回步骤(2)，如果信号点个数为λ的整数倍且当前网络节点未达到最大网络节点数，则插入新节点N．新节点N产生步骤如下:①找到具有最大累计误差的节点A;②找到与节点A连接的节点中具有最大累计误差的节点B;③新节点向量④删除节点A与节点B的连接边，分别连接节点A与N，B与N;⑤ 更新节点空间N内所有节点的累计误差eN=eN-β×eN．

(9)网络节点数达到设定数目，移动机器人驶向新目标点，返回步骤(2).

3 仿真实验

3.1 探索路径的生成

仿真实验是在Matlab环境下进行的.工作环境选取10 m×10 m的未知环境，其中设有若干规则障碍物.移动机器人装配有激光测距仪和里程计，激光传感器探测距离为2 m，扫描角度为180°.仿真图中用小圆圈表示移动机器人，半圆区域为激光测距仪扫描区域，其余图形表示障碍物.

该仿真实验中设定机器人步长为0.5 m，扫描分辨角度为10°，自转角度为90°.机器人从初始位置开始，按照1.2节叙述的探索策略在未知环境中进行探索，其探索路径如图4所示.

图4 探索过程Fig．4 Exploration procedure

3.2 环境地图的构建

在机器人探索环境过程中，按照第2节介绍的地图构建规则创建如图5所示的环境地图.该仿真实验中，五角星表示GNG网络的节点，每个节点表示一个以该节点为中心的可行区域，黑色连线表示各节点的连接边.各参数取值如下:λ =200，ew=0．5，en=0．000 5，β =0．000 5，Agemax=108，最大网络节点数设置为500.

图5中的三幅图依次与图4中的三幅图相对应，通过仿真可以看到，移动机器人较为圆满地完成了环境探索和地图创建的任务.在该环境中，机器人成功地躲避了障碍物，顺利地完成环境的探索，基本上没有出现陷入死区和环境信息的重复探测.在该探索过程中，路程损耗31.8 m，旋转角度为389°，环境遍历程度(覆盖性)为92%.

图5 地图生成过程Fig．5 Map building procedure

由图5中的三幅图可知:①随着机器人对环境探索的不断深入，通过不断地增加网络节点来实时更新环境地图，认识新的环境.因此，所提方法实现了自主机器人在环境探索的同时，同步进行地图构建的功能.②由最后获得的环境地图可以看出，用少量的GNG网络节点就可以获得大量的地图信息，且机器人在环境中探索的时间越长，获得可行区域的信息越多，对环境的认知就越充分.③验证了所提出的拓扑地图模型能很好地表示可行空间地图的连通性，其具有的增长特性表示了机器人对环境的学习过程.

从仿真结果可以看出，利用GNG网络生成的混合地图有如下优点:①GNG网络通过对网络节点累计误差的计算来调整网络节点的位置，从而保证生成的地图网络节点分布均匀.②GNG网络可以动态地删除、增加网络节点以及连接边，因此可以通过机器人的不断巡游，把局部的环境信息连接起来形成全局环境地图.③传统的环境建模方法需要对传感器采集的信息进行识别，确定墙壁或者障碍物，作者所提算法不需要对采集的信息进行识别，可减少计算的复杂度，尤其针对不规则障碍物的识别具有很好的处理效果.

4 结论

提出了未知环境中移动机器人同时环境探索和地图构建的策略方法.该方法利用随机探索策略引导移动机器人在未知环境中进行探索，同时利用GNG网络的增长特性，通过不断增加新的拓扑网络节点来对周围环境进行抽象提取，随着移动机器人的不断探索，生成易于机器人理解的环境地图，并能指示该地图中的可行区域、障碍物等信息.采用该方法所建立的环境地图，能使机器人在环境探索过程中，实时地更新地图、学习环境，体现了聚类、降维、自学习及自适应的特点.

［1］ Yamauchi B.A frontier-based approach for autonomous exploration［C］//Proceedings of the IEEE International Symposium on Computational Intelligence in Robotics and Automation.Monterey，1997:146-151.

［2］ Tovar B，Murrieta-Cid R，Esteves C.Robot motion planning for map building［C］//Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems.Lausanne，2002:673-680.

［3］ Basilico N，Amigoni F.Exploration strategies based on multicriteria decision making for search and rescue autonomous robots［C］//Proceedings of 10th International Conference on Autonomous Agents and Multiagent Systems.Taipei，2011:99-106.

［4］ Jens W，Karsten B.Ground plan based exploration with a mobile indoor robot［C］//Proceedings of the 7th German Conference on Robotics.Munich，2012:452-457.

［5］ Hirashita S，Yairi T.Information-based exploration strategy for mobile robot in dynamic environment［C］//Proceedings of the 8th IEEE International Symposium on Computational Intelligence in Robotics and Automation.Daejeon，2009:90-95.

［6］ Taillandier P，Stinckwich S.Using the PROMETHEE multi-criteria decision making method to define new exploration strategies for rescue robots［C］//Proceedings of the IEEE International Symposium on Safety，Security，and Rescue Robotics.Kyoto，2011:321-326.

［7］ Freda L，Oriolo G.Frontier-based probabilistic strategies for sensor-based exploration［C］//Proceedings of the IEEE Interna-tional Conference on Robotics and Automation.Barcelona，2005:2892-2898.

［8］ Stachniss C，Burgard W.Exploring unknown environments with mobile robots using coverage maps［C］//Proceedings of the 18th International Joint Conference on Artificial Intelligence.San Francisco，2003:1127-1132.

［9］ González-Baños H H，Latombe J.Navigation strategies for exploring indoor environments［J］.International Journal of Robotic Research，2002，21(10/11):829-848.

［10］Dirk H，Nicola B，Francesco A.A comparative evaluation of exploration strategies and heuristics to improve them［C］//Proceedings of the European Conference on Mobile Robotics.Oerebro，2011:1-6.

［11］张明状，庄严，王伟，等.移动机器人即时环境探索与地图库构建［J］.东南大学学报:自然科学版，2009，39(1):111-115.

［12］仲朝亮，刘士荣，杨帆.动态环境下基于GNG网络的拓扑地图构建［J］.华东理工大学学报:自然科学版，2012，38(1):63-68.

［13］ Fritzke B.A growing neural gas network learns topologies［J］.Advances in Neural Information Processing Systems，1995(7):625-632.

［14］仲朝亮，刘士荣，邱雪娜.未知环境下基于GNG网络的环境地图自主认知［C］//第29届中国控制会议.北京，2010:3768-3772.