基于關(guān)鍵節(jié)點(diǎn)的改進(jìn)A*無人車路徑規(guī)劃算法

張輝 張瑞亮,2 許小慶 范政武,2

（1.太原理工大學(xué)，太原 030024；2.山西省汽車設(shè)計(jì)工程技術(shù)研究中心，太原 030024）

1 前言

無人車系統(tǒng)主要包括感知、決策、規(guī)劃和控制4 個(gè)模塊[1]，其中規(guī)劃模塊負(fù)責(zé)基于目標(biāo)任務(wù)生成最優(yōu)路徑。按照搜索方式可將路徑規(guī)劃算法分為基于圖搜索、基于采樣及基于人工智能的方法。其中，基于圖搜索的A*算法因其尋優(yōu)能力強(qiáng)、場景適應(yīng)度高等特性而得到廣泛應(yīng)用[2]。

陳若男等[3]結(jié)合距離及角度信息改進(jìn)傳統(tǒng)A*算法代價(jià)函數(shù)，設(shè)計(jì)鄰域選擇策略，提升了算法效率和路徑安全性。楊瑤等[4]通過改進(jìn)距離估算方式，引入車身輪廓代價(jià)和障礙物距離代價(jià)，提升了A*算法規(guī)劃效率和路徑安全性。馮來春等[5]將A*算法和快速搜索隨機(jī)樹（Rapid-Exploring Random Tree，RRT）算法結(jié)合，降低了RRT 算法的采樣盲目性。孟珠李等[6]將A*算法與B 樣條曲線結(jié)合，改善了A*算法規(guī)劃路徑的平滑性。余文凱等[7]采用K-均值（K-Means）聚類算法對(duì)地圖進(jìn)行預(yù)處理，量化不同區(qū)域地圖復(fù)雜度，依據(jù)復(fù)雜度設(shè)置搜索權(quán)重，應(yīng)用弗洛伊德（Floyd）算法對(duì)路徑進(jìn)行平滑，提高了路徑規(guī)劃效率和路徑平滑性。祁玄玄等[8]從目標(biāo)性拓展等多個(gè)方面對(duì)傳統(tǒng)A*算法進(jìn)行改進(jìn)，提升了A*算法的搜索效率。Frantisek等[9]研究了各種改進(jìn)A*算法，如跳點(diǎn)搜索（Jump Points Search，JPS）、Phi*等，并基于部分算法進(jìn)行了仿真驗(yàn)證。Hao等[10]提出了一種可以自適應(yīng)調(diào)整搜索深度的Cell A*算法，使高復(fù)雜度場景地圖下的計(jì)算耗時(shí)進(jìn)一步縮短。Zahra等[11]在A*算法中引入動(dòng)態(tài)可變柵格，增加了危險(xiǎn)懲罰代價(jià)，提升了路徑安全性和計(jì)算效率。

搜索效率和路徑安全性及可行性是規(guī)劃算法的核心，但A*算法多循環(huán)判斷機(jī)制導(dǎo)致其路徑性能和計(jì)算效率難以同時(shí)得到有效改善。因此，本文提出一種改進(jìn)A*算法，基于地圖預(yù)覽模塊提取柵格地圖關(guān)鍵節(jié)點(diǎn)，規(guī)劃模塊依據(jù)關(guān)鍵節(jié)點(diǎn)信息判斷是否開啟增量式擴(kuò)展搜索，引入基于安全距離的碰撞場模型改進(jìn)代價(jià)函數(shù)，應(yīng)用準(zhǔn)均勻三次B 樣條曲線對(duì)生成路徑進(jìn)行平滑處理得到最終的規(guī)劃路徑。最后與對(duì)比算法在不同復(fù)雜度場景下進(jìn)行仿真驗(yàn)證。

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

