李瓊瓊，施楊洋，布升強(qiáng)，楊家富

(南京林業(yè)大學(xué)機(jī)械電子工程學(xué)院，江蘇 南京 210037)

隨著汽車保有量的不斷增加，交通事故發(fā)生的概率也越來(lái)越大，汽車安全已成為全社會(huì)關(guān)注的焦點(diǎn)問(wèn)題。無(wú)人駕駛技術(shù)在降低道路交通事故發(fā)生率方面有著重要的研究意義和價(jià)值。隨著人工智能的應(yīng)用和發(fā)展，無(wú)人駕駛汽車越來(lái)越受到關(guān)注，路徑規(guī)劃問(wèn)題也已成為當(dāng)下研究的熱點(diǎn)[1]。無(wú)人車路徑規(guī)劃是指在有障礙物的環(huán)境中，快速規(guī)劃出一條連接起始點(diǎn)與目標(biāo)點(diǎn)的可行路徑[2]。近年來(lái)關(guān)于無(wú)人車路徑規(guī)劃問(wèn)題，很多學(xué)者提出了各種應(yīng)用于不同場(chǎng)景的路徑規(guī)劃算法。主要有基于地圖搜索的概率路圖法[3]和快速隨機(jī)拓展樹(shù)法[4]，基于節(jié)點(diǎn)搜索的A*和D*算法[5-6]，基于啟發(fā)搜索的粒子群算法和蟻群算法等[7-8]。

對(duì)于靜態(tài)環(huán)境，A*算法是搜索路徑最有效的方法之一，因此被廣泛應(yīng)用在路徑規(guī)劃仿真實(shí)驗(yàn)中[9]。但由于其本身搜索原理的限制，A*算法規(guī)劃路徑效率雖高但轉(zhuǎn)折點(diǎn)較多，考慮到無(wú)人車的具體尺寸和行駛時(shí)的環(huán)境狀況，轉(zhuǎn)折點(diǎn)較多不利于無(wú)人車的行駛。Botea A 等[10]提出了HPA*算法，通過(guò)減小搜索空間來(lái)提高搜索速度，有效地提高了尋路效率，但其往往得不到最優(yōu)路徑，還需要進(jìn)一步搜索來(lái)實(shí)現(xiàn)對(duì)路徑的優(yōu)化，增加了計(jì)算量；王紅衛(wèi)等[11]提出了一種平滑方法，解決了無(wú)人車路徑規(guī)劃轉(zhuǎn)折點(diǎn)多的問(wèn)題，但沒(méi)有縮短路徑的長(zhǎng)度；辛煜等[12]提出了一種改進(jìn)A*的算法，對(duì)柵格地圖中的柵格進(jìn)行線性插值，解決了傳統(tǒng)A*算法平滑性較差的問(wèn)題，但其增加了可搜索鄰域和搜索方向，導(dǎo)致搜索的時(shí)間變長(zhǎng)。

基于以上各方法的特點(diǎn)，本文提出一種改進(jìn)的A*算法，將一個(gè)搜索優(yōu)先級(jí)信息引入啟發(fā)函數(shù)中，使A*算法在進(jìn)行路徑規(guī)劃時(shí)優(yōu)先搜索初始點(diǎn)和目標(biāo)點(diǎn)對(duì)角連線區(qū)域，縮短了路徑長(zhǎng)度和搜索時(shí)間。

1 環(huán)境建模及地圖預(yù)處理

在無(wú)人車的路徑規(guī)劃中，需要將各傳感器采集到的環(huán)境信息進(jìn)行融合，建立一個(gè)能表示周圍環(huán)境的地圖模型。目前環(huán)境建模方面應(yīng)用最廣泛的方法之一是柵格法，其具有簡(jiǎn)單、易于實(shí)現(xiàn)的特點(diǎn)。

