基于局部障礙率預(yù)獲取和雙向父節(jié)點(diǎn)變更的A*算法優(yōu)化

張志遠(yuǎn),陳海進(jìn),章一鳴

(南通大學(xué)信息科學(xué)技術(shù)學(xué)院,江蘇 南通 226019)

1 引言

隨著人工智能產(chǎn)業(yè)的高速發(fā)展,掃地機(jī)器人和送餐機(jī)器人等逐漸在人們的生活中普及,為現(xiàn)代化生活注入了“信息”基因。作為移動(dòng)機(jī)器人[1]研究領(lǐng)域的核心,路徑規(guī)劃問(wèn)題[2-4]的研究自20世紀(jì)70年代至今從未停止,研究人員積累了大量的研究成果。主流的傳統(tǒng)路徑規(guī)劃方法有可視圖法[5,6]、拓?fù)浞?、柵格法、Dijkstra算法和A*算法[7,8]等,其中可視圖法、拓?fù)浞ê蜄鸥穹ㄍǔ?yīng)用于機(jī)器人感知環(huán)境信息的地圖建模[9],而Dijkstra算法和A*算法通常應(yīng)用于最優(yōu)路徑的求解[10-13]。

近年來(lái),相關(guān)學(xué)者為優(yōu)化機(jī)器人運(yùn)動(dòng)軌跡,提高機(jī)器人的運(yùn)行效率,根據(jù)傳統(tǒng)A*算法的缺點(diǎn)進(jìn)行了各自相應(yīng)的改進(jìn)。文獻(xiàn)[14]采用歐氏距離和曼哈頓距離的線性組合作為評(píng)價(jià)函數(shù),使得評(píng)價(jià)值更接近實(shí)際值,一定程度上提高了搜索效率,但并未明確給出評(píng)價(jià)函數(shù)各部分的權(quán)值的分配方案。文獻(xiàn)[15]根據(jù)機(jī)器人已走路徑在總路徑中的占比動(dòng)態(tài)分配評(píng)價(jià)函數(shù)各個(gè)部分的權(quán)值,已達(dá)到優(yōu)化評(píng)價(jià)函數(shù)的目的,一定程度上優(yōu)化了軌跡平滑度。但是,該算法不考慮地圖局部障礙率的高低,可能導(dǎo)致在局部障礙率較低的區(qū)域搜索較大的空間,降低搜索效率;也可能導(dǎo)致在局部障礙率較高的區(qū)域搜索的空間較小,從而錯(cuò)失最優(yōu)節(jié)點(diǎn),陷入局部最優(yōu)。文獻(xiàn)[16]加權(quán)處理評(píng)價(jià)函數(shù),并通過(guò)人工搜索標(biāo)記,縮小了搜索區(qū)域,犧牲搜索精度換取了搜索效率。文獻(xiàn)[17]提出一種動(dòng)態(tài)啟發(fā)式算法,避免算法陷入局部最優(yōu),在保證搜索效率的前提下優(yōu)化了生成路徑。文獻(xiàn)[18]在復(fù)雜地形尋路的過(guò)程中,在評(píng)價(jià)函數(shù)中加入安全成本,在保證運(yùn)行效率的同時(shí),提高了機(jī)器人尋路的安全性。然而路徑規(guī)劃問(wèn)題應(yīng)不僅與搜索算法相關(guān),更應(yīng)該與環(huán)境地圖密切相關(guān)。

本文提出了基于局部障礙率預(yù)獲取和雙向父節(jié)點(diǎn)變更的改進(jìn)A*算法,能有效地識(shí)別局部環(huán)境信息,依據(jù)環(huán)境復(fù)雜程度動(dòng)態(tài)調(diào)整搜索空間,提高搜索效率,優(yōu)化路徑長(zhǎng)度。首先,基于漂移矩陣預(yù)獲取地圖各個(gè)部分的局部障礙率信息,記錄各個(gè)矩陣內(nèi)障礙率的值。其次,為矩陣內(nèi)障礙率的值建立映射函數(shù),通過(guò)映射函數(shù)動(dòng)態(tài)分配評(píng)價(jià)函數(shù)的權(quán)值,依據(jù)局部環(huán)境復(fù)雜程度靈活調(diào)整搜索空間。最后,依據(jù)改進(jìn)的父節(jié)點(diǎn)變更方式,減少生成路徑的冗余點(diǎn)和拐點(diǎn),進(jìn)一步優(yōu)化路徑。實(shí)驗(yàn)結(jié)果表明,本文改進(jìn)后的算法有效縮短了路徑長(zhǎng)度,提升了搜索效率,具有較強(qiáng)的適應(yīng)性。

