基于安全性的自主环境探索算法的改进方法

陈靖辉 崔岩 曾东香

摘  要：文章首先基于机器人自主环境探索问题分析对比了基于SLAM算法的自主探索方法、快速探索树算法、Frontier-Based边界探索算法等的优缺点，并深入分析了Frontier-Based边界探索算法在实际应用中遇到的两个问题，文章针对以上两个问题提出了基于膨胀障碍物的边界提取改进方法和基于膨胀边界线的边界点检测改进算法。最后使用机器人操作系统和Gazabo等工具实验证明了改进算法可有效提高机器人在自主探索过程中的安全性和探索效率。

关键词：自主探索;移动机器人;边界点

中图分类号：TP39          文献标志码：A         文章编号：2095-2945（2020）01-0033-04

Abstract： Firstly， based on the problem of autonomous environment exploration of robot， this paper analyzes and compares the advantages and disadvantages of autonomous exploration method based on SLAM algorithm， fast search tree algorithm and Frontier-Based boundary exploration algorithm， and makes an in-depth analysis of the two problems encountered in the practical application of Frontier-Based boundary exploration algorithm. Aiming at the above two problems， this paper proposes an improved boundary extraction method based on expansion obstacles and an improved boundary point detection algorithm based on expansion boundary. Finally， experiments using robot operating system and Gazabo tools show that the improved algorithm can effectively improve the security and efficiency of the robot in the process of autonomous exploration.

Keywords： autonomous exploration; mobile robot; boundary point

引言

自主環境探索是将机器人放置在一个陌生的环境中，机器人依据一定的探索策略，自主生成目标点，并规划移动路线向目标点前进，同时定位自身位姿建立周围环境，到达目标点后再重新生成目标点重复以上动作，直至探索完整个未知环境[1]。

在自主探索领域有大量学者提出了多种解决方案。文献[2]中作者在同时定位与建图[3-6]（Simult-aneous Localization And Mapping， SLAM）的基础上，使用元胞自动机的方式逐步向外辐射最终完成探索任务，但是此方法要求严格，它需要坐标轴和未知环境中检测出的特征线保持特殊关系，因此对机器人的初始位姿要求严苛;文献[7]中，作者提出一种快速探索随机树[7]（Rapidly-exploring Random Trees， RRT）算法，此方法是在栅格地图上随机地选择下一个需探索的目标点，并在前进过程的同时建立探索树，以路径规划的方式完成未知环境的探索任务，虽然在实际应用中较其他算法高效，但是此方法需要提前设置探索区域以及目标点，因此并不能达到机器人自主性的要求;文献[8-16]同样是以SLAM技术为基础，在进行SLAM的过程中完成探索任务，但是和文献[17-19]一样，都是利用路径规划的方式完成探索任务，需要提前知道探索区域和目标点，并不能自主选择下一个探索目标点。目前较为广泛使用的一种方法是文献[20-21]中提出的Frontier-Based边界探索算法，并有学者将其推广到多机器人协作探索领域[22-23]。文中作者假设在已探索完成和未探索区域的交会处可以获得更多的信息。其中已探索区域和未探索区域的交汇处作者定义为“边界”，作者认为当机器人前进到边界点处时，能够探索到更多的未探明区域，因此可以在此处获得更多新的区域的环境信息，地图也会随之更新扩展，同时又会出现新的边界。通过对边界的不断探索，机器人将会探索完整个未知环境。由文献[9]可知此方法是可行的，但是在动态环境中由于未知环境不断的变化，此方法在实际应用中会出现算法提取到的边界点机器人无法到达、机器人向目标点前进时碰撞到障碍物等问题。因此此方法在实际应用中不够安全和完美，对此本文提出了改进方法。

1 Frontier-Based边界探索算法问题分析

1.1 算法提取到的边界点不可用

Frontier-Based边界探索算法是以栅格地图为基础进行探索。所有的栅格依据是否被占用分为三种：空闲栅格、占用栅格和未知栅格，以此分类即可将整个未知环境划分为空闲区域、障碍物和未探索区域。因此文献[9]中定义的边界即为空闲区域和未知区域的交界处。检测边界点时首先检测地图中的空闲栅格，如果空闲栅格的邻域中包括未知栅格，则认为此栅格属于边界点。如图1所示，其中黑色栅格表示障碍物、白色栅格表示空闲区域、灰色栅格表示未探索区域，中间的深灰色栅格表示正在检测的栅格。