傳統(tǒng)A*算法融合了廣度優(yōu)先搜索（Breadth First Search，BFS）算法和深度優(yōu)先搜索（Depth First Search，DFS）算法的優(yōu)勢[3]，其基于當(dāng)前節(jié)點(diǎn)與起點(diǎn)和目標(biāo)點(diǎn)之間的距離信息進(jìn)行節(jié)點(diǎn)擴(kuò)展和選擇。傳統(tǒng)A*算法作為典型圖搜索算法，其規(guī)劃地圖通常以柵格地圖形式表達(dá)，如圖1所示為某柵格地圖示例。柵格地圖尺寸決定了地圖表達(dá)的精度和規(guī)模[12]，廣義柵格地圖僅包含障礙物信息。

圖1 柵格地圖

如圖1所示，在規(guī)劃過程中，車輛從起點(diǎn)出發(fā)，通過擴(kuò)展循環(huán)最終行駛至目標(biāo)點(diǎn)，傳統(tǒng)A*算法具體流程如圖2所示。

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

節(jié)點(diǎn)擴(kuò)展時(shí)依據(jù)場景特點(diǎn)及無人車運(yùn)動(dòng)學(xué)特性選取四鄰域方式進(jìn)行節(jié)點(diǎn)擴(kuò)展；代價(jià)函數(shù)f(N)通過當(dāng)前節(jié)點(diǎn)與起始點(diǎn)間的真實(shí)距離g(N)和當(dāng)前節(jié)點(diǎn)與目標(biāo)節(jié)點(diǎn)間的預(yù)估距離h(N)累加得到[13-16]，h(N)一般采用曼哈頓（Manhattan）、歐幾里得（Euclidean）、切比雪夫（Chebyshev）距離。

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

傳統(tǒng)A*算法存在搜索路徑多曲折、緊貼障礙物邊緣、不平滑及搜索時(shí)間隨柵格地圖規(guī)模增大而呈現(xiàn)指數(shù)型增長趨勢等缺陷。一般結(jié)構(gòu)化道路作為車輛的主要應(yīng)用場景，其特點(diǎn)為道路多正向直行區(qū)間、多交叉區(qū)域、空間障礙物類型較多，因此其規(guī)劃的路徑無法直接適應(yīng)無人車在此類環(huán)境下的工作需求。本文針對(duì)此類場景需求提出改進(jìn)A*算法，流程如圖3所示。

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

相對(duì)于傳統(tǒng)A*算法，算法的主要改進(jìn)如下：

a.引入地圖預(yù)覽模塊提取道路轉(zhuǎn)向關(guān)鍵節(jié)點(diǎn)和道路死角關(guān)鍵節(jié)點(diǎn)，并基于目標(biāo)向量信息選取關(guān)鍵節(jié)點(diǎn)，基于當(dāng)前節(jié)點(diǎn)和擬選擇關(guān)鍵節(jié)點(diǎn)形成搜索域，基于障礙物判定規(guī)則判斷是否開啟增量式擴(kuò)展搜索；

b.對(duì)不同類型障礙物進(jìn)行分類，提出一種基于安全距離的碰撞場模型，并結(jié)合其對(duì)傳統(tǒng)A*算法代價(jià)函數(shù)進(jìn)行改進(jìn)；

c.應(yīng)用準(zhǔn)均勻三次B 樣條曲線對(duì)規(guī)劃路徑在轉(zhuǎn)折處進(jìn)行平滑，生成滿足車輛運(yùn)動(dòng)學(xué)約束的最終路徑。

3.1 基于關(guān)鍵節(jié)點(diǎn)信息的擴(kuò)展搜索策略

3.1.1 關(guān)鍵節(jié)點(diǎn)信息獲取

傳統(tǒng)柵格地圖作為地理信息載體[17]，其將環(huán)境抽象為柵格狀態(tài)，僅反映不同位置障礙物信息。為進(jìn)一步提高算法效率，本文提出一種基于地圖預(yù)覽模塊獲取柵格地圖關(guān)鍵節(jié)點(diǎn)的方式。