本文采用21×21柵格組成的地圖來(lái)表示無(wú)人車周圍的環(huán)境信息，如圖1所示。柵格法將無(wú)人車行駛環(huán)境用一系列具有相同尺寸的柵格表示，并根據(jù)環(huán)境信息將柵格地圖分為行駛區(qū)域和障礙物區(qū)域。其中行駛區(qū)域?yàn)榘咨珫鸥?，障礙物區(qū)域?yàn)楹谏珫鸥瘛５貓D四周邊界處都設(shè)置為障礙物，防止初始點(diǎn)和目標(biāo)點(diǎn)設(shè)置在地圖外側(cè)。若輸入的初始點(diǎn)或目標(biāo)點(diǎn)的坐標(biāo)與某障礙物坐標(biāo)重合，則地圖默認(rèn)把此障礙物刪除。

圖1 柵格地圖

為便于研究和進(jìn)行仿真實(shí)驗(yàn)，本文做出以下合理假設(shè)：

(1)假設(shè)地圖和障礙物邊界都是在考慮無(wú)人車安全距離的情況下建立，因此可以將無(wú)人車視為一個(gè)質(zhì)點(diǎn)，且只能在網(wǎng)格范圍內(nèi)移動(dòng)。

(2)在沒(méi)有邊界和障礙物的情況下，無(wú)人車可以向周圍8個(gè)方向的柵格移動(dòng)，并且不考慮自身外型的影響。

(3)在無(wú)人車尋徑過(guò)程中，周圍環(huán)境保持不變。

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

A*算法是一種應(yīng)用于靜態(tài)全局路徑規(guī)劃的搜索算法，其關(guān)鍵在于評(píng)價(jià)函數(shù)的選取[13]。從初始點(diǎn)開(kāi)始，根據(jù)啟發(fā)函數(shù)搜索與初始點(diǎn)相鄰的節(jié)點(diǎn)，通過(guò)代價(jià)函數(shù)來(lái)選取最優(yōu)的一個(gè)相鄰節(jié)點(diǎn)作為當(dāng)前節(jié)點(diǎn)繼續(xù)前進(jìn)搜索，直至搜索到目標(biāo)點(diǎn)為止，最后由目標(biāo)點(diǎn)回溯到初始點(diǎn)連接形成一條全局規(guī)劃路徑。其代價(jià)估計(jì)函數(shù)為：

f(x，y)=g(x，y)+h(x，y)

(1)

式中：f(x，y)為起始點(diǎn)到目標(biāo)點(diǎn)的估價(jià)函數(shù)；g(x，y)為從起始點(diǎn)到當(dāng)前節(jié)點(diǎn)的實(shí)際代價(jià)值；h(x，y)為啟發(fā)函數(shù)，表示當(dāng)前節(jié)點(diǎn)到目標(biāo)點(diǎn)的代價(jià)估計(jì)值。若h(x，y)=0，即啟發(fā)函數(shù)為零，估價(jià)函數(shù)完全由g(x，y)決定，搜索效率降低，A*算法退化為Dijkstra算法；若g(x，y)=0，則估價(jià)函數(shù)完全由啟發(fā)函數(shù)h(x，y)決定，A*算法演變?yōu)閷挾葍?yōu)先搜索算法。A*算法是否高效取決于啟發(fā)函數(shù)h(x，y)。h(x，y)中包含的啟發(fā)式信息越多，搜索路徑的效率越高；h(x，y)中包含的啟發(fā)式信息越少，規(guī)劃出來(lái)的路徑與最優(yōu)路徑相差就越大。A*算法中有Open與Close列表，其中有待搜索的可行相鄰節(jié)點(diǎn)存放在Open列表中，已搜索過(guò)的節(jié)點(diǎn)保存在Close列表中。傳統(tǒng)A*算法流程圖如圖2所示。

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

3 改進(jìn)的A*算法

啟發(fā)函數(shù)的選取對(duì)于整個(gè)A*算法至關(guān)重要，若想尋得最優(yōu)路徑，需要保證始終小于當(dāng)前節(jié)點(diǎn)到目標(biāo)點(diǎn)的實(shí)際距離。傳統(tǒng)A*算法通常采用曼哈頓距離和歐氏距離作為啟發(fā)函數(shù)。若無(wú)人車可以朝任意方向移動(dòng)，常采用歐氏距離來(lái)表示對(duì)應(yīng)的啟發(fā)函數(shù)：