图1（a）中检测栅格的八个邻域中有5个未知栅格和3个空闲栅格，则此栅格为一个边界点;图1（b）中检测栅格的八个邻域中有3个障碍物栅格和2个未知栅格3个空闲栅格，因此此栅格同样为分界点;而图1（c）中检测栅格的八个邻域中有5个障碍物栅格和3个空闲栅格并没有未知栅格，所以此栅格不是边界点。以此方法可方便的提取出地图中的分界点，但是使用此方法提取出的边界点中机器人并不一定都可以到达。例如由上文分析可知图

1（b）中的检测点为分界点，但是此分界点紧挨着障碍物，因此这类边界点并不适合做下一个探索点。

1.2 机器人移动时撞到隐障碍物

Frontier-Based边界探索算法除了1.1节所提出的问题外，另一个存在的问题是机器人未探索的区域并不一定都是空闲区域，一种真实存在的可能是在机器人检测的边界线处正好是障碍物，在动态环境中此种情况极有可能发生。机器人在边界点集中选取下一个待探测的栅格后，由于移动路径不长，或者路径规划时间过长等可能，机器人在下次规划路径前已经到达了探测目标点，这样机器人存在撞上隐障碍物的风险。

如图2所示的情况，图中深灰色栅格表示机器人位置，图2（a）表示机器人从当前位置向下一个探索点规划的路径，在图2（b）中随着机器人向前移动的过程中，虽然已更新了地图信息，已检测出探测点处的障碍物，但是由于没有及时重新规划路径，机器人会沿着原始规划的路径前进，最终撞上障碍物。

2 Frontier-Based边界提取改进方法

2.1 基于膨胀障碍物的边界提取方法

针对1.1节中分析的问题，本文提出一种基于膨胀障碍物的边界提取方法。在地图中提取边界点之前首先对障碍物栅格进行膨胀操作。膨胀操作是指将障碍物栅格周边的一定膨胀长度内的栅格都标记为障碍物栅格，如图3所示，图3（a）为原始地图示意图，其中黑色区域为障碍物，图3（b）中显示了通过膨胀操作后障碍物地图结果示意图。

本文将膨胀长度设置为机器人半径大小。图3为障碍物进行膨胀操作前后提取边界点的对比图，图中黑色表示障碍物，白色表示空闲区域。在图3（a）中检测到9个边界点，而对障碍物进行膨胀操作后检测到的边界点减少到3个，并且这3个边界点都离障碍物有一定的距离，处在机器人可以顺利通过的位置。由此可见，本文所提出的在提取边界点前先对障碍物进行膨胀操作的策略不仅可以提高机器人移动时的安全性，同时提高了检测边界点算法的效率。

2.2 基于膨胀边界线的边界点检测算法

针对1.2节中分析的问题，本文提出一种基于膨胀边界线的边界点检测算法。在检测边界点前先对空闲区域和未知区域的边界线进行膨胀操作，同样本文将膨胀长度设置为机器人半径大小，然后在膨胀区域和未知区域的交界處检测边界点，最后从所有的边界点中按照一定策略选取下一个待探索的目标点，然后规划路径，并向目标点前进。

图4是基于膨胀边界线的边界点检测算法示意图，从图4（a）中可以看出，机器人在空闲区域和膨胀区域的交界线上选取一个栅格点作为下一个待探测的目标点，并规划出来移动路线，在图4（b）中可以看出，机器人在移动到待探索栅格点后，与障碍物保持着一定的距离，到达目标点后再重新检测下一个待探测点。由此可以看出本文提出的基于膨胀边界线的检测算法可有效提高机器人运动中的安全性。

3 实验与分析

3.1 实验设置

本实验在Ubuntu16.04系统上实现，采用机器人操作系统（Robot Operating System， ROS）平台，以及开源软件 Rviz作为实验结果的可视化展示，同时使用经典的SLAM算法（Gmapping算法）对周围环境进行建图。图5显示的是实验时所用到的世界地图，使用Gazabo模拟器模拟。

3.2 实验结果

实验结果如图6所示，其中图6（a）-（c）为原始算法建图结果，原始算法在障碍物周围提取边界点时经常提取到障碍物附近的栅格点，如图6（a）所示，可以看出原始算法所选取的边界点处于障碍物处，由于此类边界点距离障碍物太近，机器人移动到目标点后碰撞到障碍物。因此此类边界点不适合作为下一个探索点。如图6（b）（c）所示算法提取出的边界点正好位于空白区域与未探索区域的交界处，若此类边界点作为下一个待探索点，那么机器人极有可能碰撞到隐障碍物。

由图6（d）（e）可以看出改进算法所提取到的探索点是在膨胀边界与空闲栅格的交界处选取，由于对边界线以及障碍物做了膨胀操作，所以改进算法所提取到的边界点距离边界线和障碍物栅格都有一定的距离，由图6（f）可以看出在膨胀边界与空闲栅格的交界处选取的边界点作为下一个待探索节点机器人可以有效的规划出路径并安全无碰撞的通过狭窄障碍物。因此此类边界点作为探索点可保证机器人在移动过程中的安全性。

