基于改進(jìn)A*算法的無人駕駛車輛路徑規(guī)劃方法研究

林黃智, 田柳

基于改進(jìn)A*算法的無人駕駛車輛路徑規(guī)劃方法研究

林黃智1, 田柳2

(1. 安徽職業(yè)技術(shù)學(xué)院 機(jī)電工程學(xué)院, 安徽 合肥, 230011; 2. 中國移動(dòng)通信集團(tuán)安徽有限公司, 安徽 合肥, 230088)

針對傳統(tǒng)A*算法所規(guī)劃路徑距離障礙物近、轉(zhuǎn)折點(diǎn)多、路徑不平滑的問題, 對A*算法進(jìn)行改進(jìn)并應(yīng)用于無人駕駛車輛路徑規(guī)劃中。在傳統(tǒng)A*算法分析的基礎(chǔ)上對背向障礙物搜索和評價(jià)函數(shù)進(jìn)行改進(jìn), 同時(shí)采用3次樣條插值方法對規(guī)劃后路徑平滑處理。將傳統(tǒng)A*算法和改進(jìn)A*算法應(yīng)用于MATLAB環(huán)境下搭建的無人駕駛車輛模型進(jìn)行路徑規(guī)劃仿真分析。結(jié)果表明, 改進(jìn)A*算法所規(guī)劃的路徑距離障礙物比較遠(yuǎn), 轉(zhuǎn)折點(diǎn)數(shù)量明顯減少, 同時(shí)路徑更加平滑。

改進(jìn)A*算法; 路徑規(guī)劃; 無人駕駛車輛

國民經(jīng)濟(jì)的快速發(fā)展使得汽車保有量不斷增加, 這使得城市交通更加擁堵, 各種交通事故頻發(fā)。每年全球死于交通事故的人數(shù)占據(jù)總死亡人數(shù)的20%左右, 同時(shí)也造成了巨大的經(jīng)濟(jì)損失[1]。人工智能技術(shù)的快速發(fā)展使得無人駕駛汽車受到了越來越多的關(guān)注, 無人駕駛技術(shù)對降低汽車道路交通事故發(fā)生率具有至關(guān)重要的意義。路徑規(guī)劃是無人駕駛車輛研發(fā)的核心技術(shù)之一, 其任務(wù)是獲取一條安全無碰撞的軌跡, 確保車輛沿著該軌跡可以從起點(diǎn)安全地到達(dá)目標(biāo)點(diǎn)[2]。無人駕駛車輛在行進(jìn)的過程中需要對動(dòng)靜態(tài)的障礙物進(jìn)行避讓, 同時(shí)確保路徑最短, 實(shí)現(xiàn)能量最優(yōu)化[3]。

A*算法是一種求解最短路徑的啟發(fā)式搜索算法, 在無人駕駛車輛路徑規(guī)劃中得到了廣泛的應(yīng)用[4]。但是采用A*算法規(guī)劃的路徑往往存在折線、轉(zhuǎn)折多的問題, 同時(shí)和障礙物距離比較近, 容易發(fā)生碰撞, 存在比較大的安全隱患[5]。基于此, 本文在A*算法的基礎(chǔ)上對其進(jìn)行改進(jìn), 同時(shí)將改進(jìn)的A*算法應(yīng)用于無人駕駛車輛的路徑規(guī)劃中, 為無人駕駛車輛路徑規(guī)劃提供參考。

1 A*算法及改進(jìn)

1.1 A*算法