獲取柵格地圖后，地圖預(yù)覽模塊從柵格群中提取關(guān)鍵節(jié)點(diǎn)至關(guān)鍵節(jié)點(diǎn)列表中，并將道路邊界節(jié)點(diǎn)集合提取至道路邊界節(jié)點(diǎn)列表中。其中，關(guān)鍵節(jié)點(diǎn)包括道路轉(zhuǎn)向關(guān)鍵節(jié)點(diǎn)和道路死角節(jié)點(diǎn)兩類，分別存放于關(guān)鍵節(jié)點(diǎn)列表的不同列中，兩類節(jié)點(diǎn)見圖1，其中，道路死角關(guān)鍵節(jié)點(diǎn)僅能作為起點(diǎn)位置，一旦規(guī)劃過程擬選定道路死角關(guān)鍵節(jié)點(diǎn)，則放棄該操作，重新進(jìn)行節(jié)點(diǎn)選擇。

3.1.2 目標(biāo)向量定義

無人車在進(jìn)行節(jié)點(diǎn)選擇時(shí)，依據(jù)當(dāng)前節(jié)點(diǎn)與目標(biāo)點(diǎn)間向量，即目標(biāo)向量進(jìn)行判斷，選取策略如圖4所示，其中，S節(jié)點(diǎn)為起點(diǎn)，A、B、C、D節(jié)點(diǎn)為車輛可選關(guān)鍵節(jié)點(diǎn)，G節(jié)點(diǎn)為目標(biāo)點(diǎn)。車輛從起點(diǎn)S出發(fā)，并基于當(dāng)前位置的向量SG（當(dāng)車輛行駛至新位置時(shí)，目標(biāo)向量由當(dāng)前節(jié)點(diǎn)與目標(biāo)點(diǎn)構(gòu)成）選擇方向趨近于目標(biāo)點(diǎn)的關(guān)鍵節(jié)點(diǎn)，判定擬選定的關(guān)鍵節(jié)點(diǎn)是否為道路死角關(guān)鍵節(jié)點(diǎn)，如果是，則放棄此節(jié)點(diǎn)，重新選擇其他可行節(jié)點(diǎn)，反之，判斷當(dāng)前節(jié)點(diǎn)至擬選定節(jié)點(diǎn)間搜索域內(nèi)是否存在障礙物，如果不存在，則直接將車輛從當(dāng)前位置節(jié)點(diǎn)移至擬選定關(guān)鍵節(jié)點(diǎn)處，如果存在，則進(jìn)行增量式擴(kuò)展，得到該區(qū)域內(nèi)無碰撞的安全路徑。當(dāng)車輛駛至擬選定關(guān)鍵節(jié)點(diǎn)后，依據(jù)直行優(yōu)先原則，結(jié)合當(dāng)前節(jié)點(diǎn)至目標(biāo)節(jié)點(diǎn)向量進(jìn)行關(guān)鍵節(jié)點(diǎn)選擇，直至到達(dá)目標(biāo)點(diǎn)G，跳出循環(huán)，輸出最終路徑。

圖4 基于目標(biāo)向量的關(guān)鍵節(jié)點(diǎn)選取策略

3.2 改進(jìn)代價(jià)函數(shù)

傳統(tǒng)A*算法的代價(jià)函數(shù)僅考慮當(dāng)前節(jié)點(diǎn)與起始點(diǎn)和目標(biāo)點(diǎn)之間的距離關(guān)系。其中：當(dāng)前節(jié)點(diǎn)與起始節(jié)點(diǎn)之間真實(shí)距離代價(jià)g(N)可使已搜索路徑最優(yōu)，但無法抑制無效節(jié)點(diǎn)擴(kuò)展；當(dāng)前節(jié)點(diǎn)與目標(biāo)節(jié)點(diǎn)之間的預(yù)估代價(jià)h(N)可以有效改善算法節(jié)點(diǎn)擴(kuò)展盲目性，但目標(biāo)趨向也將導(dǎo)致A*算法規(guī)劃路徑過早轉(zhuǎn)折或緊貼障礙物邊界，不利于行車安全。因此，本文結(jié)合地圖預(yù)覽模塊獲得的關(guān)鍵節(jié)點(diǎn)信息和道路邊界信息，對(duì)A*算法進(jìn)行改進(jìn)。

