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

摘 要：針對智能車使用A*路徑規(guī)劃算法存在轉折點和冗余點的問題，提出一種考慮智能車靜態(tài)特性的改進A*路徑規(guī)劃算法。在已知靜態(tài)環(huán)境信息的柵格地圖上，考慮到智能車自身存在實際寬度，對障礙物進行膨脹擴展;其次根據(jù)路徑上前后節(jié)點相對方向的改變提取必要的轉折點，并依次連結前后轉折點，若轉折點連線不經(jīng)過障礙物，刪除連結轉折點之間冗余的轉折點;重復上述操作，直至所有冗余點被刪除，保留關鍵轉折點。仿真結果表明，該方法可以實現(xiàn)車輛安全無碰撞地到達目標終點。關鍵詞：路徑規(guī)劃;A*算法;障礙物膨脹;軌跡平滑中圖分類號：V323.19? 文獻標識碼：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)外學者和各大汽車廠商研究的熱點和重點。導航是智能車非常重要的功能模塊，路徑規(guī)劃技術作為導航的基礎和關鍵^[1，2]，直接影響著智能車行進中的安全避障性和快速通過性。早期的路徑規(guī)劃技術主要針對移動機器人進行主要研究，最常見的路徑規(guī)劃算法主要分為兩類，一類是基于節(jié)點搜索的以A*算法和Dijkstra算法為代表的傳統(tǒng)路徑規(guī)劃算法^[3，4]，一類是基于遺傳式的以蟻群算法和粒子群算法為代表的智能路徑規(guī)劃算法^[5，6]。在全局靜態(tài)路徑規(guī)劃領域，傳統(tǒng)的A*算法具有計算量小、搜索精度高等優(yōu)點，將移動機器人作為質(zhì)點完成路徑規(guī)劃，卻無法滿足智能車在實際導航中的綜合需求，存在忽略智能車自身靜態(tài)特性與動態(tài)特性的問題。為了解決傳統(tǒng)算法不適用于智能車路徑規(guī)劃的問題，本文在已有研究的基礎上提出一種考慮智能車靜態(tài)特性的改進A*算法。

1 A*算法介紹

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

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

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

2 改進A*算法

2.1 障礙物膨脹

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

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

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

2.2 軌跡平滑

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

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

3 仿真實驗與結果分析

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

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

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

4 結論

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

參考文獻

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

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

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

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

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

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

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