基于改進的A*算法機器人導航路徑研究

胡廣雪 鄭亞清 韓洋祺

摘要：針對移動機器人在不同的工作場景不確定性，設計了將相鄰節(jié)點優(yōu)先級分組與Floyd-Warshall算法相結合路徑規(guī)劃研究方法。首先，對全局規(guī)劃A* 算法相鄰節(jié)點優(yōu)先級分組。其次，綜合環(huán)境和路徑的情況以全局路徑的拐點為局部目標點，采用改進的Floyd-Warshall算法進行局部路徑規(guī)劃，從而使規(guī)劃路徑尋路時間及轉折點次數(shù)優(yōu)于A*算法。最后進行仿真驗證，仿真結果表明：該算法有效解決復雜移動環(huán)境的路徑規(guī)劃的問題，提高了機器人導航路徑規(guī)劃的準確性和魯棒性。

關鍵詞：移動機器人;改進的A*算法;路徑規(guī)劃

1.引言

隨著智能制造技術的不斷發(fā)展，機器人在在野外探測、工業(yè)流水線制造、物流輸送等多個領域廣泛應用。其中，定位和導航系統(tǒng)是研究機器人的核心問題。智能移動機器人系統(tǒng)主要由環(huán)境感知、環(huán)境邏輯決策及輔助路徑規(guī)劃系統(tǒng)組成，且導航路徑規(guī)劃是移動機器人性能衡量的重要指標。目前也有一些其他導航定位方法，一些學者采用人工路標定位，但此類定位方法需要提前布置導航的室內場景[1]。[2]通過改進A* 算法的關鍵節(jié)點實現(xiàn)了靜態(tài)移動環(huán)境下的路徑規(guī)劃。[3-6]根據(jù)已知和未知環(huán)境信息進行局部和全局路徑的規(guī)劃。[7]提出了基于二次規(guī)劃改進的A*算法，但并未考慮移動機器人的體積和偏轉角，實際應用不強。[8]提出跳過節(jié)點搜索策略，減少了計算過程中訪問節(jié)點數(shù)，加快程序的運行速度，但路徑中轉折點仍比較多。采用改進蟻群算法搜索全局路徑點，但搜索節(jié)點數(shù)據(jù)量太大。提高控制程序運算速度，但對行駛路徑的彎曲程度沒有考慮。

針對傳統(tǒng)算法計算量大，由于地下車庫和不同工作廠房復雜不確定性，為了提高智能移動機器人在位置環(huán)境中精確性，本文采用改進的A*算法進行智能移動機器人導航路徑規(guī)劃，為實現(xiàn)高效率的工作提供實現(xiàn)基礎。

假設智能移動機器人M在有限個障礙物的二維柵格平面區(qū)域Y內移動，以Y的左下角為坐標原點，以水平方向為橫坐標x軸，垂直方向為縱坐標y軸，建立如圖1直角坐標系xOy。其中，xmax、ymax分別為橫縱坐標軸方向上的最大值。以移動機器人的步長s對坐標區(qū)域進行劃分行和列的柵格數(shù)。

每個柵格有相應的坐標值與其一一對應，將其序號集定義為，以坐標區(qū)域的左上角為原點，由左向右、自上至下，對二維平面區(qū)域Y進行編號，坐標與序號之間的關系為

2.改進的A*算法

由于傳統(tǒng)的A* 算法存在運行求解速度較慢，當移動機器人從柵格A移動到柵格B時，考慮到移動機器人有一定的輪廓體積，因此，在紅點處可能會發(fā)生碰撞，從而造成移動機器人損壞。對此，本文通過對傳統(tǒng)的A*算法節(jié)點的擴展順序進行改進，如圖2所示。設移動機器人當前運動環(huán)境節(jié)點為O，周圍相鄰節(jié)點分別為 A、B、C、D、E、S、W、N。以便降低在實際移動過程中與障礙物發(fā)生碰撞的概率，相鄰兩個節(jié)點優(yōu)先分組。

上述方法對A*算法子節(jié)點的選擇優(yōu)化，可以提高移動機器人規(guī)劃路徑的安全性，但路徑規(guī)劃過程中轉折次數(shù)較多，行駛路線的不平滑難度增加很多。針對上述問題問題，在優(yōu)化選擇子節(jié)點的基礎上，將雙向平滑理念引入到Floyd-Warshall 算法中對 A* 算法進行改進，通過建立兩點之間路徑長度的二維數(shù)組來計算最短路徑。將雙向平滑理念引入到 Floyd-Warshall 算法中，即在優(yōu)化正向路徑的基礎上，加入目標點 T 到起始點 K 的反向優(yōu)化。具體改進步驟如圖3 所示。

