基于改進A*算法和DFS算法的割草機器人遍歷路徑規劃*

王新彥，盛冠杰，張凱，易政洋

(江蘇科技大學機械工程學院，江蘇鎮江，212100)

0 引言

近年來，隨著移動機器人技術的迅速發展，智能化設備已被廣泛應用于社會的各個領域，給人們的生產生活帶來了極大的便利[1-3]。割草機器人作為農業機器人的一種，不僅用于市政綠地、機場、高爾夫球場等場地的草坪修剪工作，還用于耕地和林地的除草工作，因此受到廣泛關注，而遍歷路徑規劃在割草機器人應用過程中起著至關重要的作用[4-6]。

全覆蓋遍歷路徑規劃是一種在二維環境中特殊的路徑規劃，指在滿足某種性能指標最優的前提下，在設定區域內尋找一條從起點到終點且經過所有可達點的連續路徑[7-9]。該技術發展至今已涌現出了大量研究成果，Balch采用隨機遍歷算法進行目標區域遍歷，使機器人沿直線移動，當遇到障礙物時隨機轉動一個角度繼續前進，該方法原理簡單、易于實現，但要達到高覆蓋率需要很多時間，工作效率低。張赤斌等[10]將蟻群算法應用到遍歷路徑規劃中，通過牛耕式分解法將目標區域分解成若干個不含障礙物的子區域，采用蟻群算法搜索出子區域的遍歷順序，該方法覆蓋率高，但算法運算量大且跨區域轉移路徑長。李楷等[11]提出了一種局部區域覆蓋和回溯機制相結合的遍歷方法，利用回溯機制對局部覆蓋過程中存在的遺漏區域進行回溯遍歷，以此提高遍歷覆蓋率，但存在遍歷重復率較高的問題。Le等[12]提出了一種基于螺旋生成樹的遍歷方法，該方法遍歷重復率低，但其規劃的遍歷路徑轉向次數多且易陷入死區。馬全坤等[13]提出了一種基于記憶模擬退火和A*算法的遍歷方法，采用記憶模擬退火算法確定各子區域的遍歷順序，通過A*算法規劃跨區域轉移路徑，該方法性能較優，但跨區域轉移路徑較長。

上述研究成果對遍歷路徑規劃技術的發展起到了積極的推動作用，但仍存在遍歷重復率高、遺漏區域多、普適性弱的問題。為此，本文提出一種改進A*算法與DFS算法相結合的遍歷算法，通過DFS算法確定目標區域劃分后的子區域遍歷順序，然后使用改進A*算法進行跨區域轉移路徑規劃，從而實現割草機器人的遍歷路徑規劃。

1 環境建模

1.1 建立柵格地圖

本文采用柵格法[14]進行環境建模，將割草機器人的工作環境全局信息分解成一系列具有二值信息的等大小正方形網格單元，單元格邊長為割草機器人割幅。接著每個柵格被賦予環境信息值：若某個柵格內不含障礙物，則稱該柵格為自由柵格并賦值為0，反之被稱為障礙柵格并賦值為1。本文結合市政綠地的現實情況，對環境做如下假定：(1)假定市政綠地環境全局信息已知；(2)假定灌木植物為圓形障礙物；(3)假定石塊、垃圾桶等為多邊形障礙物；(4)假定積水區、小土丘等為形狀不規則障礙物。

建立的柵格地圖如圖1所示，把環境信息賦予對應的柵格，相當于將環境地圖離散化，每個單元格映射出環境信息的一部分。

圖1 柵格地圖

1.2 障礙物膨脹處理

在柵格地圖中存在一些障礙物的邊緣不完全與柵格單元邊界重合，如圖1所示，此時需要進行圖像處理，通過二值形態學中的膨脹運算對這些障礙物的邊緣區域進行膨脹處理，使其邊緣在柵格化的地圖中與柵格單元邊界重合，以防止割草機器人陷入死角以及智能算法陷入局部最優[15]，以便后續遍歷算法在此基礎上進行路徑規劃。

(1)

根據上述膨脹數學模型，邊緣不完全與柵格單元邊界重合的障礙物目標經過膨脹處理后得到的新障礙物柵格M，如圖2所示。

圖2 膨脹處理后的障礙物

1.3 目標區域劃分

柵格地圖建立后，由于障礙物分布毫無規律，割草機器人工作時易出現漏割、重復遍歷、效率低等情況。為提高工作效率，采用牛耕式分解法將目標區域劃分成多個不含障礙物的子區域，使割草機器人通過遍歷單個子區域并進行子區域之間路徑轉移，來達到全覆蓋遍歷路徑規劃。