(2)

但本文中以柵格作為地圖環(huán)境，地圖中存在障礙物，無(wú)人車不能全向移動(dòng)，且采用歐式距離的搜索速度比曼哈頓慢，因此本文選用曼哈頓距離作為啟發(fā)函數(shù)：

h(x，y)=B×(|xi-xg|+|yi-yg|)

(3)

式(2)、式(3)中B為每個(gè)相鄰單位節(jié)點(diǎn)之間的路徑代價(jià)，無(wú)人車當(dāng)前的位置為(xi，yi)，目標(biāo)點(diǎn)位置為(xg，yg)。

起始點(diǎn)和目標(biāo)點(diǎn)的對(duì)角連線附近連線區(qū)域?yàn)樽顑?yōu)路徑大概率出現(xiàn)的地方，可視為優(yōu)先搜索區(qū)域。最優(yōu)路徑的出現(xiàn)概率隨著優(yōu)先搜索區(qū)域向兩側(cè)延伸而減小。基于此理論，本文提出一種新的啟發(fā)函數(shù)，具體為在原有的啟發(fā)函數(shù)h(x，y)里引入一個(gè)搜索優(yōu)先級(jí)啟發(fā)式信息η(i，j)=1/d(i，j)，其中：

(4)

h′(x，y)=B×(|xi-xg|+|yi-yg|)×η(i，j)

(5)

式(4)中，(xi，yi)表示當(dāng)前節(jié)點(diǎn)的坐標(biāo)位置，(xs，ys)表示起始點(diǎn)，(xo，yo)表示原點(diǎn)位置，(xn，yn)表示柵格地圖頂點(diǎn)坐標(biāo)，mid表示地圖劃分的分割線?；诘貓D位置信息劃分過(guò)的啟發(fā)式函數(shù)，劃分出核心區(qū)域和非核心區(qū)域。在無(wú)人車搜索路徑過(guò)程中，從起始點(diǎn)開(kāi)始，根據(jù)目標(biāo)點(diǎn)的位置，優(yōu)先搜索起始點(diǎn)和目標(biāo)點(diǎn)的對(duì)角連線附近區(qū)域，若該區(qū)域內(nèi)有障礙物，則搜索區(qū)域逐漸向兩側(cè)偏離。搜索優(yōu)先級(jí)啟發(fā)式信息量，沿著初始點(diǎn)與目標(biāo)點(diǎn)的連線向兩側(cè)遞減。

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

本文基于MATLAB 2018b軟件來(lái)驗(yàn)證改進(jìn)A*算法的有效性。首先建立一個(gè)21×21的柵格地圖，為便于仿真，將無(wú)人車視為一個(gè)質(zhì)點(diǎn)。初始點(diǎn)設(shè)為(1，20)，目標(biāo)點(diǎn)設(shè)置為(20，1)。障礙物和邊界位置固定，傳統(tǒng)A*算法仿真實(shí)驗(yàn)如圖3所示，改進(jìn)后的A*算法仿真實(shí)驗(yàn)如圖4所示，兩種算法仿真實(shí)驗(yàn)結(jié)果對(duì)比見(jiàn)表1。其中，“★”表示Close節(jié)點(diǎn)，“+”為Open節(jié)點(diǎn)，連線為規(guī)劃出的路徑；保證初始點(diǎn)和目標(biāo)點(diǎn)分別為(1，20)和(20，1)，保持地圖環(huán)境不變，對(duì)改進(jìn)前后的A*算法分別進(jìn)行25次仿真實(shí)驗(yàn)，兩者時(shí)間對(duì)比結(jié)果如圖5所示；改變起始點(diǎn)和目標(biāo)點(diǎn)，保持地圖環(huán)境不變，進(jìn)行10次仿真實(shí)驗(yàn)，得到的實(shí)驗(yàn)數(shù)據(jù)見(jiàn)表2。