2 傳統(tǒng)A*算法

2.1 柵格法地圖建模

傳統(tǒng)A*算法用柵格法進(jìn)行地圖建模,用二進(jìn)制編碼0和1來(lái)表示環(huán)境地圖,0表示無(wú)障礙柵格,1表示障礙柵格。設(shè)機(jī)器人的工作區(qū)域?yàn)閍′×b′的矩形區(qū)域,柵格單位長(zhǎng)度為c,所得柵格地圖為m×n的矩陣,m和n數(shù)值如式(1)所示:

(1)

其中floor(·)為向下取整函數(shù)。

2.2 A*算法路徑規(guī)劃

A*算法每移動(dòng)一格都要對(duì)周?chē)?鄰域柵格內(nèi)的評(píng)價(jià)函數(shù)進(jìn)行計(jì)算,其計(jì)算公式如式(2)所示:

(2)

其中,(x,y)為當(dāng)前柵格s的坐標(biāo),(xS,yS)為起點(diǎn)S的坐標(biāo),(xD,yD)為終點(diǎn)D的坐標(biāo),g(s)為當(dāng)前柵格s到起點(diǎn)的歐氏距離,h(s)為當(dāng)前柵格s到終點(diǎn)的歐氏距離。依次將8鄰域內(nèi)的可選柵格(無(wú)障礙柵格、非已走過(guò)柵格)放入open列表,并從open列表中選出評(píng)價(jià)函數(shù)f(·)值最小的柵格作為下一個(gè)節(jié)點(diǎn)柵格,并將當(dāng)前節(jié)點(diǎn)柵格放入close列表。傳統(tǒng)A*算法從起點(diǎn)出發(fā)搜索至終點(diǎn)結(jié)束,生成路徑。

3 分配權(quán)重的A*算法及其相關(guān)性質(zhì)證明

分配權(quán)重的A*算法對(duì)h(s)和g(s)賦予不同的權(quán)重a和b,以達(dá)到增大或縮小搜索區(qū)域的目的,其評(píng)價(jià)函數(shù)如式(3)所示:

fweight(s)=a·h(s)+b·g(s),a+b=1

(3)

對(duì)于分配權(quán)重的A*算法,有如下結(jié)論:

結(jié)論1當(dāng)a<0.5

證明如圖1所示,當(dāng)a<0.5g(B),且點(diǎn)B滿足以下關(guān)系:

Figure 1 Proof of the relationship between function weight and search area size

BS+BD=AS+AD=

g(B)+h(B)=g(A)+h(A)

(4)

由式(3)可得:

(5)

式(5)中兩式相減后,令b=a+a1,經(jīng)變換得:

fweight(A)-fweight(B)=

a·(h(A)+g(A)-(h(B)+g(B)))+

a1·(g(A)-g(B))

(6)

由式(4)可得:

fweight(A)-fweight(B)=a1·(g(A)-g(B))

(7)

因?yàn)間(A)-g(B)>0,故在點(diǎn)B處,fweight(A)-fweight(B)>0。

過(guò)點(diǎn)B作起終點(diǎn)連線SD的垂線,當(dāng)點(diǎn)B在垂線上向遠(yuǎn)離SD方向移動(dòng)時(shí),h(B)和g(B)值也隨之增大,記增大后的值為h′(B)和g′(B),則:

(8)

其中,Δh(B)和Δg(B)為點(diǎn)B遠(yuǎn)離SD帶來(lái)的增量。

由式(8)可將式(6)變換為:

fweight(A)-fweight(B)=-a·(Δh(B)+Δg(B))-

a1·Δg(B)+a1·(g(A)-g(B))

(9)

式(9)中第1項(xiàng)和第2項(xiàng)為負(fù)值增量,第3項(xiàng)為正值定量,可以看出點(diǎn)B移動(dòng)產(chǎn)生的負(fù)值增量使得式(9)的值逐漸向0逼近,直至式(9)的值為0,點(diǎn)B停止運(yùn)動(dòng),記此時(shí)點(diǎn)B運(yùn)動(dòng)至點(diǎn)P,fweight(A)=fweight(B)。

