移動機器人全覆蓋路徑規劃算法研究

賀利樂，劉小羅，黃天柱，楊劍樂

（1.西安建筑科技大學機電工程學院，陜西 西安 710055；2.中建建樂實業有限公司，陜西 西安 710000）

1 引言

路徑規劃是移動機器人實現智能化的關鍵技術之一，分為點對點路徑規劃和全覆蓋路徑規劃。通常所提的路徑規劃即點對點路徑規劃是指，機器人在無碰撞條件下，從起點出發規劃出一條到達終點的最短路徑，算法首要評價指標為路徑長度。但是某些作業要求并不適于點對點路徑規劃，如：室內清掃機器人、擦窗機器人、草坪修剪機器人等。這些移動機器人路徑規劃即全覆蓋路徑規劃，不僅要求尋找一條從起始位置到終點的無碰撞最短路徑，更重要的是要掃描遍歷整個無障礙工作區域，最終形成一條在工作區域內從起始位置經過所有無障礙區域的連續路徑[1]，算法首要評價指標為面積覆蓋率。全覆蓋和點對點路徑規劃最大的區別在于是否需要遍歷整個工作區域。

文獻[2-3]提出基于生物激勵神經網絡構建環境模型，并根據神經元活性值大小決定機器人運動方向，該算法實時性好，能夠解決動、靜態環境下機器人全覆蓋路徑規劃問題。但存在神經網絡環境建模需要機器人每移動一個神經元位置環境模型需更新一次，當神經元數量多時，計算量太大、算法運行效率不高的問題。文獻[4]利用單元分解法將環境地圖劃分為不同大小的區域，區域內部采用螺旋收縮算法實現遍歷，區域之間通過圖的深度優先搜索算法實現全局遍歷排序，最終達到全覆蓋路徑規劃的目的，但此方法易產生小分區，同時由于圖的深度優先搜索算法固有缺陷，機器人在實現路徑全覆蓋時軌跡重復率不高。文獻[5-6]基于動態柵格法的環境建模，分別提出優先級A*算法和置信度方向函數實現全覆蓋路徑規劃，但它們只是單一考慮未覆蓋區域或者機器人轉向，同時當機器人從死區逃離時通常不是最優路徑。

針對上述所提算法的不足，這里在構建動態柵格地圖的基礎上，綜合考慮柵格屬性、機器人轉向、臨近柵格距離、未覆蓋區域面積大小和逃離死區最優路徑，提出一種基于改進的優先級蟻群算法的移動機器人全覆蓋路徑規劃策略，以期達到降低路經重復率，減少轉彎次數，提高工作效率。

2 環境建模

環境建模是移動機器人全遍歷路徑規劃的前提和基礎，常用的環境建模方法主要有：柵格法、單元分解法、拓撲圖法、MAKLINK 圖論法[7-8]、神經網絡等。這里是在沿邊學習的基礎上，采用柵格法進行二維環境建模，方法具有簡單可靠，易于實現和維護的優點。

2.1 沿邊學習

沿邊學習是移動機器人沿環境邊界或緊靠環境邊界的障礙物分別進行水平和垂直運動，通過機器人本體左右側的測距傳感器檢測環境或障礙物邊界與機器人的相對距離，實現對工作環境輪廓學習的過程，為后期柵格法環境建模奠定基礎。對于復雜環境，移動機器人可能需要穿越環境內部，才能達到完全學習整個工作環境輪廓的目的。

2.2 動態柵格法的環境建模

經過環境輪廓學習獲得環境地圖后，以固定大小將其劃分成若干柵格[9]。柵格根據是否含障礙和是否被覆蓋，分為障礙柵格、已覆蓋柵格和未覆蓋柵格。為了便于信息存儲和計算處理，每個柵格狀態由（x，y，f）描述，（x，y）表示柵格在地圖中的位置，f為柵格的屬性值，根據式（1）給每個柵格置屬性值f。

圖1 柵格地圖Fig.1 Grid Map

動態柵格是指柵格的屬性值f是變化的。比如，為增加未覆蓋柵格對機器人的“吸引”，避免機器人反復擦拭同一柵格，約定柵格每被覆蓋一次，其屬性值遞減-1。同時，機器人在工作過程中，只更新其已覆蓋過柵格的屬性值，而不需要類似基于生物激勵的神經網絡環境模型根據分流方程[2]對所有神經元或者柵格進行迭代計算，極大地減少了計算量，提高了機器人的工作效率。假設機器人柵格地圖，如圖1 所示。

