基于改進(jìn)A_Star算法的移動(dòng)機(jī)器人動(dòng)態(tài)路徑規(guī)劃

李 杰

(安徽三聯(lián)學(xué)院機(jī)械工程學(xué)院,合肥 230601)

0 引言

隨著機(jī)器人各方面能力的不斷提高,移動(dòng)機(jī)器人可充當(dāng)勞動(dòng)力,助人類完成工作,而路徑規(guī)劃是該領(lǐng)域的一項(xiàng)關(guān)鍵技術(shù)[1]。

智能規(guī)劃算法多種多樣,包括模擬退火法[2]、人工勢(shì)場(chǎng)法[3]、神經(jīng)網(wǎng)絡(luò)[4]、蟻群算法[5]、粒子群算法[6]、遺傳算法[7]等,其中A_Star算法作為一種智能啟發(fā)式算法,因其良好的通用性及拓展性被廣泛應(yīng)用于物流運(yùn)輸[8-10]、智能倉(cāng)庫(kù)[11]、物聯(lián)網(wǎng)[12]、航空航天[13]及無人駕駛[14]等領(lǐng)域。A_Star算法也可應(yīng)用于路徑規(guī)劃問題,并對(duì)其進(jìn)行了大量研究。王忠玉等[15]拓展了A_Star算法的搜索領(lǐng)域,在優(yōu)化路徑、評(píng)價(jià)函數(shù)權(quán)重比例方面做出了貢獻(xiàn)。李二超[16]等通過改進(jìn)人工勢(shì)場(chǎng)法對(duì)移動(dòng)機(jī)器人避障軌跡進(jìn)行了研究,但其避障不適合過多障礙物的復(fù)雜環(huán)境。而動(dòng)態(tài)窗口法模型簡(jiǎn)單,局部避障能力強(qiáng),可以適應(yīng)復(fù)雜環(huán)境,但容易陷入局部最優(yōu)。

根據(jù)上述問題,本研究提出一種將改進(jìn)的A_Star算法與改進(jìn)的動(dòng)態(tài)窗口法相結(jié)合的方式,解決機(jī)器人在復(fù)雜環(huán)境下隨機(jī)避障問題。從減少搜索方向、平滑規(guī)劃路徑、優(yōu)化評(píng)價(jià)函數(shù)、障礙物拓展策略及路徑形式等方面對(duì)A_Star算法進(jìn)行改進(jìn),得出最優(yōu)路徑,為動(dòng)態(tài)窗口法提供全局指引點(diǎn)。動(dòng)態(tài)窗口法在障礙物隨機(jī)分布的復(fù)雜環(huán)境下遇到障礙物時(shí),能夠及時(shí)進(jìn)行局部避障。該方法既可以規(guī)劃出全局最優(yōu)路徑,又能夠隨時(shí)避障。

1 環(huán)境建模

環(huán)境地圖的創(chuàng)建選擇使用柵格法,將空間地圖劃分成相等的二進(jìn)制參數(shù)單元格,每個(gè)單元格的位置可以用二維坐標(biāo)及序號(hào)表示出來[17]。移動(dòng)機(jī)器人在柵格圖中被視為移動(dòng)粒子,該粒子運(yùn)動(dòng)軌跡被視作規(guī)劃路徑。由于柵格的大小會(huì)影響算法的搜索速度及結(jié)果的準(zhǔn)確度,故建立的柵格大小為46節(jié)點(diǎn)×46節(jié)點(diǎn)。地圖上共2116個(gè)節(jié)點(diǎn),并做出了以下假設(shè):

1)環(huán)境中的靜態(tài)障礙物是初始化地圖隨機(jī)生成的,動(dòng)態(tài)障礙物是根據(jù)測(cè)試情況隨機(jī)添加的。假設(shè)靜態(tài)障礙物與動(dòng)態(tài)障礙物是同時(shí)存在的,沒有障礙的柵格用白色表示,有障礙的柵格用黑色表示。

2)為了避免障礙物與移動(dòng)機(jī)器人發(fā)生碰撞,將靜態(tài)障礙物與動(dòng)態(tài)障礙物全部進(jìn)行膨化處理,膨化程度大小為移動(dòng)機(jī)器人半徑的大小,忽略障礙物的高度信息。