對(duì)于傳統(tǒng)A*算法,由式(2)和式(4)可得,在點(diǎn)B處就已經(jīng)滿足f(A)=f(B)的關(guān)系,所以三角形SBD區(qū)域內(nèi)的f(·)值均小于f(A)。故在點(diǎn)A被選取之前,三角形SBD區(qū)域內(nèi)的點(diǎn)依次會(huì)被回溯選取為當(dāng)前節(jié)點(diǎn)。三角形SBD即為此時(shí)新增的搜索區(qū)域。而對(duì)于分配權(quán)重的A*算法(a<0.5

□

結(jié)論2當(dāng)a>0.5>b時(shí),分配權(quán)重的A*算法搜索區(qū)域小于傳統(tǒng)A*算法的搜索區(qū)域。

證明式(5)中兩式相減后令a=b+b1,經(jīng)變換可得:

fweight(A)-fweight(B)=

b·(h(A)+g(A)-(h(B)+

g(B)))+b1·(h(A)-h(B))

(10)

由式(4)得:

fweight(A)-fweight(B)=b1·(h(A)-h(B))

(11)

因?yàn)閔(A)-h(B)<0,故在點(diǎn)B處,fweight(A)-fweight(B)<0。

將垂線上的點(diǎn)B向靠近SD方向移動(dòng),h(B)和g(B)的值隨之減小,記減小后的值為:

(12)

隨點(diǎn)B向靠近SD方向移動(dòng),由式(12)可將式(10)改寫(xiě)為:

fweight(A)-fweight(B)=

b·(Δh(B)+Δg(B))+

b1·Δg(B)+b1·(h(A)-h(B))

(13)

式(13)中第1和第2項(xiàng)為正值增量,第3項(xiàng)為負(fù)值定量,可以看出點(diǎn)B向靠近SD方向移動(dòng)產(chǎn)生的正值增量使式(13)的值逐漸向0逼近,直至其值為0,點(diǎn)B停止運(yùn)動(dòng),記此時(shí)點(diǎn)B運(yùn)動(dòng)至點(diǎn)C,fweight(A)=fweight(B)。顯然,a>0.5>b時(shí),三角形SCD即為新增的搜索區(qū)域,其面積小于三角形SBD,結(jié)論2得證。

□

結(jié)論3分配權(quán)重的A*算法搜索區(qū)域大小與a的值成反比,與b的值成正比。

證明當(dāng)aΔg(B),所以總的負(fù)值增量減小,故點(diǎn)B需要運(yùn)動(dòng)到比點(diǎn)P更遠(yuǎn)的位置才能使式(9)的值為0。在此種情況下,算法搜索區(qū)域增大,搜索區(qū)域大小與b值成正比,與a值成反比。

當(dāng)a>b>0.5,a=b+b1時(shí),增大a的值,b1的值增大,b的值減小,使得式(13)中,第1項(xiàng)正值增量系b數(shù)減小,第2項(xiàng)b1正值增量系數(shù)增大,由于Δh(B)+Δg(B)>Δg(B),總的正值增量減小,故點(diǎn)B需要運(yùn)動(dòng)至比點(diǎn)C更靠近SD的位置才能使式(13)的值為0。此時(shí)算法搜索區(qū)域縮小,搜索區(qū)域大小仍與b值成正比,與a值成反比,結(jié)論3得證。

□

4 基于局部障礙率預(yù)獲取的改進(jìn)A*算法

本文提出基于局部障礙率預(yù)獲取的改進(jìn)A*算法,利用漂移矩陣在對(duì)地圖的局部障礙率信息進(jìn)行預(yù)獲取后,通過(guò)第3節(jié)分配權(quán)重評(píng)價(jià)函數(shù)已證明的相關(guān)結(jié)論,將量化后的局部障礙率信息融入評(píng)價(jià)函數(shù)中,進(jìn)一步對(duì)權(quán)重的分配方式進(jìn)行改進(jìn),使得在障礙物復(fù)雜程度不同的各個(gè)區(qū)域內(nèi),算法可依據(jù)環(huán)境信息自適應(yīng)調(diào)整搜索空間,在生成路徑最優(yōu)化的同時(shí),也提升了搜索的靈活性,確保算法高效運(yùn)行。

4.1 基于漂移矩陣獲取地圖局部障礙率

