基于平滑A*人工勢場法的機器人動態路徑規劃

任玉潔+付麗霞+張勇+毛劍琳

摘要：針對動態環境下移動機器人的路徑規劃問題，提出了平滑A*人工勢場法的路徑規劃方法。首先采用平滑A*算法在靜態障礙物環境中進行全局路徑規劃；其次，在機器人遇到動態障礙物時采用A*人工勢場法進行局部動態路徑規劃，并以此調整全局路徑規劃結果；最后對路徑規劃結果進行平滑處理。將平滑A*人工勢場法應用于機器人動態路徑規劃，并與D*算法進行對比。實驗結果表明，該算法能夠在動態環境下規劃出一條更為優化的路徑，有效縮短了路徑長度，提高了規劃效率。

關鍵詞：A*算法；人工勢場法；路徑規劃；機器人

DOIDOI：10.11907/rjdk.172192

中圖分類號：TP301

文獻標識碼：A文章編號文章編號：16727800（2018）001000803

Abstract：A path planning method based on smoothed A* artificial potential field is proposed aiming the path planning problem of mobile robot in dynamic environment， In order to improve the planning efficiency， Firstly a smoothed A* algorithm was used to perform the global path planning in the static obstacle environment；Secondly the A* artificial potential field method was applied to perform the local dynamic path planning and adjusted then the global path planning results when the robot encounters a dynamic obstacle；Finally the path planning results were smoothed.The smoothed A* artificial potential field method is applied to the robot dynamic path planning and compared with the D*algorithm. Experimental results have shown that the proposed algorithm can be worked out a more optimized path in dynamic environment， effectively shorten the path length， improve the planning efficiency.

Key Words：A* algorithm； artificial potential field method； path planning； robot

0引言

路徑規劃是移動機器人控制領域的一個重要研究方向，它是指依據某些指標在一個障礙物環境下搜尋一條從起始點到目標點的最優或近似最優無碰撞路徑[12]。依據環境信息，大體上可將路徑規劃分為環境信息已知的全局路徑規劃和基于傳感器感知的局部路徑規劃[3]。其中，全局路徑規劃能處理障礙物信息已知情況下的路徑規劃，但當出現動態障礙物時，規劃效果不理想；局部路徑規劃能夠通過傳感器反饋的信息，規避環境中的動態障礙物。

A*算法是一種經典的啟發式搜索算法，適用環境已知的全局路徑規劃，它具備最優性、完備性和高效性[4]，利用A*算法可以得到較好的路徑規劃效果。但是由于A*算法的計算特點，規劃出的路徑點一般存在折線多、累計轉折角度大等問題。平滑A*[5]通過建立平滑模型，有效降低了路徑中的轉折點與轉折角度。D*算法[6]是基于A*算法提出的機器人動態路徑規劃算法，其思想是在向目標點移動過程中，若檢測到環境中的動態障礙物，則搜尋障礙物附近節點的變化情況，重新規劃路徑。人工勢場法[7]是一種比較成熟的局部路徑規劃算法，其由于具有計算速度快、適用于實時控制的優點而得到廣泛應用。但由于該方法依據的是局部環境信息，缺乏全局自我調節能力，易陷入局部最優[8]。

本文提出平滑A*算法和改進人工勢場法結合的動態路徑規劃算法。首先，為提高算法搜索效率，采用文獻[5]中的平滑A*算法對障礙物環境進行全局路徑規劃，再引入改進的人工勢場法對動態障礙物進行避障。

1A*算法

1.1傳統A*算法

A*算法是一種經典的啟發式算法，在靜態環境中能高效地求出從起始點到目標點的路徑，其估價函數定義為：

其中，X是當前節點，f（x）是當前節點的總啟發代價，g（x）是初始點到當前點的實際路徑代價，h（x）是當前點到目標點的估計路徑代價。

h（x）的取值對算法效率具有決定性作用。本文采用當前點與目標點之間的歐幾里得距離作為估計代價，如下所示：

其中，xt為目標點橫坐標，yt為目標點縱坐標，xx為當前點橫坐標，yx為當前點縱坐標。

A*算法尋徑首先要創建兩張表：open list和close list。其中，open list用來保存拓展節點，close list用來保存障礙物和已使用過的節點。搜尋過程中，先從open list找出總啟發代價最小的點設為當前節點，將其放入close list，并對其進行擴展；將擴展后的節點更新到open list，再從open list選取總啟發代價最小的點設為當前節點；重復過程，直到找到目標點。

1.2平滑A*算法endprint

文獻[5]中提出，傳統A*算法規劃出的路徑存在冗余轉折點，為了避免不必要的轉折，對求得的路徑進行平滑處理。從當前點開始，依次連接之后的節點，判斷是否與障礙物有交點，如果無交點，舍棄中間節點，求出平滑路徑。具體過程如下：①取出傳統A*算法規劃出的路徑點，將起點設為pcurrent，下一節點依次設為pnext、pdnext；②執行check（pcurrent，pdnext，barrier list）方法獲得返回值，如果為0則繼續執行，否則跳轉至第4步；③pnext賦值給pcurrent，pdnext賦值給pnext，pdnext下一節點賦值給pdnext，跳轉至第5步；④路徑點中刪除pnext節點，將pdnext賦值給pnext，pdnext下一節點賦值給pdnext；⑤若pdnext為目標點則繼續執行，否則跳轉至第2步；⑥輸出平滑后的路徑。

其中，barrier list是路徑規劃環境中的障礙物列表，函數check（pcurrent，pdnext，barrier list）用來檢測pcurrent和pdnext連線與障礙物邊線是否相交，如果不相交則返回1，否則返回0。

2人工勢場法

