融合改進A*算法與動態窗口法的煤礦足式機器人路徑規劃

摘要：為提高煤礦足式機器人路徑規劃算法的運行效率、搜索精度及避障靈活性，提出了一種融合改進A*算法與動態窗口法（DWA）的煤礦足式機器人路徑規劃方法。首先對A*算法進行改進，通過去冗余節點策略減短規劃路徑的長度，通過改進鄰域搜索方式和代價函數提高路徑規劃速度，采用分段二階貝塞爾曲線進行路徑平滑。將改進A*算法規劃出的路徑節點依次作為局部路徑規劃DWA 的局部目標點進行算法融合，篩選鄰近的障礙物節點，從而再次縮短路徑長度，并通過調整DWA 代價函數中的權值比例提升避障性能。針對機器人遇到無法避開的障礙物而陷入“假死”狀態的問題，以當前初始點為起點，重新調用融合算法，即重新進行全局路徑規劃，將得到的新節點代替原有的局部目標點，按照新路徑進行后續工作。仿真結果表明：在保證機器人行走安全穩定的基礎上，改進A*算法較傳統A*算法的計算時間縮短了65%，路徑長度縮短了24.1%，路徑節點數量減少了27.65%，最終得出的路徑更為平滑；融合算法進一步提升了全局路徑規劃能力，在多障礙物環境下能夠繞開新增的動態和靜態障礙物；機器人遇到“L”型障礙物進入“假死”狀態時，在“假死”位置重新進行全局路徑規劃，更新行走路徑，成功到達了最終目標點。基于融合算法的JetHexa 六足機器人路徑規劃實驗結果驗證了融合算法的有效性和優越性。

關鍵詞：煤礦足式機器人；路徑規劃；A*算法；動態窗口法；復雜環境避障；全局路徑規劃；局部路徑規劃

中圖分類號：TD67 文獻標志碼：A

0 引言

煤礦井下作業環境復雜多變，存在各種障礙物和危險因素，傳統的人工巡檢存在各種安全危險問題，應用煤礦足式機器人進行巡檢不僅能保障礦工生命安全，還能提高井下作業效率。其中機器人路徑規劃是煤礦足式機器人自主導航的核心模塊，也是技術難點之一。

機器人路徑規劃算法是尋找機器人抵達某一目的地所需要行走的最優路徑，其評價指標包括尋路速度、路徑長短等。機器人路徑規劃算法包括全局路徑規劃算法和局部路徑規劃算法。全局路徑規劃算法又稱離線算法， 包括Dijkstra 算法[1]、A*算法[2]、快速搜索隨機樹（Rapidly-exploring RandomTree，RRT） [3]、概率路圖法[4]、遺傳算法[5]、蟻群算法等[6]。全局路徑規劃算法在給定的起始點和目標點之間尋找出最短路徑，但規劃完路徑后無法對路徑上后續新增障礙物及時進行再次路徑尋優。局部路徑規劃算法又稱在線算法， 包括人工勢場法[7]（Artificial Potential Field， APF） 、時間彈性帶法[8]（Timed Elastic Band， TEB） 以及動態窗口法[9]（Dynamic Windows Approach， DWA） 等。局部路徑規劃算法可實時計算機器人自身的方向、速度等參數并及時對機器人進行控制，可避開路徑上新增的障礙物，但一般無法實現復雜環境下的避障工作，特別是機器人在遇到某些障礙物密集環境、“L”型和“U”型障礙物時會出現“假死”狀態。

目前大多路徑規劃算法都是全局路徑規劃算法和局部路徑規劃算法結合使用[10-11]。A*算法原理簡單、計算效率高、易于改進與優化，因此得到廣泛研究和應用[12-14]。文獻[15-16]對A*算法進行改進，通過融合轉折點的方式減少路徑上的拐點數量，所得路線更平滑，但尋路性能提升有限。文獻[17-18]對A*算法進行改進，并結合其他算法加快收斂速度，大幅提高了計算效率，然而避障性能仍有提升空間。

文獻[19]提出了一種改進A*算法與增強型DWA 相結合的機器人路徑規劃方案，對搜索點選擇策略和代價函數進行了優化，提高了路徑規劃效率，但對DWA 在密集障礙物環境下出現“假死”的問題缺少討論。文獻[20]引入柵格環境下的障礙物占比作為修改權值的變量，對A*算法的代價函數進行優化，同時結合DWA 實現了簡單環境下的實時避障，算法性能較單一算法提升較大，但實驗環境較為簡單，只優化了A*算法的代價函數，全局路徑規劃能力提升較小，未考慮A*算法計算得出的節點可能被遮擋等特殊情況。文獻[21]提出了一種基于改進A*算法與DWA 相融合的移動機器人導航算法，實現了基于全局最優的未知障礙物規避，算法邏輯清晰，但只通過引入安全距離和路徑平滑處理對A*算法進行改進，全局路徑搜索能力提升較小，且未能解決局部路徑規劃算法丟失節點導致的“假死”問題。

針對上述問題，通過去冗余節點策略、鄰域搜索方式改進、代價函數改進和路徑平滑對A*算法進行改進，將DWA 與改進A*算法融合，對路徑長度、避障性能等進行優化，最后對機器人“假死”問題提出解決方案。