基于柵格法對(duì)機(jī)器人工作環(huán)境進(jìn)行地圖建模。設(shè)所獲柵格地圖為m×n的矩形。構(gòu)建漂移矩陣A1。在同一地圖范圍內(nèi),漂移矩陣的邊長(zhǎng)l取值越小,漂移矩陣數(shù)量越多,所獲取的局部障礙率信息越豐富。顯然,在同一位置用不同大小的漂移矩陣獲取局部障礙率,其邊長(zhǎng)l越小,局部障礙率的精度越高,越能準(zhǔn)確反映當(dāng)前位置附近的環(huán)境信息。本文中l(wèi)取3個(gè)單位柵格長(zhǎng)度,為可取范圍內(nèi)的最小取值,所得漂移矩陣為當(dāng)前位置鄰域內(nèi)3×3大小的柵格矩陣。

用式(3)作為評(píng)價(jià)函數(shù)的A*算法,給予h(s)高權(quán)重,快速規(guī)劃出一條自起點(diǎn)至終點(diǎn)的路徑,漂移矩陣在A*算法尋路過(guò)程中跟隨移動(dòng)并記錄當(dāng)前矩陣內(nèi)部障礙率,每當(dāng)尋路所在當(dāng)前柵格超出漂移矩陣范圍時(shí),則重新構(gòu)建漂移矩陣,記當(dāng)前柵格坐標(biāo)為(x,y),記第i個(gè)漂移矩陣Ai的障礙率值如式(14)所示:

(14)

其中,oi是矩陣中值為1的柵格(障礙柵格)的數(shù)目。記最后一個(gè)漂移矩陣的局部障礙率為pk,從p1到pk中獲得地圖局部障礙率p的取值在[pmin,pmax]。基于漂移矩陣獲取地圖局部障礙率具體流程如圖2所示。

Figure 2 Flow chart of drift matrix algorithm

圖3所示為基于漂移矩陣獲取地圖局部障礙率的實(shí)例,設(shè)柵格法建模所獲地圖為30×30矩陣,起點(diǎn)S坐標(biāo)為(1,1),終點(diǎn)D坐標(biāo)為(30,30),漂移矩陣為3×3大小的柵格矩陣。按圖3所示流程,由于起點(diǎn)(1,1)的橫縱坐標(biāo)值均小于2,故算法首先以a1(2,2)為中心構(gòu)建包含起點(diǎn)的漂移矩陣A1,并記錄當(dāng)前矩陣內(nèi)的障礙率值p1。當(dāng)A*算法尋路至a2點(diǎn)時(shí),當(dāng)前位置坐標(biāo)(4,4)超出漂移矩陣A1所在范圍,且其橫縱坐標(biāo)值均大于2,故以當(dāng)前位置(4,4)為中心構(gòu)建新的漂移矩陣A2,同樣記錄當(dāng)前矩陣內(nèi)的障礙率值p2,以此類(lèi)推,當(dāng)算法尋路至終點(diǎn)D時(shí),統(tǒng)計(jì)漂移矩陣A1至An內(nèi)障礙率的極大值pmax和極小值pmin,獲取局部障礙率p值的取值區(qū)間[pmin,pmax],算法結(jié)束。

Figure 3 Schematic diagram of map local obstacle rate pre-acquisition

4.2 評(píng)價(jià)函數(shù)權(quán)重比例的改進(jìn)

由第3節(jié)已證明的相關(guān)結(jié)論可知,分配權(quán)重的評(píng)價(jià)函數(shù)通過(guò)改變各項(xiàng)的權(quán)重比例可以擴(kuò)大或縮小搜索空間。當(dāng)h(s)的權(quán)重增大時(shí),算法的表現(xiàn)為搜索區(qū)域縮小,運(yùn)行效率提升,更偏向于選擇距終點(diǎn)代價(jià)更小的路徑,會(huì)陷入局部最優(yōu);當(dāng)h(s)的權(quán)重減小時(shí),搜索區(qū)域逐漸增大,運(yùn)行效率降低,但往往能夠優(yōu)化生成路徑的長(zhǎng)度。為了平衡啟發(fā)式信息強(qiáng)度和優(yōu)化生成的路徑,本文將4.1節(jié)基于漂移矩陣預(yù)獲取的障礙率信息融入評(píng)價(jià)函數(shù)中,設(shè)計(jì)如式(15)所示的權(quán)重關(guān)系函數(shù):

(15)

其中,c和d為權(quán)重調(diào)節(jié)因子,p為局部障礙率。

將式(15)代入式(3)可得:

(16)

