基于自適應(yīng)A*算法的自動(dòng)駕駛車(chē)輛路徑規(guī)劃方法研究

張 涌,成海飛,趙奉奎

(南京林業(yè)大學(xué) 汽車(chē)與交通工程學(xué)院,江蘇 南京 210037)

0 引 言

路徑規(guī)劃是自動(dòng)駕駛車(chē)輛自主完成導(dǎo)航任務(wù)的重要環(huán)節(jié)和關(guān)鍵技術(shù)之一,也是實(shí)現(xiàn)完全自動(dòng)駕駛的核心難題[1]。它的目的主要是根據(jù)已知或者未知障礙物的地圖環(huán)境與所需的約束條件,尋找到一條從起點(diǎn)到終點(diǎn)的最優(yōu)或次優(yōu)的安全路徑。在自動(dòng)駕駛車(chē)輛路徑規(guī)劃領(lǐng)域,眾多學(xué)者對(duì)算法的開(kāi)發(fā)與探索展開(kāi)了大量研究,主要包括基于采樣的快速搜索隨機(jī)樹(shù)方法[2]、Voronoi圖方法等,基于節(jié)點(diǎn)的Dijkstra算法、A*算法,基于模型的人工勢(shì)場(chǎng)法[3]、動(dòng)態(tài)窗口法等,以及基于生物啟發(fā)式的神經(jīng)網(wǎng)絡(luò)算法、遺傳算法[4]等。

A*算法作為一種啟發(fā)式搜索算法,節(jié)點(diǎn)的拓展具備一定的方向性,且計(jì)算量小,被廣泛應(yīng)用于全局路徑規(guī)劃算法,但傳統(tǒng)的A*算法存在搜索效率低、拐點(diǎn)數(shù)量較多和轉(zhuǎn)折角度較大等問(wèn)題[5-7]。針對(duì)傳統(tǒng)A*算法的這些問(wèn)題,許多學(xué)者針對(duì)性地進(jìn)行了相關(guān)研究。姜媛媛等[6]利用垂距限值法快速刪除搜索路徑中存在的冗余節(jié)點(diǎn),并通過(guò)B樣條曲線平滑擬合出一條光滑的曲線,仿真實(shí)驗(yàn)表明該改進(jìn)算法縮短了運(yùn)算時(shí)間和減少了路徑長(zhǎng)度;吳鵬等[7]采用目標(biāo)正反向搜索交替機(jī)制使兩路徑的最終節(jié)點(diǎn)在起點(diǎn)和終點(diǎn)連線的中點(diǎn)鄰域相遇,提高了搜索效率;王維等[8]通過(guò)考慮當(dāng)前節(jié)點(diǎn)與其父節(jié)點(diǎn)的估計(jì)代價(jià)并采用指數(shù)衰減的方式對(duì)估價(jià)函數(shù)進(jìn)行加權(quán)、五次多項(xiàng)式平滑處理的方法使規(guī)劃路徑可以在復(fù)雜環(huán)境下可以可靠地到達(dá)目標(biāo);孔慧芳等[9]采用加權(quán)曼哈頓距離與轉(zhuǎn)彎修正代價(jià)作為新的啟發(fā)函數(shù),改進(jìn)的算法可以有效減少AGV路徑規(guī)劃時(shí)的節(jié)點(diǎn)遍歷數(shù)與轉(zhuǎn)彎次數(shù);張建光等[10]在四節(jié)點(diǎn)擴(kuò)展方式的基礎(chǔ)優(yōu)先考慮目標(biāo)點(diǎn)方位的相鄰節(jié)點(diǎn),并在估價(jià)函數(shù)中添加略大于1的權(quán)重因子與拐點(diǎn)處轉(zhuǎn)彎代價(jià),使生成的路徑能有效的減少搜索節(jié)點(diǎn)數(shù)目以及搜尋路徑的轉(zhuǎn)彎次數(shù);孟珠李等[11]將傳統(tǒng)A*算法得到的路徑作為控制點(diǎn),并利用3次B樣條插值使路徑尖峰處得到優(yōu)化,并生成一條平滑的曲線,使得農(nóng)用機(jī)器人運(yùn)行更加順暢;田海波等[12]通過(guò)在估價(jià)函數(shù)中考慮轉(zhuǎn)彎成本、預(yù)判斷規(guī)劃策略、冗余拐點(diǎn)剔除策略3個(gè)方面對(duì)傳統(tǒng)A*算法進(jìn)行優(yōu)化處理,使生成的路徑長(zhǎng)度縮短,拐點(diǎn)數(shù)量減少,轉(zhuǎn)折角變小。上述研究通過(guò)節(jié)點(diǎn)擴(kuò)展、平滑處理等方法優(yōu)化了路徑,但是并沒(méi)有綜合考慮得到的路徑是否符合自動(dòng)駕駛車(chē)輛的實(shí)際運(yùn)動(dòng)約束。