3)隨機(jī)添加動(dòng)態(tài)障礙物選擇的坐標(biāo)與對(duì)應(yīng)柵格的坐標(biāo)存在偏差,按照就近原則,在一定范圍內(nèi)返回柵格所在整數(shù)坐標(biāo)位置,并進(jìn)行填充標(biāo)記。

4)移動(dòng)機(jī)器人步長(zhǎng)為兩個(gè)柵格中心點(diǎn)之間的距離,每一步都占滿整個(gè)柵格,忽略機(jī)器人的高度信息。

2 A_Star算法的改進(jìn)

2.1 A_Star算法原理

A_Star算法是由Hart等在文獻(xiàn)[18]中提出的一種智能啟發(fā)式算法,通過廣度優(yōu)先搜索的Dijkstra與最佳優(yōu)先搜索的BFS優(yōu)點(diǎn)的結(jié)合,組成一種設(shè)計(jì)最短路徑的算法。在廣度搜索算法基礎(chǔ)上加入估價(jià)函數(shù),對(duì)結(jié)點(diǎn)的每一個(gè)方向進(jìn)行評(píng)估,從中選擇消耗代價(jià)最低、最容易到達(dá)的路徑,解決了廣度搜索算法每一個(gè)節(jié)點(diǎn)都要走一遍的缺點(diǎn),極大地提高了搜索效率。

在A_Star算法中,每一個(gè)結(jié)點(diǎn)位置的選擇都取決于其估價(jià)函數(shù)f(n),如式(1)所示:

f(n)=g(n)+h(n);h(n)≤h*(n)

(1)

其中,n表示當(dāng)前所在的節(jié)點(diǎn)數(shù),f(n)代表機(jī)器人從起始點(diǎn)經(jīng)過相應(yīng)節(jié)點(diǎn)到達(dá)目標(biāo)點(diǎn)的估計(jì)總代價(jià),g(n)代表機(jī)器人從起始點(diǎn)到達(dá)當(dāng)前節(jié)點(diǎn)所花費(fèi)的實(shí)際代價(jià)值,h(n)代表機(jī)器人從當(dāng)前節(jié)點(diǎn)到達(dá)目標(biāo)點(diǎn)的估計(jì)代價(jià),h*(n)代表機(jī)器人從當(dāng)前節(jié)點(diǎn)到達(dá)目標(biāo)點(diǎn)的實(shí)際最小代價(jià)。

h(n)也叫做啟發(fā)函數(shù),啟發(fā)函數(shù)h(n)的選取與優(yōu)化直接影響著節(jié)點(diǎn)的搜索與擴(kuò)展,進(jìn)而影響算法的速度及精度。要提高算法的精度與速度,就需要對(duì)啟發(fā)函數(shù)h(n)進(jìn)行優(yōu)化。

A_Star算法的評(píng)價(jià)函數(shù)是由Dijkstra與BFS兩種算法結(jié)合而成,當(dāng)g(n)的權(quán)重為1、h(n)為0時(shí),為Dijkstra算法,通過遍歷所有節(jié)點(diǎn)到起始點(diǎn)的距離,找出并記錄距離最短的節(jié)點(diǎn),進(jìn)而找出最短路徑。但遍歷的節(jié)點(diǎn)過多,導(dǎo)致算法運(yùn)算速度緩慢。當(dāng)g(n)的權(quán)重為0、h(n)為1時(shí),為BFS算法,通過計(jì)算當(dāng)前點(diǎn)節(jié)點(diǎn)到目標(biāo)點(diǎn)的代價(jià),按照代價(jià)最小原則向外擴(kuò)展鄰近節(jié)點(diǎn),直到找到目標(biāo)點(diǎn)。雖然此算法運(yùn)算速度較快,但很容易找不到目標(biāo)點(diǎn),因此分配合適的g(n)與h(n)比例權(quán)重,能夠使規(guī)劃的路徑更平滑、更短。