A*算法是一種靜態(tài)全局路徑規(guī)劃算法, 其從車輛的起始點(diǎn)開始, 根據(jù)啟發(fā)函數(shù)來搜索和起始點(diǎn)相鄰的節(jié)點(diǎn), 同時(shí)通過代價(jià)函數(shù)來選擇一個(gè)最優(yōu)的相鄰節(jié)點(diǎn)作為當(dāng)前節(jié)點(diǎn)進(jìn)行繼續(xù)搜索, 直到搜索到目標(biāo)點(diǎn)為止, 最后由目標(biāo)點(diǎn)回溯到起始點(diǎn)形成一條全局規(guī)劃的路徑。采用A*算法進(jìn)行無人駕駛車輛的路徑規(guī)劃需要建立A*優(yōu)化函數(shù)[6], 即(,) =(,) +(,), 其中:(,)為無人駕駛車輛起始點(diǎn)到目標(biāo)點(diǎn)的估價(jià)函數(shù);(,)為無人駕駛車輛起始點(diǎn)到當(dāng)前點(diǎn)的實(shí)際代價(jià);(,)為無人駕駛車輛當(dāng)前點(diǎn)到目標(biāo)點(diǎn)的代價(jià), 是啟發(fā)函數(shù)。

對于A*算法而言, 算法的效率高低取決于啟發(fā)函數(shù)。如果啟發(fā)函數(shù)(,) = 0, 那么評估函數(shù)完全由(,)決定, 此時(shí)A*算法退化為Dijkstra算法[7]。對于啟發(fā)函數(shù)(,)而言, 其包含的啟發(fā)信息越多, 那么在實(shí)際路徑搜索的過程中效率就會(huì)越高[8]。如果啟發(fā)函數(shù)(,)包含的啟發(fā)信息比較少, 那么在實(shí)際路徑搜索的過程中效率就會(huì)大大降低, 同時(shí)所規(guī)劃的路徑和實(shí)際的最優(yōu)路徑之間往往有比較大的差距。在A*算法中, 啟發(fā)函數(shù)(,) = 0決定了路徑的搜索方向和算法的效率, 定義啟發(fā)函數(shù)為(,) =11+2(2– 21), 其中:1為對角線移動(dòng)一格的代價(jià);2為水平移動(dòng)一格的代價(jià);1= min(|-|, |-|),2= |-| + |-|, (,)為無人駕駛車輛當(dāng)前所在位置; (,)為無人駕駛車輛路徑規(guī)劃目標(biāo)點(diǎn)所在位置。

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

為了解決采用傳統(tǒng)A*算法進(jìn)行無人駕駛車輛規(guī)劃路徑存在的距離障礙物比較近、轉(zhuǎn)折點(diǎn)數(shù)量多以及路徑不平滑等問題, 本文從3個(gè)角度對傳統(tǒng)A*算法進(jìn)行改進(jìn)。

1.2.1 背向障礙物搜索

無人駕駛車輛運(yùn)行中由于慣性的存在, 如果所規(guī)劃路徑距離障礙物過近, 那么和障礙物碰撞的可能性就會(huì)大大增加。采用背向障礙物搜索策略, 即和障礙物相鄰的節(jié)點(diǎn)不會(huì)作為規(guī)劃路徑的考慮范圍, 有效克服了傳統(tǒng)A*算法所規(guī)劃路徑距離障礙物過近的缺陷[9]。

1.2.2 提取最優(yōu)轉(zhuǎn)折點(diǎn)

采用傳統(tǒng)的A*算法進(jìn)行無人駕駛車輛路徑規(guī)劃, 得到的路徑常常包含有比較多的轉(zhuǎn)折點(diǎn)。無人駕駛車輛在實(shí)際運(yùn)行的過程中如果采用A*算法所規(guī)劃的路徑, 那么將會(huì)影響到車輛的乘坐舒適性, 同時(shí)慣性也使得行車安全性難以保證。采用傳統(tǒng)A*算法規(guī)劃得到的路徑中許多的轉(zhuǎn)折點(diǎn)往往是不必要的, 在確保和障礙物保持一定距離的前提下可以剔除一些不必要的轉(zhuǎn)折點(diǎn)[10]。

采用A*算法對無人駕駛車輛進(jìn)行路徑規(guī)劃, 路徑中轉(zhuǎn)折點(diǎn)集合為{p}, 從起始點(diǎn)依次采用有向線段連接之后的轉(zhuǎn)折點(diǎn), 具體如圖1所示。

