基于復合探索策略的多機器人未知環境探索算法

柳全澤 姚芝鳳

摘要：為解決多機器人探索算法存在的計算資源大，探索后期效率較低等問題，提出了一種基于復合探索策略的多機器人未知環境探索算法。該算法分為三3個模塊，首先，利用機器人傳感器構建初始地圖，并使用基于快速邊界和基于RRT的探索算法來獲取邊界點，；其次，對邊界點進行過濾和聚類以減少邊界點數量并降低計算量，；最后，通過任務分配模塊，綜合計算相對每個機器人的邊界點信息增益、導航成本和定位精度等因素后引導機器人前往未知區域。通過在不同開闊程度的仿真環境下進行對比實驗，結果表明，該算法提高了探索效率，并在復雜環境下表現出了更好的探索性能。

關鍵詞：RRT算法?快速邊界探索?任務分配?多機器人

中圖分類號：TP242?????文獻標識碼：A

The?Multi-Robot?Unknown?Environment?Exploration?Algorithm?Based?on?the?Composite?Exploration?Strategy

LIU?QuanzZe???YAO?Zhifeng

（Qiqihar?University，Qiqihar，Heilongjiang?Province，161006?China）

Abstract：?A?multi-robot?unknown?environment?exploration?algorithm?based?on?the?composite?exploration?strategy?is?proposed?to?solve?the?problems?of?large?computing?resources?and?low?efficiency?in?the?later?stage?of?exploration?of?the?multi-robot?exploration?algorithm.?The?algorithm?is?divided?into?three?modules.?Firstly，?it?uses?robot?sensors?to?construct??the?initial?map，?and?uses?fast?boundary-based?and?RRT-based?exploration?algorithms?to?obtain?boundary?points.?Secondly，?it?filters?and?clusters?frontier?points?to?reduce?the?number?of?boundary?points?and?computing?effort.?Finally，?it?comprehensively?calculates?the?factors?such?as?the?boundary?point?information?gain，?navigation?cost?and?positioning?accuracy?relative?to?each?robot，?and?then?guides?robots?to?unknown?areas?by?the?task?assignment?module.Comparative?experiments?are?conducted?in?simulated?environments?with?different?degrees?of?openness，?and?results?show?that?the?algorithm?improves?exploration?efficiency?and?shows?better?exploration?performance?in?complex?environments.

Key?Words：?RRT?algorithm;?Fast?frontier?exploration;?Task?assignment;?Multi-robot

未知環境探索是機器人研究領域的一個重要方向，其目的是讓機器人在有限時間內利用傳感器從地圖中獲取信息，以更小的成本和時間對未知環境進行探索。

最早的自主探索策略是由Yamauchi提出的基于邊界的自主探索策略，其論文中提出將地圖分割為已知區域和未知區域，通過引導機器人前往已知區域與未知區域之間的邊界來完成探索任務。但該算法僅通過地圖來獲取邊界，對所有邊界都平等對待，使得計算資源巨大，也就導致了重復探索問題的出現。在此基礎上，孫旭東在其論文中針對邊界點選取問題提出了一種僅處理激光讀取數據的邊界檢測算法（（FFD算法）[1]FFD算法）。該算法雖然降低了邊界探索算法的時間，但是對候選邊界的評估有所欠缺，同樣容易產生無效不可達邊界。

在之后的研究中，鄧志超在其論文中提出了另一種基于快速探索隨機樹的自主探索策略，，簡稱RFD算法[2]。該探索策略基于RRT算法，利用RRT算法對于未知區域的傾向性，通過RRT樹的生長獲取到邊界點來引導機器人前往未知區域。但由于RRT算法的隨機性，生成的邊界點分布并不均勻，這會導致在狹窄地圖環境中探索效率下降，不能很好地完成自主探索任務。

針對以上問題，本該文提出了一種基于復合探索策略的多機器人邊界探測算法（Multi-robot?Frontier?Detection?Algorithm?Based?on?a?Composite?Exploration?Strategy，簡稱MFD算法）。該算法將基于邊界的探索算法和基于RRT的探索算法進行結合。首先，每個機器人單獨執行一個基于快速邊界探索算法的局部探索模塊，通過傳感器獲取自身雷達探測范圍內的邊界點；同時，以每個機器人的初始位置為根節點在整個地圖中生成RRT樹，構建了一種多根節點的RRT全局探索算法。并引入動態步長機制，提高了RRT樹在已知區域的生長速度。其次將兩種探索算法獲取到的邊界點發送到過濾模塊進行聚類過濾。最后通過任務分配模塊，綜合考慮相對每個機器人的邊界點信息增益、導航成本和定位精度等因素，對每個機器人分配對應的最優邊界點以實現整個多機器人自主探索策略。整個探索策略流程如下圖1所示。