為了解決上述問(wèn)題,針對(duì)A*算法計(jì)算時(shí)間較長(zhǎng)的問(wèn)題,筆者采用指數(shù)增長(zhǎng)法對(duì)啟發(fā)式函數(shù)進(jìn)行加權(quán),從而提高搜索效率?？紤]自動(dòng)駕駛車(chē)輛在實(shí)際運(yùn)行過(guò)程中自身轉(zhuǎn)向特性的限制,得到長(zhǎng)度更短、轉(zhuǎn)折角度更小的路徑。此外,采用三次B樣條曲線對(duì)生成路徑的拐點(diǎn)處進(jìn)行平滑處理,使路徑具有連續(xù)的曲率,有利于自動(dòng)駕駛車(chē)輛的控制。仿真結(jié)果表明：與傳統(tǒng)A*算法相比,改進(jìn)的A*算法生成的路徑長(zhǎng)度明顯縮短,總航向角更小,路徑更加平滑。

1 算法描述

1.1 環(huán)境建模描述

自動(dòng)駕駛車(chē)輛進(jìn)行路徑規(guī)劃前,須根據(jù)傳感器感知的環(huán)境信息進(jìn)行地圖模型搭建。目前,使用最多的地圖種類(lèi)有3種：可視地圖、柵格地圖、拓?fù)涞貓D。其中,柵格地圖由于自身模型易構(gòu)建以及位置表示的唯一性等優(yōu)點(diǎn),在路徑規(guī)劃時(shí)被廣泛采用,因此筆者將采用柵格法來(lái)構(gòu)建地圖。

在柵格地圖上構(gòu)建障礙物時(shí),為保證環(huán)境信息的真實(shí)性,通常將障礙物的原始形狀作為首要選擇,此方法會(huì)導(dǎo)致障礙物的邊緣失真,從而影響路線的可追溯性和安全性?，F(xiàn)有的研究大多采用矩形封閉障礙物的原始形狀的方法來(lái)避免邊緣局部失真[14]。同樣應(yīng)用文獻(xiàn)[13]所提及的障礙物處理辦法,地圖環(huán)境中的障礙物形狀統(tǒng)一用矩形表征,圖1為利用矩形代替圓形和不規(guī)則五邊形的實(shí)際外形。由圖1可以看出,此時(shí)原障礙物的安全性問(wèn)題轉(zhuǎn)化為矩形障礙物的安全性問(wèn)題。

圖1 障礙物代替示意Fig.1 Schematic diagram of obstacle replacement

靜態(tài)全局環(huán)境下,柵格地圖實(shí)例如圖2,左下角柵格為起點(diǎn),右上角柵格為終點(diǎn),空白柵格表示自動(dòng)駕駛車(chē)輛可以通過(guò)(可通行區(qū)域);黑色柵格表示不可通行的障礙物(不可通行區(qū)域)。

圖2 柵格地圖實(shí)例Fig.2 Grid map example

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

