基于改進(jìn)A*算法的智能車路徑規(guī)劃研究

沈剛　邵金菊　譚德榮　牛亞明　馬曉田

摘 要：針對智能車使用A*路徑規(guī)劃算法存在轉(zhuǎn)折點和冗余點的問題，提出一種考慮智能車靜態(tài)特性的改進(jìn)A*路徑規(guī)劃算法。在已知靜態(tài)環(huán)境信息的柵格地圖上，考慮到智能車自身存在實際寬度，對障礙物進(jìn)行膨脹擴(kuò)展;其次根據(jù)路徑上前后節(jié)點相對方向的改變提取必要的轉(zhuǎn)折點，并依次連結(jié)前后轉(zhuǎn)折點，若轉(zhuǎn)折點連線不經(jīng)過障礙物，刪除連結(jié)轉(zhuǎn)折點之間冗余的轉(zhuǎn)折點;重復(fù)上述操作，直至所有冗余點被刪除，保留關(guān)鍵轉(zhuǎn)折點。仿真結(jié)果表明，該方法可以實現(xiàn)車輛安全無碰撞地到達(dá)目標(biāo)終點。關(guān)鍵詞：路徑規(guī)劃;A*算法;障礙物膨脹;軌跡平滑中圖分類號：V323.19? 文獻(xiàn)標(biāo)識碼：B ?文章編號：1671-7988（2020）02-28-03

Abstract： In order to solve the problem of turning points and redundant points in using A* path planning algorithm for intelligent vehicles， an improved A* path planning algorithm considering the static characteristic of intelligent vehicles is proposed. On the grid map with known static environmental information， considering the actual width of the intelligent vehicle itself， the obstacles are expanded. Secondly， the necessary turning points are extracted according to the change of the relative direction of the front and rear nodes on the path， and the front and rear turning points are connected in turn. If the turning points are connected without passing through the obstacles， the redundant turning points between the turning points are deleted. Repeat the above operations until all redundant points are deleted and key turning points are reserved. The simulation results show that the method can ensure the vehicle to reach the destination safely without collision.Keywords： Path Planning; A* Algorithm; Obstacles Expansion; Track SmoothingCLC NO.： V323.19? Document Code： B ?Article ID： 1671-7988（2020）02-28-03

前言

近年來，智能車越來越成為國內(nèi)外學(xué)者和各大汽車廠商研究的熱點和重點。導(dǎo)航是智能車非常重要的功能模塊，路徑規(guī)劃技術(shù)作為導(dǎo)航的基礎(chǔ)和關(guān)鍵^[1，2]，直接影響著智能車行進(jìn)中的安全避障性和快速通過性。早期的路徑規(guī)劃技術(shù)主要針對移動機(jī)器人進(jìn)行主要研究，最常見的路徑規(guī)劃算法主要分為兩類，一類是基于節(jié)點搜索的以A*算法和Dijkstra算法為代表的傳統(tǒng)路徑規(guī)劃算法^[3，4]，一類是基于遺傳式的以蟻群算法和粒子群算法為代表的智能路徑規(guī)劃算法^[5，6]。在全局靜態(tài)路徑規(guī)劃領(lǐng)域，傳統(tǒng)的A*算法具有計算量小、搜索精度高等優(yōu)點，將移動機(jī)器人作為質(zhì)點完成路徑規(guī)劃，卻無法滿足智能車在實際導(dǎo)航中的綜合需求，存在忽略智能車自身靜態(tài)特性與動態(tài)特性的問題。為了解決傳統(tǒng)算法不適用于智能車路徑規(guī)劃的問題，本文在已有研究的基礎(chǔ)上提出一種考慮智能車靜態(tài)特性的改進(jìn)A*算法。

1 A*算法介紹

A*算法是一種標(biāo)準(zhǔn)的靜態(tài)全局路徑尋優(yōu)算法，其關(guān)鍵在于評價函數(shù)的選取^[7]。通過對環(huán)境地圖中初始位置到目標(biāo)位置進(jìn)行代價估計，對比選擇最優(yōu)的搜索方向，直至搜尋到目標(biāo)位置，從而回溯到起始位置形成最終的全局最優(yōu)路徑。其估價函數(shù)可以表示為：

