摘 要：針對傳統(tǒng)Astar算法在復(fù)雜場景下的路徑規(guī)劃任務(wù)中存在路徑搜索效率低、路徑轉(zhuǎn)折次數(shù)多等問題，本文提出一種基于動態(tài)五鄰域搜索的改進Astar算法。通過改進算法的啟發(fā)函數(shù)，將曼哈頓距離與歐式距離融合得到的距離度量代替?zhèn)鹘y(tǒng)Astar算法的單一距離度量，引入動態(tài)加權(quán)機制，并將傳統(tǒng)的固定八鄰域搜索策略改進為動態(tài)五鄰域搜索策略。通過剔除最終路徑的冗余節(jié)點并進行貝塞爾曲線平滑處理，使最終路徑更平滑。試驗表明，與傳統(tǒng)Astar算法相比，采用本文算法的路徑搜索時間減少了約69%，路徑拓展節(jié)點數(shù)減少了約66.35%，路徑包括節(jié)點數(shù)減少了約38.8%，路徑尋優(yōu)能力較好。

關(guān)鍵詞：Astar；路徑規(guī)劃；貝塞爾平滑曲線；混合加權(quán)；鄰域搜索

中圖分類號：TP 393" " " " " 文獻標志碼：A

路徑規(guī)劃是解決移動機器人導(dǎo)航問題的關(guān)鍵技術(shù)之一?，F(xiàn)階段路徑規(guī)劃方法主要分為2類，一類是以A*算法（Astar）[1]為主的靜態(tài)全局路徑規(guī)劃算法[2]，另一類是以動態(tài)窗口算法（Dynamic Window Approach）[3]為主的動態(tài)局部路徑規(guī)劃算法[4]。

Astar算法能在提升搜索效率的同時能兼顧尋找較優(yōu)路線，已經(jīng)成為機器人應(yīng)用中最普遍的全局路徑規(guī)劃算法[5]。但是Astar算法也有局限性，例如當(dāng)面對復(fù)雜場景時，由于障礙物增多，因此Astar算法會搜索大量非必要節(jié)點，導(dǎo)致搜索效率降低。

針對傳統(tǒng)Astar算法存在的缺陷，國內(nèi)學(xué)者進行了廣泛研究，遠子涵等[6]提出一種12方向二十四鄰域搜索方式的改進Astar方法，該方法減少了搜索路徑的拓展節(jié)點，節(jié)約了搜索時間，但是其規(guī)劃路徑并非最優(yōu)路徑；孔繼利等[7]在傳統(tǒng)Astar算法中引入雙向搜索機制，減少了對拓展節(jié)點的搜索，但是未解決規(guī)劃路徑節(jié)點冗余、計算時間過長等問題。針對上述問題，筆者提出一種基于動態(tài)五鄰域搜索的改進Astar算法。該方法通過在啟發(fā)函數(shù)中融入混合距離度量和動態(tài)加權(quán)機制提高了節(jié)點的搜索效率，解決了在搜索過程中內(nèi)存消耗的問題，并對最終路徑進行平滑處理，使機器人行駛軌跡更平滑。

1 傳統(tǒng)Astar算法

1.1 Astar算法原理

Astar算法利用啟發(fā)式函數(shù)來估計從當(dāng)前節(jié)點到目標節(jié)點的代價，從而引導(dǎo)搜索方向，減少搜索空間，提高搜索效率[8]。Astar算法結(jié)合了最佳優(yōu)先搜索和Dijkstra算法的特點，當(dāng)尋找起始節(jié)點至目標節(jié)點的路徑時，效率很高，應(yīng)用價值廣泛。

用Astar算法的節(jié)點定義評估函數(shù)f（n），如公式（1）所示。

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

式中：g（n）為從起始節(jié)點到當(dāng)前節(jié)點的實際距離；h（n）為當(dāng)前節(jié)點到目標節(jié)點的啟發(fā)式估計距離[9]。

Astar算法的關(guān)鍵是設(shè)計啟發(fā)式函數(shù)h（n）。在理想情況下，h（n）應(yīng)該精確反映從節(jié)點n到目標的成本。然而，在實際應(yīng)用中，Astar算法通常使用歐式距離、曼哈頓距離和切比雪夫距離來近似表示h（n）。