A*算法是一種經(jīng)典啟發(fā)式搜索算法,在Dijkstra算法和BFS算法基礎(chǔ)上,結(jié)合二者的優(yōu)點(diǎn),通過(guò)啟發(fā)式搜索,利用代價(jià)函數(shù)作為尋路依據(jù),避免了搜索過(guò)程中方向的盲目性,從而獲取最優(yōu)路徑。A*算法的基本思想是將起始點(diǎn)S作為第1個(gè)父節(jié)點(diǎn)添加至Open list列表中,利用代價(jià)函數(shù)估值從父節(jié)點(diǎn)到周?chē)?jié)點(diǎn)n的價(jià)值,選擇最小的節(jié)點(diǎn)作為下一個(gè)父節(jié)點(diǎn),直至搜索到目標(biāo)節(jié)點(diǎn)G并且將目標(biāo)節(jié)點(diǎn)G添加至Close list列表為止。啟發(fā)函數(shù)由兩部分組成,如式(1)：

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

(1)

式中：f(n)為起始節(jié)點(diǎn)S到目標(biāo)節(jié)點(diǎn)G的路徑總代價(jià);g(n)為從起始點(diǎn)S到當(dāng)前點(diǎn)n的實(shí)際代價(jià);h(n)為當(dāng)前節(jié)點(diǎn)n到目標(biāo)節(jié)點(diǎn)G的預(yù)估距高。

一般地,計(jì)算h(n)的典型距離計(jì)算公式有曼哈頓距離、歐幾里得距離、切比雪夫距離,對(duì)應(yīng)表達(dá)式分別如式(2)～式(4)：

h(n)=|xn-xm|+|yn-ym|

(2)

(3)

h(n)=max(|xn-xm|,|yn-ym|)

(4)

對(duì)比3種距離運(yùn)算公式且基于行走規(guī)則,式(2)的曼哈頓距離運(yùn)算簡(jiǎn)單,搜索效率高,但其運(yùn)動(dòng)方向只允許朝上下左右4個(gè)方向移動(dòng)導(dǎo)致生成的路徑質(zhì)量偏低;式(3)的歐幾里得距離易求得最短路徑,且可使自動(dòng)駕駛車(chē)輛朝任何方向移動(dòng),但計(jì)算時(shí)必須先平方和后開(kāi)根,造成搜索效率低;式(4)的切比雪夫距離在進(jìn)行估值運(yùn)算時(shí)與最優(yōu)路徑的估值誤差不大,但在斜向搜索時(shí)會(huì)低估距離(沒(méi)有考慮斜向路徑的實(shí)際長(zhǎng)度且路徑規(guī)劃過(guò)程中允許朝8個(gè)方向移動(dòng),以車(chē)輛所處位置為中心單元,在3×3鄰域里,八方向指的是前、后、左、右、左前、左后、右前、右后)。自動(dòng)駕駛車(chē)輛完成駕駛?cè)蝿?wù)過(guò)程時(shí),運(yùn)動(dòng)方向是任意的且使用歐幾里得距離更逼近實(shí)際駕駛過(guò)程,所以筆者使用歐幾里得距離公式計(jì)算h(n)的值。

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

傳統(tǒng)A*算法及文獻(xiàn)[11]的改進(jìn)A*算法在任意地圖中自適應(yīng)性較差,在路徑規(guī)劃時(shí)存在遍歷節(jié)點(diǎn)數(shù)多、總轉(zhuǎn)折角度大、規(guī)劃路徑不夠平滑、尋路時(shí)間較長(zhǎng)等問(wèn)題。綜合文獻(xiàn)[11]所提改進(jìn)思路,在設(shè)計(jì)思路時(shí)需要避免出現(xiàn)因提高某一方面性能指標(biāo)導(dǎo)致其他性能降低的情況。通過(guò)設(shè)計(jì)自適應(yīng)調(diào)整權(quán)重因子、轉(zhuǎn)彎成本函數(shù)(航向角影響因子)、路徑平滑處理方式來(lái)改進(jìn)A*算法,保證最終規(guī)劃出的路徑相對(duì)最優(yōu),提高算法的魯棒性和搜索效率,減少拐點(diǎn)數(shù)和總航向角。

