基于A*算法與人工勢場法無人車路徑規劃的改進探索

張皞宇 楊劉一 陳旭淼

摘要：針對靜態地圖全局路徑規劃問題提出了一種改進的A*算法。根據激光雷達掃描從而獲取地圖數據再建立柵格地圖環境模型，再使用A*算法進行初步的路徑規劃。其次，針對A*算法規劃的路徑靠近障礙物以及轉向角度偏大的缺陷，提出將A*算法與人工勢場法相結合，在行駛階段中通過建立車輛與障礙物之間的斥力場使得行駛路徑遠離障礙物。當目標車輛行駛到一定范圍內，通過人工勢場法的引導將車輛準確引導至目標地點，同時解決轉折角度過大等問題，讓車輛的行駛路線更加平滑，經仿真實驗，測試和證實了本文算法的可行性。

關鍵詞：A*算法;人工勢場法;路徑規劃

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

文章編號：1009-3044（2021）17-0233-03

開放科學（資源服務）標識碼（OSID）：

1 引言

避障路徑規劃和跟蹤控制是智能車輛研究領域的熱點之一，其中避障路徑規劃經過多年的發展，已經積累了許多的研究成果，包括A*、蟻群算法、人工勢場法，多項式規劃等[1]。

A*算法通過啟發函數能夠快速鎖定目標方向進行路徑規劃。能在已知地圖中有效地規劃最優路徑，但實際導航中需與局部規劃算法結合[2]。

傳統的A*算法中有依舊存在如：路徑緊貼障礙物和轉向角度過大和不滿足車輛運動學等問題[3]。

針對上述問題，本文通過對傳統A*實施改進，加入了人工勢場法并對車輛模型進行簡化，通過人工勢場法的引力場的引力得出汽車的目標姿態角，從而改進傳統A*算法中的轉向角過大的問題。同樣對障礙物與目標車輛附加了斥力場，通過人工勢場法中斥力場的作用解決了路徑緊貼障礙物的問題。

2 A*算法與人工勢場法

2.1 A*算法

A*算法是一種典型的啟發式搜索計算方式，其中可在一定程度上避免無效搜索路徑，有較好的搜索效率。在深度優先、廣度優先和最佳優先3種啟發式搜索算法中，A*算法歸屬于最佳優先類。在A*中通過評估函數進行引導搜索與決定的方向。其公式表示為：

[f（n）=g（n）+h（n）]? ? ? ? ? ? ? ? ? ? ? ? ? （1）

[f（n）]表示從起始點到目標點的估價函數;[g（n）]是在從起始點到節點[n]的移動代價;[h（n）]是從節點[n]到目標節點估計代價，通過上述函數可以得到每個函數的價值，通過選取價值最低的節點來進行最優節點的選取，從而直接決定了算法能否進行最優路徑的查找。

2.2 人工勢場法

人工勢場法是由Khatib提出，通過設置假想力的概念促使目標進行移動[4]。該方法將控制對象、目標點、障礙物看作質點，目標點對控制對象形成引力場，障礙物對控制對象形成斥力場。通過產生的引力場與斥力場的合力從而引導控制對象的行動。此過程是將控制對象在實際環境中的運動過程虛擬為電荷在受力場中的運動。

同樣，在駕駛環境中，不可通過的部分設置為與控制對象相同的電荷，即可產生斥力場，可以在目標地點設置相反電荷來形成引力場。由此來控制目標的行走路徑。有著結構簡單，實時性強，規劃路徑簡單且路徑平滑等優點。

3 本文算法

3.1.環境模型

在小車機器人工作中，對地圖的構建是關鍵。在通過URG-04LX-UG01激光雷達掃描得到數據，規劃由本算法過柵格地圖的方式進行表現，通過柵格法將小車可通過的區域和不可通過的區域在柵格地圖中做出呈現。

在算法中每個柵格的狀態位兩種分別為可通過與不可通過。在算法中分別由0與1進行表示。在柵格地圖中分別由白色（可通過）和黑色（不可通過表示）。

其中在柵格地圖中的柵格大小會影響后續對于路徑規劃的效果。當柵格偏大時，能夠減小運算量與規劃時間，但會導致規劃的路線過于粗糙使得行走的路線增加;當柵格偏小時，使得行走的路程準確率增高，讓規劃時間大幅度上升。由此，柵格地圖的大小需要更具實際情況進行設定，包含場地與實驗對象的考量。

3.2算法實現

3.2.1 A*的路徑選取

將實驗對象的場地用柵格地圖進行表示后，可以根據柵格地圖的信息得到實驗對象的地圖環境：

[M={Mi，i=0，1，2，3}]? ? ? ? ? ? ? ? ? ? ? ? ? ? ?（2）

其中[M0]為實驗對象起始點，[M1]為可通過區域，[M2]為不可通過區域，[M3]為目標區域。

