基于改進的A算法的復雜環境下路徑規劃研究

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

0 引言

移動機器人是目前科學技術發展最活躍的領域之一，其應用范圍不斷擴展，不僅在工業、農業、醫療等行業中得到廣泛應用，而且在城市安全、國防和空間探測等有害與危險場合得到了很好的應用。路徑規劃是移動機器人能否自主完成任務的關鍵，已成為研究的熱點和難點。路徑規劃的主要目的是在有障礙物的環境下，避開障礙物并搜索出最優路徑。

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

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

1A*算法的改進

1. 1 傳統A算法

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

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

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

式中， （X_s，Y_s） 表示起點坐標； （X_n ， Y_n 表示節點坐標。

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

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

式中， （X_g，Y_g） 表示終點坐標。

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

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

1. 2 A^* 算法的改進

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

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

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

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

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

F_i=G_i+H_i+C_i

式中， F_i 為總成本； G_i 為已有成本； H_i 為啟發成本；

C_i 為代價估值。

G_i 的計算式為

式中， X_i? Y_i 為搜索過程中的節點坐標； X_i-1 、 Y_i-1 為前一個節點坐標。

H_i 的計算式為

式中， X_aim ！ Y_aim 為目標點的坐標。

C_i 的計算式為

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

γ_i=0.5R+τ

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

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

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

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

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

2 改進的A算法的仿真驗證

2.1復雜環境的構建與柵格地圖的繪制

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

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

2.2仿真過程與結果

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

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

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

3改進的A算法的試驗驗證

3.1 試驗場地和移動機器人

本文在對傳統A算法和改進A算法進行仿真對比的基礎上，又進行了試驗對比。基于Linux系統，記錄A算法和改進算法在實際環境中的路徑規劃數據，主要包括路徑情況、執行時間、拐點等。對比兩種算法在實際環境中的處理情況，重點觀察路徑規劃的準確性、移動機器人與障礙物的距離。

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

3.2試驗過程與結果

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

3.3 試驗結果分析

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

4結論

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

參考文獻

[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算法的平滑路徑規劃方法 [J].北京航空航天大學學報，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]張建民，黎鐵軍，張峻，等.基于深度優先搜索與增量式求解的極 小一階不可滿足子式提取算法[J].國防科技大學學報，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]徐啟澤，韓文廷，陳俊仕，等.眾核平臺上廣度優先搜索算法的優 化[J].計算機科學，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算法的最小生成樹優化研究[J].計算機工 程與設計，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］李兆強，張時雨.基于快速RRT算法的三維路徑規劃算法研究 [J].系統仿真學報，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蟻群和動態窗口法的機器人路徑規劃 [J].電子測量與儀器學報，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]史久根，劉春霞，席海強.CA模型下的改進 D^* 路徑規劃算法 [J].電子測量與儀器學報，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］孫小倩，辛紹杰.基于改進型A算法的移動機器人路徑規劃[J]. 組合機床與自動化加工技術，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].自動 化學報，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]徐微，湯俊偉，張馳.改進A與動態窗口算法的移動機器人路徑 規劃[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］何慶，吳意樂，徐同偉.改進遺傳模擬退火算法在TSP優化中的 應用[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］劉景森，吉宏遠，李煜.基于改進蝙蝠算法和三次樣條插值的機 器人路徑規劃[J].自動化學報，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].機器人，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］蔣林，方東君，周和文，等.基于射線模型的改進全局路徑規劃算 注「］中子學0）50（2）.540556 JIANGLin，FANG Dongjun，ZHOUHewen，etal. Improved global path planningalgorithmbasedonraymodel[J].Acta ElectronicaSinica，2022，50（3）：548-556.

[17]焦嵩鳴，姚鑫，丁輝，等.適應于環境空間變化的激光雷達SLAM 建圖方法[J].系統仿真學報，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］操鳳萍，樊啟要.基于自適應蒙特卡洛算法的實時定位研究[J]. 計算機工程，2018，44（9）：28-32，37. CAOFengping，FAN Qiyao.Research on real-time positioning based on adaptiveMonte Carlo algorithm[J].ComputerEngineer ing，2018，44（9）：28-32，37.

[19］張海剛，聶圓圓，張磊，等.基于改進卡爾曼濾波的無速度傳感器探究[J].系統仿真學報，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］楊峰，王永齊，梁彥，等.基于概率假設密度濾波方法的多目標跟蹤技術綜述[J].自動化學報，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