4 结束语

本文基于机器人自主环境探索的多种算法出发，分析了各算法优缺点，并就Frontier-Based边界探索算法在实际应用中所遇到的两个问题，本文提出了基于膨胀障碍物的边界提取方法和基于膨胀边界线的边界点检测算法，以栅格地图为例，具体分析了原算法在实际应用中遇到问题的原因，从理论上解决了原算法选取的边界点不合理的问题。最后利用实验证明改进算法的有效性。虽然改进算法在安全性上有了较高的提升，但是同时也增加了算法复杂度。

参考文献：

[1]王栎斐.移动机器人动态室内场景中的自主环境探索[D].大连理工大学，2018.

[2]陈炜楠，刘冠峰，李俊良，等.室内环境的元胞自动机SLAM算法[J].机器人，2016，38（2）：169-177.

[3]祁健诚.基于双目SLAM的室内导航系统[J].通讯世界，2019，26（01）：194-195.

[4]Liu， Jia， Xie， Yulei， Gu， Shuang， et al. A SLAM-based Mobile Augmented Reality Tracking Registration Algorithm[J]. International Journal of Pattern Recognition and Artificial Intelligence， 2019（1）.

[5]Kalogeiton， V. S， Ioannidis， K， Sirakoulis， G. Ch， et al. Real-Time Active SLAM and Obstacle Avoidance for an Autonomous Robot Based on Stereo Vision[J]. Cybernetics & Systems， 2019，50（3）：1-22.

[6]Nicholson L， Milford M， Sünderhauf N. QuadricSLAM： Dual Quadrics from Object Detections as Landmarks in Object-oriented SLAM[C]// 2018.

[7]Aguinaga I， Diego Borro， Luis Matey. Parallel RRT-based path planning for selective disassembly planning[J]. International Journal of Advanced Manufacturing Technology， 2008，36（11）：1221-1233.

[8]王彤彤.動态环境下移动机器人路径规划方法研究[D].哈尔滨工程大学，2018.

[9]Cepeda， Jesús S， Chaimowicz L， Soto R， et al. A Behavior-Based Strategy for Single and Multi-Robot Autonomous Exploration[J]. Sensors， 2012，12（12）：12772-12797.

[10] Dang H， Song J， Guo Q. An Efficient Algorithm for Robot Maze-Solving[C]// International Conference on Intelligent Human-machine Systems & Cybernetics. IEEE， 2010.

[11]陈洋，谭艳平，程磊，等.邻域约束下空地异构机器人系统路径规划方法[J].机器人，2017，39（1）：1-7.

[12]陈冬梅，张思民，李涛.室内动态环境下的机器人路径规划方法、装置和机器人[P].CN106774347A，2017.

[13]张捍东，陈阳，吴玉秀.未知环境下移动机器人实时路径规划[J].计算机工程与应用，2018，54（19）：146-152.

[14]张明状.移动机器人室内环境自主探索与认知[D].大连理工大学，2009.

[15]Yamauchi B. A Frontier-Based Approach for Autonomous Navigation[J]. N Rodng of H Nrnaonal Ymom on Omaonal Nllgn Robo & Aomaon， 1997：146-151.

[16]李秀智，邱欢，贾松敏，等.基于动态精简式混合地图的移动机器人自主探索[J].控制与决策，2017，32（5）：817-822.

[17]王丹阳.移动机器人室内环境探索与路径规划问题的研究[D].北京工业大学，2016.

[18]苏鸿明，陈雄，韩建达.多机器人的改进型边界探索算法[J].系统工程与电子技术，2009，31（4）：901-904.

[19]任玉洁，付丽霞，张勇，等.基于平滑A*人工势场法的机器人动态路径规划[J].软件导刊，2018（1）：8-10.

[20]Yamauchi B. A frontier-based approach for autonomous exploration[C]// Computational Intelligence in Robotics and Automation，1997. CIRA'97. Proceedings.1997 IEEE InternationalSymposium on. IEEE， 1997.

[21]高环宇，邓国庆，张龙，等.基于Frontier-Based边界探索和探索树的未知区域探索方法[J].计算机应用，2017，37（a02）：120-126.

[22]苏鸿明，陈雄，韩建达.多机器人的改进型边界探索算法[J].系统工程与电子技术，2009，31（4）：901-904.

[23]刘栋，童敏明，路红蕊.无人机多机协作探索煤矿灾变环境算法[J].计算机应用，2017，37（08）：279-282+298.