3.2.1 距離表達(dá)函數(shù)

為了適應(yīng)結(jié)構(gòu)化道路特性和無人駕駛汽車運(yùn)動(dòng)學(xué)特性，本文選用Manhattan 函數(shù)計(jì)算當(dāng)前節(jié)點(diǎn)至目標(biāo)節(jié)點(diǎn)的距離[18]。Manhattan 距離是為規(guī)劃方型建筑區(qū)塊的最短行車路徑而提出的，因此采用Manhattan 函數(shù)預(yù)估結(jié)構(gòu)化道路中兩點(diǎn)之間距離更接近真實(shí)值[19]。以圖1為例，節(jié)點(diǎn)S與目標(biāo)點(diǎn)G的距離為：

式中，dM為當(dāng)前節(jié)點(diǎn)與目標(biāo)節(jié)點(diǎn)之間的Manhattan距離；(Sx,Sy)、(Gx,Gy)分別為節(jié)點(diǎn)S和目標(biāo)節(jié)點(diǎn)G的坐標(biāo)。

3.2.2 障礙物判定規(guī)則

無人車在目標(biāo)向量引導(dǎo)下選取下一關(guān)鍵節(jié)點(diǎn)，如圖5所示，車輛在規(guī)劃過程中基于障礙物判定開啟增量式擴(kuò)展搜索。當(dāng)前車輛下一擬選定節(jié)點(diǎn)為節(jié)點(diǎn)N，此時(shí)車輛搜索域?yàn)閳D5 所示的長度為|Nx-Sx|、寬度為5 m（道路寬度）的矩形區(qū)域。其中，Nx為車輛擬選定節(jié)點(diǎn)的橫坐標(biāo)。判斷此區(qū)域是否存在障礙物占據(jù)柵格節(jié)點(diǎn)，如果存在，啟用增量式擴(kuò)展進(jìn)行無碰撞路徑規(guī)劃，反之，直接將車輛移動(dòng)至擬選定節(jié)點(diǎn)N。

圖5 障礙物檢測區(qū)域示意

3.2.3 基于安全距離的碰撞場模型

實(shí)際行駛中，車輛應(yīng)保持足夠的安全距離。根據(jù)本車和前車的運(yùn)行狀態(tài)及相關(guān)因素估算實(shí)施制動(dòng)干預(yù)距離，保證車輛不發(fā)生追尾碰撞[20]。典型的安全距離包括固定安全距離、基于自由滑行時(shí)間的安全距離、基于駕駛員預(yù)估模型的安全距離和基于車間距的安全距離等[21]。本文基于安全距離提出一種新的碰撞場模型，并將其應(yīng)用于代價(jià)函數(shù)改進(jìn)。

本文依據(jù)不同物體特點(diǎn)將障礙物主要分為道路邊界、移動(dòng)概率高但形狀尺寸較小的障礙物和移動(dòng)概率低但形狀尺寸較大的障礙物。其中，道路邊界選用固定距離碰撞場模型。針對(duì)另外兩種類型的障礙物，經(jīng)過對(duì)駕駛員駕乘習(xí)慣的分析，基于車間距模型設(shè)計(jì)，得到一種基于安全距離的碰撞場模型。

基于安全距離的碰撞場模型由車輛當(dāng)前行駛速度、路面附著系數(shù)等參數(shù)共同決定：

式中，ds為不同類型障礙物的安全距離；k為不同類型障礙物的權(quán)重；v為車輛當(dāng)前行駛速度；μ為車輛當(dāng)前所在路面的附著系數(shù)；g=9.8 m/s2為重力加速度；du為單位距離，此處取值為1 m。

其中，不同障礙物類型定義如下：

a.沿道路寬度方向投影長度l∈[1,2)m 的物體，即為形狀尺寸較大的障礙物，如道路側(cè)方的靜止車輛等，其移動(dòng)概率較低，不易突然運(yùn)動(dòng)；

