基于改進A星算法的無人車路徑規劃研究

繆殷俊　施衛

關鍵詞：無人車避障路徑規劃；改進Ａ星算法；關鍵節點優化

中圖分類號：TP301 文獻標識碼：A

文章編號：1009-3044（2024）03-0004-04

0 引言

路徑規劃是無人車智能駕駛技術中非常核心的一門技術[1]，無人車需要按照預定的地圖到達指定目的地，在相對應的地圖上進行路徑規劃，需要相應的路徑規劃算法，而常用的全局路徑規劃算法有很多種，比如：Dijkstra算法[2]、A星算法[3]、蟻群算法[4]等。其中，A星算法是一種較經典啟發式搜索算法，被廣泛應用在全局路徑規劃中[5]。傳統的A星尋路算法是用于解決靜態環境中最優路徑的直接搜索算法，其廣泛應用于室內無人車路徑搜索，是在Dijkstra算法的基礎上結合了廣度優先搜索算法（BFS）[6]。因此，為了能使無人車在柵格化的電子地圖中規劃出較優的路徑，以安全高效的速度抵達目標點，本文提出了一種基于優化改進A星算法的路徑規劃算法，具體的，優化改進的過程如下：首先，對傳統的A星算法進行改進，對A星算法的評價函數進行改進，優化啟發函數h（n）加入權重系數，使得搜索效率提高，搜索鄰域優化，優化搜索方向將多余的搜索方向剔除以減少遍歷節點數目，提高搜索效率，其次，對關鍵節點進行優化處理，刪除多余節點，減少路徑上的冗余節點和轉折點，提高算法的運行效率，提高路徑的平滑度，然后，對柵格地圖進行優化，將地圖中的障礙物進行膨脹處理，提高安全性能，并將優化后的算法與原先的算法進行實際分析比較，最終實現無人車的路徑規劃。

1 優化A星算法

1.1 環境地圖構建

在對無人車進行全局路徑規劃時，首先需要建立一個可以完整表達地圖環境信息的環境地圖，然后在構建好的環境地圖上規劃出一條滿足要求的最優路徑。而在常用環境地圖構建的方法中，一般采用柵格地圖，因為柵格地圖具有簡單有效、易于實現的特點，而且可以通過改變柵格大小來改變環境的分辨率，也可以展示出各種不同形狀，大小的障礙物。

本文采用柵格法進行環境地圖的構建，構建的柵格地圖如圖1所示。

如圖1所示，構建一個大小為10×10的柵格地圖，在圖中標注出無人車的起始點s，目標點g。

1.2 傳統A星算法

傳統的A星算法基于代價函數在電子地圖中規劃全局路徑，是最有效的求解全局路徑的啟發式搜索方法，是貪心算法和Dijkstra算法的結合[7]，其基本的表達式為：

f （n） = g （n） + h （n） （1）

式中：f（n）表示為當前節點的總代價，g（n）當前節點與起點的實際代價，h（n）為當前節點距離目標節點的預估代價。

啟發函數h（n）的選擇對于A星算法的搜索效率有著重要的影響。通常啟發函數h（n）的選擇有曼哈頓距離、歐幾里得距離、切比雪夫距離3種。

歐幾里得距離是這3種距離當中運算量最大的，但是求得的路徑質量是最好的，所以本文采用歐幾里得距離來計算節點的估計代價h（n），歐幾里得距離的公式為：

傳統A星算法的基本步驟如下：

第1步：建立open列表與close列表，將起點放入open列表中，close列表為空。

第2步：遍歷起點周圍的節點，計算出他們的評價函數f，將它們放入open列表中，將open列表中評價函數f最小的節點從open列表中移除，并將其加入close 列表中。如果open列表中沒有節點，則尋路失??；如果當前節點為終點，則尋路結束，并將終點的前置節點設置為當前節點，然后返回由當前節點到起點的路徑。

