一種改進(jìn)啟發(fā)函數(shù)的A*算法

樊康生, 楊光永, 黃訓(xùn)愛, 陳旭東, 徐天奇

(云南民族大學(xué)電氣信息工程學(xué)院, 昆明 650500)

路徑規(guī)劃是輪式移動(dòng)機(jī)器人領(lǐng)域的研究重點(diǎn)[1]. 根據(jù)已知環(huán)境信息可將路徑規(guī)劃分為局部規(guī)劃和全局規(guī)劃, 全局路徑規(guī)劃算法主要有Dijkstra算法[2]和A*算法[3-4]等, 其中A*算法因其規(guī)劃路徑短和計(jì)算速度快而得到普遍應(yīng)用. 然而, 傳統(tǒng)A*算法存在規(guī)劃路徑搜索節(jié)點(diǎn)多和轉(zhuǎn)折角度大等缺點(diǎn)[5], 故為了提升A*算法的性能, 諸多學(xué)者提出了改進(jìn)方法．趙曉等[6]使用跳點(diǎn)搜索策略, 加快了搜索速度, 但優(yōu)化后的路徑存在大角度的拐點(diǎn); Tang等[7]將幾何思想引入算法中,縮短了路徑長度, 但增加了搜索時(shí)間; Shang等[8]通過刪除邊生成更短的k倍路徑, 提高了搜索效率, 但增加了尋路時(shí)間; Mi等[9]基于快速搜索隨機(jī)樹(rapidly-exploring random tree, RRT)和跳點(diǎn)搜索(jump point search, JPS)改進(jìn)A*算法, 有效減少了無用擴(kuò)展節(jié)點(diǎn), 提高了搜索效率和路徑平滑度, 但增加了路徑長度; Zhang等[10]提出了一種包含雙向扇區(qū)擴(kuò)展和變步長搜索策略的改進(jìn)A*算法, 提高了搜索效率,但路徑較長; Zhang等[11]采用混合蟻群算法改進(jìn)A*算法, 提高了規(guī)劃路徑的安全性,但搜索效率較低; Sui等[12]利用粒子群算法改進(jìn)A*算法, 獲得較短的優(yōu)化路徑,但算法復(fù)雜度較高且不穩(wěn)定; Dong等[13]提出幾何A*算法, 有效縮短了規(guī)劃路徑,但搜索效率較低; Sang等[14]采用混合人工智能改進(jìn)A*算法, 有效提高了算法搜索效率,但路徑轉(zhuǎn)折拐點(diǎn)較多; Liu[15]和Lai[16]等利用Bézier曲線獲得了較為平滑的路徑, 但增加了路徑長度; Zhang[17]和Bai[18]等改變鄰域搜索策略,有效提高了搜索效率,但路徑拐點(diǎn)較多．針對以上問題, 本文擬提出一種改進(jìn)啟發(fā)函數(shù)的A*算法, 通過改進(jìn)啟發(fā)函數(shù)的表達(dá)式, 引入動(dòng)態(tài)權(quán)重因子調(diào)整啟發(fā)函數(shù), 并在累積代價(jià)函數(shù)前引入權(quán)重因子, 以期提高算法搜索效率, 減少算法搜索節(jié)點(diǎn)和拐點(diǎn), 減小路徑累積轉(zhuǎn)折角度．

1 改進(jìn)啟發(fā)函數(shù)的A*算法

1.1 A*算法

A*算法采用總代價(jià)評(píng)價(jià)并選擇后續(xù)節(jié)點(diǎn)的搜索方向, 總代價(jià)函數(shù)表達(dá)式為

f(n)=g(n)+h(n),

(1)

其中g(shù)(n)為起始節(jié)點(diǎn)n0至節(jié)點(diǎn)ni的累積代價(jià); 啟發(fā)函數(shù)h(n)為節(jié)點(diǎn)ni至目標(biāo)節(jié)點(diǎn)nt的距離, 提供了對當(dāng)前狀態(tài)到目標(biāo)狀態(tài)的估計(jì)代價(jià)或優(yōu)先級(jí)信息, 使算法能夠更加有針對性地搜索潛在路徑．本文采用歐幾里德距離表示啟發(fā)函數(shù)

(2)