為便于研究和仿真實驗，作如下假設：

（1）機器人在運動過程中，障礙物和環境始終保持不變，即機器人是在靜態環境下工作，且障礙物為規則形狀。

（2）環境和障礙物邊界已根據機器人的實際物理尺寸進行“膨化”處理，故障礙物邊界為安全區域且機器人以質點表示。同時，在不存在障礙物和環境邊界時，機器人可向鄰域8 個方向的柵格運動，如圖1 所示。

（3）機器人覆蓋一個柵格后即認為其已按要求完成工作，比如清掃或者擦拭工作。當再次覆蓋同一柵格時，屬于重復遍歷。

3 全覆蓋路徑規劃算法

基于環境模型機器人根據既定優先級規則不斷選擇擬移動柵格，當機器人陷入死區時，采用逃逸算法規劃出迅速逃離死區的路徑，并繼續既定任務，最終達到全覆蓋的目的。在動態柵格法環境建模基礎上，優先級規則和逃逸算法直接關系到機器人的面積覆蓋率和軌跡重復率，是全覆蓋路徑規劃研究的重點。

3.1 改進的優先級啟發規則

文獻[5]所提算法將啟發式規則定義為上柵格、下柵格、左柵格優先次序，規則簡單可行，但機器人頻繁轉彎，能耗較大。文獻[6]所提算法考慮機器人轉向，利用方向函數策略使得規劃路徑盡可能保持直行，減少能耗，但這類似于機器人隨機運動方法，機器人易陷入死鎖狀態。

針對傳統算法中存在的問題，在考慮柵格屬性和機器人轉向的基礎上，引入鄰域柵格距離項和未覆蓋區域面積大小項，提出如式（2）優先級啟發規則，供機器人在非死區狀態下選擇下一移動柵格位置。

式中：fj—柵格j的屬性值，柵格j屬于機器人當前柵格i的鄰域柵格。Gcmax—機器人在當前柵格時未覆蓋的柵格總數；Gc—擬移動柵格方向一側未覆蓋柵格數量與原運動方向上的未覆蓋柵格數量之和。當擬移動柵格的方向與原方向一致時，如果除移動方向外不存在未覆蓋柵格，則規定如果只有一側存在未覆蓋柵格，Gc為該側所求Gc減0.5；如果兩側均存在未覆蓋柵格，Gc為最少一側所求Gc加0.5。該項的設置是確保機器人先遍歷未覆蓋柵格數量最少一側后轉而遍歷另一側，以期降低機器人的路徑重復率。wij—當前柵格i與擬移動柵格j之間的距離。當擬移動柵格在當前柵格的整數倍方向時取wij＝1.414；當擬移動柵格在當前柵格的整數倍方向時取wij＝1。sj—轉向函數是關于機器人前一柵格rp、當前柵格rc與擬移動柵格rj之間方向角差值△θj的函數。下式為機器人方向角差值△θj。

式中：（xpp，ypp）、（xpc，ypc）和（xpj，ypj）—前一柵格rp、當前柵格rc與擬移動柵格rj的位置坐標，方向角計算簡圖，如圖2 所示。θj—擬移動柵格rj和當前柵格rc的角度差。θc—當前柵格rc和前一柵格rp的角度差。△θj∈［0，π］，由于每次只能運動到當前柵格的鄰域，所以△θj常取

圖2 方向角計算簡圖Fig.2 Simplified Diagram for Calculating the Direction Angle

c為未覆蓋區域系數，表示原運動方向兩側中未覆蓋柵格數量最少一側對機器人選擇下一柵格的影響程度，取c=0.5。

d為轉向系數，表示轉向對機器人選擇下一柵格的影響程度，取d=0.5。

當機器人處于非死區狀態時，根據式（2）求出機器人鄰域柵格中該項最大者作為下一步實際移動位置，然后重復此過程，直至機器人陷入死區。

3.2 機器人逃離死區

對于全覆蓋工作要求而言，機器人在動態柵格法構建的環境地圖里面運動過程中常常會陷入死區。機器人陷入死區是指它的周邊相鄰柵格是邊界、障礙物柵格和已覆蓋柵格的組合，不存在未覆蓋的柵格，只有從死區逃離出來，才能繼續全覆蓋任務。而逃離死區的路徑，影響全覆蓋的路徑重復率[6]。當機器人利用優先級啟發規則陷入死區時，采用蟻群算法能夠快速規劃出最優逃離路徑，很好地解決了此問題。