第3步：遍歷當前節點的周圍節點。如果鄰接點在close列表中，則不作處理；若有鄰接點為障礙物，則不予考慮；如果鄰接點不在open列表中，則更新其評價函數中的g（n），h（n），并計算出評價函數f（n），再將其放入open列表中；如果鄰接點已經在open列表中，則比較從當前節點到這個鄰接點的實際損耗g（n）是否比這個點原來的實際損耗g（n）更優，如果不更優，則不作處理；如果更優，則將鄰接點的實際損耗g（n）更新為更優值，并將鄰接點現在的評價函數f（n）取代之前的f（n）。

第4步：回到第3步，繼續處理當前節點周圍的下一個鄰接點。

第5步：重復以上步驟，直至擴展到目標節點或open列表為空，若非空，則回到第2步繼續循環，最終將close列表中的節點依次連接，生成路徑。

傳統A*算法流程圖如圖2所示。

1.3 優化啟發函數

傳統A星算法存在一些問題，比如：冗余節點過多，存在重復訪問不必要節點的情況；路徑不平滑問題，會產生較多的轉折點，降低了路徑的順滑度；搜索范圍較大，出現不必要的搜索范圍，降低搜索速度；最終規劃出的路線不太符合實際用途，與障礙物距離較近，易發生事故風險。因此，本文采用動態權重的方法，通過動態調整啟發函數的權重系數來提高搜索效率，提高算法的地圖適應性。

h（n）的選取是規劃最優路徑的關鍵[8]，若h（n）小于g（n），雖然此時的路徑是最小代價路徑，但是搜索節點會變多，范圍會變大，搜索時間變長，效率低下；若h（n） 大于g（n），則搜索的速度會大幅提升，但此時的路徑可能不是最優解；因此考慮在初期增加h（n）值，提高搜索速度；當當前節點的位置接近終點時，實際代價值g（n） 與估計代價值h（n）大小接近，此時的執行效率處在最優的情況；當障礙物數量占比較多時，動態減小搜索速度，確保尋得路徑的精度，提高安全性能，通過減少h（n）的權重系數來處理。當障礙物占比較少時，應加快搜索速度，如果按照傳統A星算法的h（n）尋找最優路徑，會導致搜索節點過多，搜索效率降低，此時加大h（n）的權重系數。因此，改進后的啟發函數如式（3） 所示：

式中，P 表示起始點與目標點之間的障礙率，d 為此時所在節點n 距離目標點的長度；D 為起始點距離目標點的距離長度。

圖3為采用傳統A星算法規劃的路徑和遍歷的節點。

1.4 搜索鄰域優化

傳統的A星算法在進行相應的節點搜索時會擴展以當前節點為中心的相鄰8個柵格[9]，如圖4所示，節點1～8為當前可探索的所有節點方向，因為在實際的無人車運動時，目標點的方位已經確定了，在知曉目標點方位的情況下，如果還對八個方向都進行相應的節點搜索就會花費更多時間，遍歷更多的節點，導致搜索效率的下降，在實際的搜索過程當中，有些方向是根本運用不到的，需要將這些多余的方向剔除掉。根據上述問題，本文提出一種根據目標點的方位，在搜索過程中只使用其中的5個方向的方法，假設目標點與當前節點的連線與節點2的指示方向的夾角度數為θ，則保留與舍棄方向的規則如表1所示。

1.5 優化關鍵節點

由圖3可知，本文的傳統的A星算法在路徑規劃的過程中會產生有較多的轉折點，轉折點越多，則越不利于無人車的運動，無人車的工作效率就會降低，并且容易出現與障礙物發生碰撞、刮蹭的行為。針對上述的問題，本文將對關鍵節點進行優化提取，將路徑規劃過程中的拐點數目減少，優化關鍵節點的相關步驟如下：

第1步：在算法遍歷節點的過程中會得到相應的節點，節點數目為n₁，n₂，…，n_z個，設立一個集合U用于存放全部遍歷的節點，集合V用于存放關鍵節點。將得到的全部節點都存入到節點集U{n_i，1≤i≤z}，其中n₁表示路徑的起點，n_z表示路徑的終點。將關鍵節點集V進行相應的初始化，以滿足后面的應用需求，關鍵節點集V中存入起點n₁和終點n_z。

