基于改進A*算法的智能車路徑規劃研究

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

摘 要：針對智能車使用A*路徑規劃算法存在轉折點和冗余點的問題，提出一種考慮智能車靜態特性的改進A*路徑規劃算法。在已知靜態環境信息的柵格地圖上，考慮到智能車自身存在實際寬度，對障礙物進行膨脹擴展;其次根據路徑上前后節點相對方向的改變提取必要的轉折點，并依次連結前后轉折點，若轉折點連線不經過障礙物，刪除連結轉折點之間冗余的轉折點;重復上述操作，直至所有冗余點被刪除，保留關鍵轉折點。仿真結果表明，該方法可以實現車輛安全無碰撞地到達目標終點。關鍵詞：路徑規劃;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

前言

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

1 A*算法介紹

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

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

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

2 改進A*算法

2.1 障礙物膨脹

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

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

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

2.2 軌跡平滑

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

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

3 仿真實驗與結果分析

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

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

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

4 結論

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

參考文獻

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

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

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

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

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

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

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