基于安全性的自主環境探索算法的改進方法

陳靖輝 崔巖 曾東香

摘 ?要：文章首先基于機器人自主環境探索問題分析對比了基于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.