第2步：將n1依次與n₂，n₃，n₄，…，nm連接，判斷連接之后所產生的線路是否出現穿過障礙物的情況，當n₁nm是第一條穿過障礙物的直線，則n_m的前一個節點n_m-1作為路徑優化過程中的關鍵節點，將節點n_m-1添加到關鍵節點集V中，并且將n₁與n_m-1之間的節點判定為冗余節點。隨后以同樣的方式進行判斷，即從n_m開始依次連接后面的節點，并判斷是否穿過障礙物，如果穿過就按照之前的處理步驟，將穿過障礙物的點的前一個節點設置為關鍵節點，并存入關鍵節點集V 中，一直到連接到終點n_z結束。

第3步：步驟二中得到了路徑中的所有關鍵節點，將這些關鍵節點依次連接起來，最終所得到的路徑即為提取關鍵節點后的路徑。

圖5為優化示例圖：

1.6 障礙物膨脹處理

通過觀察圖3的傳統A星算法路徑規劃圖可以發現，在經過一些障礙物時，傳統A星算法是貼著障礙物的邊緣走的，這顯然不符合無人車實際運動要求，因為無人車本身存在自身寬度，在路徑規劃過程中，按照一般路徑規劃算法所規劃出的路徑有時會出現無人車與障礙物發生碰撞、刮蹭的情況，所以需要先對障礙物進行膨脹處理，膨脹范圍為無人車的車身寬度d。在路徑規劃完之后再將障礙物縮小成原來的大小，從而很好地避免在無人車運動拐彎的時候與障礙物發生碰撞、刮蹭的情況，圖6為障礙物膨脹處理示意圖。

2 仿真實驗與分析

2.1 改進A 星算法仿真分析

仿真實驗在MATLAB R2022B環境下進行，為驗證改進后算法的有效性以及適應性。分別采用傳統A星算法與優化改進后的A星算法進行路徑規劃實驗分析，為了保證有較好的對比效果，改進Ａ星算法的仿真結果如圖7所示，傳統A星算法與改進優化后的A星算法的對比圖，如圖8所示，傳統A星算法與改進優化后的A星算法的數據性能比較如表2所示。

由表2中的實驗數據可知，經過改進優化后的A 星算法與傳統A星算法的路徑相比要更優，算法的探索規劃時間更短，速度更快，相比于傳統的A星算法的規劃時間結果，改進優化后的A星算法的規劃時間減少了28.25%，遍歷節點總數減少了27.12%，路徑長度從14.188 6縮短到了14.071 1，優化了0.83%；拐點數從5次變為了3次，優化了40%。

因此，本文的改進A星算法可以提高傳統A星算法的效率。

3 結束語

本文主要針對傳統A星算法的路徑規劃過程中出現的一些問題進行優化處理，比如：拐點過多、冗余節點多、容易發生碰撞、效率低，路徑非最優解。本文對傳統的A星算法進行改進。在全局路徑規劃方面，首先，通過對h（n）進行改進加入權重系數，然后，對搜索鄰域進行優化，剔除多余的方向，其次，使用關鍵點提取策略去除冗余節點，最后，對路徑過程中的障礙物進行膨脹處理以避免無人車在路徑規劃中過度靠近障礙物產生碰撞風險。通過對傳統A星算法與優化改進后的A星算法進行仿真實驗分析，并對實驗數據進行相應的比較，驗證出本文改進優化后的A星算法的性能相比于傳統的A星算法要更好，路徑搜索的效率更高。但是只做全局路徑規劃還是不夠的，即使應用在無人車上也不能很好地保障實際運行過程中的安全、高效。今后筆者將考慮局部路徑規劃的問題，對局部路徑規劃進行相應的算法優化，將優化后的局部路徑規劃算法與優化改進后的A星算法進行融合，并進行相應的實驗分析，以進一步驗證該優化融合之后的算法在實際場景中進行路徑規劃時的有效性。

【通聯編輯：唐一東】