其中nix為當(dāng)前節(jié)點(diǎn)橫坐標(biāo),niy為當(dāng)前節(jié)點(diǎn)縱坐標(biāo),ntx為目標(biāo)節(jié)點(diǎn)橫坐標(biāo),nty為目標(biāo)節(jié)點(diǎn)縱坐標(biāo)．

1.2 改進(jìn)A*算法

1.2.1 改進(jìn)啟發(fā)函數(shù)表達(dá)式

為了更好地引導(dǎo)算法搜索方向, 提高算法搜索效率,本文引入子節(jié)點(diǎn)(當(dāng)前節(jié)點(diǎn)通過移動(dòng)、旋轉(zhuǎn)或轉(zhuǎn)換等一步操作即可到達(dá)的相鄰節(jié)點(diǎn))坐標(biāo)信息計(jì)算啟發(fā)函數(shù)

(3)

其中n(i+1)x為子節(jié)點(diǎn)橫坐標(biāo),n(i+1)y為子節(jié)點(diǎn)縱坐標(biāo)．改進(jìn)的啟發(fā)函數(shù)可使A*算法借助啟發(fā)函數(shù)信息優(yōu)先選擇潛力更大、更接近目標(biāo)的路徑進(jìn)行搜索, 并且搜索過程中可略過代價(jià)過高或無效的路徑, 從而提高搜索效率和縮小搜索空間, 使得算法能夠更快地找到最優(yōu)路徑．

1.2.2 動(dòng)態(tài)權(quán)重因子調(diào)整啟發(fā)函數(shù)

傳統(tǒng)A*算法中若當(dāng)前節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)之間沒有障礙物, 則h(n)與實(shí)際路徑距離相等, 算法搜索速度快、準(zhǔn)確率高, 但實(shí)際情況下往往存在障礙物, 路徑實(shí)際距離大于h(n), 致使算法搜索空間變大, 搜索效率降低．當(dāng)h(n)→0,f(n)=g(n), 即為Dijkstra算法; 當(dāng)h(n)?g(n),f(n)=h(n), 即為廣度優(yōu)先算法(breadth first search, BFS)．若h(n)過小, 則算法擴(kuò)展節(jié)點(diǎn)多, 搜索效率低; 若h(n)過大, 則難以保證所規(guī)劃路徑為最短路徑．因此, 適當(dāng)調(diào)整h(n)權(quán)重可提高算法性能．當(dāng)障礙物較少時(shí), 適當(dāng)增大h(n)權(quán)重可縮小算法搜索范圍,提高算法搜索效率; 當(dāng)障礙物較多時(shí), 適當(dāng)減小h(n)權(quán)重可擴(kuò)大算法搜索范圍, 有利于算法尋找最優(yōu)路徑．

本文通過子節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)障礙物占地面積s1與子節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)地圖總面積s2的比值ρ構(gòu)造動(dòng)態(tài)權(quán)重因子β,調(diào)整啟發(fā)函數(shù), 改進(jìn)總代價(jià)函數(shù)

f(n)=g(n)+β·h′(n),

(4)

β=f(ρ)=g(s1,s2,α),

(5)

(6)

(7)

其中α為ρ的調(diào)和因子,α∈(0,1); Δnjx和Δnjy分別為橫坐標(biāo)和縱坐標(biāo)的變化量．通過實(shí)驗(yàn)測試不同α值對算法搜索節(jié)點(diǎn)N和路徑長度L的影響, 設(shè)置α的步長為0.01, 結(jié)果如表1所示．由表1可知, 當(dāng)α∈[0.1, 0.57)時(shí), 搜索節(jié)點(diǎn)和搜索路徑長度均為最小值.本文取α=0.1．

表1 不同α值對應(yīng)的搜索節(jié)點(diǎn)和路徑長度

由s1和s2的定義可知,s1≤s2,ρ∈(0,1)．采用對數(shù)函數(shù)、線性函數(shù)、指數(shù)函數(shù)、sigmoid函數(shù)和正切函數(shù)構(gòu)造h′(n)的動(dòng)態(tài)權(quán)重因子, 進(jìn)行仿真測試．圖1為函數(shù)β=f(ρ)的仿真結(jié)果．由圖1可知,β與ρ呈正相關(guān),表示障礙物越多,h′(n)權(quán)重越大, 不符合算法設(shè)計(jì)要求．