A*算法在靜態環境中進行路徑規劃實驗時具有較好的實時性，從而可迅速高效地求解最優路徑[5]。在A*算法設計中，本文采用歐式距離作為啟發式函數：

[h（n）=（xi-xn）2-（yi-yn）2]? ? ? ? ? ? ? ? ? ? ? （3）

其中起始點在柵格地圖中橫坐標為[xi]，起始點在柵格地圖中縱坐標[yi]。終點在柵格地圖中橫坐標[xn]，終點在柵格地圖中縱坐標[yn]。

其中圖1為A*算法的實例：

3.2.2 行駛階段

在行駛階段中，為解決傳統A*算法中出現的規劃路徑貼近障礙物邊緣導致不符合正常汽車行駛情況。本文算法中將人工勢場法加入，通過給障礙物添加負電荷，形成斥力場在行駛過程中，目標車輛受到障礙物的斥力隨著距離減小使得斥力越大。因此，勢能和距離成反比。公式如下：

[F=-grad（kl），l≤lmax0，其他]? ? ? ? ? ? ? ? ? ? ? （4）

其中[F]代表目標車輛受到的斥力，[k]代表相應系數，[l]代表目標車輛與障礙物的距離，[lmax]為勢場作用的最大范圍。

同樣通過斥力場的產生的斥力作用，解決在路徑緊貼障礙物這一不符合汽車行駛的情況。

由于本文在地圖掃描階段中采用URG-04LX-UG01激光雷達，此雷達掃描范圍為240°（圖2）。故本文提出在目標汽車后方120°人工添加假想障礙物（圖3），從而在人工勢場法斥力場計算給予目標汽車一個斥力使得汽車在引力場和斥力場計算中能夠獲得一個向前行駛的斥力。

3.2.3局部階段

因在環境模型中將地圖通過柵格的表達方式，故當實驗對象進入目的地柵格時，則進入局部規劃階段。在局部規劃階段中，本算法通過人工勢場法中的應力場對小車機器人進行引導。

在目標汽車的引導階段中，會出現需要使目標階段轉向的情況，此時則需要對目標的轉向角與姿態角進行計算。在本文算法中為將目標四輪車輛簡化為兩輪車輛。從而進行相應的計算。

通過引力場的牽引力，在計算出小車每時刻的姿態角，其中計算轉向角[u]的公式為：

[u=tan-1[Lv（λ（θr-θ）+θr）]]? ? ? ? ? ? ? ? ? （5）

其中[L]為車輛軸距，[v]為車輛速度，[θ]為車輛姿態角，[θr]為目標姿態角，[λ]是轉向系數。

其中在確定轉向角之前，需要確定目標姿態角，該姿態角等于人工勢場法中合力的角度。

基于應力場的特性，可以讓小車的轉向曲線更加平滑，符合實際的汽車運動情況。

4實驗結果

為驗證算法的可行性和有效性，進行了計算機仿真實驗，使用Matlab軟件對汽車目標做出規劃與到達地點的行駛，并對轉向角度進行測試。其中地圖的掃描構建采用URG-04LX-UG01激光雷達。所用小車如圖4所示：

由于在仿真中，車輛的行駛默認為勻速駕駛，在到達目標地點時，由于出現了轉向，勻變行駛使得在到達指定地點時出現些許誤差。通過多次測試，與設定的目標點偏差如圖5在10mm之內：

在行駛過程中目標汽車的轉向角和姿態角變化如圖6、圖7所示。

5 結論

通過將A*算法和人工勢場法相結合，能夠較好地對汽車目的地進行路徑規劃。同時由于人工勢場法的引入，能更好地調整汽車目標轉向角，使得在轉向操作時角度更加合理，從而達到汽車行駛為平滑路徑的效果。在與目標汽車障礙物建立斥力場，規避了路線緊貼障礙物，使其更符合實際行駛需要。通過一系列的仿真實驗，證明了本算法的可行性。

參考文獻：

[1] 楊博，張緩緩，江忠順.智能車輛的避障路徑規劃與跟蹤控制仿真分析[J/OL].中國測試：1-8[2020-11-11].http：//kns.cnki.net/kcms/detail/51.1714.TB.20201016.1753.015.html.

[2] 孫煒，呂云峰，唐宏偉，等.基于一種改進A*算法的移動機器人路徑規劃[J].湖南大學學報（自然科學版），2017，44（4）：94-101.

[3] 馬飛，楊皞屾，顧青，等.基于改進A*算法的地下無人鏟運機導航路徑規劃[J].農業機械學報，2015，46（7）：303-309.

[4] KHATIB O.Real-time obstacle avoidance for manipulators and? and mobile robots[J].The International Journal of Robotics Research，1986，5（1）：90-98.

[5] 王維，裴東，馮璋.改進A*算法的移動機器人最短路徑規劃[J].計算機應用，2018，38（5）：1523-1526.

【通聯編輯：光文玲】