方文凱 廖志高

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

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

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

0 引言

隨著現(xiàn)代科技不斷高速發(fā)展，智能移動機器人憑借小巧靈活、簡單操作、功能豐富以及能滿足人們諸多需求的優(yōu)勢，始終處于科學(xué)研究的前沿，同時也不斷推動著科技的進(jìn)步。在移動機器人的研究中，如何使機器人自主規(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)路徑，被廣泛應(yīng)用于路徑規(guī)劃領(lǐng)域中。為了獲取更優(yōu)的路徑效果，學(xué)者們進(jìn)行了諸多研究。周超等[14]對A*算法的啟發(fā)搜索函數(shù)進(jìn)行改進(jìn)，引入坡度信息影響因素，使得A*算法能夠在坡度不平的環(huán)境中規(guī)劃最優(yōu)路徑，但在規(guī)劃路徑的過程中造成節(jié)點過多，從而導(dǎo)致路徑不夠平滑。陳家寶等[15]通過對啟發(fā)函數(shù)引入權(quán)重值來優(yōu)化評估函數(shù)模型，使得A*算法能夠加快搜索效率，但易陷入局部最優(yōu)解中。柴紅杰等[16]針對A*算法規(guī)劃的路徑不夠平滑等問題，提出在障礙物節(jié)點附近建立緩沖地帶來增加移動過程中的安全性，但在仿真過程中算法搜索效率低下及搜索時間較長。劉子豪等[17]針對A*算法搜索效率低下等問題，提出使用跳躍點搜索理論來搜索運動的節(jié)點，有效地減少了在搜索過程中無效節(jié)點的遍歷，但所規(guī)劃的路徑不夠平滑，不利于移動機器人的路徑行駛。黃迎港等[18]針對多障礙物環(huán)境設(shè)計一種運動優(yōu)先級策略以提高搜索效率，但并未考慮到改進(jìn)后的算法在特殊環(huán)境中的路徑狀況。

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

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

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

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

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

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

傳統(tǒng)A*算法是一種啟發(fā)式搜索算法，該算法既有Dijkstra算法全局搜索性，又有BFS算法的貪心性。區(qū)別于A*算法，Dijkstra算法是遍歷全局節(jié)點進(jìn)行搜索的，并沒有考慮到與目標(biāo)點位置之間的導(dǎo)向作用，故在使用Dijkstra算法路徑規(guī)劃時搜索效率低下，但因全局搜索導(dǎo)致搜索的路徑往往是最優(yōu)路徑。而BFS算法中的貪心性增添了與目標(biāo)點位置之間的導(dǎo)向作用，收錄節(jié)點時會選擇與目標(biāo)點方向相近的節(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為搜索當(dāng)前節(jié)點；x、y分別為當(dāng)前節(jié)點的位置坐標(biāo)；xs、ys為初始節(jié)點的橫、縱坐標(biāo)；xg、yg為目標(biāo)點的橫、縱坐標(biāo)；[fn]為當(dāng)前節(jié)點搜索時的評估函數(shù)值；[λn]為當(dāng)前節(jié)點與起點之間的評估值；[μn]為當(dāng)前節(jié)點與目標(biāo)點之間的評估值。當(dāng)[λn]為0時表示該算法退化為BFS算法，當(dāng)[μn]為0時表示該算法退化為Dijkstra算法。

2 改進(jìn)雙向搜索A*算法

2.1 改進(jìn)搜索鄰域

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

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

2.2 改進(jìn)雙向搜索

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

Step 1 首先構(gòu)建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é)點且放置虛擬目標(biāo)點，并將起點放到open_list 1中，將目標(biāo)點放到open_list 2中，開始遍歷全局節(jié)點。

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

Step 4 按照該節(jié)點為新節(jié)點進(jìn)行遍歷，先判斷與障礙物之間的安全距離，大于安全距離時采用八鄰域遍歷搜索，小于安全距離時采用四鄰域搜索，生成對應(yīng)的子節(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對應(yīng)的值，當(dāng)open_list 1及open_list 2列表為空則算法結(jié)束，并返回Step 3。

2.3 改進(jìn)評估函數(shù)

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

如圖4所示，A、B兩點為起始點和目標(biāo)點，C點為虛擬目標(biāo)點，搜索節(jié)點a和b向虛擬目標(biāo)點靠攏，其節(jié)點a改進(jìn)后評估函數(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π]，[?]為虛擬目標(biāo)點的中點。根據(jù)評估函數(shù)模型，在保證最優(yōu)性基礎(chǔ)上使得評估值[fa]比實際值小，從而不斷地改變[η]值，繼而規(guī)劃出最優(yōu)路徑。

2.4 改進(jìn)路徑平滑性

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

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

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

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

3 仿真及結(jié)果分析

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

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

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

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

3.2 雙向搜索仿真

實驗二：針對傳統(tǒng)A*算法在搜索中存在著搜索過慢等問題，改進(jìn)A*算法采用雙向搜索路徑方式，在混合搜索機制基礎(chǔ)上進(jìn)行仿真并做橫向?qū)Ρ确治觯玫絺鹘y(tǒng)算法及雙向搜索A*算法仿真圖如圖6所示，仿真數(shù)據(jù)見表2。

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

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

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

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

3.4 路徑平滑性仿真

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

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

4 結(jié)論

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

參考文獻(xiàn)

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

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

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

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

[18] 黃迎港，陳鍇，羅文廣.復(fù)雜環(huán)境下無人機全覆蓋路徑規(guī)劃混合算法研究[J].廣西科技大學(xué)學(xué)報，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