基于動(dòng)態(tài)五鄰域搜索的改進(jìn)Astar算法路徑規(guī)劃研究

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

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

中圖分類號(hào)：TP 393" " " " " 文獻(xiàn)標(biāo)志碼：A

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

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

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

1 傳統(tǒng)Astar算法

1.1 Astar算法原理

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

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

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

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

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

1.2 Astar算法與WAstar算法比較

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

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

2 改進(jìn)Astar算法

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

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

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

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

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

（3）

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

（4）

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

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

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

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

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

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

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

當(dāng)前點(diǎn)與目標(biāo)節(jié)點(diǎn)相對(duì)位置 保留搜索方向 舍棄搜索方向

第一象限 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é)點(diǎn)冗余、轉(zhuǎn)折點(diǎn)過(guò)多等問(wèn)題，導(dǎo)致移動(dòng)機(jī)器人當(dāng)沿該路徑導(dǎo)航時(shí)需要頻繁轉(zhuǎn)彎。因此，本文從最終路徑起始點(diǎn)開始刪除當(dāng)前節(jié)點(diǎn)與前一節(jié)點(diǎn)同向運(yùn)動(dòng)的節(jié)點(diǎn)，進(jìn)而去除冗余節(jié)點(diǎn)。分段處理最終路徑，每4個(gè)節(jié)點(diǎn)1組進(jìn)行三階貝塞爾曲線平滑處理，處理規(guī)則見表2。如果節(jié)點(diǎn)數(shù)﹤4個(gè)，則根據(jù)表2進(jìn)行貝塞爾曲線平滑處理，從而提高規(guī)劃路徑的可行性。

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

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

4 三階貝塞爾曲線

3 二階貝塞爾曲線

lt;3 一階貝塞爾曲線

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

（6）

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

（7）

連接DE，在DE上選取點(diǎn)F，如公式（8）所示。

（8）

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

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

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

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

表3 不同場(chǎng)景的路徑長(zhǎng)度與搜索時(shí)間數(shù)據(jù)對(duì)比

Astar算法 路徑長(zhǎng)度/m 搜索時(shí)間/s

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

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

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

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

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

表4 不同場(chǎng)景的路徑拓展節(jié)點(diǎn)數(shù)與路徑包括節(jié)點(diǎn)數(shù)數(shù)據(jù)對(duì)比

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

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

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

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

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

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

4 結(jié)論

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

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

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

參考文獻(xiàn)

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

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

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

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

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

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

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