圖3 傳統(tǒng)A*算法仿真實(shí)驗(yàn)

由圖3和圖4可知，相對(duì)于傳統(tǒng)A*算法，啟發(fā)函數(shù)引入優(yōu)先級(jí)啟發(fā)式信息，使A*算法搜索路徑時(shí)優(yōu)先搜索初始點(diǎn)和目標(biāo)點(diǎn)連線區(qū)域，減少了A*算法的隨機(jī)性。由表1可知，改進(jìn)A*算法仿真實(shí)驗(yàn)所得到的路徑軌跡轉(zhuǎn)折點(diǎn)較少且平均轉(zhuǎn)折角度減小，路徑軌跡更加平滑，縮短了路徑的長(zhǎng)度和路徑規(guī)劃所需的時(shí)間，順利到達(dá)了目標(biāo)位置，提高了搜索效率，實(shí)現(xiàn)了路徑優(yōu)化目標(biāo)。

表1 兩種算法仿真實(shí)驗(yàn)結(jié)果

算法轉(zhuǎn)折點(diǎn)數(shù)路徑長(zhǎng)度平均運(yùn)行時(shí)間/s傳統(tǒng)A?1629.2119.871 3改進(jìn)A?927.2112.313 8

圖4 改進(jìn)A*算法仿真實(shí)驗(yàn)

圖5 時(shí)間對(duì)比

表2 兩種算法仿真實(shí)驗(yàn)數(shù)據(jù)

初始點(diǎn)傳統(tǒng)A?轉(zhuǎn)折點(diǎn)改進(jìn)A?轉(zhuǎn)折點(diǎn)傳統(tǒng)A?路徑長(zhǎng)度改進(jìn)A?路徑長(zhǎng)度(2,20)17730.384 827.213 2(3,19)15725.556 324.384 8(4,18)14722.727 921.556 3(4,17)141022.142 121.556 3(4,20)151028.384 826.142 1(3,19)15725.556 324.384 8(5,20)171029.799 124.970 6(2,18)161226.970 626.382 8(3,17)161224.142 123.556 3(1,18)171329.799 825.970 6平均值15.69.528.897 224.611 8

注：令每一個(gè)目標(biāo)點(diǎn)的橫坐標(biāo)和縱坐標(biāo)分別與初始點(diǎn)的縱坐標(biāo)和橫坐標(biāo)相同

由表2可知，多次實(shí)驗(yàn)中，改進(jìn)A*算法的轉(zhuǎn)折點(diǎn)個(gè)數(shù)均少于傳統(tǒng)A*算法，實(shí)現(xiàn)了路徑平滑。此外，基于改進(jìn)A*算法得到的路徑長(zhǎng)度均小于傳統(tǒng)A*算法。實(shí)驗(yàn)表明改進(jìn)的A*算法在路徑平滑、縮短路徑長(zhǎng)度、提高搜索效率方面有顯著的效果。

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

針對(duì)無(wú)人車路徑規(guī)劃問(wèn)題，以傳統(tǒng)A*算法為基礎(chǔ)，在啟發(fā)函數(shù)里引入新的搜索優(yōu)先級(jí)信息，在路徑搜索過(guò)程中，以起始點(diǎn)和目標(biāo)點(diǎn)的對(duì)角線為基準(zhǔn)，優(yōu)先搜索起始點(diǎn)和目標(biāo)點(diǎn)的對(duì)角連線附近區(qū)域，減少了A*算法尋徑時(shí)的隨機(jī)性，提高了搜索效率，改善了傳統(tǒng)A*算法耗時(shí)長(zhǎng)、轉(zhuǎn)折點(diǎn)多和路徑不平滑等不足。本文設(shè)計(jì)的改進(jìn)A*算法，對(duì)路徑的轉(zhuǎn)折角度和長(zhǎng)度的優(yōu)化效果不明顯，需要進(jìn)一步的研究