基于改進A*算法的移動機器人全局路徑優(yōu)化研究

方文凱 廖志高

摘 要：針對傳統(tǒng)A*（A-STAR）算法在移動機器人全局路徑規(guī)劃中存在搜索效率低下、搜索路徑不夠平滑及不安全等問題，提出一種雙向搜索A*算法。在傳統(tǒng)A*算法上建立起四鄰域及八鄰域混合搜索路徑機制，設定雙向搜索中的虛擬目標點，借助人工勢場算法思想，建立雙向搜索時搜索點到該虛擬目標點的衰減函數(shù)，并在保證最優(yōu)性的基礎上改進評估函數(shù)模型以及調(diào)試適當?shù)臋嘀刂担肴A貝塞爾曲線規(guī)劃新的行駛路徑。通過Pycharm平臺進行仿真，結果表明：改進后的A*算法所規(guī)劃的路徑長度、搜索效率及路徑平滑性等特性都優(yōu)于傳統(tǒng)A*算法，規(guī)劃出的路徑長度較傳統(tǒng)算法提高19.61%，搜索效率較傳統(tǒng)算法提高66.19%，路徑平滑度大幅度提高，全局路徑優(yōu)化效果較為明顯。

關鍵詞：移動機器人；全局路徑規(guī)劃；人工勢場；雙向搜索；貝塞爾曲線

中圖分類號：TP242.6 DOI：10.16375/j.cnki.cn45-1395/t.2023.01.011

0 引言

隨著現(xiàn)代科技不斷高速發(fā)展，智能移動機器人憑借小巧靈活、簡單操作、功能豐富以及能滿足人們諸多需求的優(yōu)勢，始終處于科學研究的前沿，同時也不斷推動著科技的進步。在移動機器人的研究中，如何使機器人自主規(guī)劃出最優(yōu)路徑是重點問題[1-2]。移動機器人路徑規(guī)劃分為全局路徑和局部路徑[3]，全局路徑是指在運動信息已知的狀態(tài)下全局搜索到最優(yōu)路徑，而局部路徑是指運動信息未知或獲取不全的狀態(tài)下自主規(guī)劃路徑的過程。常用于移動機器人全局路徑規(guī)劃的算法有A*算法[4]、Dijkstra算法[5]、RRT算法[6]、粒子群算法[7]以及仿生智能算法[8]等，局部路徑規(guī)劃算法有動態(tài)規(guī)劃法[9]、動態(tài)窗口算法[10]、人工勢場法[11]等。

A*算法是一種啟發(fā)式搜索路徑算法，既有深度優(yōu)先遍歷算法的全局搜索性[12]，又有廣度優(yōu)先遍歷算法的貪心性[13]，能夠在運動環(huán)境已知的場景下快速搜索到最優(yōu)路徑，被廣泛應用于路徑規(guī)劃領域中。為了獲取更優(yōu)的路徑效果，學者們進行了諸多研究。周超等[14]對A*算法的啟發(fā)搜索函數(shù)進行改進，引入坡度信息影響因素，使得A*算法能夠在坡度不平的環(huán)境中規(guī)劃最優(yōu)路徑，但在規(guī)劃路徑的過程中造成節(jié)點過多，從而導致路徑不夠平滑。陳家寶等[15]通過對啟發(fā)函數(shù)引入權重值來優(yōu)化評估函數(shù)模型，使得A*算法能夠加快搜索效率，但易陷入局部最優(yōu)解中。柴紅杰等[16]針對A*算法規(guī)劃的路徑不夠平滑等問題，提出在障礙物節(jié)點附近建立緩沖地帶來增加移動過程中的安全性，但在仿真過程中算法搜索效率低下及搜索時間較長。劉子豪等[17]針對A*算法搜索效率低下等問題，提出使用跳躍點搜索理論來搜索運動的節(jié)點，有效地減少了在搜索過程中無效節(jié)點的遍歷，但所規(guī)劃的路徑不夠平滑，不利于移動機器人的路徑行駛。黃迎港等[18]針對多障礙物環(huán)境設計一種運動優(yōu)先級策略以提高搜索效率，但并未考慮到改進后的算法在特殊環(huán)境中的路徑狀況。