1?基于簡化快速邊界探索的局部自主探索策略

基于邊界的自主探索策略是目前較為常用的一種自主探索策略，當機器人地圖中移動同時構建新地圖時，基于邊界的檢測算法可以立即識別地圖上的邊界點。本文該文采用一種基于快速邊界探索的探索算法[13]并對其進行改進。由于可以通過后續的邊界點過濾模塊對探索到的邊界點進行過濾，從而不需要對先前探測到的邊界點進行維護。因此，改進后的快速邊界探測算法僅包含三3個步驟：（1），分別為排序分類；（2）、構建邊界輪廓；（3）、探測新邊界。

整體探索流程如下圖2所示。

首先（步驟1）以每個機器人自身為中心作為極坐標的原點，根據角度對傳感器范圍內的讀數進行排序。通過SORT_POLAR函數進行坐標轉換，隨后根據排序好的激光數據讀數構建邊界輪廓（步驟2-7），根據激光雷達獲取的數據，通過調用GET_LINE函數計算每個相鄰像素點之間的連線，并將所有的連線與激光讀數獲取的點融合構成邊界輪廓。

最后，我們根據算法計算獲得的輪廓構建新邊界（步驟8-21），對于輪廓中的相連的每個像素點，存在三3種情況。

（1）當前像素點不是邊界單元格，則代表它可以被忽略，因為該點不存在新的有用信息。

（2）當前像素點和其相連的點都是邊界單元格，則證明兩個點都屬于同一邊界點，則將當前像素點作為邊界點發送到過濾模塊，并略過剩余與其相連的單元格。

（3）當前像素點為邊界點，而與其相連的像素點不為邊界單元格，則僅將當前像素點作為新的邊界點發送到過濾模塊。

通過上述流程，我們可以從每個機器人通過激光雷達獲取的數據中獲取其附近的邊界點，并通過過濾模塊對其進行聚類和過濾，對冗余邊界點和已探索過的邊界點進行刪除，將剩余的邊界點發送給任務分配模塊分配給每個機器人以實現自主探索。

2?基于多根節點的改進RRT自主探索策略

該探索策略與寧宇銘等人論文[24]中的全局探測模塊算法流程基本相同，我們在其基礎上進行了一定程度的改進。RRT樹首先以每個機器人的初始位置作為初始頂點和邊集合開始，并且在每次迭代時都會通過函數在地圖中隨機選取一個點，在RRT樹中找到距離最近的一個頂點。然后，通過函數判斷與之間是否存在障礙物或未知區域，根據判斷結果，分三3種情況決定RRT樹的生長步長。

（1）如果函數返回值為1，即與之間不存在障礙物和未探索區域，那么就將直接作為新節點加入到樹中。

（2）如果函數返回值為-1，即與之間存在未知區域，則進行二次判斷，首先沿向xrand以最大步長進行延伸獲得點，之后再次通過函數判斷與之間是否仍存在未知區域，若仍舊存在未知區域，那么就沿向方向獲取距離最近的處于未知區域的點作為邊界點發送到過濾器，隨后重置RRT樹并刪除所有節點，并以機器人當前位置的坐標為初始點重新生長；若與之間為已知區域，則將作為新節點加入到樹中。

（3）如果函數返回值為0，即與之間存在障礙物，則計算沿著方向與最近的障礙物之間的距離，記為，如果大于步長的最大值，則取為步長從向方向生長得到新節點加入樹中，如果小于步長的最小值，則放棄這個點，重新選擇新的點，也可以認為步長取0；否則以為步長獲取新節點加入到樹中，如公式（1）所示。之后再次判定與之間是否與障礙物發生碰撞，如果仍舊發生碰撞則舍棄這條路徑，如果不發生碰撞則將作為新節點加入樹中。根據上述三3種情況的描述，就可以實現RRT樹的動態步長生長，隨著已知區域的不斷擴大，引入動態步長機制的RRT樹會在已知區域快速生長，同時降低向障礙區域生長的步長，從而提高對未知區域的探索速度。

改進后的RRT自主探索策略算法流程圖3所示。

3?過濾模塊

過濾模塊的目的是接收上述兩種探索策略所獲取到的所有邊界點并對其進行聚類過濾。由于這些邊界點有些可能彼此非常接近，如果將這些邊界點全部都發送到任務分配模塊來進行任務分配將占用大量計算資源，因此，我們采用mean-shift算法對這些邊界點進行聚類選取其中較優的邊界點發送到任務分配模塊，同時刪除無效邊界點和已探索過的邊界點以減少計算量。