2.1傳統人工勢場法

人工勢場法在機器人運動空間構造虛擬的力勢場，包括目標點產生的引力勢場和障礙物產生的斥力勢場。目標點引力與當前點到目標間距離成正比，障礙物產生斥力與當前點到障礙物距離成反比，通過引力和斥力的作用，尋找一個從初始點到目標點的安全無碰撞路徑。其引力勢場函數和斥力勢場函數分別定義為：

式中，X是當前位置，Xg是目標點位置，X0是障礙物位置，Katt是引力場常量，Krep是斥力場常量，ρ0是障礙物最大威脅距離。

根據引力勢場和斥力勢場的負梯度可以得到引力函數和斥力函數：

通過人工勢場法可以在較簡單的障礙物環境中規劃出一條從初始點到目標點的安全無碰撞路徑。當環境中障礙物變多，則可能存在人工勢場法的局部極小值點問題。局部極小值點是機器人運動環境中某些點由于受多個力的共同作用，造成了斥力和引力相互抵消，從而使合力為0。隨著障礙物增多，尋徑過程中陷入局部極小值點的機率隨之增大。

2.2A*人工勢場法

針對人工勢場法局部極小值點問題，提出A*人工勢場法。主要包括局部極小值檢測和A*人工勢場法避障。

本文人工勢場法局部極小值檢測采用一定間隔內機器人行進距離和閾值進行比較的方法。該方法首先根據機器人移動步長和障礙物影響范圍大小設置一個閾值T，然后檢測當前節點前一個節點與后一個節點之間的距離并與T進行比較。若距離小于閾值T，可以認為機器人陷入了局部極小值點，反之則沒有陷入。

檢測到移動機器人陷入局部極小值點時，對局部極小值點用A*算法進行規劃從而將其避開，脫離局部極小值點后回到人工勢場法。傳統A*算法路徑點為柵格中點，對障礙物的判斷為檢測拓展節點是否為障礙物點。但此時路徑點不再局限于柵格中點，在尋徑過程中，連接當前節點與拓展節點，通過判斷連線與障礙物邊線是否有交點判斷是否與障礙物相交。圖1是傳統人工勢場法的路徑規劃結果，圖2是A*人工勢場法的路徑規劃結果。

3平滑A*人工勢場法

將平滑A*算法與A*人工勢場法結合。首先用柵格法[9]進行建模，將機器人移動區域劃分為相同的小柵格。靜態障礙物標記為黑色，可通行區域標記為白色。由于障礙物形狀不確定，為了簡化操作，當障礙物不足一個柵格時，將其補全至一個柵格；然后采用平滑A*算法對障柵格法處理后的障礙物環境進行全局路徑規劃，當遇到動態障礙物時，將全局規劃路徑點中障礙物的前一節點設為初始節點，障礙物后一節點設為目標點，采用A*人工勢場法進行動態路徑規劃；再對A*人工勢場法規劃的路徑進行平滑處理，消除冗余節點，最后輸出路徑。具體流程如圖3所示。

4實驗研究

為了驗證動態規劃性能，在Matlab2014上進行仿真，設人工勢場法初始參數引力場常量Katt=100，斥力場常量Krep=3，斥力影響范圍ρ0=3，步長l=0.5；圖中矩形網格為動態障礙，沿y軸負方向作速度為1柵格/s的勻速運動。圖4為在20×20柵格環境下采用平滑A*算法預規劃路徑圖，圖5為未碰撞時的路徑圖，圖6是動態障礙物碰撞時D*算法規避路線圖，圖7是動態障礙物碰撞時平滑A*人工勢場法算法規避路線圖。表1給出了D*算法和平滑A*人工勢場法路徑規劃參數對比。

實驗結果表明，當傳感器檢測到動態障礙物時，采用A*人工勢場法能夠有效避障并快速回到預規劃路徑，與D*算法相比，路徑長度減少了7.001%，累計轉折次數減少了23.077%，累計轉折角度減少了37.973%。

5結語

本文將平滑A*算法與改進人工勢場法相結合，首先用平滑A*算法進行全局路徑規劃，再用A*人工勢場法引導機器人進行動態避障，最后對求得的路徑點進行平滑處理。仿真實驗結果表明，本文算法在動態環境中能較好地滿足移動機器人的路徑規劃要求。

參考文獻：

[1]朱大奇，顏明重.移動機器人路徑規劃技術綜述[J].控制與決策，2010，25（7）：961967.

[2]ZAMIRIAN M， KAMYAD A V， FARAHI M H.A novel algorithm for solving optimal path planning problems based on parametrization method and fuzzy aggregation[J].Physics Letters A，2009，373（38）：34393449.

[3]楊世良.動態環境下機器人混合型路徑規劃算法[D].鄭州：鄭州大學，2011.

[4]李沖，張安，畢文豪.單邊矩形擴展A*算法[J].機器人，2017，39（1）：4656.

[5]王紅衛，馬勇，謝勇，等.基于平滑A～*算法的移動機器人路徑規劃[J].同濟大學學報：自然科學版，2010，38（11）：16471650.

[6]FERGUSON D， STENTZ A. The field D* algorithm for improved path planning and replanning in uniform and nonuniform cost environments[R].Technical Report CMUTRRI0519，2005.

[7]KHATIB O. Realtime obstacle avoidance for manipulators and mobile robots[M]. Sage Publications， Inc.1986.

[8]張殿富，劉福.基于人工勢場法的路徑規劃方法研究及展望[J].計算機工程與科學，2013，35（6）：8895.

[9]王娟娟，曹凱.基于柵格法的機器人路徑規劃[J].農業裝備與車輛工程，2009（4）：1417.

（責任編輯：黃健）endprint