1.2 Astar算法與WAstar算法比較

Astar算法基于啟發(fā)式搜索的思想，估計從起始狀態(tài)到目標狀態(tài)的代價，并結(jié)合搜索路徑中已知的信息來指導(dǎo)搜索過程，以找到最優(yōu)路徑或者滿足特定條件的路徑。傳統(tǒng)Astar算法路徑規(guī)劃效果如圖1所示。WAstar算法是在Astar算法的基礎(chǔ)上添加啟發(fā)函數(shù)的權(quán)重因子，以路徑最優(yōu)性換取搜索速度，WAstar算法路徑規(guī)劃效果如圖2所示。

在圖1和圖2中，深色圓點為起點，深色叉號為終點，淺色叉號為搜索節(jié)點。從圖2可以看出，與傳統(tǒng)Astar算法相比，WAstar算法的搜索節(jié)點數(shù)量明顯減少，搜索速度更快，但是規(guī)劃的路徑并不是最佳路徑。

2 改進Astar算法

2.1 混合動態(tài)加權(quán)

Astar算法的效率和準確性深受其啟發(fā)式函數(shù)h（n）的影響。盡管WAstar算法對h（n）進行了加權(quán)處理，與傳統(tǒng)的Astar算法相比，搜索效率有了很大程度提升，但是WAstar算法存在一定缺陷，例如無法根據(jù)當(dāng)前結(jié)點位置動態(tài)選擇合適的權(quán)重，在WAstar算法中的單一距離度量有一定局限性。

基于上述問題，本文在改進的Astar算法的啟發(fā)函數(shù)中，引入動態(tài)加權(quán)機制，如公式（2）所示。

f（n）=（1-α）·g（n）+α·h（n） （2）

式中：α為動態(tài)加權(quán)因子，α隨當(dāng)前點的變化而改變，如公式（3）所示。

（3）

式中：Lstart_goal為起始點到目標節(jié)點的歐氏距離；h1（n）為當(dāng)前點到目標點的歐式距離。該方法使啟發(fā)函數(shù)能夠根據(jù)實際搜索情況動態(tài)調(diào)整權(quán)重。這種動態(tài)加權(quán)策略可以更好地平衡搜索的廣度和深度，從而提高搜索效率。針對傳統(tǒng)Astar算法中單一距離度量的局限性，筆者融合曼哈頓距離與歐式距離，作為新的啟發(fā)函數(shù)距離度量hEM（n），如公式（4）所示。

（4）

式中：h2（n）為當(dāng)前點到目標點的曼哈頓距離；h3（n）為起始點到目標點的曼哈頓距離；ω為可變倍數(shù)。

曼哈頓距離和歐式距離各有特點，曼哈頓距離更適合網(wǎng)格狀地圖的路徑搜索，歐式距離更適合連續(xù)空間的路徑規(guī)劃。融合這2種距離度量方式，新的啟發(fā)函數(shù)能夠更全面地考慮路徑的特性和環(huán)境的幾何信息，生成更優(yōu)質(zhì)的路徑。改進后的Astar算法評估函數(shù)如公式（5）所示。

f（n）=（1-α）·g（n）+α·hEM（n） （5）

2.2 動態(tài)五鄰域搜索

在Astar算法中，傳統(tǒng)的八鄰域搜索是在二維平面上的節(jié)點周圍考慮8個可能的移動方向。如果縮小這個范圍，只考慮以目標點為導(dǎo)向的5個方向（如圖3所示），則可以進一步減輕算法運算負擔(dān)，從而提高Astar算法的整體運行效率。

僅考慮以目標點為導(dǎo)向進行單一五鄰域搜索，當(dāng)5個鄰域方向均存在障礙物時，Astar算法會在該區(qū)域陷入死鎖狀態(tài)，無法有效規(guī)劃路徑。為避免發(fā)生以上情況，引入動態(tài)五鄰域搜索理念，在搜索過程中，實時判斷當(dāng)前節(jié)點與目標點之間的相對位置關(guān)系，方向搜索規(guī)則見表1。再根據(jù)表1進行動態(tài)調(diào)整，避免Astar算法陷入死鎖狀態(tài)，更集中地搜索可能包括最優(yōu)路徑的節(jié)點，從而提高搜索效率。