針對改進的A*算法優(yōu)化路徑算法，主要從以下步驟進行仿真驗證：對路徑中同一直線上的中間冗余節(jié)點進行刪除，僅保留起始點K、拐點和目標點T。刪除冗余節(jié)點后的移動路徑為 K→p1→p2→p3→T。從起點K開始，在保留節(jié)點pi、pj之間每q步取一節(jié)點，判斷取的節(jié)點與上一路徑節(jié)點之間是否存在障礙物。若有障礙物，則當前路徑節(jié)點不變;若無障礙物，則由程序計算障礙物與節(jié)點pi、pj連線的距離。

根據(jù)柵格的大小將規(guī)劃的路徑安全距離定義為d，當d>dOB時，該路徑可以進行選擇，否則該路徑不可選，加入安全距離后的路徑為K→p33→T。

3.仿真結果驗證

為驗證上述理論分析及改進 A* 算法規(guī)劃路徑的有效性，在 Matlab 2010a實驗平臺下分別對傳統(tǒng)的 A*算法。其中 d = 0.8 m，q = 0.1 m，柵格大小為1 m。黑色柵格為障礙物區(qū)域，占地圖總面積為19.5%，灰色柵格為遍歷的節(jié)點區(qū)域，兩組柵格地圖路徑規(guī)劃結果如圖4所示。

由仿真的路徑曲線可得，傳統(tǒng)A*算法所規(guī)劃的移動路徑存在斜穿障礙物頂點的不足，適應性較差。改進后的A*算法在設定機器人行駛的安全距離后，規(guī)劃路徑與障礙物的距離始終大于d，從而避免了移動機器人距障礙物較近而發(fā)生碰撞的情況，提高了移動機器人路徑行駛的安全性。基于雙向FloydWarshall改進的A*算法折點的數(shù)量較傳統(tǒng)A*算法有所減少，其規(guī)劃的移動路徑曲線更加平滑，在實際應用中，有利于減少移動機器人運動過程中的航向角，有效提高移動機器人運動的平穩(wěn)性和工作效率，具有一定的實用價值。

4.結論

（1）為提高A*算法的運行效率及移動機器人規(guī)劃路徑的安全性，提出對子節(jié)點的擴展的順序進行優(yōu)化選擇，將8個領域節(jié)點劃分為高級組和一般組，縮短尋優(yōu)路徑的時間，避免規(guī)劃路徑存在斜穿障礙物頂點問題。

（2）針對傳統(tǒng)的A*算法搜索路徑轉折點個數(shù)多、路徑曲線不平滑等不足，采用 Floyd-Warshall算法對路徑曲線進行雙向平滑處理，從而減少航向角的次數(shù)，改善行駛路徑的質量。

（3）采用Floyd-Warshall算法改進后的的A*算法，符合移動機器人的運動控制，具有實際的使用價值。

參考文獻：

[1]黃露.基于人工路標的室內機器人導航方法研究與實現(xiàn)[D].中國科學技術大學，2017.

[2]王帥軍，胡立坤，王一飛.基于改進D*算法的室內移動機器人路徑規(guī)劃[J]. 計算機工程與設計，2020，41（4）：7.

[3]Baoye， Song， Zidong， et al. On Global Smooth Path Planning for Mobile Robots using a Novel Multimodal Delayed PSO Algorithm[J]. Cognitive Computation， 2017， 9（1）：5–17.

[4]Chen H ，F(xiàn)ei J . UAV Path Planning Based on Particle Swarm Optimization with Global Best Path Competition[J]. International Journal of Pattern Recognition and Artificial Intelligence， 2017， 32（1）.

[5]Golda A F ，Aridha S ， Elakkiya D . Algorithmic agent for effective mobile robot navigation in an unknown environment[C]// Intelligent Agent & Multi-Agent Systems， 2009. IAMA 2009. International Conference on. IEEE， 2009.

[6]Mohtasham S K ， Abbas S . Adaptive Path Planning for Navigation and Sensing of Micro Aerial Vehicles.? 2016.

[7]楊璐， 汪博涵， 張雪潔. 基于A*算法的AGV路徑規(guī)劃研究[J]. 公路與汽運， 2014.

[8]Pal A ， Tiwari R ， Shukla A . Modified A* Algorithm for Mobile Robot Path Planning[M]. Springer Berlin Heidelberg， 2012.