定義評價(jià)函數(shù)(x,y), 將其作為最優(yōu)轉(zhuǎn)折點(diǎn)的選擇依據(jù), 評價(jià)函數(shù)(x,y) = (1-)/1+2, 其中:1為障礙物中心到起始點(diǎn)與轉(zhuǎn)折點(diǎn)連線的垂直距離,2為轉(zhuǎn)折點(diǎn)到障礙物所在線段末端轉(zhuǎn)折點(diǎn)的距離, 具體如圖1所示, 系數(shù)為可調(diào)參數(shù)。

圖1 起始點(diǎn)連接轉(zhuǎn)折點(diǎn)示意圖

計(jì)算各個(gè)轉(zhuǎn)折點(diǎn)的評價(jià)函數(shù), 選擇評價(jià)函數(shù)值最小的轉(zhuǎn)折點(diǎn)為最優(yōu)轉(zhuǎn)折點(diǎn)。在確定了第一個(gè)最優(yōu)轉(zhuǎn)折點(diǎn)之后, 以該點(diǎn)為新的起點(diǎn)重復(fù)上述過程直到無人駕駛車輛目標(biāo)點(diǎn)結(jié)束。從起始點(diǎn)依次連接所有的最優(yōu)轉(zhuǎn)折點(diǎn)所得到的路徑為最終規(guī)劃的路徑。

1.2.3 樣條插值平滑路徑

2 無人駕駛車輛路徑規(guī)劃仿真分析

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

在無人駕駛車輛路徑規(guī)劃之前需要對安裝在車輛上的傳感器采集到的環(huán)境信息進(jìn)行融合, 從而得到一個(gè)可以有效表示周圍環(huán)境的地圖模型。本文采用32 × 32的柵格地圖來表示無人駕駛車輛周邊的環(huán)境, 其中可以行使的區(qū)域采用白色柵格表示, 障礙物區(qū)域采用黑色柵格表示, 在地圖的邊界均設(shè)置障礙物, 避免無人駕駛車輛的初始位置點(diǎn)和目標(biāo)位置點(diǎn)在地圖之外。本論文的研究將無人駕駛車輛視為一個(gè)質(zhì)點(diǎn), 同時(shí)只能在網(wǎng)格范圍內(nèi)運(yùn)動(dòng)。在沒有邊界和障礙物的情況下, 無人駕駛車輛可以向周圍8個(gè)方向的柵格移動(dòng)。另外, 無人駕駛車輛在進(jìn)行路徑規(guī)劃的過程中周圍的環(huán)境始終保持不變, 即不包含有動(dòng)態(tài)的障礙物。

2.2 仿真試驗(yàn)及結(jié)果分析

為了對比傳統(tǒng)A*算法和改進(jìn)A*算法對無人駕駛車輛路徑規(guī)劃的效果, 采用仿真試驗(yàn)進(jìn)行分析。傳統(tǒng)A*算法的路徑規(guī)劃流程如圖2所示。改進(jìn)A*算法主要是采取背向障礙物搜索、優(yōu)化規(guī)劃路徑轉(zhuǎn)折點(diǎn)以及規(guī)劃路徑平滑對無人駕駛車輛路徑進(jìn)行規(guī)劃, 使得規(guī)劃后的路徑距離障礙物比較遠(yuǎn)、路徑比較平滑, 提高無人駕駛車輛的行使平順性。改進(jìn)A*算法的路徑規(guī)劃流程如圖3所示。

圖2 A*算法流程圖

選擇無人駕駛車輛的起始點(diǎn)坐標(biāo)為(3, 30), 目標(biāo)點(diǎn)坐標(biāo)為(29, 11), 分別采用傳統(tǒng)A*算法和改進(jìn)的A*算法進(jìn)行路徑規(guī)劃, 路徑規(guī)劃結(jié)果如圖4所示。為了對比傳統(tǒng)A*算法和改進(jìn)A*算法路徑規(guī)劃性能, 從規(guī)劃路徑長度、規(guī)劃路徑轉(zhuǎn)折點(diǎn)個(gè)數(shù)、規(guī)劃路徑距離障礙物最近距離、運(yùn)行時(shí)間4個(gè)方面進(jìn)行對比, 結(jié)果如表1所示。