式中f（n）為初始節(jié)點到目標(biāo)節(jié)點的代價估計函數(shù)，g（n）為狀態(tài)空間中從初始節(jié)點到當(dāng)前節(jié)點n的實際代價，h（n）為從當(dāng)前節(jié)點n到目標(biāo)節(jié)點路徑最優(yōu)的代價估計。若啟發(fā)式函數(shù)h（n）為0時，估價函數(shù)則完全由實際代價函數(shù)g（n）來決定，類似于廣度優(yōu)先搜索算法。相反若不考慮實際代價，即當(dāng)g（n）為0時，估計代價決定整個規(guī)劃路徑代價，此時類似于深度優(yōu)先搜索算法。因此A*算法也可以稱為是優(yōu)化版的盲目搜索算法，結(jié)合了廣度優(yōu)先搜索算法和深度優(yōu)先搜索算法各自的優(yōu)點。A*算法執(zhí)行步驟如下流程圖所示：

A*算法中估價函數(shù)的選取對最優(yōu)路徑的選擇至關(guān)重要，如果估計函數(shù)選取不當(dāng)會造成路徑搜索非最優(yōu)且效率低下。只有估計代價值和實際代價值接近時，估價函數(shù)的選取才更準(zhǔn)確高效，基于這些選擇兩點間的曼哈頓距離作為函數(shù)估計值。

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

2.1 障礙物膨脹

A*算法規(guī)劃的最優(yōu)路徑能夠確保智能車沿著路徑快速、準(zhǔn)確地到達(dá)目標(biāo)終點。但是傳統(tǒng)路徑規(guī)劃算法以移動機(jī)器人作為運動目標(biāo)，這種情況下移動機(jī)器人本身作為質(zhì)點，不會考慮運動對象的靜態(tài)特征，忽略了運動對象的長、寬、高等外部特征，在這種情況下運動對象與障礙物任何時刻都沒有碰撞風(fēng)險，如圖2所示。

智能車作為特殊的運動體，它所處的行駛環(huán)境十分復(fù)雜多變，行駛路徑周圍必然存在很多固定的障礙物。如果通過算法規(guī)劃出的路徑緊貼障礙物，那么當(dāng)智能車沿著路經(jīng)到達(dá)障礙物拐角處，由于智能車自身存在不可忽略的長度與寬度，會導(dǎo)致智能車與障礙物發(fā)生碰撞，如圖3所示。

針對上述問題，本文將靜態(tài)地圖中的障礙物進(jìn)行膨脹處理?？紤]到智能車與移動機(jī)器人的差異性，智能車自身存在相對于路徑與障礙物不可忽略的長度和寬度，由于一般車輛的長度在4.7米左右，寬度在1.8米左右，因此將障礙物膨脹半徑設(shè)定為智能車寬度的一半左右，同時為提高安全性設(shè)定為1米，這樣智能車在道路行進(jìn)過程中規(guī)劃出的路徑與障礙物的最小距離大于車輛寬度的一半，可以確保可通行路段寬度至少大于車輛的寬度，使車輛安全無碰撞地通過。

2.2 軌跡平滑

A*算法是按照分層遍歷的方法規(guī)劃最優(yōu)路徑，不可避免的會導(dǎo)致規(guī)劃路徑中包含很多冗余的轉(zhuǎn)折點，對于智能車在實際道路行駛中后續(xù)的局部路徑規(guī)劃十分不利，增加計算量?；诖藛栴}本文首先選擇提取轉(zhuǎn)折點。在規(guī)劃的路徑中，從起始點開始，根據(jù)坐標(biāo)判斷第二個節(jié)點相對于起點的方向，然后向該方向延伸，直到路徑上的節(jié)點開始轉(zhuǎn)向，偏離初始方向。此時保留轉(zhuǎn)折點和起點，刪除中間的冗余點。例如，若起點的坐標(biāo)為（2，2），第二個節(jié)點的坐標(biāo)為（2，5），則可以判斷第二個節(jié)點以后的節(jié)點橫坐標(biāo)即可，直到該節(jié)點的橫坐標(biāo)不是2為止，將其前一個節(jié)點作為轉(zhuǎn)折點。繼續(xù)重復(fù)上述步驟，從新的轉(zhuǎn)折點開始尋找下一個轉(zhuǎn)折點，直到路徑結(jié)束。

