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

張皞宇 楊劉一 陳旭淼

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

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

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

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

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

1 引言

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

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

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

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

2 A*算法與人工勢場法

2.1 A*算法

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

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

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

2.2 人工勢場法

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

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

3 本文算法

3.1.環(huán)境模型

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

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

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

3.2算法實現(xiàn)

3.2.1 A*的路徑選取

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

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

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

A*算法在靜態(tài)環(huán)境中進行路徑規(guī)劃實驗時具有較好的實時性，從而可迅速高效地求解最優(yōu)路徑[5]。在A*算法設計中，本文采用歐式距離作為啟發(fā)式函數(shù)：

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

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

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

3.2.2 行駛階段

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

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

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

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

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

3.2.3局部階段

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

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

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

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

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

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

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

4實驗結果

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

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

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

5 結論

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

參考文獻：

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

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

[3] 馬飛，楊皞屾，顧青，等.基于改進A*算法的地下無人鏟運機導航路徑規(guī)劃[J].農(nóng)業(yè)機械學報，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*算法的移動機器人最短路徑規(guī)劃[J].計算機應用，2018，38（5）：1523-1526.

【通聯(lián)編輯：光文玲】