表1 傳統(tǒng)A*算法和改進(jìn)A*算法仿真結(jié)果對比

由圖4和表1可知, 傳統(tǒng)A*算法對無人駕駛車輛路徑規(guī)劃未考慮車輛和障礙物的距離, 這導(dǎo)致所規(guī)劃的路徑總是和障礙物的邊緣相切, 同時(shí)存在比較多的轉(zhuǎn)折點(diǎn)。對于改進(jìn)的A*算法, 其所規(guī)劃的路徑長度比A*算法所規(guī)劃的路徑長度有所增加, 同時(shí)路徑規(guī)劃耗時(shí)也有所增加, 但是所規(guī)劃的路徑轉(zhuǎn)折點(diǎn)個(gè)數(shù)明顯減少, 所規(guī)劃的路徑確保和障礙物有一定的距離。改進(jìn)A*算法中的參數(shù)對路徑規(guī)劃的長度、規(guī)劃路徑轉(zhuǎn)折點(diǎn)個(gè)數(shù)、和障礙物的最近距離以及路徑規(guī)劃耗時(shí)之間均有一定的關(guān)系, 只有通過多次調(diào)試才能確保所規(guī)劃的路徑最優(yōu)。

圖3 改進(jìn)A*算法流程圖

圖4 無人駕駛車輛路徑規(guī)劃結(jié)果

為了確保所規(guī)劃的路徑更加平滑, 在改進(jìn)A*算法的基礎(chǔ)上采用樣條插值進(jìn)行路徑平滑。本文采用3次均勻樣條插值函數(shù)對規(guī)劃后的路徑進(jìn)行平滑處理, 結(jié)果如圖5所示。

由圖5可見, 采用3次均勻樣條插值函數(shù)對規(guī)劃后的路徑進(jìn)行平滑處理, 所得到的路徑相比較未處理之前的路徑更為平滑, 在平滑后的路徑中不存在尖銳的轉(zhuǎn)角, 這有利于無人駕駛車輛的轉(zhuǎn)向控制, 提高車輛的乘坐舒適性。

通過對比A*算法和改進(jìn)的A*算法, 采用改進(jìn)的A*算法對無人駕駛車輛進(jìn)行路徑規(guī)劃, 其規(guī)劃路徑的轉(zhuǎn)折點(diǎn)數(shù)明顯減少, 和障礙物的最近距離明顯增大, 同時(shí)所規(guī)劃的路徑也更為平滑, 但是改進(jìn)A*算法對路徑的規(guī)劃耗時(shí)相對較長, 這是改進(jìn)算法的不足之處。

圖5 改進(jìn)A*算法采用3次樣條插值平滑處理后路徑

3 結(jié)論

針對傳統(tǒng)A*算法在無人駕駛車輛路徑規(guī)劃方面存在所規(guī)劃路徑距離障礙物近、轉(zhuǎn)折點(diǎn)數(shù)量多、路徑不平滑的問題, 在對傳統(tǒng)A*算法分析的基礎(chǔ)上提出了改進(jìn)的A*算法。通過背向障礙物搜索確保規(guī)劃路徑和障礙物的距離, 通過定義評價(jià)函數(shù)來選擇最佳的轉(zhuǎn)折點(diǎn), 同時(shí)通過3次均勻樣條函數(shù)來對規(guī)劃的路徑進(jìn)行平滑處理。通過仿真試驗(yàn)表明采用改進(jìn)A*算法所規(guī)劃的路徑和障礙物保持有一定的安全距離, 同時(shí)轉(zhuǎn)折點(diǎn)的數(shù)目也有所減少, 規(guī)劃的路徑更加平滑, 但是存在路徑長度和規(guī)劃耗時(shí)增加的問題。