當(dāng)p值變化時(shí),g(s)的權(quán)重與h(s)的權(quán)重始終成反比,且二者之和為1。當(dāng)d/(c+p)取值為0.5時(shí),式(16)改寫(xiě)為:

fweight(s)=0.5·g(s)+0.5·h(s)

(17)

式(17)中2項(xiàng)權(quán)重均為0.5,搜索空間和生成路徑與傳統(tǒng)A*算法一致。c、d為常數(shù),與預(yù)獲取的局部障礙率信息pmin、pmax滿足以下關(guān)系:

(18)

通過(guò)式(18)確定常數(shù)c、d的值,同時(shí)對(duì)應(yīng)p的取值在[pmin,pmax]內(nèi),權(quán)重d/(c+p)和(c-d+p)/(c+p)的取值始終在[λ1,λ2],λ1和λ2為搜索區(qū)域調(diào)節(jié)因子,當(dāng)λ1和λ2分別處于0.45和0.55的鄰域內(nèi)時(shí),算法既不會(huì)因?yàn)間(s)的權(quán)重過(guò)低(<0.45)而產(chǎn)生較多的冗余點(diǎn)和拐點(diǎn),也不會(huì)因?yàn)間(s)的權(quán)重過(guò)高(>0.55)而產(chǎn)生過(guò)多無(wú)用的搜索空間。評(píng)價(jià)函數(shù)的權(quán)重始終維持在一個(gè)合理的范圍之內(nèi),在不同的漂移矩陣內(nèi)依據(jù)其內(nèi)部的局部障礙信息,自適應(yīng)地調(diào)整權(quán)重,按需產(chǎn)生不同的有效的搜索空間,在對(duì)路徑優(yōu)化的同時(shí),也保證了算法高效、靈活地運(yùn)行。

5 父節(jié)點(diǎn)變更方式優(yōu)化

A*算法作為一種啟發(fā)式搜索算法,在尋路過(guò)程中會(huì)產(chǎn)生多條子路徑,而最先找到終點(diǎn)的路徑為最終生成的規(guī)劃路徑,該條件下,各個(gè)子路徑之間柵格父節(jié)點(diǎn)的變更對(duì)路徑優(yōu)化起著至關(guān)重要的作用。本文在傳統(tǒng)A*算法父節(jié)點(diǎn)變更的方式上進(jìn)行改進(jìn),以有效減少生成路徑的冗余點(diǎn),進(jìn)一步優(yōu)化路徑。

如圖4所示,柵格V及其它空白柵格為未選柵格,Xn+1～Xn+7按下標(biāo)順序先后被選為當(dāng)前柵格,設(shè)置子父節(jié)點(diǎn)的鏈接后放入close列表(圖中黑色箭頭的起點(diǎn)為父節(jié)點(diǎn),終點(diǎn)為指向子節(jié)點(diǎn))。設(shè)由起點(diǎn)start→柵格V為路徑route1,由起點(diǎn)start→柵格Xn為路徑route2,且route1的長(zhǎng)度遠(yuǎn)小于route2的。顯然,路徑route1→Xn+4→Xn+2→Xn+5要優(yōu)于實(shí)際路徑route2→Xn+1→Xn+2→Xn+5。這是由于分配給h(s)較高的權(quán)值,算法遵循終點(diǎn)最優(yōu)原則,會(huì)優(yōu)先選取靠近終點(diǎn)的柵格作為當(dāng)前柵格,搜索區(qū)域也相對(duì)較小,因此錯(cuò)失更優(yōu)路徑上的柵格V,因而錯(cuò)失全局最優(yōu)路徑,陷入局部最優(yōu)。

Figure 4 Pointing diagram of child and parent nodes in traditional A* algorithm

針對(duì)上述問(wèn)題,本文對(duì)傳統(tǒng)A*算法的父節(jié)點(diǎn)變更方式進(jìn)行改進(jìn),在檢測(cè)由起點(diǎn)至當(dāng)前柵格到子路徑柵格是否存在更優(yōu)路徑的同時(shí),也檢測(cè)子路徑柵格所屬路徑到當(dāng)前柵格是否存在更優(yōu)路徑,由原本的單向訪問(wèn)優(yōu)化為雙向訪問(wèn),在保證搜索空間有限的前提下不遺漏更優(yōu)路徑,確保路徑的全局最優(yōu)性。