圖1 函數(shù)β=f(ρ)仿真結(jié)果

為了滿足算法要求, 構(gòu)造函數(shù)β=1-f(ρ), 其仿真結(jié)果如圖2所示．由圖2可知: 1) 對數(shù)函數(shù)的一階導(dǎo)數(shù)β′=-ρ-1, 當(dāng)ρ→0時(shí),β′→-∞,β→+∞; 當(dāng)ρ∈(0,1)時(shí),β>1, 表明算法搜索效率有所提高, 但搜索范圍小, 易陷入局部最優(yōu); 2) 指數(shù)函數(shù)中β<0, 不能有效引導(dǎo)算法搜索方向; 3) 正切函數(shù)中ρ→1時(shí),β<0, 說明障礙物較多時(shí)不能正向引導(dǎo)算法搜索; 4) sigmoid函數(shù)中β隨ρ的變化較小, 說明障礙物對算法搜索的影響不大, 與實(shí)際情況不符; 5) 線性函數(shù)中ρ→0時(shí),β→1, 相當(dāng)于傳統(tǒng)A*算法;ρ∈(0,1)時(shí),β<1, 相當(dāng)于減小傳統(tǒng)A*算法中啟發(fā)函數(shù)的權(quán)重, 雖擴(kuò)大了搜索范圍, 有利于算法逃離局部最優(yōu)解, 但搜索效率下降．

圖2 函數(shù)β=1-f(ρ)仿真結(jié)果

為達(dá)到算法性能要求, 采用對數(shù)函數(shù)和線性函數(shù)構(gòu)造動(dòng)態(tài)權(quán)重因子

β=a0ρ3+a1ρ2+a2ρ+a3,

(8)

圖3為函數(shù)β=a0ρ3+a1ρ2+a2ρ+a3的仿真結(jié)果．由圖3可知: 當(dāng)ρ∈(0,0.48]時(shí),β>1, 有利于算法縮小搜索空間, 提高搜索效率; 當(dāng)ρ∈(0.48,1)時(shí),β∈(0,1), 有利于算法擴(kuò)大搜索空間, 逃離局部最優(yōu)解; 當(dāng)ρ=1時(shí),β=0, 表示該區(qū)域內(nèi)全是障礙物, 沒有可通行路徑．綜上, 該函數(shù)符合算法設(shè)計(jì)要求和實(shí)際應(yīng)用場景．

圖3 函數(shù)β=a0ρ3+a1ρ2+a2ρ+a3仿真結(jié)果

1.2.3 權(quán)重因子調(diào)整累積代價(jià)函數(shù)

為避免g(n)和h′(n)失去平衡, 本文引入權(quán)重因子μ調(diào)整累積代價(jià)函數(shù), 進(jìn)一步改進(jìn)總代價(jià)函數(shù)

f(n)=μg(n)+βh′(n),

(9)

(10)

其中μ∈(0,1)．求μ的一階導(dǎo)數(shù)

(11)

由此得出,μ′<0,μ為遞減函數(shù)．當(dāng)h′(n)為0～100時(shí), 權(quán)重因子μ的變化曲線如圖4所示．由圖4可知: 早期h′(n)較大,μ較小; 隨著子節(jié)點(diǎn)逐漸靠近目標(biāo)節(jié)點(diǎn),h′(n)逐漸減小,μ逐漸增大, 有利于提高算法搜索效率．故引入權(quán)重因子μ可有效減少算法搜索節(jié)點(diǎn)和拐點(diǎn), 降低路徑轉(zhuǎn)折角度, 縮短路徑長度．

圖4 h(n)′與μ關(guān)系曲線

2 實(shí)驗(yàn)結(jié)果與分析