牛耕式分解法[16]是從梯形單元分解法[17]上改進而來，該方法假設一條垂直的切割線從左往右掃描整個有界區域，每當遇到障礙物上的臨界點或邊時便進行分割，目標區域中的非障礙物部分進而被分割成多個子區域。

相比梯形單元分解法，該方法使目標區域劃分過程中產生的子區域數量更少，可有效降低遍歷重復率。子區域劃分后，按照從上到下、從左到右的原則對各子區域進行數字標號，如圖3所示，以便后續子區域遍歷順序的規劃。

圖3 目標區域劃分

2 基于柵格地圖的遍歷方法

目標區域完成劃分后，割草機器人要實現對目標區域的全覆蓋遍歷可通過以下兩個步驟：(1)根據子區域之間連通關系確定子區域的遍歷順序，保證每個子區域在遍歷路徑規劃中有且僅被訪問一次；(2)按照給定的遍歷順序依次訪問每個子區域，完成子區域間路徑轉移。

2.1 子區域遍歷順序規劃

子區域的遍歷順序規劃采用DFS算法[18]，該算法是圖算法中一種著名的搜索算法，經常被用來遍歷連通圖中每個節點，找到一條詳盡可靠的覆蓋路徑，算法步驟如表1所示。

將目標區域劃分得到的每個子區域看作連通圖中節點，按照子區域間相鄰關系建立連通圖，如圖4(a)所示。根據目標區域劃分中切割線移動方向，將①設置為遍歷起始區域，圖4(b)是使用DFS算法規劃的子區域遍歷順序圖。

表1 DFS算法步驟Tab. 1 DFS algorithm steps

(a) 連通圖

(b) 遍歷順序圖

2.2 子區域間路徑轉移

為了使割草機器人有序地完成對每個子區域的遍歷，就需要解決子區域之間路徑轉移的問題。針對該問題，本文采用改進A*算法規劃從上一個子區域遍歷終點到下一個子區域遍歷起點的最短路徑。

2.2.1 A*算法的評價函數

A*算法是人工智能中一種典型的啟發式搜索算法，被廣泛應用于靜態路網中兩點間最優路徑的求解。其評價函數如式(2)所示。

f(n)=g(n)+h(n)

(2)

式中：f(n)——從起始節點到目標節點的評價函數；

g(n)——起始節點到當前節點n的實際代價函數；

h(n)——當前節點n到目標節點的啟發代價函數。

在二維地圖中，代價函數的值通常指兩個節點之間的歐幾里得距離，即

(3)

(4)

式中： (xs,ys)——起始點位置；

(xn,yn)——當前點位置；

(xt,yt)——目標點位置。

2.2.2 改進A*算法

A*算法規劃所得到的是一系列相鄰的路徑節點，將各相鄰節點用直線連接起來即為所得到的路徑。由于A*算法規劃的路徑存在冗余的路徑節點且轉向次數多[19]，導致路徑平滑性較差且路徑長度不是最短，同時路徑穿過障礙物邊界點時易發生碰撞。針對上述問題，本文通過路徑平滑性優化和添加防碰撞安全間距對A*算法進行改進，改進A*算法的流程圖如圖5所示。

圖5 改進A*算法流程圖

防碰撞預處理是通過計算障礙物邊界點到路徑的垂直距離l，與設置的安全間距η進行對比，判斷路徑是否安全。防碰撞安全間距η的大小與柵格單元邊長γ有關，滿足η∈(0,0.5γ),η的值可根據實際情況進行調節。如圖6所示，路徑節點A、B坐標分別為(xa,ya)、(xb,yb)，障礙物邊界點H坐標為(xe,ye)，直線BC垂直于H點所在的橫軸，垂足為C點，連接CH，直線AB與直線CH相交于F點，H點到直線AB的垂直距離DH即為l的長度，線段FH長度為t，θ為直線AB與直線BC所夾銳角。由于A、B、H三點坐標已知，可求解障礙物邊界點H到路徑AB的垂直距離l。

直線AB與直線BC所夾銳角

(5)

線段FH長度

(6)

障礙物邊界點H到路徑AB的垂直距離

l=t·cosθ

(7)

圖6 防碰撞路徑圖

A*算法的改進是在獲取A*算法規劃的路徑節點后進行，如圖7所示，Ni(i=1～13)是A*算法規劃的路徑節點，i為路徑節點的標號。改進算法的步驟如下。

步驟1：從起點G往終點E方向，取初始路徑的第一個節點Ni(i=1)。

