基于地圖預(yù)處理及改進(jìn)A*算法的路徑規(guī)劃①

余文凱* ** 章 政 付雪畫 王昭偉

(*武漢科技大學(xué)機(jī)器人與智能系統(tǒng)研究院 武漢 430081) (**武漢科技大學(xué)信息科學(xué)與工程學(xué)院 武漢 430081) (***中山大學(xué)數(shù)學(xué)學(xué)院 廣州 510970)

0 引 言

路徑規(guī)劃是實(shí)現(xiàn)移動(dòng)機(jī)器人自主無碰撞移動(dòng)的關(guān)鍵技術(shù)之一。機(jī)器人根據(jù)特定的工作需求，依據(jù)路徑距離最短、能耗最少或者移動(dòng)時(shí)間最少等優(yōu)化指標(biāo)，搜索一條從起始點(diǎn)到目標(biāo)點(diǎn)的最優(yōu)路徑[1-4]。A*算法具有搜索效率高、規(guī)劃速度快和克服了搜索過程中形成的早熟現(xiàn)象等特點(diǎn)，在機(jī)器人路徑規(guī)劃中得到了廣泛應(yīng)用[5，6]。

傳統(tǒng)A*算法在路徑規(guī)劃應(yīng)用中，隨著地圖面積的增大其搜索空間會(huì)產(chǎn)生多余的搜索節(jié)點(diǎn)，導(dǎo)致算法效率降低、規(guī)劃路徑出現(xiàn)不必要的轉(zhuǎn)折等問題。針對(duì)這些問題，許多學(xué)者從不同的角度提高了A*算法的搜索效率。文獻(xiàn)[7]在啟發(fā)函數(shù)中增加了父節(jié)點(diǎn)信息，并修改了評(píng)價(jià)函數(shù)的權(quán)重，增加啟發(fā)函數(shù)的權(quán)重，減少搜索空間來提高算法的搜索效率。文獻(xiàn)[8]引入領(lǐng)域矩陣進(jìn)行障礙搜索以提高路徑的安全性，并通過結(jié)合方向角度和位置距離對(duì)啟發(fā)函數(shù)進(jìn)行修改，提高了計(jì)算效率。文獻(xiàn)[9]加權(quán)處理評(píng)價(jià)函數(shù)，并通過人工搜索標(biāo)記，減少了搜索區(qū)域，讓搜索的精度下降，來提高算法的效率。文獻(xiàn)[10]針對(duì)復(fù)雜地形的路徑規(guī)劃問題，在A*算法的評(píng)價(jià)函數(shù)中增加安全成本，并將評(píng)價(jià)函數(shù)轉(zhuǎn)換成統(tǒng)一的時(shí)間成本，由此提高了機(jī)器人的安全性。然而，路徑規(guī)劃問題不僅與路徑搜索算法有關(guān)，還與環(huán)境地圖復(fù)雜度密切相關(guān)。……