[1] 麥明珠. 純電動(dòng)汽車動(dòng)力系統(tǒng)參數(shù)匹配及優(yōu)化研究[J]. 湖南文理學(xué)院學(xué)報(bào)(自然科學(xué)版), 2020, 32(3): 25–29.

[2] 彭曉燕, 謝浩, 黃晶. 無人駕駛汽車局部路徑規(guī)劃算法研究[J]. 汽車工程, 2020, 42(1): 1–10.

[3] 劉博, 羅霞, 朱健. 無人駕駛車輛自動(dòng)避障路徑規(guī)劃仿真研究[J]. 計(jì)算機(jī)仿真, 2018, 35(2): 105–110.

[4] 胡蔚旻, 靳文舟. 改進(jìn)平滑A~*算法的多AGV路徑規(guī)劃[J]. 計(jì)算機(jī)工程與應(yīng)用, 2020, 56(16): 204–210.

[5] 祁玄玄, 黃家駿, 曹建安. 基于改進(jìn)A~*算法的無人車路徑規(guī)劃[J]. 計(jì)算機(jī)應(yīng)用, 2020, 40(7): 2 021–2 027.

[6] 郭蓬, 吳學(xué)易, 戎輝, 等. 基于代價(jià)函數(shù)的無人駕駛汽車局部路徑規(guī)劃算法[J]. 中國公路學(xué)報(bào), 2019, 32(6): 79–85.

[7] 張奮, 黃鐵, 周軍輝. 空間分析中雙向Dijkstra算法優(yōu)化研究[J]. 湖南文理學(xué)院學(xué)報(bào)(自然科學(xué)版), 2007, 19(2): 71–73, 86.

[8] 劉生偉, 馬鉞, 孟樹峰, 等. 改進(jìn)A*算法的AGV路徑規(guī)劃[J]. 計(jì)算機(jī)應(yīng)用, 2019, 39(z2): 41–44.

[9] 喬云俠, 王慶, 陽媛, 等. 基于背向障礙物搜索A~*算法的平滑路徑規(guī)劃[J]. 傳感器與微系統(tǒng), 2020, 39(8): 127–129.

[10] 隨博文, 黃志堅(jiān). 基于改進(jìn)A~*算法的水面無人艇路徑規(guī)劃[J]. 艦船科學(xué)技術(shù), 2019, 41(23): 162–166.

[11] 董敏, 陳鐵樁, 楊浩. 基于改進(jìn)RRT算法的無人車路徑規(guī)劃仿真研究[J]. 計(jì)算機(jī)仿真, 2019, 36(11): 96–100.

Research on path planning method of driverless vehicle based on improved A* algorithm

Lin Huangzhi1, Tian Liu2

(1. Mechanical and Electrical Engineering, Anhui Vocational and Technical College, Hefei, Anhui, 230011, China; 2. China Mobile Communications Group Anhui Co Ltd, Hefei 230088, China)

In order to solve the problems of the traditional A* algorithm, such as near distance to obstacles, many turning points and unsmooth path, A* algorithm is improved and applied to the path planning of unmanned vehicles. Based on the analysis of the traditional A* algorithm, the search and evaluation function of back obstacles is improved, and the cubic spline interpolation method is used to smooth the path after planning. The traditional A* algorithm and the improved A* algorithm are applied to the unmanned vehicle model built in MATLAB environment for path planning simulation analysis. The results show that the path planned by the improved A* algorithm is far away from the obstacles, the number of turning points is significantly reduced, and the path is smoother.

Improved A* algorithm; Path planning; Driverless vehicle

U 461

A

1672–6146(2021)02–0017–04

10.3969/j.issn.1672–6146.2021.02.004

林黃智, highgecho@foxmail.com。

2020–09–14

(責(zé)任編校: 張紅)