樊康生, 楊光永, 黃訓愛, 陳旭東, 徐天奇

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

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

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

1.1 A*算法

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

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

(1)

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

(2)

其中nix為當前節(jié)點橫坐標,niy為當前節(jié)點縱坐標,ntx為目標節(jié)點橫坐標,nty為目標節(jié)點縱坐標．

1.2 改進A*算法

1.2.1 改進啟發(fā)函數(shù)表達式

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

(3)

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

1.2.2 動態(tài)權重因子調整啟發(fā)函數(shù)

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

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

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

(4)

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

(5)

(6)

(7)

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

表1 不同α值對應的搜索節(jié)點和路徑長度

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

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

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

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

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

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

(8)

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

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

1.2.3 權重因子調整累積代價函數(shù)

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

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

(9)

(10)

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

(11)

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

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

2 實驗結果與分析

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

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

圖6 不同算法的尋路時間對比

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

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

3 結論

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