融合改進(jìn)A*算法與動態(tài)窗口法的煤礦足式機(jī)器人路徑規(guī)劃

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

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

中圖分類號：TD67 文獻(xiàn)標(biāo)志碼：A

0 引言

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

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

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

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

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