A_Star算法的啟發(fā)函數(shù)常用歐幾里得距離、切比雪夫距離、曼哈頓距離。究選取歐幾里得距離為啟發(fā)函數(shù)代價(jià)的計(jì)算標(biāo)準(zhǔn)。3種距離的計(jì)算如圖1所示。

圖1 3種距離示意圖

2.2 改進(jìn)A_Star算法

2.2.1 優(yōu)化A_Star算法的評(píng)價(jià)函數(shù)

A_Star算法的評(píng)價(jià)函數(shù)主要由g(n)與啟發(fā)函數(shù)h(n)組成,其中起主導(dǎo)作用的是啟發(fā)函數(shù)h(n)。當(dāng)h(n)h*(n)時(shí),搜索的空間變小,搜索節(jié)點(diǎn)減少,計(jì)算量減少,效率變高,但搜索的路徑很難是最優(yōu)解;當(dāng)h(n)=h*(n)時(shí),算法運(yùn)行效率是最高的。當(dāng)前節(jié)點(diǎn)與目標(biāo)點(diǎn)距離太遠(yuǎn)、h(n)?h*(n)時(shí),算法的運(yùn)算效率很低,為了提高運(yùn)算效率,應(yīng)提高權(quán)重;反之,隨著當(dāng)前節(jié)點(diǎn)與目標(biāo)點(diǎn)越來越近,h(n)≈h*(n)時(shí),為了防止找不到最優(yōu)規(guī)劃路徑,由于始終h(n)≤h*(n),故當(dāng)障礙物較少時(shí),應(yīng)適當(dāng)降低啟發(fā)函數(shù)h(n)的權(quán)重。綜上所述,將A_Star算法的評(píng)價(jià)函數(shù)改進(jìn)為如式(2)所示:

(2)

其中,r為機(jī)器人當(dāng)前位置到目標(biāo)點(diǎn)的距離,R為起始點(diǎn)到目標(biāo)點(diǎn)的距離。

2.2.2 選取最佳關(guān)鍵點(diǎn)

傳統(tǒng)的A_Star算法路徑規(guī)劃是由每個(gè)柵格的中心點(diǎn)連接而成的。當(dāng)障礙物增多時(shí),會(huì)導(dǎo)致路徑的彎折次數(shù)增多,使路徑不平滑。針對(duì)這一缺點(diǎn),基于Floyd算法思想[19]對(duì)路徑的彎折問題做出以下優(yōu)化。

遍歷所有節(jié)點(diǎn),刪除每一段路徑中間存在的多余節(jié)點(diǎn),保留起始點(diǎn)與拐點(diǎn)。

遍歷起始點(diǎn)及拐點(diǎn),從起始點(diǎn)開始將每一個(gè)節(jié)點(diǎn)與后面的節(jié)點(diǎn)相互連接作為可供選擇的路徑,判斷每條路徑與障礙物的距離,如果小于安全距離,則舍棄該路徑,如果大于安全距離,則保留該路徑。

提取連接剩余的節(jié)點(diǎn),作為最優(yōu)路徑輸出。

傳統(tǒng)的A_Star算法規(guī)劃路徑是以斜線的形式靠近并通過障礙物頂點(diǎn)的,這種情況在真實(shí)環(huán)境下很容易發(fā)生障礙物與機(jī)器人的碰撞事件。經(jīng)過選取最佳關(guān)鍵點(diǎn)改進(jìn)后,規(guī)劃出的路徑與障礙物保證了一定的安全距離,極大保證了移動(dòng)機(jī)器人在真實(shí)環(huán)境中的安全。

2.2.3 平滑曲線路徑

傳統(tǒng)的A_Star算法規(guī)劃路徑是以折線形式連接而成的,機(jī)器人在每次轉(zhuǎn)彎處都會(huì)出現(xiàn)停頓、再轉(zhuǎn)向、再繼續(xù)前進(jìn)的現(xiàn)象。為了使機(jī)器人在每次轉(zhuǎn)彎處能平滑運(yùn)行,在拐彎處以畫弧線的方式代替折線進(jìn)行拐彎,這樣轉(zhuǎn)彎時(shí)機(jī)器人的運(yùn)動(dòng)就會(huì)相對(duì)平滑、連貫。圖2是優(yōu)化前后機(jī)器人通過障礙物頂點(diǎn)的對(duì)比圖。