步驟1從待選柵格列表選取柵格作為當(dāng)前柵格,并記當(dāng)前柵格current的8鄰域內(nèi)的柵格依次為currenti(i=1,…,8),判斷當(dāng)前柵格是否為終點(diǎn),若是,算法運(yùn)行結(jié)束,若不是,轉(zhuǎn)到步驟2。

步驟2判斷i是否等于8,若等于返回步驟1,若不等于,i=i+1,轉(zhuǎn)到步驟3。

步驟3判斷currenti是否為障礙,若為障礙,返回步驟2;若不為障礙,轉(zhuǎn)到步驟4。

步驟4判斷currenti是否在open列表中,若在open列表中,轉(zhuǎn)到步驟5;若不在,則將currenti父節(jié)點(diǎn)設(shè)為當(dāng)前柵格current,i=i+1,轉(zhuǎn)到步驟2。

步驟5判斷經(jīng)由所屬路徑到達(dá)currenti是否更優(yōu),若更優(yōu)則將currenti的父節(jié)點(diǎn)變更為當(dāng)前柵格current,轉(zhuǎn)到步驟2。

步驟6判斷經(jīng)由currenti所屬路徑到達(dá)當(dāng)前柵格current是否更優(yōu),若更優(yōu),則將當(dāng)前柵格的父節(jié)點(diǎn)變更為currenti,同時(shí)將currenti作為下一個(gè)待選柵格放入待選柵格列表,轉(zhuǎn)到步驟2。

圖5a所示為改進(jìn)前的示意圖,當(dāng)選中Xn+1為當(dāng)前柵格時(shí),經(jīng)其右上角柵格V所屬路徑route1到達(dá)當(dāng)前柵格Xn+1,顯然比Xn+1所屬路徑route2代價(jià)更小。改進(jìn)后,經(jīng)由route1→Xn+4→Xn+2→Xn+5的路徑要優(yōu)于原先由route2→Xn+1→Xn+2→Xn+5的路徑?？梢钥闯?在h(s)權(quán)值較高,搜索區(qū)域較小的情況下,即使所屬更優(yōu)路徑的柵格V沒(méi)有被選為當(dāng)前柵格,按改進(jìn)后的父節(jié)點(diǎn)變更方式,也可以通過(guò)其相鄰柵格檢測(cè)出V所在的更優(yōu)路徑,并以V為當(dāng)前柵格進(jìn)一步對(duì)該條路徑進(jìn)行延續(xù)性擴(kuò)展,由局部路徑優(yōu)化延續(xù)為全局路徑優(yōu)化,有效減少生成路徑的冗余點(diǎn)。

Figure 5 Comparison diagram of parent node changes before and after improvement

6 仿真與結(jié)果分析

6.1 基于局部障礙率預(yù)獲取的改進(jìn)A*算法仿真

為驗(yàn)證基于局部障礙率預(yù)獲取的改進(jìn)A*算法的適應(yīng)性和有效性,本節(jié)選取3個(gè)不同尺寸和障礙物密度的柵格地圖,將本文算法和傳統(tǒng)A*算法及文獻(xiàn)[15]引入路徑權(quán)值的改進(jìn)A*算法進(jìn)行對(duì)比,3組實(shí)驗(yàn)的對(duì)比仿真結(jié)果如圖6所示。

Figure 6 Comparison of simulation results among three algorithms

本次對(duì)比實(shí)驗(yàn)是理想仿真,建立了30×30的移動(dòng)機(jī)器人工作環(huán)境地圖,假定環(huán)境地圖的柵格邊長(zhǎng)為1 m,對(duì)角線長(zhǎng)度為1.42 m,為測(cè)算實(shí)際情況下機(jī)器人按實(shí)驗(yàn)路徑尋路所花費(fèi)的時(shí)間,假設(shè)機(jī)器人的移動(dòng)速度v=0.5 m/s,原地旋轉(zhuǎn)45°所需時(shí)間為1 s。3種算法的評(píng)價(jià)指標(biāo)為:柵格搜索個(gè)數(shù)(搜索區(qū)域大小)、路徑長(zhǎng)度、轉(zhuǎn)角次數(shù)和機(jī)器人實(shí)際尋路時(shí)間。本文具體實(shí)驗(yàn)數(shù)據(jù)統(tǒng)計(jì)結(jié)果如表1所示。

Table 1 Analysis of three algorithms simulation results

