基于改進A*算法的無人車路徑規(guī)劃研究

李瓊瓊，施楊洋，布升強，楊家富

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

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

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

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

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

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

本文采用21×21柵格組成的地圖來表示無人車周圍的環(huán)境信息，如圖1所示。柵格法將無人車行駛環(huán)境用一系列具有相同尺寸的柵格表示，并根據(jù)環(huán)境信息將柵格地圖分為行駛區(qū)域和障礙物區(qū)域。其中行駛區(qū)域為白色柵格，障礙物區(qū)域為黑色柵格。地圖四周邊界處都設置為障礙物，防止初始點和目標點設置在地圖外側。若輸入的初始點或目標點的坐標與某障礙物坐標重合，則地圖默認把此障礙物刪除。

圖1 柵格地圖

為便于研究和進行仿真實驗，本文做出以下合理假設：

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

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

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

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

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

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

(1)

式中：f(x，y)為起始點到目標點的估價函數(shù)；g(x，y)為從起始點到當前節(jié)點的實際代價值；h(x，y)為啟發(fā)函數(shù)，表示當前節(jié)點到目標點的代價估計值。若h(x，y)=0，即啟發(fā)函數(shù)為零，估價函數(shù)完全由g(x，y)決定，搜索效率降低，A*算法退化為Dijkstra算法；若g(x，y)=0，則估價函數(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ī)劃出來的路徑與最優(yōu)路徑相差就越大。A*算法中有Open與Close列表，其中有待搜索的可行相鄰節(jié)點存放在Open列表中，已搜索過的節(jié)點保存在Close列表中。傳統(tǒng)A*算法流程圖如圖2所示。

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

3 改進的A*算法

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

(2)

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

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

(3)

式(2)、式(3)中B為每個相鄰單位節(jié)點之間的路徑代價，無人車當前的位置為(xi，yi)，目標點位置為(xg，yg)。

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

(4)

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

(5)

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

4 仿真實驗與結果分析

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

圖3 傳統(tǒng)A*算法仿真實驗

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

表1 兩種算法仿真實驗結果

算法轉折點數(shù)路徑長度平均運行時間/s傳統(tǒng)A?1629.2119.871 3改進A?927.2112.313 8

圖4 改進A*算法仿真實驗

圖5 時間對比

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

初始點傳統(tǒng)A?轉折點改進A?轉折點傳統(tǒng)A?路徑長度改進A?路徑長度(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

注：令每一個目標點的橫坐標和縱坐標分別與初始點的縱坐標和橫坐標相同

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

5 結束語

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