圖2 優(yōu)化前后對(duì)比

2.2.4 優(yōu)化搜索方向選取策略

傳統(tǒng)A_Star算法當(dāng)前節(jié)點(diǎn)到達(dá)鄰近節(jié)點(diǎn)的搜索方向?yàn)?個(gè),如圖3表示。D代表當(dāng)前點(diǎn)的位置,D1～D8代表當(dāng)前節(jié)點(diǎn)可移動(dòng)的8個(gè)方向。

圖3 節(jié)點(diǎn)移動(dòng)方向

由于8個(gè)搜索方向會(huì)增加算法的運(yùn)算時(shí)間,故將搜索方向根據(jù)當(dāng)前節(jié)點(diǎn)與目標(biāo)點(diǎn)的相對(duì)方向優(yōu)化為5個(gè)[20],以減少運(yùn)算,提升算法運(yùn)行速度及效率。不足之處是當(dāng)5個(gè)搜索方向都存在障礙物時(shí),搜索會(huì)陷入死區(qū),無法繼續(xù)實(shí)現(xiàn)路徑規(guī)劃。

將當(dāng)前節(jié)點(diǎn)與目標(biāo)點(diǎn)的連線與D1的夾角設(shè)為α,夾角α與保留的5個(gè)方向及舍棄的3個(gè)方向之間的對(duì)應(yīng)關(guān)系如表1所示。

表1 夾角α與保留的5個(gè)方向的對(duì)應(yīng)

3 DWA算法的原理與優(yōu)化

動(dòng)態(tài)窗口法工作原理是對(duì)機(jī)器人運(yùn)動(dòng)過程中的線速度及角速度進(jìn)行采樣分析,通過速度的數(shù)值計(jì)算出機(jī)器人下一步的運(yùn)動(dòng)軌跡,使用評(píng)價(jià)函數(shù)對(duì)獲得的每條軌跡進(jìn)行打分評(píng)價(jià),從中選出最安全、最平滑的局部最優(yōu)行駛路線。此時(shí)機(jī)器人的線速度及角速度為最佳行駛速度。

3.1 動(dòng)力學(xué)模型

假設(shè)v(t)與w(t)分別表示Turtlebot2 在世界坐標(biāo)系下t時(shí)刻的線速度及角速度,在采樣周期ht內(nèi),位移較小,可看做做勻速直線運(yùn)動(dòng)[18],則運(yùn)動(dòng)學(xué)模型的數(shù)學(xué)表達(dá)式

如式(3)表示:

(3)

式中,x(t),y(t),θ(t)分別代表時(shí)刻機(jī)器人在世界坐標(biāo)系下的位置姿態(tài)。

3.2 速度采樣

動(dòng)態(tài)窗口法將避障問題描述為速度空間內(nèi)帶約束的優(yōu)化問題,根據(jù)環(huán)境的變換對(duì)速度采樣的范圍進(jìn)行相應(yīng)的約束,主要約束機(jī)器人的速度、電機(jī)加速度及與障礙物的安全距離。

速度約束。移動(dòng)機(jī)器人的速度可以分為線速度與角速度,對(duì)速度的約束相當(dāng)于把線速度與角速度控制在合理的區(qū)間內(nèi),將其設(shè)置為線速度與角速度的集合,DWA算法搜索求解的范圍如式(4)所示:

(4)

其中,vmin與vmax分別為移動(dòng)機(jī)器人的最小線速度與最大線速度,wmin與wmax分別為移動(dòng)機(jī)器人的最小角速度與最大角速度。

電機(jī)加減速度約束。在對(duì)機(jī)器人速度進(jìn)行采樣時(shí),要充分考慮電機(jī)的性能問題,采樣速度單位時(shí)間內(nèi)的變化量應(yīng)保持在電機(jī)最大加減速度規(guī)定范圍內(nèi),其約束條件如式(5)所示:

(5)