步驟2：若節點Ni+1是終點E，轉至步驟6；若節點Ni+1既不是終點E，也不是起點G，轉至步驟3；若節點Ni+1是起點G，轉至步驟7。

步驟3：判斷直線NiNi+1與直線Ni+1Ni+2斜率是否相等。若斜率相等，節點Ni、Ni+1、Ni+2共線，刪除節點Ni+1并使Ni后面節點的標號均減1，返回步驟2；若斜率不相等，節點Ni、Ni+1、Ni+2不共線，轉至步驟4。

步驟4：判斷節點Ni和Ni+2之間是否存在障礙物。若有障礙物，路徑節點不變，轉至步驟5；若無障礙物，由式(5)～式(7)計算障礙物邊界點到路徑NiNi+2的垂直距離l并判斷與安全間距η的大小：如果l≤η，路徑節點不變，轉至步驟5；如果l>η，刪除節點Ni+1并使Ni后面節點的標號均減1，返回步驟2。

步驟5：令i=i+1，更新i的值并返回步驟2。

步驟6：從終點E往起點G方向，取初始路徑的第一個節點Ni(i=1)，返回步驟2。

步驟7：輸出優化路徑Path，算法結束。如圖7所示，優化后路徑為：G→N6→M1→E。從起點G往終點E正向取點，處理后路徑為：G→N6→N11→E；從終點E往起點G反向取點，處理后路徑為：E→N7→N4→N3→G。

圖7 路徑平滑性處理

3 遍歷路徑規劃仿真

通過使用牛耕式分解法將目標區域劃分成多個不含障礙物的子區域；其次，使用DFS算法確定子區域的遍歷順序；然后，采用改進A*算法搜索出最短、無碰撞的跨區域轉移路徑并對子區域內部進行往復前進式遍歷，最終實現對整個柵格地圖的遍歷路徑規劃。

為了直觀、清晰地顯示仿真結果，柵格地圖由23×23 個柵格組成，其中黑色區域為障礙物占據的柵格，其他白色區域是自由柵格。圖8為遍歷路徑規劃仿真結果圖，由圖可知，不論在上文建立的普通環境模型中，還是在特殊的復雜環境模型中，本文提出的遍歷路徑規劃算法的覆蓋率都達到100%且遍歷重復率為0。

圖9為A*算法改進前后規劃的跨區域轉移路徑對比圖，其中每個子區域的遍歷起點用“●”表示，每個子區域的遍歷終點用“★”表示。遍歷整個柵格地圖需進行九次跨區域路徑轉移，這里主要對比其中三條轉移路徑：⑩—⑨區域、⑨—⑥區域、⑥—③區域，對應路徑在圖9中用加粗黑線表示。

結合圖9、表2和表3可以看出，改進后的A*算法所規劃的路徑刪除了冗余的路徑節點，使路徑長度縮短了3.26%，轉向次數減少了62.5%，提高了路徑的平滑性，同時，由于添加了防碰撞安全間距，改進后的A*算法所規劃的路徑不會出現穿過障礙物邊界點的情況，路徑安全性得到提高。

(a) 普通環境

(b) 復雜環境

(a) A*算法

(b) 改進A*算法

表2 路徑轉移距離對比Tab. 2 Comparison of path transfer distance

表3 路徑轉移轉向次數對比Tab. 3 Comparison of the number of times of path transfer

4 結論

針對割草機器人大面積作業時遍歷路徑規劃覆蓋率低、重復率高、普適性弱的問題，本文提出了一種改進A*算法與DFS算法相結合的遍歷算法。

1) 針對目標區域劃分后的子區域間路徑轉移，采用改進A*算法規劃轉移路徑。通過路徑平滑性優化與添加防碰撞安全間距對A*算法進行改進，使之規劃的路徑更平滑、更安全，路徑長度更短。MATLAB仿真試驗表明，采用改進A*算法所規劃的跨區域轉移路徑長度和轉向次數比A*算法分別減少了3.26%和62.5%，路徑不會穿過障礙物邊界點。

2) 針對割草機器人遍歷路徑規劃，提出了一種改進A*算法與DFS算法相結合的遍歷算法。通過DFS算法確定目標區域劃分后的子區域遍歷順序，然后使用改進A*算法進行跨區域轉移路徑規劃。通過仿真試驗表明，遍歷路徑規劃覆蓋率達到100%，遍歷重復率為0，本文遍歷算法具備有效性和可行性。由于本文算法只適用于靜態環境，下一步將在此工作基礎上進一步展開動態環境中遍歷路徑規劃的探討與研究。