2.1 啟發(fā)函數(shù)自適應(yīng)權(quán)重因子

A*算法的預(yù)估代價(jià)函數(shù)是影響算法效率的重要因素,h(n)的值越接近實(shí)際值,搜索的效率就越高。若h(n)=0時(shí),A*算法退化為Dijkstra算法,此時(shí)算法可以在全局范圍內(nèi)搜索到一條最短的路徑,但是需要遍歷所有節(jié)點(diǎn),搜索效率以及時(shí)間成本會(huì)大大增加。若h(n)>>g(n)時(shí),啟發(fā)函數(shù)中g(shù)(n)的作用可忽略不計(jì),此刻A*算法會(huì)演變成為 BFS算法,該算法嚴(yán)格遵守最短距離擴(kuò)展節(jié)點(diǎn),但這僅僅保證了相對(duì)最優(yōu)的路徑,而不是最優(yōu)選擇。綜上,筆者在啟發(fā)函數(shù)的預(yù)估代價(jià)部分引入自適應(yīng)權(quán)重因子w,則原算法公式中的h(n)就變成了w×h(n),由此式(1)可表示為：

f(n)=g(n)+w×h(n)

(5)

(6)

w的引入可以為h(n)帶來(lái)更大的權(quán)重。自適應(yīng)權(quán)重因子w的值取決于從起始節(jié)點(diǎn)S到當(dāng)前節(jié)點(diǎn)n的實(shí)際代價(jià)與從當(dāng)前節(jié)點(diǎn)n到目標(biāo)節(jié)點(diǎn)G的預(yù)估代價(jià)的比值(呈正比例關(guān)系)。在改進(jìn)的A*算法的執(zhí)行過(guò)程中,需要收集實(shí)時(shí)的數(shù)據(jù),啟發(fā)函數(shù)中的動(dòng)態(tài)調(diào)整自適應(yīng)權(quán)重因子w的g(n)/h(n)部分會(huì)隨著路徑搜索進(jìn)程的變化而不斷更新取值,使得算法更加注重平衡搜索效率和路徑質(zhì)量。具體來(lái)說(shuō),如果當(dāng)前搜索節(jié)點(diǎn)與起點(diǎn)距離較近,那么改進(jìn)的A*算法會(huì)更加注重搜索效率,從而在搜索過(guò)程中更加注重速度;如果當(dāng)前搜索節(jié)點(diǎn)與起點(diǎn)距離較遠(yuǎn),那么改進(jìn)的A*算法會(huì)更加重視啟發(fā)式函數(shù),從而在搜索過(guò)程中更加注重路徑質(zhì)量。

同時(shí),為保證路徑搜索時(shí)間w≥1,筆者在g(n)/h(n)的基礎(chǔ)上引入以e為底的指數(shù)函數(shù)。因此在路徑搜索初期,w的值較小,可以通過(guò)增強(qiáng)算法的發(fā)散性達(dá)到擴(kuò)大路徑搜索范圍的目的;路徑搜索后期,w的值較大,可以通過(guò)增強(qiáng)算法快速收斂的性能以提高路徑搜索的效率。

2.2 考慮航向角影響因子的啟發(fā)函數(shù)

路徑規(guī)劃時(shí),由于障礙物的分布與最短路徑效應(yīng),會(huì)使規(guī)劃生成的路徑有較多轉(zhuǎn)折點(diǎn)數(shù)量且出現(xiàn)較大轉(zhuǎn)折角的情況,對(duì)應(yīng)地,自動(dòng)駕駛車(chē)輛在轉(zhuǎn)彎過(guò)程中會(huì)出現(xiàn)先減速后加速的情況,通過(guò)轉(zhuǎn)彎所花費(fèi)的時(shí)間代價(jià)相對(duì)來(lái)說(shuō)比直線行駛高,從而使得整體的效率下降,而且生成的路徑質(zhì)量無(wú)法得到保證。因此,將航向角成本也考慮進(jìn)A*算法的啟發(fā)函數(shù)信息中,使自動(dòng)駕駛車(chē)輛盡可能選擇滿足其自身轉(zhuǎn)彎特性的路徑。要控制自動(dòng)駕駛車(chē)輛的運(yùn)動(dòng),就必須建立準(zhǔn)確的車(chē)輛運(yùn)動(dòng)數(shù)學(xué)模型,此模型不僅需要真實(shí)反映車(chē)輛的某些特性,還應(yīng)該盡可能地簡(jiǎn)單易用。所以,對(duì)自動(dòng)駕駛車(chē)輛模型簡(jiǎn)化,將自動(dòng)駕駛車(chē)輛作為一個(gè)整體,只考慮航向角對(duì)全局路徑規(guī)劃的影響,因此,得到其簡(jiǎn)化模型如圖3。