3.2.1 搜索臨時目標點

當機器人陷入死區時，在利用蟻群算法逃離死區之前，必須確立一個臨時搜索點，作為機器人逃離目標點，它要求柵格未被覆蓋且距機器人當前位置距離最短。同時，目標點的選取影響機器人的重復率的高低。在充分考慮障礙物的基礎上，選取離機器人實際距離最近的點作為臨時目標點，從而極大降低了重復率。

假設機器人當前位置為Pr（xc，yc），待選柵格位置為Pi（xi，yi），i=1，…，m，m為滿足條件的待選目標點的總數。當機器人與待選點之間不存在障礙物時，機器人位置與待選柵格之間的距離di，如式（3）所示。

當機器人與待選點之前存在障礙物時，可將障礙物位置描述為Qri=｛A（x1i，y1i），B（x1i，y2i），C（x2i，y1i），D（x2i，y2i）｝。首先將距離機器人當前位置最近且到直線PrPi垂直距離最短的障礙物頂點作為過渡點，比存在障礙物時點B即為過渡點，如圖3 所示。然后根據式（4）求距離di。

式中：θc—機器人當前位置、過渡點和坐標軸之間的夾角；θi—待選柵格、過渡點和坐標軸之間的夾角。

圖3 存在障礙物時機器人位置與待選柵格距離Fig.3 The Distance Between the Robot Position and the Grid to be Selected in the Presence of Obstacles

在求得所有待選柵格與機器人位置距離di后，比較得到di距離最小柵格并記其位置坐標為po（xo，yo），此柵格即作為機器人逃離死區時的臨時搜索點。

3.2.2 蟻群算法

當確定臨時搜索點后，機器人逃離死區的過程轉化為點對點路徑規劃問題。文章采用蟻群算法能夠快速規劃出最優逃離路徑，較好地解決了此問題。

蟻群算法是在模擬自然界螞蟻群體覓食行為的基礎上提出的智能優化算法，具有全局尋優能力強和復雜程度低等特點。傳統的蟻群算法中，螞蟻k在t時刻由位置i選擇下一位置j時，傾向于選擇短路徑且信息素濃度高的作為移動方向，忽略了路徑規劃全局尋優性的要求，為此在狀態轉移規則中引入能表征擬移動位置與目標位置距離項，使搜索更具導向性。螞蟻在狀態轉移時首先產生一個隨機數0≤q≤1，如果q≤q0則按照狀態轉移規則式（5）選取下一位置，否則按照轉盤賭式（6）選擇。

式中：S—按照轉盤賭式（6）選擇的下一位置。

式中：j∈allowedk—螞蟻k下一步允許轉移的位置；τij—邊（i，j）上的信息素濃度；ηij—一個啟發信息，通常γjg—允許轉移位置到目標位置之間的歐式距離；α、β、γ—信息素濃度、啟發信息和目標位置信息在螞蟻選擇路徑中的相對重要程度。

對于信息素更新而言，為有效避免螞蟻收斂到同一路徑，螞蟻從城市i向城市j移動時需要局部信息素更新，規則如式（7）所示。

式中：μ—信息素揮發系數，0＜μ＜1；τ0—一小正常數。

在所有螞蟻完成一次迭代后進行全局信息素更新，根據最大最小螞蟻系統原理，只增強當前迭代最優路徑上的信息素[10]，同時為避免出現停滯現象，每次迭代信息素濃度設置上下限τmin≤τij（t）≤τmax。全局信息素更新規則，如式（8）所示。

式中：ρ—信息素揮發系數，0＜ρ＜1；Lib—當前迭代最優路徑。

3.3 改進算法具體步驟

改進優先級蟻群算法移動流程圖，如圖4 所示。

圖4 改進優先級蟻群算法流程圖Fig.4 The Flow Chart of Improved Priority Rule with Ant Colony Algorithm

具體步驟描述如下：

（1）環境建模。利用機器人本體上的傳感器對環境進行沿邊學習得到環境輪廓，對其進行等大小網格劃分，并根據各網格的狀態置屬性值，最終形成柵格地圖。