其中,admax與aimax為機(jī)器人線速度的最大減速度與最大加速度,αdmax與αimax為機(jī)器人角速度的最大減速度與最大加速度。vc與wc為當(dāng)前機(jī)器人的線速度與角速度[19]。

對(duì)安全距離的約束。為了防止機(jī)器人與障礙物發(fā)生碰撞,機(jī)器人在距離障礙物一定距離時(shí),要滿足機(jī)器人的線速度與角速度都降為零,其約束條件如式(6)所示:

(6)

其中,admax,αdmax分別為移動(dòng)機(jī)器人的最大減速度與最大加速度,代表預(yù)測(cè)軌跡末端距離障礙物的距離[11]。

動(dòng)態(tài)窗口算法的速度約束為上述3種速度約束的交集,動(dòng)態(tài)窗口速度可以表示為VW=Vt∩Vs∩Vd。

3.3 評(píng)價(jià)函數(shù)優(yōu)化與改進(jìn)

傳統(tǒng)的DWA評(píng)價(jià)函數(shù)主要由指向終點(diǎn)的方位角、機(jī)器人速度大小、模擬軌跡末端與障礙物的距離3個(gè)指標(biāo)組成。但存在以下不足:由于目標(biāo)點(diǎn)只有一個(gè),中間缺少指引的臨時(shí)目標(biāo)點(diǎn),在大面積環(huán)境中容易陷入局部最優(yōu)路徑。將DWA算法與改進(jìn)后的A_Star算法相結(jié)合,可以提供中間缺少的引導(dǎo)點(diǎn),極大程度地改善此問題。其未將障礙物進(jìn)行區(qū)分,導(dǎo)致動(dòng)態(tài)避障過程中靈敏度降低[19]。針對(duì)此不足,對(duì)傳統(tǒng)的DWA評(píng)價(jià)函數(shù)進(jìn)行優(yōu)化,增加了機(jī)器人在動(dòng)態(tài)避障過程中的靈敏度,得出改進(jìn)后的評(píng)價(jià)函數(shù)如式(7)所示:

G(v,w)=αheading(v,w)+βvel(v,w)

+σpath(v,w)+δdist_1(v,w)+μdist_2(v,w)

(7)

其中,α,β,σ,δ,μ分別為各個(gè)子函數(shù)的加權(quán)系數(shù)。heading(v,w)為模擬軌跡終點(diǎn)不斷朝向目標(biāo)點(diǎn)的方向角偏差;vel(v,w)用來評(píng)價(jià)當(dāng)前機(jī)器人運(yùn)動(dòng)速度的大小;path(v,w)用來評(píng)價(jià)模擬軌跡終點(diǎn)與全局規(guī)劃路徑的距離,使其在局部避障后,能快速回歸全局規(guī)劃路徑;dist_1(v,w)用來評(píng)價(jià)模擬軌跡終點(diǎn)到靜態(tài)障礙物的最近距離,控制障礙物對(duì)局部障礙的干擾;dist_2(v,w)用來評(píng)價(jià)模擬軌跡終點(diǎn)到動(dòng)態(tài)障礙物的最近距離,通過增加對(duì)障礙物的識(shí)別能力,提高避障的靈敏度,體現(xiàn)了機(jī)器人的避障能力,只有距離大于機(jī)器人的半徑,模擬軌跡才能通過該評(píng)價(jià)條件。

4 融合算法

將改進(jìn)后的A_Star算法與改進(jìn)后的DWA算法進(jìn)行融合,主要目的是針對(duì)兩者算法的優(yōu)勢(shì)與不足,達(dá)到優(yōu)勢(shì)互補(bǔ)的效果。

改進(jìn)后的A_Star算法雖然在已知障礙物靜態(tài)環(huán)境下能得到全局規(guī)劃的最優(yōu)解,但在未知障礙物的環(huán)境中無法避障,僅能達(dá)到局部的路徑規(guī)劃。DWA算法由于只有一個(gè)目標(biāo)點(diǎn)指引,全程缺少局部方向的指引,當(dāng)障礙物較多時(shí)很容易陷入局部最優(yōu),導(dǎo)致無法進(jìn)行全局的路徑規(guī)劃。