圖3 某一時(shí)刻自動(dòng)駕駛車(chē)輛航跡Fig.3 The track of the autonomous vehicle at a certain moment

自動(dòng)駕駛車(chē)輛運(yùn)動(dòng)時(shí),位置由節(jié)點(diǎn)A→B→C的變化過(guò)程中,為了方便計(jì)算與更好地描述,在慣性坐標(biāo)系XOY下,對(duì)以下坐標(biāo)點(diǎn)假設(shè)：父節(jié)點(diǎn)前一節(jié)點(diǎn)A(n0,m0),子節(jié)點(diǎn)C(nn,mn),子節(jié)點(diǎn)C的父節(jié)點(diǎn)B(nn-1,mn-1),ΔL為節(jié)點(diǎn)A到節(jié)點(diǎn)C的直線距離。故自動(dòng)駕駛車(chē)輛的航向角的表達(dá)式可以寫(xiě)成如下：

(7)

α=arccosb

(8)

(9)

式中：α為自動(dòng)駕駛車(chē)輛某時(shí)刻運(yùn)動(dòng)狀態(tài)的航向角;d為α轉(zhuǎn)換為弧度制下的值?？紤]到車(chē)輛本身的最大轉(zhuǎn)向角度限制。在自適應(yīng)權(quán)重因子的A*算法啟發(fā)函數(shù)的基礎(chǔ)上添加航向角影響因子q,其中,q為自動(dòng)駕駛車(chē)輛在進(jìn)行轉(zhuǎn)向時(shí)因航向角變化而引起的代價(jià)。其運(yùn)算公式如式(10)：

q=d

(10)

綜上所述,改進(jìn)后的A*算法的啟發(fā)函數(shù)如式(11)：

f(n)=g(n)+w×h(n)+q

(11)

2.3 B樣條算法光滑處理

A*算法規(guī)劃出來(lái)的路徑是由一些有向線段組成的,雖然筆者提出的改進(jìn)方法在一定程度上優(yōu)化了轉(zhuǎn)折角過(guò)大的問(wèn)題,但是在某兩線段的轉(zhuǎn)折點(diǎn),如圖4的(9.5,15.5)處,路徑比較尖銳,此時(shí)會(huì)因?yàn)檫\(yùn)動(dòng)方向突變使自動(dòng)駕駛車(chē)輛的安全性得不到保證。因此筆者將采用B樣條算法,以產(chǎn)生出連續(xù)、平滑的路徑曲線。

圖4 考慮自適應(yīng)調(diào)整權(quán)重因子與航向角影響因子時(shí)某段生成的路徑Fig.4 The path generated by a certain segment considering the adaptive adjustment of the weight factor and the heading angle influence factor

B樣條算法的優(yōu)點(diǎn)為曲線會(huì)落在曲線階數(shù)的控制點(diǎn)所形成的凸多邊形內(nèi)。3次B樣條算法在節(jié)點(diǎn)連接處二階連續(xù),應(yīng)用于路徑規(guī)劃時(shí),可以滿足自動(dòng)駕駛車(chē)輛速度和加速度連續(xù)性的要求,因此筆者采用3次B樣條算法來(lái)平滑A*算法已規(guī)劃出路徑[14]。

k次B樣條算法的數(shù)學(xué)表達(dá)式為：