b.l∈(0,1)m的物體，即為形狀尺寸較小的障礙物，如道路邊沿的靜止行人等，其移動(dòng)概率較高，易突然運(yùn)動(dòng)。

經(jīng)過仿真及對(duì)實(shí)際駕駛情況的分析，上述不同類型障礙物安全距離計(jì)算權(quán)重中，形狀尺寸較大的障礙物取值為1.5，形狀尺寸較小的障礙物取值為1.2。如圖6 和圖7 所示分別為不同形狀尺寸的障礙物所對(duì)應(yīng)的碰撞場模型。隨著道路附著系數(shù)的降低和車速的增大，碰撞場距離增長速度呈現(xiàn)由緩及增的趨勢，這與人類駕駛員駕乘習(xí)慣相符。

圖6 形狀尺寸較大的障礙物碰撞場模型

一般路面的附著系數(shù)不小于0.7。由圖6、圖7 可知，當(dāng)路面附著系數(shù)達(dá)到0.7及以上時(shí)，考慮車速最高為20 m/s的情況，形狀尺寸較大的障礙物碰撞場距離最大為44.16 m，形狀尺寸較小的障礙物碰撞場距離最大為35.59 m，符合實(shí)際駕駛工況需求。

圖7 形狀尺寸較小的障礙物碰撞場模型

由ds可求得擴(kuò)展柵格的總層數(shù)c為：

將碰撞場距離重新賦值為10 m×c，并作為擴(kuò)展柵格最內(nèi)層?xùn)鸥翊鷥r(jià)值，依次向外以10 m的倍數(shù)進(jìn)行遞減賦值，如果障礙物擴(kuò)展柵格中包含障礙物柵格，則不對(duì)其進(jìn)行賦值。如圖8所示，當(dāng)車速為10 m/s，路面附著系數(shù)為0.8時(shí)，由式（2）可得ds=8.7 m，由式（3）可得c=1，因此直接將代價(jià)值10 m賦予障礙物邊界外第1層?xùn)鸥瘢浯鷥r(jià)值等同于算法循環(huán)中車輛移動(dòng)1個(gè)柵格距離的代價(jià)值。

圖8 基于碰撞場距離擴(kuò)展柵格

3.2.4 總體代價(jià)函數(shù)

改進(jìn)A*算法代價(jià)函數(shù)為：

式中，o(N)為不同障礙物的碰撞場距離代價(jià)；k1、k2為不同代價(jià)函數(shù)的權(quán)重。

其中k1越大，路徑趨向目標(biāo)點(diǎn)速率越快，計(jì)算耗時(shí)越短，但這將會(huì)影響路徑最優(yōu)性，而k2取值則會(huì)直接影響規(guī)劃路徑與障礙物邊界的距離，進(jìn)而影響車輛行駛安全性。經(jīng)過多次仿真和驗(yàn)證，本文取k1=2、k2=2。

3.3 路徑平滑方式

準(zhǔn)均勻B樣條曲線不僅能夠保證路徑曲率連續(xù)，還能夠滿足路徑的首尾約束，保證擬合路徑部分與原路徑平滑匹配[22]。

設(shè)準(zhǔn)均勻B樣條曲線為：

式中，{P1,P2,…,Pi,…,Pn-1,Pn}(Pi=(xi,yi),i=0,1,2,…,n)為曲線控制點(diǎn)坐標(biāo)序列；{Ni,p(u)}(i=0,1,2,…,n)為非周期且非均勻節(jié)點(diǎn)矢量u=(0,0,0,0,up+1,up+2,…,un+1,un+2,un+2,un+2,un+2)上的p次B樣條基函數(shù)[23]。

將各區(qū)間中整體參數(shù)u所表示的基函數(shù)替換為局部參數(shù)t∈[0,1]，準(zhǔn)均勻三次B 樣條曲線中第i段曲線的矩陣表達(dá)式為：