（2）路徑選擇。機器人根據改進的優先級規則式（2）尋找下一可行柵格，并修改已覆蓋柵格的屬性值，如此循環直到機器人當前位置鄰域柵格不存在未覆蓋柵格。

（3）陷入死區。遍歷柵格地圖，如果存在屬性值為1 的柵格，則轉（4）；否則轉（6）。

（4）臨時目標點。當機器人與待選點之間不存在障礙物時，根據式（3）求它們之間的距離；當機器人與待選點之前存在障礙物時，根據式（4）求它們之間的距離；最終選擇距離最短柵格作為臨時搜索目標點。

（5）逃離死區。蟻群算法狀態轉移規則加入距離目標點項，然后機器人利用其規劃出最優逃離死區路線，并轉步驟2 繼續進行路徑全覆蓋工作。

（6）結束搜索。當柵格地圖中不存在屬性值為1 的柵格時，表示全覆蓋工作已經完成，算法結束。

4 仿真驗證

4.1 路徑規劃算法性能指標

機器人全覆蓋路徑規劃算法常用性能評價指標為轉彎總數、軌跡重復率和面積覆蓋率。令SΩ表示機器人待覆蓋區域總面積，Sd表示機器人已覆蓋（單次）區域總面積，Sg表示機器人完成全覆蓋任務后經過區域總面積，T表示機器人轉彎總次數。

轉彎總次數T是指機器人運動方向改變45°的次數。

面積覆蓋率pc是指機器人完成任務后單次覆蓋區域總面積Sd與機器人待覆蓋區域總面積SΩ的比值：

軌跡重復率pr是指機器人多次覆蓋的區域面積Sg-Sd與待覆蓋區域總面積SΩ的比值：

綜合機器人運動過程的轉彎數、面積覆蓋率和軌跡重復率等指標全面評價全覆蓋路徑規劃算法。若轉彎總數越低、面積覆蓋率越高、軌跡重復率越低，則機器人工作效率越高，路徑規劃算法可行越好。

4.2 仿真分析

為說明所提算法的可行性和有效性，在10*10 的環境地圖下，分別采用文獻[5-6]和所提算法進行全覆蓋路徑規劃仿真實驗。不同算法全覆蓋路徑規劃仿真結果，如圖5 所示。其中標識點S表示機器人的初始位置，標識點F表示機器人的終止位置。文獻[5]基于優先級A*算法的路徑規劃仿真結果，如圖5（a）所示。文獻[6]基于方向信度函數算法的路徑規劃仿真結果，如圖5（b）所示。所提算法的路徑規劃算法，如圖5（c）所示。不同路徑規劃算法性能指標，如表1 所示。

圖5 不同算法全覆蓋路徑規劃仿真結果Fig.5 The Simulation Results of Different Complete-Coverage Path Planning Algorithms

表1 不同算法性能對比Tab.1 Performances of Different Algorithms

通過圖5 和表1 可知，雖然不同算法均可實現面積全覆蓋，但機器人的轉彎次數和軌跡重復率不盡相同。文獻[5]的路徑規劃算法由于強調環境地圖的左側始終保持已覆蓋狀態，使轉彎總數和軌跡重復率較高；文獻[6]的路徑規劃算法利用方向信度函數盡可能使機器人保持直線運動以降低能耗；使轉彎總數和軌跡重復率較文獻[5]所下降；綜合考慮機器人轉彎能耗和未覆蓋區域的基礎上，提出新的優先級啟發規則，同時當機器人陷入死區時，利用蟻群算法能夠找到最優路徑。比較文獻[5-6]，本算法不僅陷入死鎖次數較少，而且在軌跡重復方面分別降低了81.80%和66.64%；在轉彎總數方面，本算法比文獻[5]降低了26.83%，而與文獻[6]相差不大。仿真實驗結果表明，所提算法在保證面積全覆蓋的基礎上，更加有效地降低了軌跡重復率，減少了轉彎次數，提高了機器人工作效率，降低了能耗。

5 結論

針對常見移動機器人全覆蓋路徑規劃算法的不足，提出一種改進優先級蟻群算法。該算法在傳統優先級啟發規則的基礎上進行了改進，在機器人狀態陷入死區時，進一步考慮了死區點到臨時搜索點之間存在障礙的情況。通過仿真實驗表明，改進后的方法在保證面積覆蓋率為100%的同時能降低死鎖次數和軌跡重復率，方法可行有效，為移動機器人全覆蓋路徑規劃提供了參考。