表1 方向搜索規(guī)則

當(dāng)前點與目標節(jié)點相對位置 保留搜索方向 舍棄搜索方向

第一象限 O2，O3，O4，O5，O6 O1，O7，O8

第二象限 O4，O5，O6，O7，O8 O1，O2，O3

第三象限 O6，O7，O8，O1，O2 O3，O4，O5

第四象限 O8，O1，O2，O3，O4 O5，O6，O7

2.3 路徑平滑處理

傳統(tǒng)的Astar算法規(guī)劃的最終路徑存在節(jié)點冗余、轉(zhuǎn)折點過多等問題，導(dǎo)致移動機器人當(dāng)沿該路徑導(dǎo)航時需要頻繁轉(zhuǎn)彎。因此，本文從最終路徑起始點開始刪除當(dāng)前節(jié)點與前一節(jié)點同向運動的節(jié)點，進而去除冗余節(jié)點。分段處理最終路徑，每4個節(jié)點1組進行三階貝塞爾曲線平滑處理，處理規(guī)則見表2。如果節(jié)點數(shù)﹤4個，則根據(jù)表2進行貝塞爾曲線平滑處理，從而提高規(guī)劃路徑的可行性。

表2 分段貝塞爾曲線平滑處理規(guī)則

分段節(jié)點數(shù) 貝塞爾曲線策略

4 三階貝塞爾曲線

3 二階貝塞爾曲線

lt;3 一階貝塞爾曲線

三階貝爾塞爾曲線原理如圖4所示，選取平面內(nèi)任意4個節(jié)點P1、P2、P3和P4作為控制點，在線段P1、P2上選取點A，在線段P2、P3上選取點B，在線段P3、P4上選取點C，如公式（6）所示。

（6）

連接線段AB與線段BC，在線段AB上選取點D，在線段BC上選取點E，如公式（7）所示。

（7）

連接DE，在DE上選取點F，如公式（8）所示。

（8）

將所有滿足上述條件的點F相連接，生成的線段就是三階貝塞爾曲線平滑處理后產(chǎn)生的路徑。

3 仿真驗證及結(jié)果

為了提高 Astar算法的有效性，本文基于PC實驗平臺、Intel Core i7-7500U CPU、GPU NVIDIA GeForce 940MX和12 RAM，分別對傳統(tǒng)Astar算法、混合動態(tài)加權(quán)后的Astar算法和基于動態(tài)五鄰域搜索的改進Astar算法進行2組不同地圖下的仿真試驗，以避免由于改進后的算法更適用于某單一場景，因此導(dǎo)致試驗結(jié)果出現(xiàn)偶然性的情況。2組不同地圖的路徑規(guī)劃效果如圖5、圖6所示。同時對比3種算法在2組不同場景的路徑長度、搜索時間、路徑拓展節(jié)點數(shù)和路徑

包括節(jié)點數(shù)，對比結(jié)果見表3、表4。

表3 不同場景的路徑長度與搜索時間數(shù)據(jù)對比

Astar算法 路徑長度/m 搜索時間/s

地圖一 地圖二 地圖一 地圖二

傳統(tǒng)Astar 124.36 109.88 4.86 5.50

混合動態(tài)加權(quán) 127.88 117.88 2.10 3.78

動態(tài)五鄰域搜索 122.14 112.39 1.50 1.69

由表3可知，使用混合動態(tài)加權(quán)改進傳統(tǒng)Astar算法的啟發(fā)函數(shù)后，與傳統(tǒng)Astar算法相比，混合動態(tài)加權(quán)算法的搜索時間平均縮短了44%，在混合動態(tài)加權(quán)的基礎(chǔ)上引入動態(tài)五鄰域搜索的改進Astar算法，與傳統(tǒng)Astar算法相比，搜索時間平均縮短了約69%。在路徑長度方面，當(dāng)面對場景較為簡單的地圖時，基于動態(tài)五鄰域搜索的改進Astar算法路徑長度優(yōu)于傳統(tǒng)Astar算法。