式中，di、di+1、di+2、di+3為特征多邊形的頂點(diǎn)坐標(biāo)；Mi為p次準(zhǔn)均勻B樣條的系數(shù)矩陣：

其中，mi,j計(jì)算公式為：

本文基于地圖預(yù)覽模塊獲取的道路轉(zhuǎn)向關(guān)鍵節(jié)點(diǎn)和在行駛過程中產(chǎn)生的避障轉(zhuǎn)向節(jié)點(diǎn)進(jìn)行路徑平滑，采用準(zhǔn)均勻三次B 樣條曲線對(duì)相應(yīng)的軌跡進(jìn)行優(yōu)化。如圖9 所示為基于道路轉(zhuǎn)向關(guān)鍵節(jié)點(diǎn)和避障轉(zhuǎn)向節(jié)點(diǎn)進(jìn)行的路徑平滑過程示意。其中，基于道路轉(zhuǎn)向關(guān)鍵節(jié)點(diǎn)進(jìn)行路徑平滑時(shí)，共選用7 個(gè)控制節(jié)點(diǎn)，其位置分別為基于選定的關(guān)鍵轉(zhuǎn)向節(jié)點(diǎn)向兩側(cè)各擴(kuò)展橫向相等間距為1 m的3個(gè)節(jié)點(diǎn)；基于避障轉(zhuǎn)向節(jié)點(diǎn)進(jìn)行平滑時(shí)，以2個(gè)變向節(jié)點(diǎn)為控制點(diǎn)，向前、后兩側(cè)擴(kuò)展橫向相等間距為1 m的3個(gè)節(jié)點(diǎn)。

圖9 路徑平滑方式

乘用車最小轉(zhuǎn)彎半徑通常為4～6 m，一般城市主干道交叉口轉(zhuǎn)彎半徑大于20 m，此處平滑后所生成的路徑既滿足汽車最小轉(zhuǎn)彎半徑約束，也滿足道路交叉口轉(zhuǎn)彎半徑約束。

4 仿真驗(yàn)證

為了驗(yàn)證改進(jìn)A*算法的性能，本文分別將傳統(tǒng)A*算法、Weighted-A*算法和改進(jìn)A*算法應(yīng)用于基于校園地圖所繪制的區(qū)域柵格地圖上。

為驗(yàn)證改進(jìn)算法的泛化能力和改進(jìn)性能，本文采用小區(qū)域低復(fù)雜度場景地圖和大區(qū)域高復(fù)雜度場景地圖進(jìn)行仿真對(duì)比驗(yàn)證。

本文設(shè)定相同的起始點(diǎn)和目標(biāo)點(diǎn)，運(yùn)行后分別記錄不同算法路徑長度la、平均計(jì)算耗時(shí)ta、擴(kuò)展節(jié)點(diǎn)數(shù)量na、轉(zhuǎn)向次數(shù)sa、與道路邊界或其他障礙物邊界的最小距離da（假設(shè)車輛寬度為1.6 m）等參數(shù)。其中Weighted-A*算法啟發(fā)函數(shù)權(quán)重設(shè)為2，經(jīng)仿真驗(yàn)證可知，此時(shí)路徑效果和搜索速度較為均衡。

仿真環(huán)境計(jì)算機(jī)配置為：Windows 10 操作系統(tǒng)，Intel Core i5處理器，主頻為3.0 GHz，運(yùn)行內(nèi)存為8 GB。

4.1 小區(qū)域低復(fù)雜度場景