由以上分析可知，A*算法仍然存在搜索路徑時路徑不夠平滑、搜索時間過長以及算法效率低下等問題。故本文先建立起較為復雜的全局靜態(tài)障礙物環(huán)境，提出改進移動機器人運動模型，引入四鄰域及八鄰域混合搜索模型，使得規(guī)劃出的路徑相對安全。在此基礎上，設置虛擬目標點，借助人工勢場算法思想設計出衰減函數(shù)，從而雙向搜索路徑使得搜索點在虛擬目標點重合，減少無效節(jié)點搜索，并改進A*算法中的評估函數(shù)以及增添適當?shù)臋嘀刂担肴A貝塞爾曲線軌跡優(yōu)化，最終達到提高算法搜索效率及優(yōu)化軌跡的目的。

1 傳統(tǒng)A*算法

1.1 仿真環(huán)境及遍歷節(jié)點

在研究移動機器人路徑規(guī)劃時需要確定其仿真環(huán)境，常用的仿真環(huán)境分為柵格地圖、矢量地圖以及自由空間地圖等。因柵格地圖具有易理解、結構簡單清晰等優(yōu)勢，故采用較為廣泛的等精度正方形柵格地圖來模擬機器人運動環(huán)境，以柵格大小為單位記錄其運動信息。

傳統(tǒng)A*算法在遍歷節(jié)點時一般是四鄰域或八鄰域方式。如圖1所示，圖1（a）所示為四鄰域遍歷，遍歷下一個節(jié)點方向為正上、正下、正左以及正右，但容易造成規(guī)劃出的路徑轉折點過多的問題。圖1（b）所示為八鄰域遍歷，在四鄰域上增加了左上、左下、右上以及右下方向，擴大了遍歷節(jié)點范圍，但容易造成遍歷節(jié)點時忽略障礙物的存在。

1.2 傳統(tǒng)A*算法原理

傳統(tǒng)A*算法是一種啟發(fā)式搜索算法，該算法既有Dijkstra算法全局搜索性，又有BFS算法的貪心性。區(qū)別于A*算法，Dijkstra算法是遍歷全局節(jié)點進行搜索的，并沒有考慮到與目標點位置之間的導向作用，故在使用Dijkstra算法路徑規(guī)劃時搜索效率低下，但因全局搜索導致搜索的路徑往往是最優(yōu)路徑。而BFS算法中的貪心性增添了與目標點位置之間的導向作用，收錄節(jié)點時會選擇與目標點方向相近的節(jié)點，故遍歷搜索時較快，但規(guī)劃的路徑往往是次優(yōu)路徑。而A*算法則融合了Dijkstra算法全局搜索性及BFS算法的貪心性，建立起新的啟發(fā)式評估函數(shù)模型，如式（1）—式（3）所示：

[fn=λn+μn，] （1）

[λn=x-xs2+y-ys2，] （2）

[μn=x-xg2+y-yg2.] （3）

式中：n為搜索當前節(jié)點；x、y分別為當前節(jié)點的位置坐標；xs、ys為初始節(jié)點的橫、縱坐標；xg、yg為目標點的橫、縱坐標；[fn]為當前節(jié)點搜索時的評估函數(shù)值；[λn]為當前節(jié)點與起點之間的評估值；[μn]為當前節(jié)點與目標點之間的評估值。當[λn]為0時表示該算法退化為BFS算法，當[μn]為0時表示該算法退化為Dijkstra算法。

2 改進雙向搜索A*算法

2.1 改進搜索鄰域