表4 不同場景的路徑拓展節(jié)點數(shù)與路徑包括節(jié)點數(shù)數(shù)據(jù)對比

Astar算法 路徑拓展節(jié)點數(shù)/個 路徑包括節(jié)點數(shù)/個

地圖一 地圖二 地圖一 地圖二

傳統(tǒng)Astar 505 620 52 46

混合動態(tài)加權(quán) 238 424 55 50

動態(tài)五鄰域搜索 164 216 32 28

由表4可知，使用混合動態(tài)加權(quán)改進傳統(tǒng)Astar算法的啟發(fā)函數(shù)后，與傳統(tǒng)Astar算法相比，其搜索效率有顯著提升，路徑拓展節(jié)點數(shù)平均減少了42.24%。在混合動態(tài)加權(quán)的基礎(chǔ)上引入動態(tài)五鄰域搜索的改進Astar算法進一步提升了算法的搜索效率，與傳統(tǒng)Astar算法相比，路徑拓展節(jié)點數(shù)平均減少了約66.35%。經(jīng)過冗余節(jié)點剔除處理與貝塞爾平滑處理后，規(guī)劃路徑轉(zhuǎn)折點更少，平滑度更高，與傳統(tǒng)Astar算法相比，路徑包括節(jié)點數(shù)減少了38.8%。

4 結(jié)論

為提高Astar算法的搜索效率，本文提出在傳統(tǒng)Astar算法的基礎(chǔ)上優(yōu)化其啟發(fā)函數(shù)，設(shè)置動態(tài)權(quán)重因子α，并將歐氏距離啟發(fā)函數(shù)替換為融合曼哈頓距離與歐氏距離優(yōu)勢的混合啟發(fā)函數(shù)hEM（n），縮短了尋優(yōu)時間，提高了搜索效率。

將傳統(tǒng)Astar算法中八鄰域搜索改為動態(tài)五鄰域搜索，算法目標導(dǎo)向性增強，也避免了在定向五鄰域搜索中出現(xiàn)在復(fù)雜情況下找不到最優(yōu)路徑的問題。

針對傳統(tǒng)Astar算法規(guī)劃的路徑節(jié)點冗余、轉(zhuǎn)折點過多和平滑度差等現(xiàn)象，對改進后的Astar算法進行三階貝塞爾曲線平滑處理，并剔除最終路徑冗余節(jié)點，減少了轉(zhuǎn)折點個數(shù)，提高了路徑質(zhì)量。

參考文獻

[1]DECHTER R，PEARL J.Generalized best-first search strategies and the optimality of A*[J].Journal of the ACM，1985，32（3）：505-536.

[2]ZAID T，QURESHI A H，YASAR A，et al.Potentially guided

bidirectionalized RRT* for fast optimal path planning in cluttered

environments[J].Robotics and Autonomous Systems， 2018（108）：13-27.

[3]朱茂飛，胡方亞，李娜可，等.無人駕駛汽車路徑規(guī)劃算法綜述[J].農(nóng)業(yè)裝備與車輛工程，2023，61（11）：18-22.

[4]李曉旭，馬興錄，王先鵬.移動機器人路徑規(guī)劃算法綜述[J].計算機測量與控制，2022，30（7）：9-19.

[5]李晨輝，王澤峰，胡德燕，等.移動機器人的路徑規(guī)劃技術(shù)研究[J].機電工程技術(shù)，2023，52（1）：5-9.

[6]遠子涵，張皓，左晉，等.基于12方向24鄰域的A*算法路徑規(guī)劃研究[J].北京印刷學(xué)院學(xué)報，2023，31（9）：38-43.

[7]孔繼利，張鵬坤，劉曉平.雙向搜索機制的改進A*算法研究[J].計算機工程與應(yīng)用，2021，57（8）：231-237.

[8]劉夢杰，朱希安，王占剛，等.基于雙向A*算法的礦井水災(zāi)逃生路徑應(yīng)用研究[J].煤炭工程，2019，51（9）：42-47.

[9]胡杰，朱琪，陳銳鵬，等.引入必經(jīng)點約束的智能汽車全局路徑規(guī)劃[J].汽車工程，2023，45（3）：350-360.