通過兩種算法的融合,改進(jìn)后的A_Star算法能夠提取全局規(guī)劃路徑上的關(guān)鍵點(diǎn)為DWA算法作為中間的指引點(diǎn),在動(dòng)態(tài)環(huán)境下為DWA算法提供方向,避免陷入局部最優(yōu)的狀況。優(yōu)化后的DWA算法也能夠?qū)?dòng)態(tài)障礙物與靜態(tài)障礙物進(jìn)行區(qū)分,消除一些已知障礙物對(duì)路徑的干擾,進(jìn)一步提高算法運(yùn)算速度。融合算法能夠結(jié)合兩種算法的優(yōu)點(diǎn),既具有避障功能,又能規(guī)劃出最短路徑。融合算法的流程如圖4所示。

圖4 融合算法流程

5 仿真實(shí)驗(yàn)

5.1 改進(jìn)后的A_Star算法仿真實(shí)驗(yàn)

仿真實(shí)驗(yàn)在MATLAB 2016b環(huán)境下進(jìn)行驗(yàn)證,為了驗(yàn)證算法的適應(yīng)性及有效性,隨機(jī)建立了柵格地圖,每個(gè)柵格設(shè)置為面積相等的小正方形,白色柵格代表無障礙區(qū),黑色柵格代表有障礙區(qū)。“△”代表機(jī)器人的起始點(diǎn),“○”代表目標(biāo)點(diǎn)。將改進(jìn)的A_Star算法、Dijkstra算法、BFS算法進(jìn)行對(duì)比仿真實(shí)驗(yàn),如圖5所示。

圖5 4種算法仿真實(shí)驗(yàn)對(duì)比圖

5.2 仿真實(shí)驗(yàn)結(jié)果分析

從仿真圖上來看,Dijkstra算法的拐點(diǎn)是最多的、最不平滑的路徑,改進(jìn)的A-Star算法的拐點(diǎn)是最少的,路徑是最平滑的。當(dāng)機(jī)器人從一個(gè)節(jié)點(diǎn)移動(dòng)到另一個(gè)節(jié)點(diǎn)的過程中,需要進(jìn)行原位置轉(zhuǎn)向,轉(zhuǎn)向下一節(jié)點(diǎn)方向后再繼續(xù)前行,故路徑過于曲折或過長(zhǎng)都會(huì)造成機(jī)器人能量與時(shí)間消耗。由此可以看出,改進(jìn)的A_Star算法在能量消耗與時(shí)間花費(fèi)上都優(yōu)于其余3種路徑規(guī)劃算法,便于機(jī)器人在實(shí)際情況下更好地進(jìn)行路徑規(guī)劃,到達(dá)目標(biāo)點(diǎn)。

從表2可知,4種不同的路徑規(guī)劃算法最終都能規(guī)劃出路徑,但從各項(xiàng)數(shù)據(jù)來看還是存在差異的。從計(jì)算時(shí)間與遍歷節(jié)點(diǎn)數(shù)來看,BFS算法計(jì)算時(shí)間是最短的,但規(guī)劃路徑是最長(zhǎng)的;Dijkstra算法計(jì)算時(shí)間是最長(zhǎng)的,但規(guī)劃路徑是最優(yōu)的;改進(jìn)的A_Star算法相比于傳統(tǒng)的A_Star,計(jì)算時(shí)間上平均提高了70%,但路徑長(zhǎng)度也略微增加了2.4%。改進(jìn)的A_Star算法性能大幅度優(yōu)于其他3類算法。

表2 4種路徑規(guī)劃算法性能比較

5.3 融合算法的仿真實(shí)驗(yàn)與分析