小區(qū)域低復(fù)雜度場景指不存在其他類型障礙物，且道路結(jié)構(gòu)較簡單的場景。此類環(huán)境下，影響行車安全性和可行性的主要因素為車輛與道路邊界的距離及轉(zhuǎn)向次數(shù)。如圖10 所示，小區(qū)域低復(fù)雜度場景柵格地圖尺寸為30 m×30 m，對(duì)3 種算法設(shè)定相同起始點(diǎn)和目標(biāo)點(diǎn)。A*算法屬于最優(yōu)搜索算法，因此其輸出路徑是唯一的，但受系統(tǒng)測試環(huán)境及硬件性能的綜合影響，計(jì)算耗時(shí)在單次迭代中存在差異，經(jīng)過多次迭代尋路的誤差累積后，最終導(dǎo)致不同測試過程中計(jì)算耗時(shí)出現(xiàn)差異。為消除計(jì)算耗時(shí)的隨機(jī)影響，在相同測試條件下對(duì)不同算法測試50 次，并計(jì)算各算法平均計(jì)算耗時(shí)ta，以充分驗(yàn)證改進(jìn)算法計(jì)算效率。某次規(guī)劃最終結(jié)果如圖10所示。

圖10 小區(qū)域低復(fù)雜度場景下不同算法行駛覆蓋軌跡

由圖10 可知，傳統(tǒng)A*算法和Weighted-A*算法得到的路徑結(jié)果一致，但其行駛覆蓋軌跡，即車輛行駛過程中Z向投影面積移動(dòng)覆蓋區(qū)域，緊貼道路邊沿，且轉(zhuǎn)折較多，并不適用于該場景無人車行駛。由本文改進(jìn)算法得到的路徑不僅能夠遠(yuǎn)離障礙物，同時(shí)能夠盡量保持直行，保證了規(guī)劃路徑的安全性和可行性。

50 次測試計(jì)算耗時(shí)結(jié)果如圖11 所示。由圖11可知，改進(jìn)A*算法在小區(qū)域低復(fù)雜度場景下計(jì)算耗時(shí)相比傳統(tǒng)A*算法明顯縮短，但其與Weighted-A*算法計(jì)算耗時(shí)接近。不同算法的計(jì)算耗時(shí)波動(dòng)范圍均保持在20 ms 范圍內(nèi)，可見改進(jìn)算法的計(jì)算性能較為穩(wěn)定。

圖11 小區(qū)域低復(fù)雜度場景下不同算法計(jì)算耗時(shí)

分別記錄不同算法在50 次測試中的主要參數(shù)如表1 所示。其中改進(jìn)率表示本文改進(jìn)算法與其他算法不同參數(shù)值之差的絕對(duì)值占其他算法該參數(shù)取值的比例。

表1 小區(qū)域低復(fù)雜度場景下不同算法測試結(jié)果

由表1 可知，在小區(qū)域低復(fù)雜度場景下，本文算法擴(kuò)展節(jié)點(diǎn)數(shù)量相對(duì)傳統(tǒng)A*算法和Weighted-A*算法大幅減少，但本文算法引入循環(huán)判斷，因此計(jì)算耗時(shí)相比Weighted-A*算法提升效果并不明顯，僅提升8.3%。本文改進(jìn)A*算法相對(duì)傳統(tǒng)A*算法和Weighted-A*算法轉(zhuǎn)折次數(shù)更少，路徑與不同類型障礙物邊界的最小距離也足以保障行車安全性。綜上所述，本文改進(jìn)算法的效果更加突出。

如圖12所示為本文算法經(jīng)過路徑平滑處理后得到的優(yōu)化路徑，以微分的方法計(jì)算規(guī)劃路徑的曲率，得到此環(huán)境下路徑最小曲率半徑為6.5 m，滿足車輛最小轉(zhuǎn)彎半徑約束，同時(shí)全路徑曲率保持連續(xù)。為進(jìn)一步判斷平滑后路徑的性能，對(duì)平滑路徑與未平滑路徑之間的偏離量及平滑路徑與道路邊界的距離最小值分別進(jìn)行計(jì)算。由路徑平滑方式可知，平滑路徑在曲率最大處與未平滑路徑偏離量最大，最大值為1.41 m，此時(shí)，其與道路邊界最小距離為1.32 m。綜上可知，平滑后的路徑不僅滿足車輛的運(yùn)動(dòng)學(xué)約束，同時(shí)仍能夠與道路邊界保持足夠的安全距離，可見其相比未平滑路徑更適合車輛的穩(wěn)定控制[24]。

