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

關鍵詞：煤礦足式機器人；路徑規(guī)劃；A*算法；動態(tài)窗口法；復雜環(huán)境避障；全局路徑規(guī)劃；局部路徑規(guī)劃

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

0 引言

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

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

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

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

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