基于動態五鄰域搜索的改進Astar算法路徑規劃研究

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

關鍵詞：Astar；路徑規劃；貝塞爾平滑曲線；混合加權；鄰域搜索

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

路徑規劃是解決移動機器人導航問題的關鍵技術之一。現階段路徑規劃方法主要分為2類，一類是以A*算法（Astar）[1]為主的靜態全局路徑規劃算法[2]，另一類是以動態窗口算法（Dynamic Window Approach）[3]為主的動態局部路徑規劃算法[4]。

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

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

1 傳統Astar算法

1.1 Astar算法原理

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

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

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

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

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

1.2 Astar算法與WAstar算法比較

Astar算法基于啟發式搜索的思想，估計從起始狀態到目標狀態的代價，并結合搜索路徑中已知的信息來指導搜索過程，以找到最優路徑或者滿足特定條件的路徑。傳統Astar算法路徑規劃效果如圖1所示。WAstar算法是在Astar算法的基礎上添加啟發函數的權重因子，以路徑最優性換取搜索速度，WAstar算法路徑規劃效果如圖2所示。

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

2 改進Astar算法

2.1 混合動態加權

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

基于上述問題，本文在改進的Astar算法的啟發函數中，引入動態加權機制，如公式（2）所示。

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

式中：α為動態加權因子，α隨當前點的變化而改變，如公式（3）所示。

（3）

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

（4）

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

曼哈頓距離和歐式距離各有特點，曼哈頓距離更適合網格狀地圖的路徑搜索，歐式距離更適合連續空間的路徑規劃。融合這2種距離度量方式，新的啟發函數能夠更全面地考慮路徑的特性和環境的幾何信息，生成更優質的路徑。改進后的Astar算法評估函數如公式（5）所示。

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

2.2 動態五鄰域搜索

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

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

表1 方向搜索規則

當前點與目標節點相對位置 保留搜索方向 舍棄搜索方向

第一象限 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 路徑平滑處理

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

表2 分段貝塞爾曲線平滑處理規則

分段節點數 貝塞爾曲線策略

4 三階貝塞爾曲線

3 二階貝塞爾曲線

lt;3 一階貝塞爾曲線

三階貝爾塞爾曲線原理如圖4所示，選取平面內任意4個節點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相連接，生成的線段就是三階貝塞爾曲線平滑處理后產生的路徑。

3 仿真驗證及結果

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

包括節點數，對比結果見表3、表4。

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

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

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

傳統Astar 124.36 109.88 4.86 5.50

混合動態加權 127.88 117.88 2.10 3.78

動態五鄰域搜索 122.14 112.39 1.50 1.69

由表3可知，使用混合動態加權改進傳統Astar算法的啟發函數后，與傳統Astar算法相比，混合動態加權算法的搜索時間平均縮短了44%，在混合動態加權的基礎上引入動態五鄰域搜索的改進Astar算法，與傳統Astar算法相比，搜索時間平均縮短了約69%。在路徑長度方面，當面對場景較為簡單的地圖時，基于動態五鄰域搜索的改進Astar算法路徑長度優于傳統Astar算法。

表4 不同場景的路徑拓展節點數與路徑包括節點數數據對比

Astar算法 路徑拓展節點數/個 路徑包括節點數/個

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

傳統Astar 505 620 52 46

混合動態加權 238 424 55 50

動態五鄰域搜索 164 216 32 28

由表4可知，使用混合動態加權改進傳統Astar算法的啟發函數后，與傳統Astar算法相比，其搜索效率有顯著提升，路徑拓展節點數平均減少了42.24%。在混合動態加權的基礎上引入動態五鄰域搜索的改進Astar算法進一步提升了算法的搜索效率，與傳統Astar算法相比，路徑拓展節點數平均減少了約66.35%。經過冗余節點剔除處理與貝塞爾平滑處理后，規劃路徑轉折點更少，平滑度更高，與傳統Astar算法相比，路徑包括節點數減少了38.8%。

4 結論

為提高Astar算法的搜索效率，本文提出在傳統Astar算法的基礎上優化其啟發函數，設置動態權重因子α，并將歐氏距離啟發函數替換為融合曼哈頓距離與歐氏距離優勢的混合啟發函數hEM（n），縮短了尋優時間，提高了搜索效率。

將傳統Astar算法中八鄰域搜索改為動態五鄰域搜索，算法目標導向性增強，也避免了在定向五鄰域搜索中出現在復雜情況下找不到最優路徑的問題。

針對傳統Astar算法規劃的路徑節點冗余、轉折點過多和平滑度差等現象，對改進后的Astar算法進行三階貝塞爾曲線平滑處理，并剔除最終路徑冗余節點，減少了轉折點個數，提高了路徑質量。

參考文獻

[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]朱茂飛，胡方亞，李娜可，等.無人駕駛汽車路徑規劃算法綜述[J].農業裝備與車輛工程，2023，61（11）：18-22.

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

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

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

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

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

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