為驗(yàn)證本文算法的有效性, 選取Dijkstra算法、BFS算法、傳統(tǒng)A*算法、調(diào)和A*算法和啟發(fā)函數(shù)+B樣條改進(jìn)A*算法等5種路徑規(guī)劃方法與本文改進(jìn)的A*算法在相同柵格地圖中進(jìn)行路徑規(guī)劃仿真實(shí)驗(yàn), 路徑規(guī)劃結(jié)果如圖5所示, 圖中黑色柵格代表障礙物, 灰色柵格代表算法路徑規(guī)劃過程中的搜索節(jié)點(diǎn), 起始位置標(biāo)記為△,目標(biāo)點(diǎn)位置標(biāo)記為○．每種算法各設(shè)置10個(gè)實(shí)驗(yàn)組, 每組實(shí)驗(yàn)對應(yīng)的平均尋路時(shí)間如圖6所示．由圖6可知, 本文算法的平均尋路時(shí)間最少, 且不同實(shí)驗(yàn)組之間的平均尋路時(shí)間差異較小, 表明該算法的搜索效率最高, 穩(wěn)定性最好．

圖5 不同算法路徑規(guī)劃仿真結(jié)果

圖6 不同算法的尋路時(shí)間對比

為更好地驗(yàn)證本文改進(jìn)后A*算法的性能, 對比不同算法的路徑規(guī)劃過程中搜索節(jié)點(diǎn)、尋路時(shí)間、路徑長度、路徑拐點(diǎn)數(shù)和路徑轉(zhuǎn)折角度, 結(jié)果如表2所示．由表2可知:與Dijkstra算法相比,本文算法搜索節(jié)點(diǎn)減少了85.17%, 尋路時(shí)間減少了109.648 ms,搜索效率提高了91.88%, 路徑長度縮短了6.15%, 路徑拐點(diǎn)數(shù)減少了28.57%,路徑總轉(zhuǎn)折角度減小了40.00%; 與BFS算法相比,本文算法搜索節(jié)點(diǎn)減少了18.32%, 尋路時(shí)間減少了5.689 ms, 搜索效率提高了37.00%, 路徑長度縮短了15.59%, 路徑拐點(diǎn)數(shù)減少了45.45%, 路徑總轉(zhuǎn)折角度減小了50.00%; 與傳統(tǒng)A*算法相相比, 本文算法搜索節(jié)點(diǎn)減少了51.14%, 尋路時(shí)間減少了24.397 ms, 搜索效率提高了75.58%, 路徑長度縮短了3.90%, 路徑經(jīng)過拐點(diǎn)數(shù)減少了50.00%, 路徑總轉(zhuǎn)折角度減小了53.85%; 與調(diào)和A*算法相比, 本文算法搜索節(jié)點(diǎn)減少了11.57%, 尋路時(shí)間減少了7.198 ms, 搜索效率提高了42.63%, 路徑長度縮短了30.85%, 路徑經(jīng)過拐點(diǎn)數(shù)減少了61.29%, 路徑總轉(zhuǎn)折角度減小了73.91%; 與啟發(fā)函數(shù)+B樣條改進(jìn)A*算法相比, 本文算法搜索節(jié)點(diǎn)減少了31.41%,尋路時(shí)間減少了7.198 ms, 搜索效率提高了42.63%, 路徑長度縮短了4.21%, 路徑經(jīng)過拐點(diǎn)數(shù)減少了50.00%, 路徑總轉(zhuǎn)折角度減小了50.00%．綜上得出, 本文改進(jìn)的A*算法用于路徑規(guī)劃時(shí),搜索節(jié)點(diǎn)更少,搜索效率更高, 搜索路徑更短, 拐點(diǎn)數(shù)更少, 總轉(zhuǎn)折角度更小, 故改進(jìn)后A*算法具有更好的路徑規(guī)劃性能．

表2 不同算法的路徑規(guī)劃性能指標(biāo)

3 結(jié)論

本文基于子節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)距離改進(jìn)A*算法中啟發(fā)函數(shù)的表達(dá)式,通過子節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)障礙物占地面積與子節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)地圖總面積比值構(gòu)造的動(dòng)態(tài)權(quán)重因子調(diào)整啟發(fā)函數(shù), 并以啟發(fā)函數(shù)構(gòu)造累積代價(jià)函數(shù)的權(quán)重因子．實(shí)驗(yàn)結(jié)果表明, 改進(jìn)后A*算法有效減少了搜索節(jié)點(diǎn), 縮短了尋路時(shí)間和路徑長度, 減少了路徑拐點(diǎn), 降低了路徑轉(zhuǎn)折角度, 具有較好的路徑規(guī)劃性能．