4任務分配模塊

該模塊從過濾模塊獲取過濾后的邊界點，并將其分配給機器人，采用與陰賀生等人論文[35]類似的任務分配算法，任務分配模塊對每個過濾后的邊界點將考慮以下因素來構建邊界點評估函數，用于分配每個機器人要探索的邊界點具體敘述如下。

信息增益（I）：信息增益定義為到達給定邊界點預計能夠探索到的未知區域的面積。該面積通過計算以該邊界點為中心，以半徑（為機器人雷達探索半徑）所畫的圓內的未知單元格的數量乘以每個單元格的面積來確定。

導航成本（N）：導航成本為機器人到達該邊界點的預期距離。為了簡化計算，本文僅考慮機器人當前位置與邊界點之間的距離的范數作為導航成本。

建圖精度（F）：建圖精度定義為給定邊界點預計能夠探索到的障礙區域的面積。是以邊界點為圓心，以半徑所畫的已知區域內障礙物的面積。由于地圖中的障礙物可以作為構建地圖的某些標定點，通過考慮該參數，在提升機器人自身定位精度的同時也提高了地圖繪制的精度。

所述的邊界點評估函數如公式（2）所示：

式（2）中，：α、β為權重參數，分別用于控制建圖精度的權重以及控制導航成本的權重，若需要提高建圖精度則提高α值并降低β值；若需要更快的建圖速度則提高β值并降低α值。；為當前機器人坐標到邊界點的滯后增益[46]。

滯后增益的計算公式如（3）所示：。

式（3）中，|為機器人當前坐標到邊界點的直線距離，若該距離小于機器人傳感器的半徑長度，就將該參數設為1；若該距離小于機器人傳感器的半徑長度，則該參數設為（為用戶設置的一個大于1的常數）。該參數能夠使機器人優先探索自身附近的邊界點。

對于每個邊界點，我們都使用公式（2）進行收益計算，并將其中收益最高的邊界點分配給相對應的機器人，引導機器人前往該點進行探索。

5仿真實驗

由于本該文提出了將兩種探索策略進行結合的復合式自主探索策略，因此，我們首先針對探索策略方面與孫旭東論文[51]提出的FFD探索算法以及鄧志超論文[62]提出的RFD算法進行對比實驗，為了便于對比，三這3種探索策略我們都選用了與鄧志超論文[62]相同的路徑規劃模塊和SLAM模塊以便于進行對比實驗。具體相關信息請參考[6]。

本該文通過Gazebo仿真實驗平臺進行模擬仿真實驗，仿真機器人采用三3臺kubuki移動機器人，同時根據地圖的復雜程度，建立復雜程度不同的兩種仿真環境，一種為障礙物較稀疏的20?m×*20?m仿真環境，一種為障礙物較稠密的20?m×*40?m仿真環境。圖4和圖5分別表示探索完成后的環境和相應的柵格地圖模型。在兩種仿真實驗環境下，我們設定改進后的全局RRT探測模塊與RFD算法[62]中的全局探測模塊的步長相同，分別設置為1?m、2?m、4?m、8?m、10?m；同時，在每個環境中，在每個機器人隨機初始位置的情況下每步長進行20次實驗。將構建地圖所用的平均時間繪制為直方圖，具體情況如圖6所示。

根據圖6可以看出，對比貪婪邊界探索算法[7]和RFD算法，在開闊地形仿真環境中，完成探索所需平均時間分別提高了14.4%和10.2%，同時在狹窄地形仿真環境中分別提高了22.5%和33.8%。

6結語

在本文中，我們該研究提出了一種基于復合探索策略的多機器人探索算法。通過結合基于邊界的探索算法和基于RRT的探索算法。首先，每個機器人單獨執行一個基于快速邊界的探索算法，僅通過傳感器獲取自身探測范圍內的邊界點；同時，以每個機器人的初始位置為根坐標，構建了一種多根節點的RRT自主探索策略，并引入動態步長機制提高了RRT樹的生長速度。最后在仿真實驗環境下建立了仿真實驗環境，實驗結果表明，本該算法在提高了探索效率，在復雜環境下能夠表現出更好的性能。證明了該方法的可行性及優越性。

參考文獻[1] 孫旭東.基于ROS的輪式機器人自主融合探索建圖與路徑規劃[D].石家莊：石家莊鐵道大學，2017.