(12)

式中：Pi為控制轉(zhuǎn)折點(diǎn)i的坐標(biāo);Fi,k(t)為k次B樣條的基函數(shù),其表達(dá)式為：

(13)

(14)

由式(12)、式(13)可得3次B樣條曲線的基函數(shù)數(shù)學(xué)表達(dá)式

(15)

將式(15)代入式(12)可得：

P(t)=[(-C0+3C1-3C2+C3)t3+(3C0-6C1+3C2)t2+(-3C0+3C2)t+(C0+4C1+C2)]/6

(16)

將式(16)用矩陣形式表達(dá)為：

(17)

式中：t∈[0,1]。

3 仿真結(jié)果和分析

為驗(yàn)證改進(jìn)A*算法的有效性和靈活性,筆者在2組不同的環(huán)境下進(jìn)行了仿真試驗(yàn),仿真軟件平臺(tái)為MATLAB R2019a,硬件平臺(tái)為Intel Core i5-10200H 2.40GHz CPU,RAM 16 GB。

為保證筆者所提出算法的可靠性與優(yōu)越性,設(shè)置了20×20、30×30和50×50的3組柵格地圖進(jìn)行仿真驗(yàn)證,最小柵格大小為1 m×1 m。每組地圖分別應(yīng)用傳統(tǒng)A*算法、文獻(xiàn)[11]的改進(jìn)A*算法(BA*算法)、自適應(yīng)權(quán)重因子A*算法(WBA*算法)與最終改進(jìn)A*算法(AWBA*算法)。其中,BA*算法是一種基于A*算法的路徑規(guī)劃算法,通過(guò)引入B樣條平滑技術(shù)來(lái)提高路徑的平滑度;WBA*算法是在傳統(tǒng)A*算法的基礎(chǔ)上進(jìn)行改進(jìn)的搜索算法,它考慮了自適應(yīng)權(quán)重因子和3次B樣條平滑處理方法;AWBA*算法是在WBA*算法的基礎(chǔ)上進(jìn)一步改進(jìn)的搜索算法,它引入了航向角影響因子來(lái)更好地適應(yīng)具有方向性的問(wèn)題。構(gòu)建的柵格地圖和傳統(tǒng) A*算法路徑規(guī)劃仿真結(jié)果如圖5(a)、圖6(a)與圖7(a)。

圖5 20×20柵格地圖路徑規(guī)劃Fig.5 20×20 raster map path planning

圖6 30×30柵格地圖路徑規(guī)劃Fig.6 30×30 raster map path planning

在文獻(xiàn)[11]中,利用3次B樣條算法對(duì)傳統(tǒng)A*算法規(guī)劃出的路徑進(jìn)行了平滑處理,并設(shè)計(jì)了相關(guān)系統(tǒng)驗(yàn)證了此算法的可行性,即優(yōu)化后的光滑路徑可以使農(nóng)用機(jī)器人順暢運(yùn)行。相比于BA*算法,AWBA*算法雖然在搜索時(shí)間方面沒(méi)有較大提升,但是在路徑長(zhǎng)度與總航向角等方面的提升較大。

表1比較了3種不同地圖環(huán)境中4種算法的性能指標(biāo)。結(jié)合表1、圖5(c)圖6(c)與圖7(c)可以看出,20×20、30×30與50×50的3組柵格地圖中,WBA*算法相較于傳統(tǒng)A*算法路徑長(zhǎng)度分別減了5.48%、6.33%、9.03%,搜索時(shí)間縮短了21.43%、23.73%、7.59%,總航向角減少了1.83%、0.18%、12.57%。搜索時(shí)間的顯著減少,表明WBA*算法更高效,可以在更短的時(shí)間內(nèi)完成路徑搜索。

圖7 50×50柵格地圖路徑規(guī)劃Fig.7 50×50 raster map path planning