針對傳統(tǒng)A*算法搜索鄰域較差導致規(guī)劃路徑不平滑及行駛不安全等問題，本文將傳統(tǒng)的單一四鄰域及八鄰域搜索機制改進為四鄰域及八鄰域混合切換搜索機制，即遍歷子節(jié)點時首先判斷與障礙物之間的距離，當運動節(jié)點到達以障礙物為圓心、單位柵格對角線長度為直徑的安全距離時切換成四鄰域搜索，大于安全距離時切換成八鄰域搜索。此方法融合了四鄰域及八鄰域搜索優(yōu)勢，使得移動機器人在行駛的過程中更加安全。

四鄰域及八鄰域混合切換機制是一種新的遍歷節(jié)點策略。如圖2所示，當節(jié)點A點需要收錄B點時，若采用單一的四鄰域搜索遍歷，得出的路徑則是A-b1-a1-B或A-b1-b2-B；若采用單一的八鄰域搜索遍歷時，得出的路徑是A-b2-B；而若采用混合切換機制搜索遍歷時，得出的路徑是A-b1-B。從不同搜索路徑方式可知，混合切換機制搜索得到的路徑相對遠離障礙物，避免了轉折點過多及穿過障礙物的情況發(fā)生，對于移動機器人行駛則更加安全，從而體現(xiàn)出混合切換搜索機制的優(yōu)勢。

2.2 改進雙向搜索

雙向搜索A*算法是在傳統(tǒng)A*算法基礎上采用雙向同步搜索方式，即將起點和目標點當成新的搜索點，引入虛擬目標點，即起點與目標點的中點，若虛擬目標點為障礙物，則按照四鄰域及八鄰域混合搜索機制重新搜索到滿足條件的虛擬目標點，使得新的搜索點同時向虛擬目標點方向搜索，直至在虛擬目標點相遇，從而停止搜索得到全局路徑。具體的算法步驟及流程圖（圖3）如下：

Step 1 首先構建100*100柵格環(huán)境地圖。

Step 2 創(chuàng)建3個列表：open_list 1（S）、open_list 2（H）以及closed_list 1（D），其中open_list 1和open_list 2表示雙向搜索過程中待遍歷收錄的節(jié)點，closed_list表示收錄已存放遍歷的節(jié)點且放置虛擬目標點，并將起點放到open_list 1中，將目標點放到open_list 2中，開始遍歷全局節(jié)點。

Step 3 判斷收錄的節(jié)點中closed_list是否與虛擬目標點重合，如果是，利用回溯算法原理將closed_list中的節(jié)點遍歷，求解該最短路徑長度，結束算法；如果不是，則執(zhí)行下一步操作。

Step 4 按照該節(jié)點為新節(jié)點進行遍歷，先判斷與障礙物之間的安全距離，大于安全距離時采用八鄰域遍歷搜索，小于安全距離時采用四鄰域搜索，生成對應的子節(jié)點。判斷該子節(jié)點是否在open_list 1及open_list 2中，如果是，則更新open_list 1及open_list 2中的[fa]，如果不是，則需要收錄該節(jié)點，并分別計算該節(jié)點的[fa]值。

Step 5 選取最小的[fa]中的節(jié)點加入到closed_list前序及后序中，并刪掉在open_list 1及open_list 2對應的值，當open_list 1及open_list 2列表為空則算法結束，并返回Step 3。

2.3 改進評估函數(shù)

為使得改進后A*算法能夠保持前期加快搜索而后期擴大搜索范圍，引入人工勢場算法思想，根據(jù)人工勢場中引力作用設立衰減函數(shù)，使得虛擬目標點為雙向搜索點提供一個新的評估函數(shù)。其值為初始點A點及目標點B點的中心點C點（xu，yu），以節(jié)點a為例，即（a-A）作用、（a-C）作用以及（A-C）作用，通過不斷調(diào)整引力作用權重值使得移動機器人向虛擬目標點靠攏并相遇，其引力圖如圖4所示。