為了驗(yàn)證融合算法的有效性,在仿真軟件中建立了46 m×46 m、柵格間距為1 m的模擬真實(shí)場(chǎng)景的柵格地圖,進(jìn)行了1組仿真實(shí)驗(yàn),環(huán)境中的靜態(tài)障礙物覆蓋率為30%,隨機(jī)添加了5組動(dòng)態(tài)障礙物分布在全局規(guī)劃軌跡附近,目的是最大程度地增加避障難度。實(shí)驗(yàn)中,起點(diǎn)坐標(biāo)為(42 m,45 m),目標(biāo)點(diǎn)坐標(biāo)為(11 m,2 m)。實(shí)驗(yàn)參數(shù)設(shè)置如下:最大角速度為15.0 °/s,最大線速度為0.8 m/s,最大角加速度為45.0°/s,最大線加速度為0.25 m/s2。評(píng)價(jià)函數(shù)各項(xiàng)參數(shù)如下:α=0.1,β=0.2,σ=0.1,σ=0.05,μ=0.05。融合算法仿真實(shí)現(xiàn)過程如圖6所示。

圖6 融合算法仿真實(shí)現(xiàn)過程

從圖6可以看出,圖6(a)中的虛線為改進(jìn)后A_Star算法在未添加動(dòng)態(tài)障礙物前所規(guī)劃的全局路徑。圖6(b)中方塊用來表示全局路徑中隨機(jī)添加的未知障礙物點(diǎn)。圖6(c)融合算法路徑規(guī)劃曲線末端的短曲線代表模擬軌跡,路徑上的“*”代表提取關(guān)鍵點(diǎn),作為融合算法的中間引導(dǎo)點(diǎn)。圖6(d)代表DWA算法正在繞過了隨機(jī)添加的動(dòng)態(tài)障礙物,與虛線不吻合的弧線部分代表DWA算法繞過障礙物與全局路徑之間的偏差。圖6(d)曲線代表機(jī)器人在保證規(guī)劃路徑長(zhǎng)度最優(yōu)的基礎(chǔ)上使用DWA算法在完美躲避所有障礙物的情況下完成了從起始點(diǎn)到目標(biāo)點(diǎn)的路徑規(guī)劃。

從最終結(jié)果分析,全局靜態(tài)規(guī)劃路徑的長(zhǎng)度為55.87 m,局部動(dòng)態(tài)規(guī)劃的路徑長(zhǎng)度為57.32 m,僅僅增加了2.6%。由此可以得出,融合算法既具有避障功能又具有全局最優(yōu)路徑的規(guī)劃功能,充分地將改進(jìn)后的A_Star算法與DWA算法的優(yōu)勢(shì)相融合。

6 結(jié)論

隨著機(jī)器人領(lǐng)域的蓬勃興起,路徑規(guī)劃的應(yīng)用場(chǎng)景越來越廣闊,路徑規(guī)劃功能需求也越來越多。傳統(tǒng)的A_Star算法存在效率低、路徑規(guī)劃不平滑、只能適應(yīng)于已知障礙的環(huán)境等問題。為了滿足實(shí)際需求,改進(jìn)了傳統(tǒng)的A_Star算法,利用優(yōu)先搜索策略將搜索方向從8減少到5,以提高算法的搜索效率。設(shè)計(jì)了一種路徑平滑優(yōu)化算法,刪除多余節(jié)點(diǎn)與拐點(diǎn),提高路徑的平滑度,并對(duì)自適應(yīng)函數(shù)進(jìn)行優(yōu)化,使其隨著環(huán)境的復(fù)雜度變化進(jìn)行自適應(yīng)調(diào)整,提高了算法的效率及靈活性,加快了收斂速度。通過與Dijkstra算法、DFS算法、傳統(tǒng)A_Star算法的對(duì)比實(shí)驗(yàn)可知,改進(jìn)后的A_Star算法提高了70%的運(yùn)算效率。

通過提取改進(jìn)后的A_Star算法關(guān)鍵點(diǎn)作為DWA算法中間目標(biāo)點(diǎn)的方式,在全局規(guī)劃路徑最優(yōu)的基礎(chǔ)上實(shí)現(xiàn)融合算法。實(shí)驗(yàn)結(jié)果表明,融合算法規(guī)劃的全局路徑不僅實(shí)現(xiàn)了與全局最優(yōu)路徑基本吻合的效果,還能夠躲避環(huán)境中出現(xiàn)的動(dòng)態(tài)障礙物,進(jìn)一步提高了路徑規(guī)劃算法的功能,可應(yīng)用于更多復(fù)雜的環(huán)境。