圖12 本文改進(jìn)A*算法平滑路徑

4.2 大區(qū)域高復(fù)雜度場景

為進(jìn)一步驗(yàn)證本文算法在大區(qū)域高復(fù)雜度場景下的性能，選擇存在道路死角節(jié)點(diǎn)和不同類型障礙物的大尺寸柵格地圖進(jìn)行仿真。此類環(huán)境中影響行車安全性和可行性的主要因素為車輛與道路邊界及不同類型障礙物邊界的距離及轉(zhuǎn)向次數(shù)。大區(qū)域高復(fù)雜度場景柵格地圖尺寸為450 m×200 m，各算法某次規(guī)劃結(jié)果如圖13所示。

由圖13 可知，傳統(tǒng)A*算法和Weighted-A*算法在大區(qū)域高復(fù)雜度場景下，路徑多轉(zhuǎn)折、緊貼障礙物等問題更加突出，無法保證行車過程的安全性和可行性。但本文改進(jìn)A*算法規(guī)劃的路徑不僅能夠與道路邊界保持一定距離，而且在應(yīng)對(duì)不同類型障礙物時(shí)能夠基于碰撞場模型進(jìn)一步規(guī)劃出更加安全可靠的避障路徑，改進(jìn)A*算法的綜合優(yōu)勢更加明顯。

50 次測試的計(jì)算耗時(shí)結(jié)果如圖14 所示。改進(jìn)A*算法在大區(qū)域高復(fù)雜度場景下計(jì)算耗時(shí)相比傳統(tǒng)A*算法和Weighted-A*算法明顯縮短。

圖14 大區(qū)域高復(fù)雜度場景下不同算法計(jì)算耗時(shí)

不同算法測試參數(shù)如表2所示，由圖2可知：在大區(qū)域高復(fù)雜度場景下，本文算法擴(kuò)展節(jié)點(diǎn)數(shù)量相對(duì)傳統(tǒng)A*算法和Weighted-A*算法大幅減少，計(jì)算耗時(shí)明顯縮短；本文改進(jìn)A*算法相對(duì)傳統(tǒng)A*算法和Weighted-A*算法轉(zhuǎn)折次數(shù)更少，路徑與不同類型障礙物邊界的最小距離也足以保障行車安全。

表2 大區(qū)域高復(fù)雜度場景下不同算法測試結(jié)果

如圖15所示為本文算法經(jīng)過路徑平滑處理后得到的優(yōu)化路徑，以微分方法計(jì)算規(guī)劃路徑的曲率，得到此環(huán)境下路徑最小曲率半徑為6.2 m，滿足車輛最小轉(zhuǎn)彎半徑約束，同時(shí)全路徑曲率保持連續(xù)。對(duì)車輛平滑及未平滑路徑之間的偏離度和平滑路徑與道路邊界的最小距離進(jìn)行測量，測量結(jié)果同小區(qū)域場景，可見平滑路徑有利于車輛的穩(wěn)定控制。

圖15 本文改進(jìn)算法平滑路徑

5 結(jié)束語

本文針對(duì)傳統(tǒng)A*算法的缺陷進(jìn)行了改進(jìn)，通過地圖模塊的應(yīng)用、基于安全距離的碰撞場模型的引入以及三次準(zhǔn)均勻B樣條曲線路徑平滑方式，改善了算法的計(jì)算效率、可行性及安全性。

由于本文算法主要針對(duì)低速結(jié)構(gòu)化道路場景進(jìn)行路徑規(guī)劃，同時(shí)，搜索過程中僅考慮了單向行駛和靜態(tài)障礙物，因此改進(jìn)算法對(duì)高度復(fù)雜交互類交通區(qū)域仍無法適應(yīng)。本文后續(xù)研究的重點(diǎn)是基于交通規(guī)則、駕駛行為的進(jìn)一步探索和針對(duì)高速行駛等復(fù)雜動(dòng)態(tài)工況的適應(yīng)性研究[25-27]。