由于提取出所有的轉(zhuǎn)折點后仍然存在多余的轉(zhuǎn)折點，這些轉(zhuǎn)折點周圍有可能不存在實際的障礙物，因此有必要剔除它們。假設(shè)提取轉(zhuǎn)折點后的路徑點為，連接P₁P₃，若P₁P₃不經(jīng)過障礙物，則說明它們之間的P₂為多余的轉(zhuǎn)折節(jié)點，可以刪除后繼續(xù)連接P₁P₄;若連接P₁P₃經(jīng)過障礙物則繼續(xù)連接P₂P₄，重復(fù)上述步驟，直到刪除所有冗余點，保留路徑上的關(guān)鍵轉(zhuǎn)折點。

3 仿真實驗與結(jié)果分析

為了驗證改進(jìn)A*路徑規(guī)劃算法的有效性，本文選擇在基于MATLAB r2016a的20×20的平面柵格地圖上進(jìn)行仿真實驗。智能車的寬度設(shè)定為1.5m，實驗起點設(shè)為（1.5，2），終點設(shè)為（18，19），共計進(jìn)行四組實驗。如圖3所示。第一組實驗為通過標(biāo)準(zhǔn)A*算法所得的最優(yōu)路徑，從圖中可以發(fā)現(xiàn)該

路徑基本可以實現(xiàn)智能車以較短的距離從起點行駛到終點;第二組實驗為障礙物經(jīng)過膨脹處理后的路徑規(guī)劃，從圖中可以發(fā)現(xiàn)規(guī)劃出的路徑與障礙物保持基本的安全距離，可以確保智能車通過障礙物拐角時不發(fā)生碰撞;第三組和第四組實驗分別是提取關(guān)鍵轉(zhuǎn)折點和剔除冗余轉(zhuǎn)折點后平滑軌跡所得到的最優(yōu)路徑，比較分析可以發(fā)現(xiàn)在路徑平滑處理之后智能車的規(guī)劃路徑更加平順，可以確保智能車快速平穩(wěn)通過。

仿真實驗結(jié)果顯示，改進(jìn)A*算法能夠規(guī)劃出智能車全局最優(yōu)路徑，且行駛距離最短，行駛路徑最為平順，符合智能車行駛過程中的快速到達(dá)要求與安全避障要求。

4 結(jié)論

本文針對現(xiàn)有A*算法全局路徑規(guī)劃的不足提出了一種考慮智能車靜態(tài)特性的優(yōu)化A*算法進(jìn)行路徑規(guī)劃。首先在原有已知靜態(tài)柵格地圖中將障礙物進(jìn)行膨脹處理使車輛在實際行駛時與障礙物保持安全距離避免碰撞，在此基礎(chǔ)上針對規(guī)劃路徑存在較多冗余轉(zhuǎn)折點的問題進(jìn)行關(guān)鍵轉(zhuǎn)折點選取和冗余點剔除處理，確保智能車路徑規(guī)劃更加平穩(wěn)、高效。仿真結(jié)果表明優(yōu)化A*算法在智能車全局路徑規(guī)劃中效果顯著，對于車輛智能導(dǎo)航與安全避障方面具有重要的作用。

參考文獻(xiàn)

[1] 龍卓群，吳超，雷日興.移動機(jī)器人躲避多靜態(tài)障礙物路徑智能規(guī)劃方法[J].自動化與儀器儀表，2018（10）：178-181+184.

[2] 龍卓群，雷日興.移動機(jī)器人全覆蓋路徑規(guī)劃算法研究[J].自動化與儀器儀表，2018（09）：15-17.

[3] 趙曉，王錚，黃程侃等.基于改進(jìn)A*算法的移動機(jī)器人路徑規(guī)劃[J].機(jī)器人，2018，40（06）：903-910.

[4] 張希聞，肖本賢.改進(jìn)D～*算法的移動機(jī)器人路徑規(guī)劃[J].傳感器與微系統(tǒng)，2018，37（12）：52-54+58.

[5] 孫海洋，夏慶鋒，楊冠男等.基于改進(jìn)蟻群算法的機(jī)器人路徑規(guī)劃方案研究[J].軟件導(dǎo)刊，2018，17（09）：22-24.

[6] 王慧，王光宇，潘德文.基于改進(jìn)粒子群算法的移動機(jī)器人路徑規(guī)劃[J].傳感器與微系統(tǒng)，2017，36（05）：77-79.

[7] 吳麒麟，楊俊輝，汪若塵等.基于混合SA算法的智能汽車全局路徑規(guī)劃[J].江蘇大學(xué)學(xué)報（自然科學(xué)版），2019，40（03）：249-254.