從表1的對(duì)比仿真數(shù)據(jù)可以看出,傳統(tǒng)A*算法不能很好地識(shí)別地圖信息,陷入了局部最優(yōu),增加了不必要的冗余節(jié)點(diǎn),轉(zhuǎn)彎次數(shù)多,消耗了機(jī)器人的移動(dòng)時(shí)間。對(duì)于文獻(xiàn)[15]中引入路徑權(quán)值的改進(jìn)A*算法,相較于傳統(tǒng)A*算法擴(kuò)大了搜索空間,縮短了路徑長(zhǎng)度,減少了轉(zhuǎn)角次數(shù)。但是,依靠路徑權(quán)值對(duì)搜索空間的調(diào)整,沒(méi)有達(dá)到依據(jù)具體環(huán)境按需分配搜索空間的目的。比較表1中數(shù)據(jù)可以看出,本文算法在局部復(fù)雜地區(qū),擴(kuò)大了搜索空間,確保路徑最優(yōu),在局部障礙率低的區(qū)域,縮小了搜索空間,提升了搜索效率,不但在搜索空間個(gè)數(shù)這一指標(biāo)上明顯下降,較文獻(xiàn)[15]中引入路徑權(quán)值的A*算法,在3種不同地圖環(huán)境中的路徑長(zhǎng)度分別由50.34 m縮短為47.82 m,47.08 m縮短為44.66 m,46.4 m縮短為45.24 m,且轉(zhuǎn)彎次數(shù)這一指標(biāo)上也有明顯提升,有效縮短了機(jī)器人在實(shí)際環(huán)境工作中的尋路時(shí)間。

6.2 優(yōu)化父節(jié)點(diǎn)變更方式算法仿真

為驗(yàn)證改進(jìn)的父節(jié)點(diǎn)變更方式可進(jìn)一步優(yōu)化生成路徑,本節(jié)在6.1節(jié)實(shí)驗(yàn)的基礎(chǔ)上將改進(jìn)的父節(jié)點(diǎn)變更方式融入算法,其仿真結(jié)果對(duì)比如圖7所示。

Figure 7 Comparison before and after optimizing parent node

圖7中,S為起點(diǎn),D為終點(diǎn),黑色柵格為障礙,白色柵格為無(wú)障礙區(qū)域,黑色實(shí)線為尋路路徑。圖7a即為優(yōu)化父節(jié)點(diǎn)前圖6c的算法仿真結(jié)果,圖7b為優(yōu)化父節(jié)點(diǎn)后的算法仿真結(jié)果?？梢钥闯?在地圖左上角的局部區(qū)域內(nèi),障礙率較低,依據(jù)式(16),本文算法分配給h(s)較高的權(quán)值,以達(dá)到縮小搜索區(qū)域,提高運(yùn)行效率的目的,但也因此錯(cuò)過(guò)更優(yōu)路徑,陷入局部最優(yōu)。在這種情況下,改進(jìn)的父節(jié)點(diǎn)變更方式很好地彌補(bǔ)了這一弊端,將路徑總長(zhǎng)度由47.82 m縮短為46.98 m,在保證運(yùn)行效率的同時(shí),篩選出了當(dāng)前區(qū)域內(nèi)的最優(yōu)路徑并延續(xù)擴(kuò)展至終點(diǎn),由局部最優(yōu)上升為全局最優(yōu),有效地減少了生成路徑的冗余點(diǎn)。

7 結(jié)束語(yǔ)

本文就機(jī)器人如何更高效地識(shí)別和利用已知地圖進(jìn)行路徑規(guī)劃的問(wèn)題,提出了一種基于漂移矩陣地圖預(yù)獲取的改進(jìn)A*算法。通過(guò)漂移矩陣預(yù)獲取地圖各個(gè)部分的局部障礙信息,并融入評(píng)價(jià)函數(shù),使得算法能在不同復(fù)雜程度區(qū)域按需調(diào)整搜索空間,并用改進(jìn)的父節(jié)點(diǎn)變更方式進(jìn)一步優(yōu)化生成路徑。仿真結(jié)果表明,本文算法較傳統(tǒng)算法更具適應(yīng)性和有效性,在相同大小的搜索區(qū)域內(nèi),本文算法可以獲得更短的路徑長(zhǎng)度,更少的轉(zhuǎn)角次數(shù),有效減少生成路徑的冗余點(diǎn);在獲得同等路徑長(zhǎng)度的條件下,可以有效縮小搜索空間,縮短運(yùn)行時(shí)間,提高機(jī)器人的運(yùn)行效率。