如圖4所示，A、B兩點為起始點和目標點，C點為虛擬目標點，搜索節(jié)點a和b向虛擬目標點靠攏，其節(jié)點a改進后評估函數(shù)模型：

[fa=λa+ωx*?a-η*γa，η∈0，1.]

（4）

式中：[λa=x-xs2+y-ys2；]

[?a=x-xu2+y-yu2；]

[γa=xu-xs2+yu-ys2；]

[ωx=1ρ2πexp-x-?22ρ2，]

其中[ρ=12π]，[?]為虛擬目標點的中點。根據(jù)評估函數(shù)模型，在保證最優(yōu)性基礎上使得評估值[fa]比實際值小，從而不斷地改變[η]值，繼而規(guī)劃出最優(yōu)路徑。

2.4 改進路徑平滑性

通過上述改進策略使得移動機器人行駛更加安全，搜索效率大幅度提高，但仍存在著規(guī)劃路徑不夠平滑等問題，即在行駛過程中容易造成移動機器人轉彎斜度過大等問題，需要對行駛路徑進行平滑性處理。而三階貝塞爾曲線具有保凸性及平滑性等優(yōu)點，被廣泛應用在路徑規(guī)劃領域，具體表達式為：

[Dt=i=0nnipi1-tn-iti，t∈0，1，] （5）

[bt=p01-t3+3p1t1-t2+3p2t21-t+][[p3t3，t∈0，1.]] （6）

其中：式（5）為貝塞爾曲線表達式；式（6）為三階貝塞爾曲線；[pii=0， 1， …， n]為給定的軌跡點。隨著[t]不斷連續(xù)變化，可以描繪出平滑完整的移動機器人行駛路徑。

3 仿真及結果分析

為驗證本研究的科學性對其進行仿真分析。其仿真實驗環(huán)境如下：處理器為Intel CORE i7-6700 HQ，CPU為2.60 GHz，編程語言為python，面向對象開發(fā)設計并在2021版pycharm開源平臺模擬仿真。針對移動機器人全局路徑規(guī)劃研究，分別對傳統(tǒng)A*算法以及改進后A*算法在較為復雜的柵格常規(guī)環(huán)境中模擬仿真對比，其柵格環(huán)境地圖為100×100單位柵格，機器人移動半徑為1個單元柵格，起點位置為[1，1]，目標點位置為[99，99]。為驗證改進后A*算法的科學性，將A*算法改進過程逐個進行對比分析，分別提高A*算法在移動機器人路徑規(guī)劃領域中的魯棒性。

3.1 四鄰域及八鄰域混合搜索機制仿真

實驗一：為提高移動機器人行駛安全，采用四鄰域及八鄰域混合搜索機制進行仿真分析，并將各鄰域搜索仿真圖做橫向對比分析，得到傳統(tǒng)算法不同遍歷節(jié)點圖及仿真數(shù)據(jù)，如圖5和表1所示。

通過對仿真數(shù)據(jù)進行對比分析可知，在運用四鄰域及八鄰域混合機制來搜索節(jié)點的過程中能夠使得規(guī)劃出來的路徑相對平滑，可以防止出現(xiàn)圖5（b）中陡峭的移動方向改變，使得移動機器人在行駛過程中更加安全，故改進有效。同時，在運用混合遍歷方式時可以進一步得到最優(yōu)的路徑，使得規(guī)劃的路徑更短，但搜索時間將會增多。

3.2 雙向搜索仿真

實驗二：針對傳統(tǒng)A*算法在搜索中存在著搜索過慢等問題，改進A*算法采用雙向搜索路徑方式，在混合搜索機制基礎上進行仿真并做橫向對比分析，得到傳統(tǒng)算法及雙向搜索A*算法仿真圖如圖6所示，仿真數(shù)據(jù)見表2。

