基于改進(jìn)的A算法的復(fù)雜環(huán)境下路徑規(guī)劃研究

中圖分類號：TP242.6 DOI：10.16578/j.issn.1004.2539.2025.07.003

0 引言

移動機(jī)器人是目前科學(xué)技術(shù)發(fā)展最活躍的領(lǐng)域之一，其應(yīng)用范圍不斷擴(kuò)展，不僅在工業(yè)、農(nóng)業(yè)、醫(yī)療等行業(yè)中得到廣泛應(yīng)用，而且在城市安全、國防和空間探測等有害與危險場合得到了很好的應(yīng)用。路徑規(guī)劃是移動機(jī)器人能否自主完成任務(wù)的關(guān)鍵，已成為研究的熱點(diǎn)和難點(diǎn)。路徑規(guī)劃的主要目的是在有障礙物的環(huán)境下，避開障礙物并搜索出最優(yōu)路徑。

目前，主要的路徑規(guī)劃算法有A算法、Dijkstra算法[3]、深度優(yōu)先搜索（Depth-First Search，DFS）算法4、廣度優(yōu)先搜索（Breadth-First Search，BFS）算法5、最小生成樹算法、快速探索隨機(jī)樹（Rapidly-exploringRandomTree，RRT）算法等。其中， A^* 算法作為目前最經(jīng)典的路徑搜索算法，在移動機(jī)器人的路徑規(guī)劃中應(yīng)用廣泛；但A算法規(guī)劃得到的路徑可能存在節(jié)點(diǎn)多、拐點(diǎn)多、路徑不平滑、距離障礙物過近等缺點(diǎn)，不利于移動機(jī)器人的控制和保護(hù)。D*算法在A算法的基礎(chǔ)上進(jìn)行了改進(jìn)，可以實(shí)現(xiàn)在不完全重新規(guī)劃路徑的情況下進(jìn)行增量式更新，進(jìn)而適應(yīng)動態(tài)環(huán)境；但對于復(fù)雜地圖，D算法需要大量的存儲空間來維持搜索樹和其他數(shù)據(jù)結(jié)構(gòu)，因此，不適用于復(fù)雜環(huán)境下的路徑規(guī)劃。文獻(xiàn)[10]為優(yōu)化 A^* 算法的搜索效率，提出了一種改進(jìn)路徑的生成方法，采用梯度下降法1進(jìn)行路徑長度優(yōu)化。但梯度下降法容易陷入局部最優(yōu)解，在初始路徑選擇不當(dāng)或優(yōu)化過程受到局部極小值的影響時，可能無法找到全局最優(yōu)解。文獻(xiàn)[12]提出了一種結(jié)合模擬退火法[13的全局最優(yōu)路徑規(guī)劃。但是，在路徑規(guī)劃中通常有一些約束條件，在必須滿足避開障礙物或特定的路徑條件時，模擬退火法難以處理這些約束條件，導(dǎo)致在復(fù)雜環(huán)境下搜索的時間過長。

針對上述問題，本文提出了一種幾何拓展的全局路徑規(guī)劃算法。首先，將傳統(tǒng)A算法的8鄰域搜索擴(kuò)展為12鄰域搜索；再將柵格地圖[14]上的啟發(fā)式信息以移動機(jī)器人尺寸為基礎(chǔ)進(jìn)行幾何拓展，得到移動機(jī)器人的碰撞模型；然后，依據(jù)碰撞模型將遇到障礙物的路徑分為4種代價路徑，在避免碰撞的前提下取最小路徑為移動機(jī)器人的規(guī)劃路徑；最后，采用三次樣條插值法[15對路徑進(jìn)行平滑處理。

1A*算法的改進(jìn)

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

A算法是一種啟發(fā)式搜索算法，主要用于移動機(jī)器人的路徑規(guī)劃。在移動機(jī)器人的路徑規(guī)劃中，移動機(jī)器人的狀態(tài)是路徑的節(jié)點(diǎn)，移動機(jī)器人的代價是路徑的距離。A算法的工作原理：首先，通過代價估計函數(shù)確定起點(diǎn)的搜索方向；然后，向起點(diǎn)搜索的8個鄰域方向拓展，得到最小代價節(jié)點(diǎn)；再從最小代價節(jié)點(diǎn)繼續(xù)搜索鄰域的下一個最小代價的節(jié)點(diǎn)，直至搜索到目標(biāo)終點(diǎn)，生成最終路徑。在搜索過程中，由于路徑由搜索的最小代價節(jié)點(diǎn)組成，因此，得到的路徑代價是最小的。A算法的代價估計[1]函數(shù)為

F（n）=G（n）+H（n）

式中， F（n） 表示從起點(diǎn)經(jīng)由任意節(jié)點(diǎn)到終點(diǎn)的代價估計函數(shù)； G（n） 表示起點(diǎn)到節(jié)點(diǎn)的實(shí)際代價； H（n） 表示節(jié)點(diǎn)到終點(diǎn)的估計代價。常見的計算實(shí)際代價G（n） 和估計代價 H（n） 的方法有：歐幾里得距離、曼哈頓距離和切比雪夫距離。本文采用歐幾里得距離計算兩點(diǎn)之間的實(shí)際代價 G（n） 。 G（n） 的計算式為

式中， （X_s，Y_s） 表示起點(diǎn)坐標(biāo)； （X_n ， Y_n 表示節(jié)點(diǎn)坐標(biāo)。

本文采用曼哈頓距離計算兩點(diǎn)之間的估計代價H（n） 。 H（n） 的計算式為

H（n）=|X_g-X_n|+|Y_g-Y_n|

式中， （X_g，Y_g） 表示終點(diǎn)坐標(biāo)。

傳統(tǒng) ?A^* 算法在搜索過程中通常采用8鄰域的搜索方式，如圖1所示。在柵格地圖上的搜索路徑如圖2所示。

圖2中，黃色表示起點(diǎn)；綠色表示終點(diǎn)；紅色表示路徑；黑色表示障礙物；數(shù)字表示路徑代價和需要的節(jié)點(diǎn)。8鄰域搜索的避障效果如圖3所示。搜索路徑從障礙物的頂點(diǎn)處通過。在考慮移動機(jī)器人外形尺寸的前提下，可將移動機(jī)器人的避障分為兩種情況： ① 搜索路徑從障礙物頂點(diǎn)通過時，移動機(jī)器人必須執(zhí)行回轉(zhuǎn)動作才能有效避免碰撞； ② 當(dāng)移動機(jī)器人運(yùn)動在狹窄路徑時，移動機(jī)器人可能會陷入死區(qū)無法擺脫。

1. 2 A^* 算法的改進(jìn)

針對上述問題，本文將傳統(tǒng)A算法的8鄰域搜索擴(kuò)展為等分12鄰域搜索，如圖4所示。接著，結(jié)合移動機(jī)器人的外形尺寸，對地圖中的障礙物進(jìn)行幾何拓展，得到碰撞模型；再將搜索過程中遇到的單象限障礙物的避障路徑分為4類，將代價值的大小作為搜索優(yōu)先級的判斷依據(jù)，決策出移動機(jī)器人避障的最優(yōu)路徑。本文通過12鄰域搜索得到的路徑具有節(jié)點(diǎn)少、距離短等優(yōu)點(diǎn)，更適用于本文算法在復(fù)雜環(huán)境下的路徑規(guī)劃。過多的搜索鄰域會導(dǎo)致算法的計算量增大、路徑的復(fù)雜程度增加，而且，復(fù)雜環(huán)境中過多的信息容易導(dǎo)致移動機(jī)器人陷人局部最優(yōu)解。

改進(jìn)算法既可以保證移動機(jī)器人與障礙物之間的安全距離，也可以保證移動機(jī)器人在狹窄通道中正常通過。

在傳統(tǒng)A算法的代價函數(shù)中引入障礙物幾何拓展的膨脹半徑信息，以障礙物為中心進(jìn)行幾何拓展，拓展效果如圖5所示。圖5（a）、圖5（b）所示為Mat-lab軟件地圖中障礙物的處理效果；圖5（c）、圖5（d）所示為Ros軟件柵格地圖中障礙物的處理效果。優(yōu)先考慮移動機(jī)器人的避障，將拓展后的區(qū)域視為不可通行區(qū)域，將不一定可通行區(qū)域也視為不可通行區(qū)域，可以降低環(huán)境的復(fù)雜程度，縮小移動機(jī)器人的搜索范圍，提升移動機(jī)器人的搜索效率。

在移動機(jī)器人的單一象限引人碰撞模型，將移動機(jī)器人的避障路徑分為4種情況，如圖6所示。

圖6中，黑色區(qū)域為障礙物；藍(lán)色區(qū)域為障礙物的膨脹半徑；紅色為搜索路徑。圖6（a）中移動機(jī)器人與障礙物一定發(fā)生相撞；圖6（b）中移動機(jī)器人與障礙物的碰撞不一定發(fā)生，是否發(fā)生碰撞取決于移動機(jī)器人的位姿；圖6（c）中移動機(jī)器人與障礙物不會發(fā)生碰撞，該路徑可以確保移動機(jī)器人在遇見突發(fā)情況時有足夠的空間執(zhí)行旋轉(zhuǎn)、后退等操作；圖6（d）中移動機(jī)器人與障礙物不會發(fā)生碰撞，但移動機(jī)器人行走了額外的代價，降低了移動機(jī)器人的搜索效率，違背了最小代價路徑的原則。由此可見，圖6（c）中路徑是移動機(jī)器人避障中的最優(yōu)路徑。在A算法的代價函數(shù)中加入代價估值，改進(jìn)后的 A^′ 算法的代價估計函數(shù)為

F_i=G_i+H_i+C_i

式中， F_i 為總成本； G_i 為已有成本； H_i 為啟發(fā)成本；

C_i 為代價估值。

G_i 的計算式為

式中， X_i? Y_i 為搜索過程中的節(jié)點(diǎn)坐標(biāo)； X_i-1 、 Y_i-1 為前一個節(jié)點(diǎn)坐標(biāo)。

H_i 的計算式為

式中， X_aim ！ Y_aim 為目標(biāo)點(diǎn)的坐標(biāo)。

C_i 的計算式為

式中， τ 為設(shè)定的估值函數(shù)覆蓋范圍； α_i 為地圖中無障礙柵格與最近障礙物柵格膨脹半徑之間的曼哈頓距離。膨脹半徑的計算式為

γ_i=0.5R+τ

式中， γ_i 為障礙物的膨脹半徑； R 為移動機(jī)器人的外接圓半徑。

柵格地圖中，每個柵格的膨脹半徑估值均在預(yù)處理中完成。移動機(jī)器人離障礙物柵格膨脹半徑越近，得到的代價估值越高；反之越小。與障礙物的距離大于設(shè)定的覆蓋距離 τ 時，估值為0，由此設(shè)置障礙物的膨脹半徑區(qū)域估值。移動機(jī)器人搜索至障礙物附近的柵格時，柵格碰撞估值大于0且小于255，表明該區(qū)域可行；且估值越高，距離障礙物越近。非0估值會增加避障代價，僅當(dāng)其他路徑的代價均高于該區(qū)域時，移動機(jī)器人才會選擇該區(qū)域。這種方式可以根據(jù)需求調(diào)整鄰近障礙物區(qū)域的行駛代價，并通過提高代價的方式來保證移動機(jī)器人避障的優(yōu)先性。所提算法的流程如圖7所示。

傳統(tǒng)A算法規(guī)劃的路徑存在距離長、拐點(diǎn)數(shù)多等問題。拐點(diǎn)數(shù)越多，生成的路徑越曲折，路徑的曲率變化程度越大。本文針對生成的路徑存在的拐點(diǎn)過多且不平滑的問題，在拐點(diǎn)處采用三次樣條插值法進(jìn)行平滑處理。三次樣條差值法定義：假如存在這樣的分段函數(shù) S（x） ，在 n+1 個離散點(diǎn)之內(nèi)所構(gòu)成的 n 個相同的任一區(qū)間 [X_i ， X_i+1]（i=0 ，1，2，…，n-1 ， x 遞增）中 S（x）=S_i（x） 都是三次多項式，且在任意點(diǎn)處都滿足 S（x_i）=y_i（i=0 ，1，2，…， n） ，那么，可將這樣的函數(shù)稱作三次樣條差值函數(shù)。 S（x） 具有2階導(dǎo)數(shù)，且其2階導(dǎo)數(shù)在區(qū)間 [a ， b] 內(nèi)連續(xù)，所以，S（x） 曲線是一條光滑曲線，由該函數(shù)得出的路徑也是光滑的。曲線的計算式為

式中， m 為樣條基函數(shù)的階數(shù)；基函數(shù) J_j，m（x） 可表示為

路徑的平滑處理對比如圖8所示。

2 改進(jìn)的A算法的仿真驗證

2.1復(fù)雜環(huán)境的構(gòu)建與柵格地圖的繪制

為驗證改進(jìn)A算法的有效性，進(jìn)行了仿真研究。首先，進(jìn)行復(fù)雜環(huán)境的構(gòu)建與柵格地圖的繪制。采用 Ros 軟件系統(tǒng)中的Gazebo模塊搭建不同復(fù)雜程度的迷宮地圖，設(shè)置了3種復(fù)雜程度的地圖，分別是尺寸為 10m×10m 的簡單地圖、 30m×30m 的一般地圖和 100m×100m 的復(fù)雜地圖，地圖均由質(zhì)量 0.5kg 、體積為 1m³ 的方塊組成。迷宮地圖如圖9所示，地圖參數(shù)如表1所示。

采用Gmapping建圖算法繪制柵格地圖，并用蒙特卡洛定位法對移動機(jī)器人進(jìn)行實(shí)時定位。具體步驟如下：首先，使用激光雷達(dá)和輪式里程計對地圖和移動機(jī)器人數(shù)據(jù)進(jìn)行實(shí)時采集；再通過卡爾曼濾波器對已采集的激光雷達(dá)數(shù)據(jù)和里程計數(shù)據(jù)進(jìn)行融合，并將數(shù)據(jù)重新設(shè)置成一個多維狀態(tài)向量，其中，里程計數(shù)據(jù)用于對移動機(jī)器人狀態(tài)的預(yù)測，激光雷達(dá)數(shù)據(jù)用于對移動機(jī)器人當(dāng)前狀態(tài)的校正；最后，采用概率濾波算法20處理傳感器測量數(shù)據(jù)的不確定性和噪聲。該方法生成的地圖合理，具有較高的精度，且能較好地適應(yīng)不同復(fù)雜程度的仿真迷宮地圖。生成的柵格地圖如圖10所示。

2.2仿真過程與結(jié)果

在Ros軟件中的Gazebo模塊環(huán)境下搭建了簡單、一般、復(fù)雜3種復(fù)雜程度的地圖，并對傳統(tǒng)A算法和本文改進(jìn) A^* 算法進(jìn)行相同次數(shù)的路徑規(guī)劃仿真，路徑對比如圖11所示。圖11中，灰色表示障礙物；白色區(qū)域表示已探索區(qū)域；折線表示路徑；箭頭表示移動機(jī)器人的實(shí)時檢測方向。

由圖11可知，A算法得到的路徑在不同復(fù)雜程度環(huán)境下均有距離障礙物過近、發(fā)生明顯偏折、規(guī)劃錯誤的缺點(diǎn)，且移動機(jī)器人在搜索路徑時容易陷入膨脹半徑區(qū)域；而本文算法得到的路徑更簡潔平滑，大部分路徑與障礙物保持了一定距離，降低了移動機(jī)器人與障礙物發(fā)生碰撞的風(fēng)險。此外，本文算法在地圖中的狹窄區(qū)域預(yù)留出移動機(jī)器人可以執(zhí)行回轉(zhuǎn)操作的空間，且需調(diào)整位姿的拐點(diǎn)更少，解決了移動機(jī)器人陷入死區(qū)的問題。本文算法與A算法的仿真路徑主要評價指標(biāo)如表2所示。

由表2可知，本文算法生成的路徑長度縮短了約20% ，搜索速度提升了約 23% ，移動機(jī)器人的運(yùn)動時間縮短了約 32.5% 。本文算法得到的路徑比傳統(tǒng)A算法更為簡單、安全，在節(jié)點(diǎn)數(shù)以及路徑平滑性等方面比傳統(tǒng) ?A^* 算法更具優(yōu)勢。

3改進(jìn)的A算法的試驗驗證

3.1 試驗場地和移動機(jī)器人

本文在對傳統(tǒng)A算法和改進(jìn)A算法進(jìn)行仿真對比的基礎(chǔ)上，又進(jìn)行了試驗對比?；贚inux系統(tǒng)，記錄A算法和改進(jìn)算法在實(shí)際環(huán)境中的路徑規(guī)劃數(shù)據(jù)，主要包括路徑情況、執(zhí)行時間、拐點(diǎn)等。對比兩種算法在實(shí)際環(huán)境中的處理情況，重點(diǎn)觀察路徑規(guī)劃的準(zhǔn)確性、移動機(jī)器人與障礙物的距離。

試驗采用的場地如圖12（a）所示。場地為長度30m 、寬度 15m 的試驗教室，場地中擺放各種尺寸的障礙物。采用的移動機(jī)器人如圖12（b）所示。移動機(jī)器人的主要參數(shù)為：長為 0.6m ；寬為 0.4m 高為 0.8m ；質(zhì)量為 20kg ；最大承載為 50kg ；最大速度為 0.2m/s 。移動機(jī)器人配備有Linux系統(tǒng)的計算機(jī)、激光雷達(dá)等設(shè)備。

3.2試驗過程與結(jié)果

試驗過程： ① 采用Gmapping算法進(jìn)行建圖，得到圖13所示的柵格地圖。其中，柵格大小為1； ② 下載程序至移動機(jī)器人，設(shè)置移動機(jī)器人的參數(shù)；③ 指定起點(diǎn)和終點(diǎn)，移動機(jī)器人執(zhí)行傳統(tǒng)A算法或改進(jìn)的A算法進(jìn)行路徑搜索； ④ 整理試驗結(jié)果并進(jìn)行分析。試驗路徑的細(xì)節(jié)對比如圖14所示。其中，綠色為移動機(jī)器人規(guī)劃的路徑；紅色箭頭為移動機(jī)器人的實(shí)時方向；間隔時間為 0.2s 。

3.3 試驗結(jié)果分析

從圖14可以看出，傳統(tǒng)A算法規(guī)劃的路徑存在距離障礙物過近、偏折角度過大、拐點(diǎn)較多、不平滑的問題。本文算法與A算法的試驗路徑主要評價指標(biāo)如表3所示。由表3可知，本文算法生成的路徑長度縮短了約 17% ，搜索速度提升了約 27% ，移動機(jī)器人的運(yùn)動時間縮短了約 33% 。本文算法在復(fù)雜環(huán)境下能保證移動機(jī)器人與障礙物始終保持安全距離，解決了移動機(jī)器人在避障處可能發(fā)生碰撞的問題；在復(fù)雜環(huán)境下的狹窄區(qū)域中給移動機(jī)器人預(yù)留有回轉(zhuǎn)空間，需要調(diào)整移動機(jī)器人位姿的情況更少，避免了移動機(jī)器人陷入狹窄區(qū)域無法脫困的情況。

4結(jié)論

針對傳統(tǒng)A算法在復(fù)雜環(huán)境路徑規(guī)劃中存在的路徑偏折、陷入死區(qū)及平滑度不足等問題，提出了基于幾何拓展的全局路徑規(guī)劃算法，通過仿真與試驗驗證了其有效性。相較于傳統(tǒng)方法，改進(jìn)后的算法在以下三個方面展現(xiàn)出顯著優(yōu)勢：1）路徑魯棒性提升：通過12鄰域搜索擴(kuò)展與障礙物幾何建模，改進(jìn)A算法有效降低了碰撞風(fēng)險，成功解決了狹窄通道內(nèi)的回轉(zhuǎn)失效問題2）路徑質(zhì)量優(yōu)化：基于四類代價路徑的決策機(jī)制減少了路徑拐點(diǎn)數(shù)量；結(jié)合三次樣條插值法后，路徑平滑度得到明顯提升。3）算法適應(yīng)性增強(qiáng)：在復(fù)雜靜態(tài)環(huán)境下，算法改善了移動機(jī)器人的導(dǎo)航通過性，使其可更可靠地完成從起點(diǎn)到終點(diǎn)的路徑規(guī)劃任務(wù)。本文研究的是室內(nèi)靜態(tài)復(fù)雜環(huán)境中移動機(jī)器人的路徑規(guī)劃問題，難以適應(yīng)室外環(huán)境和動態(tài)環(huán)境。未來將研究改進(jìn)的A算法與其他動態(tài)路徑規(guī)劃算法結(jié)合，以用于移動機(jī)器人在動態(tài)復(fù)雜環(huán)境中的路徑規(guī)劃。

參考文獻(xiàn)

[1]XU X，ZENGJZ，ZHAO Y，etal. Research on global path plan ningalgorithmformobilerobotsbasedonimprovedA*[J].Expert Systemswith Applications，2024，243：122922.

[2] AMMARA.ERA*：EnhancedRelaxed A^* algorithm for solving theshortestpathproblemin regulargridmaps[J].InformationSciences，2024，657：120000.

[3] 鞏慧，倪翠，王朋，等.基于Dijkstra算法的平滑路徑規(guī)劃方法 [J].北京航空航天大學(xué)學(xué)報，2024，50（2）：535-541. GONG Hui，NI Cui，WANG Peng，et al.A smooth path planning method based onDijkstra algorithm[J].Journal ofBeijingUniversityofAeronauticsandAstronautics，2024，50（2）：535-541.

[4]張建民，黎鐵軍，張峻，等.基于深度優(yōu)先搜索與增量式求解的極 小一階不可滿足子式提取算法[J].國防科技大學(xué)學(xué)報，2012，34 （5）：121-126. ZHANGJianmin，LI Tiejun，ZHANG Jun，etal.Analgorithmfor extractingminimal first-orderunsatisfiable subformulaeon depth first-searchand incremental solving[J]. Journal ofNational UniversityofDefenseTechnology，2012，34（5）：121-126.

[5]徐啟澤，韓文廷，陳俊仕，等.眾核平臺上廣度優(yōu)先搜索算法的優(yōu) 化[J].計算機(jī)科學(xué)，2019，46（1）：314-319. XUQize，HAN Wenting，CHEN Junshi，et al.Optimization of breadth-first search algorithm based on many-core platform[J]. ComputerScience，2019，46（1）：314-319.

[6]江波，張黎.基于Prim算法的最小生成樹優(yōu)化研究[J].計算機(jī)工 程與設(shè)計，2009，30（13）：3244-3247. JIANG Bo，ZHANG Li. Research on minimum spanning tree based on Prim algorithm[J]. Computer Engineering and Design， 2009，30（13）：3244-3247.

[7］李兆強(qiáng)，張時雨.基于快速RRT算法的三維路徑規(guī)劃算法研究 [J].系統(tǒng)仿真學(xué)報，2022，34（3）：503-511. LI Zhaoqiang，ZHANG Shiyu. Research on 3D path planing algorithm based on fast RRT algorithm[J].Journal of System Simulation，2022，34（3）：503-511.

[8］趙倩楠，黃宜慶.融合A蟻群和動態(tài)窗口法的機(jī)器人路徑規(guī)劃 [J].電子測量與儀器學(xué)報，2023，37（2）：28-38. ZHAO Qiannan， HUANG Yiqing. Robot path planning based on A* ant colony and dynamic window algorithm[J]. Journal of ElectronicMeasurement and Instrumentation，2023，37（2）：28-38.

[9]史久根，劉春霞，席海強(qiáng).CA模型下的改進(jìn) D^* 路徑規(guī)劃算法 [J].電子測量與儀器學(xué)報，2016，30（1）：30-37. SHI Jiugen，LIU Chunxia， XI Haiqiang. Improved D^* path planning algorithm based on CA model[J]. Journal of Electronic Measurement and Instrumentation，2016，30（1）：30-37.

[10］孫小倩，辛紹杰.基于改進(jìn)型A算法的移動機(jī)器人路徑規(guī)劃[J]. 組合機(jī)床與自動化加工技術(shù)，2023（3）：5-8. SUNXiaoqian，XIN Shaojie.Research onmobile robot path planning based on improved A^* algorithm[J].Modular Machine Tool amp; Automatic Manufacturing Technique，2023（3） ：5-8.

[11］史加榮，王丹，尚凡華，等.隨機(jī)梯度下降算法研究進(jìn)展[J].自動 化學(xué)報，2021，47（9）：2103-2119. SHI Jiarong，WANG Dan，SHANG Fanhua，et al.Research advances on stochastic gradient descent algorithms[J].Acta Automatica Sinica，2021，47（9）：2103-2119.

[12]徐微，湯俊偉，張馳.改進(jìn)A與動態(tài)窗口算法的移動機(jī)器人路徑 規(guī)劃[J].計算機(jī)仿真，2023，40（3）：447-452. XU Wei，TANG Junwei，ZHANG Chi. Path planning of mobile robot based on improved A^* and dynamic window algorithm[J]. Computer Simulation，2023，40（3）：447-452.

[13］何慶，吳意樂，徐同偉.改進(jìn)遺傳模擬退火算法在TSP優(yōu)化中的 應(yīng)用[J].控制與決策，2018，33（2）：219-225. HE Qing，WU Yile，XU Tongwei. Application of improved genetic simulated annealing algorithm in TSP optimization[J].Control andDecision，2018，33（2）：219-225.

[14］劉景森，吉宏遠(yuǎn)，李煜.基于改進(jìn)蝙蝠算法和三次樣條插值的機(jī) 器人路徑規(guī)劃[J].自動化學(xué)報，2021，47（7）：1710-1719. LIU Jingsen，JI Hongyuan，LI Yu. Robot path planning based on improved bat algorithm andcubic spline interpolation[J].ActaAutomatica Sinica，2021，47（7）：1710-1719.

[15］岳偉韜，蘇婧，谷志珉，等.占據(jù)柵格地圖的最佳柵格大小與地圖 精度[J].機(jī)器人，2020，42（2）：199-206. YUE Weitao，SU Jing，GU Zhimin，et al. Best grid size of the occupancy grid map and its accuracy[J].Robot，2020，42（2）：199-206.

[16］蔣林，方東君，周和文，等.基于射線模型的改進(jìn)全局路徑規(guī)劃算 注「］中子學(xué)0）50（2）.540556 JIANGLin，F(xiàn)ANG Dongjun，ZHOUHewen，etal. Improved global path planningalgorithmbasedonraymodel[J].Acta ElectronicaSinica，2022，50（3）：548-556.

[17]焦嵩鳴，姚鑫，丁輝，等.適應(yīng)于環(huán)境空間變化的激光雷達(dá)SLAM 建圖方法[J].系統(tǒng)仿真學(xué)報，2023，35（8）：1788-1798. JIAO Songming，YAO Xin，DINGHui，etal.Lidar SLAM mapping method adapted to environmental spatial changes[J]. Journal ofSystem Simulation，2023，35（8）：1788-1798.

[18］操鳳萍，樊啟要.基于自適應(yīng)蒙特卡洛算法的實(shí)時定位研究[J]. 計算機(jī)工程，2018，44（9）：28-32，37. CAOFengping，F(xiàn)AN Qiyao.Research on real-time positioning based on adaptiveMonte Carlo algorithm[J].ComputerEngineer ing，2018，44（9）：28-32，37.

[19］張海剛，聶圓圓，張磊，等.基于改進(jìn)卡爾曼濾波的無速度傳感器探究[J].系統(tǒng)仿真學(xué)報，2018，30（10）：3761-3769.ZHANGHaigang，NIE Yuanyuan，ZHANGLei，etal.Research onsensorless control method based on improved Kalman filter of slid-ingmodeobserver[J].Journal of System Simulation，2018，30（10）：3761-3769.

[20］楊峰，王永齊，梁彥，等.基于概率假設(shè)密度濾波方法的多目標(biāo)跟蹤技術(shù)綜述[J].自動化學(xué)報，2013，39（11）：1944-1956.YANGFeng，WANGYongqi，LIANGYan，etal.AsurveyofPHDfilterbased multi-target tracking[J].Acta Automatica Sinica，2013，39（11）：1944-1956.

Research on path planning in complex environment based on improved A* algorithm

KANG Kaishen HUANG Hailong （CollegeofchanicalEngineeringandAtomation，LiaoningUiversityofechnologyJihouo，ina）

Abstract：[ObjectivelTheglobal path planningalgorithmfor mobilerobots currentlyfaces challenges suchasexcessive inflectionpoints，prolongedomputationtiandineficiencyiomplexvironments.Taddresthseissesnipoved A^* algorithmwasproposedandexperimentallyvalidatedundercomplexenvironmentalconditions.[Methods]Firstly，the traditional 8-neighborhood search of the A^* algorithm was expanded to a 12-neighborhood search.Subsequently，based on the colisionmodelderivedfromenvironmentalheursticinformationprocesing，thesearchedpathswerecategorzedintofourcost types，withtheleas-cospathselectedasteoptimalrajectoryforthemobilerobot.Finalltheoptimalpathobainedfromthe planing wassmoothed usingthecubic spline interpolation method.[Results]Testresultsdemonstratethat，comparedtothe traditional A^* algorithm，the improved A^* algorithm achieves search speed improvements of 32.68% ， 33.40% and 20.17% in simple，moderateandcomplexenvironments，espectivelyAdditionaly，thenumberofseverepathdeflections isreducedby 35.71% ， 43.67% and 47.58% in these environments.The obtained path has the advantages of fewer nodes，a shorter distance， and a smoother trajectory.

Keywords：Mobilerobot;Globalpathplanning; A^* algorithm;Costpath;Cubic spline interpolationmethod