20×20的柵格地圖環(huán)境中,AWBA*較傳統(tǒng)A*算法相比,生成的路徑長(zhǎng)度縮短了11.14 %,總航向角減小了2.15%,搜索時(shí)間無(wú)明顯變化,但是拐點(diǎn)數(shù)量較于傳統(tǒng)A*算法略增。30×30的柵格地圖環(huán)境中,AWBA*較傳統(tǒng)A*算法規(guī)劃出的路徑長(zhǎng)度縮短了7.34 %,拐點(diǎn)數(shù)量減少了42.86%,總航向角減少了1.17%,搜索時(shí)間縮短了8.47%。50×50的柵格地圖環(huán)境中,AWBA*算法較傳統(tǒng)A*算法規(guī)劃出的路徑長(zhǎng)度縮短了18.64%,拐點(diǎn)數(shù)量減少了66.67%,總航向角減少了23.08%,搜索時(shí)間縮短了2.07%。

表1 4種算法性能指標(biāo)對(duì)比Table 1 Comparison of performance indicators of four kinds of algorithms

仿真結(jié)果表明：20×20的柵格地圖環(huán)境下,WBA*算法和AWBA*算法生成的路徑拐點(diǎn)數(shù)量相較于傳統(tǒng)A*算法略增,說(shuō)明算法在搜索過(guò)程中使用了更多的信息,需要優(yōu)化除了路徑長(zhǎng)度之外的其他目標(biāo),如航向角影響因子等,導(dǎo)致算法選擇一條拐點(diǎn)數(shù)量略增的路徑,以滿足這些優(yōu)化目標(biāo)。傳統(tǒng)A*算法預(yù)估代價(jià)函數(shù)不準(zhǔn)確可能會(huì)找到次優(yōu)解,但是WBA*算法和AWBA*算法一定程度上克服了預(yù)估代價(jià)函數(shù)的不準(zhǔn)確性,導(dǎo)致搜索得到的路徑長(zhǎng)度更短。在30×30與50×50的柵格地圖環(huán)境,WBA*算法和AWBA*算法生成的路徑拐點(diǎn)數(shù)量明顯少于傳統(tǒng)A*算法,其他指標(biāo)也均優(yōu)于傳統(tǒng)A*算法與BA*算法,說(shuō)明WBA*算法和AWBA*算法都能夠適應(yīng)復(fù)雜的地圖環(huán)境并保持其可行性和優(yōu)越性。

綜合評(píng)估,地圖環(huán)境愈加復(fù)雜,AWBA*算法雖然搜索時(shí)間并沒(méi)有太大的提升,但路徑長(zhǎng)度明顯縮短、總航向角減少,并在生成路徑的基礎(chǔ)上使用3次B樣條算法對(duì)拐點(diǎn)處進(jìn)行平滑處理,使最終路徑更適合自動(dòng)駕駛車(chē)輛運(yùn)動(dòng)的特性。

4 結(jié) 語(yǔ)

針對(duì)傳統(tǒng) A*算法在路徑規(guī)劃中存在的不足,提出了具有自適應(yīng)調(diào)整權(quán)重因子、考慮航向角影響因子的啟發(fā)函數(shù)、路徑平滑處理的改進(jìn)A*算法。該算法通過(guò)指數(shù)增長(zhǎng)法使啟發(fā)函數(shù)中的估價(jià)函數(shù)隨路徑變化提高搜索效率;隨后在啟發(fā)函數(shù)中考慮轉(zhuǎn)彎所帶來(lái)的影響(航向角影響因子),使自動(dòng)駕駛車(chē)輛滿足其基本的轉(zhuǎn)向特性;最后利用3次B樣條算法平滑處理生成的路徑。通過(guò)仿真對(duì)比分析,提出的改進(jìn)A*算法在愈加復(fù)雜的環(huán)境下拐點(diǎn)數(shù)更少、路徑更為平滑、路徑距離更短,證明了所提算法的優(yōu)越性和可行性。接下來(lái)將結(jié)合其他智能算法,研究如何在動(dòng)態(tài)環(huán)境中快速準(zhǔn)確地規(guī)劃出自動(dòng)駕駛車(chē)輛最優(yōu)路徑。