通過對比分析圖6（a）與圖6（b）可知，雙向搜索A*算法在搜索過程中可以大幅度降低搜索時間，適當?shù)胤艞墴o效節(jié)點的遍歷，從而進一步提高算法搜索效率，故改進有效。但在路徑規(guī)劃中可能會導致規(guī)劃長度不是最優(yōu)，這主要是因為設計虛擬目標點時不在最優(yōu)路徑上，從而導致規(guī)劃出次優(yōu)的路徑。但運用雙向搜索可以大幅度提高算法效率，降低搜索時間。

3.3 新評估函數(shù)仿真

實驗三：為提高A*算法的搜索效率，在上述四鄰域及八鄰域混合搜索機制及雙向搜索A*算法后改進新的評估函數(shù)模型，在保證最優(yōu)性基礎上不斷調(diào)試評估函數(shù)模型中的權重值[η]，得到仿真圖及仿真數(shù)據(jù)，如圖7和表3所示。

從對圖7（a）和圖7（b）柵格環(huán)境的對比分析可知，在保證評估函數(shù)最優(yōu)性的基礎上不斷調(diào)試權重值[η]，使得規(guī)劃長度及搜索時間等指標達到最優(yōu)為止，從而進一步提升算法搜索效率，規(guī)劃出最優(yōu)路徑，使得改進算法有效。

3.4 路徑平滑性仿真

實驗四：針對移動機器人在行駛中存在拐點較多等問題，采用三階貝塞爾曲線來改進A*算法，并在上述優(yōu)化策略后，增添貝塞爾曲線得到路徑平滑性仿真圖及數(shù)據(jù)，如圖8和表4所示。

通過對比分析圖8可知，圖8（a）中存在過多的拐點，但對比圖8（b），三階貝塞爾曲線處理后使得規(guī)劃的路徑相對平滑許多，各折線擬合出一條完整的曲線，更有利于移動機器人的平滑行駛。與傳統(tǒng)A*算法四鄰域搜索仿真對比，改進后路徑長度優(yōu)化19.61%，搜索效率優(yōu)化66.19%，即三階貝塞爾曲線改進后A*算法無論是在搜索效率還是在路徑規(guī)劃安全平滑性上都有大幅度的提升，故改進有效。

4 結論

針對傳統(tǒng)A*算法在全局路徑規(guī)劃中存在路徑規(guī)劃不平滑、不安全及搜索效率低下等問題，首先，建立起四鄰域及八鄰域混合搜索機制，使得規(guī)劃出的路徑相對遠離障礙物，在移動過程中更加安全。其次，引入雙向同步搜索機制并設計虛擬目標點，借助人工勢場思想，建立搜索點到虛擬目標點的衰減函數(shù)模型，在保證最優(yōu)性基礎上，在新的評估函數(shù)中增添權重值，通過不斷調(diào)整權重值使得在保證規(guī)劃路徑最優(yōu)時提高算法搜索效率，降低算法搜索時間。最后，引入三階貝塞爾曲線使得規(guī)劃出的路徑更加平滑。但該改進后的算法并不是在任何情況下都優(yōu)于傳統(tǒng)算法，當出現(xiàn)虛擬目標點嚴重偏移最優(yōu)路徑時，改進后的算法將可能低于傳統(tǒng)算法的性能。此外，該算法只是在仿真模擬實驗，缺乏實際移動機器人的測試，下一步將結合實際應用場景展開研究。

參考文獻

[1] PATLE B K，BABU L G，PANDEY A，et al.A review：on path planning strategies for navigation of mobile robot[J].Defence Technology，2019，15（4）：582-606.

[2] ZAFAR M N，MOHANT J C. Methodology for path planning and optimization of mobile robots： a review[J].Proceda Computer Science，2018，133：141-152.

[3] GARCIA M A P，MONTIEL O，CASTILLO O，et al.Path planning for autonomous mobile robot navigation using ant colony optimization and a fuzzy cost function evaluation[J].Applied Soft Computing，2009，9（3）：1102-1110.

