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

胡廣雪 鄭亞清 韓洋祺

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

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

1.引言

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

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

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

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

2.改進的A*算法

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

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

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

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

3.仿真結果驗證

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

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

4.結論

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

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

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

參考文獻：

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

[2]王帥軍，胡立坤，王一飛.基于改進D*算法的室內移動機器人路徑規劃[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 ，Fei 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路徑規劃研究[J]. 公路與汽運， 2014.

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