[4] LI C G，HUANG X，DING J，et al.Global path planning based on a bidirectional alternating search A* algorithm for mobile robots[J].Computers and Industrial Engineering，2022，168：108123.

[5] DAKULOVI? M，HORVATIC S， PETROVIC I.Complete coverage D* algorithm for path planning of a floor-cleaning mobile robot[J].IFAC Proceedings Volumes， 2011， 44（1）：5950-5955.

[6] MASEKO B B，VAN DAALEN C E，TREURNICHT J.Optimised informed RRTs for mobile robot path planning[J].IFAC-Papers OnLine，2021，54（21）：157-162.

[7] DEWANG H S，MOHANTY P K，KUNDU S.A robust path planning for mobile robot using smart particle swarm optimization[J].Procedia Computer Science，2018，133：290-297.

[8] TUNCER A，YILDIRIM M.Dynamic path planning of mobile robots with improved genetic algorithm[J].Computers and Electrical Engineering，2012，38（6）：1564-1572.

[9] DENG X，LI R F，ZHAO L J，et al.Multi-obstacle path planning and optimization for mobile robot[J].Expert Systems with Applications，2021，183：115445.

[10] COSTANZI R，F(xiàn)ANELLI F，MELI E，et al.Generic path planning algorithm for mobile robots based on Bezier curves[J].IFAC-PapersOnLine，2016，49（15）：145-150.

[11] LAZAROWSKA A.Discrete artifificial potential field approach to mobile robot path planning[J].IFAC-Papers OnLine，2019，52（8）：334-337.

[12] WAHAB M N A，NEFTI-MEZIANI S，ATYABI A. A comparative review on mobile robot path planning： classical or meta-heuristic methods[J].Annual Reviews in Control，2020（50）：233-252.

[13] SAEED R A，RECUPERO D R，REMAGNINO P.A boundary node method for path planning of mobile robots[J].Robotics and Autonomous Systems，2020，123：103320.

[14] 周超，谷玉海，任斌.基于一種改進A*算法的移動機器人路徑規(guī)劃研究[J].重慶理工大學學報（自然科學），2021，35（5）：127-134.

[15] 陳家寶，文家燕，謝廣明.基于改進A*算法的移動機器人路徑規(guī)劃[J].廣西科技大學學報，2022，33（1）：78-84.

[16] 柴紅杰，李建軍，姚明.改進的A*算法移動機器人路徑規(guī)劃[J].電子器件，2021，44（2）：362-367.

[17] 劉子豪，趙津，劉暢，等.基于改進A*算法室內(nèi)移動機器人路徑規(guī)劃[J].計算機工程與應用，2021，57（2）：186-190.

[18] 黃迎港，陳鍇，羅文廣.復雜環(huán)境下無人機全覆蓋路徑規(guī)劃混合算法研究[J].廣西科技大學學報，2022，33（1）：85-93.

Research on global path optimization of mobile robot based

on improved A* algorithm

FANG Wenkai1，LIAO Zhigao* 1，2

（1.School of Economics and Management， Guangxi University of Science and Technology， Liuzhou 545006 China; 2. Guangxi Industrial High Quality Development Research Center （Guangxi University of Science and Technology）， Liuzhou 545006， China）

Abstract：Traditional A*（A-STAR） algorithm has some problems in global path planning of mobile robot， such as low search efficiency， insufficient smooth and safe search path， and so on. A bidirectional search A* algorithm is proposed. Firstly， based on the traditional A* algorithm， the four-neighborhood and eight-neighborhood hybrid search path mechanism is established， and the virtual target point in the two-way search is set. With the help of artificial potential field algorithm， the attenuation function from the end point to the virtual target point is established. On the basis of ensuring the optimality， the evaluation function model is improved and the appropriate weight value is debugged， and the third-order