基于改進A*算法的路徑規劃研究

摘" 要：研究了A*算法在二、三維模型路徑規劃中的優化方法。通過實時閾值法和懲罰因子法減少開放列表中不必要的搜索空間和冗余路徑；采用自定義優先級隊列、二叉堆法和哈希表替代傳統A*算法中的處理方式；在對二維地圖的研究中，采用局部A*算法避免大面積搜索。實驗結果表明，經過改進的A*算法顯著提高了搜索和路徑規劃速度，減少了計算時間和內存消耗，驗證了該算法的可行性和有效性。

關鍵詞：路徑規劃；三維規劃；懲罰因子；二叉堆與自定義優先級隊列；實時閾值；局部A*算法

中圖分類號：TP18；TP242 文獻標識碼：A 文章編號：2096-4706（2024）10-0051-06

Research on Path Planning Based on Improved A* Algorithm

CAI Zifeng， ZHANG Yansheng， LIANG Xianzhang， LUO Shihao

（Zhuhai College of Science and Technology， Zhuhai" 519040， China）

Abstract： It studies the optimization method of A* algorithm in path planning of 2D and 2D models. Reduce unnecessary search space and redundant paths in open lists through real-time threshold method and penalty factor method. Adopting custom priority queues， binary heap methods， and hash tables to replace the processing methods in traditional A* algorithms. In the study of 2D maps， local A* algorithm is used to avoid large-scale searches. The experimental results show that the improved A* algorithm significantly improves the speed of search and path planning， reduces computational time and memory consumption， and verifies the feasibility and effectiveness of the algorithm.

Keywords： path planning; 3D planning; penalty factor; binary heap and custom priority queue; real-time threshold; local A* algorithm

0" 引" 言

路徑規劃是移動機器人實現自主導航的關鍵技術之一。路徑規劃是指在有障礙物的環境中，按照一定的評價標準（如距離、時間、代價等）尋找到一條從起始點到目標點的無碰撞路徑[1-4]。經實驗驗證發現，傳統的A*算法[5，6]在二維和三維模型中生成的路徑存在多個拐點問題，路徑規劃所需時間較長，對移動機器人的性能和安全性產生負面影響。復雜的路徑規劃可能導致機器人在應對環境變化時響應速度較慢，增加過多的轉彎操作可能帶來誤差并加劇機器人硬件的磨損。此外，過多的拐角可能造成視野盲點，增加潛在風險。

針對這些規劃時間過長、效率低下等問題，常用的路徑規劃算法人工勢場法、模糊邏輯算法、自由空間法、遺傳算法等[7，8]在解決路徑規劃問題方面表現出優勢，但計算效率仍有其他的較好的優化方式。為了改善算法的計算效率和路徑優化問題，本文采用柵格法構建環境模型，從兩個方面來優化A*算法：從性能優化的角度，采用實時閾值法、二叉堆與自定義優先級隊列優化，引入哈希表、局部A*算法；從路徑優化的角度，通過設計懲罰因子來減少路徑拐點數，算法會更偏向于走直線路段，進一步優化生成的路徑。

1" 模型建立

1.1" 二維模型建立

在二維地圖模型的研究中，構建一個n行m列的柵格地圖。其中，空白柵格表示可行走區域，而黑色柵格代表障礙物，即無法穿越的區域。研究僅考慮機器人在上下左右4個正方向上的移動，不涉及對角線或其他方向的移動。圖1展示了一個7×7大小的柵格地圖，起點為S（0，0），終點為G（4，4）。

1.2" 三維模型

如圖2所示，構建了一個大小為5×5×5的三維空間，其中黑色區塊表示障礙物的位置，起點（0，0，0）終點（4，4，4）。

2" A*算法的性能優化

2.1" 實時閾值

在圖1中，使用曼哈頓距離作為啟發式函數，代表從當前位置到目標點水平和垂直移動所需的步數。最大曼哈頓距離為14步（例如從S到G），設置啟發式值的閾值為14，在A*搜索中超過閾值的格子將被濾除，濾除的節點將不會參與下一步的計算中。曼哈頓距離公式為：

再例如，假設機器人已經移動到點（2，3），此時的曼哈頓距離為d1 = 7。因此，實時閾值將設為7。在算法推進中，計算出（3，1）和（2，2）兩點的曼哈頓距離均大于閾值，那么直接忽略這兩個節點，如表1所示。

在二維模型中，當啟發式值大于等于某一閾值時，節點將從開放列表中濾除，以節省計算資源。在三維模型中，采用三維模型下的曼哈頓距離式（2）計算周圍點的值，即可達到相同的效果。這種策略特別適用于啟發式函數能夠快速確定無前景路徑的情況。

2.2" 自定義優先級隊列與二叉堆優化

對于傳統的A*算法，隨著算法推進，需要管理大量節點數據，導致時間復雜度增加，計算效率降低。為了優化這一問題，可以通過建立一個自定義的優先級隊列PriorityQueue來改進傳統的A*算法。這個自定義的優先隊列基于Python中的堆實現，同時利用哈希表來快速進行元素查找操作，避免了對整個列表的遍歷來查找特定元素。通過表2來呈現優化前后A*算法的對比。

2.2.1" 二叉堆優化

二叉堆被視為一種特殊的堆數據結構，其結構類似于完全二叉樹。其滿足堆的重要特性：父節點的值始終小于或等于（或者大于或等于）任何一個子節點的值。

如圖3所示[9]，在給定的二叉堆中，假設節點的值表示了A*算法中的F值。最小的F值節點10位于堆的頂部，其次是20作為其子節點。第三小的節點是24，距離堆頂有兩步的距離。盡管它小于30，但30位于第二層左側，距離堆頂只有一步距離。實際上，僅需滿足每個單獨子節點的值都比其父節點大或相等的條件即可，其他節點在堆中的位置并不影響這一性質。這種特性使得二叉堆成為一種高效的數據結構，能夠在A*算法中快速找到最小的節點。

2.2.2" 哈希表

當引入哈希表用于A*算法時，其中節點的狀態作為鍵，與該節點相關的信息（如代價、路徑等）作為值。

哈希函數將節點的狀態映射到存儲桶的位置，其中NodeState是節點狀態的集合，Indices是存儲桶的索引集合[10]。通常可以表示為：

存儲桶仍然代表哈希表的存儲位置，每個存儲桶包含一個鏈表，其中存儲的是與特定狀態相關的信息，如代價和路徑：

當需要查找節點時，通過哈希函數找到節點狀態對應的存儲桶位置i，在存儲桶的鏈表中搜索節點信息。同理，當需要將新的節點信息插入哈希表時，通過哈希函數找到存儲桶的位置i。

搜索操作：

插入操作：

2.3" 局部A*算法

針對大規模二維地圖的問題，無論是經過優化的A*算法還是傳統A*算法都需要處理大量候選節點，從而導致搜索的時間復雜度增加。因此，提出了一種針對大型二維地圖的局部A*算法思路。該方法的主要目標是根據當前節點的位置為中心（xs，ys），裁剪出一塊可自定義邊長rs的區域作為子地圖（x s- rs，ys - rs） （xs + rs，ys + rs），如圖4所示，深灰色區域為D1點的子地圖。這樣算法不再需要處理大量的節點，只需對當前所在子地圖進行計算即可。同時，啟發式函數被修改為當前節點到最終目標點的曼哈頓距離，以更好地適應局部搜索的特點。

將子地圖定義為（left，right，top，bottom），子地圖劃分計算：

確保了子地圖邊界不會超出地圖的合法范圍。

為了展示該方法的有效性，構建一個50×50的二維地圖，并設置起點為（0，0），終點為（49，49）。根據當前點D1的位置，重新修改起始坐標并進行應用A*算法得到D1到D2點為路徑，如圖5所示。

當到達子地圖邊界時，當前節點D2坐標以其為中心劃出新的子地圖，如圖6所示。當劃出的區域超出大地圖時，會做出越界處理靈活改變子地圖的大小，如圖7所示，黑色框為靈活變化后的實際子地圖。

如圖8所示，將所有小地圖的路徑拼接在一起得到最終的路徑。局部的A*算法有效地減少了對大量節點的管理和搜索，從而降低了計算復雜度，提高了搜索效率，并優化了資源利用。

3nbsp; A*算法的路徑優化

在復雜環境中，由于路徑中可能存在大量拐點，導致算法效率降低。圖8、圖9（a）和圖10（a）展示了二維模型和三維模型中傳統算法輸出路徑，其拐點數量顯著。

3.1" 二維模型

為解決該問題，引入節點懲罰因子成為改進A*算法路徑選擇的一項策略。通過添加拐點懲罰因子，算法更傾向于選擇直線路徑而非頻繁轉向的路徑，從而減少拐彎次數，提高路徑規劃效率。

引入父節點P，即當前節點的前一個節點，假設父節點P為（xp，yp），當前節點C為（xc，yc）。

3.1.1" 計算轉向角度

1）計算當前節點C到父節點P的向量和到相鄰節點N的向量：

2）計算向量的點積d和長度l：

3）計算余弦值：

4）進行范圍修正：

如果余弦值cosθ＞1.0，則設置cosθ = 1.0。

如果余弦值cosθ＜-1.0，則設置cosθ = -1.0。

5）計算轉向角度：

3.1.2" 計算轉向懲罰因子

由上一節得到轉向角度θ，假設轉向懲罰因子為K（θ）。假設θ的取值范圍是從0到360度（0到2π弧度），K（θ）的取值范圍是從0到1。

其中，m和b是線性函數的斜率和截距，用于將轉向角度映射到轉向懲罰因子的范圍內。為了滿足條件：

可以確定m和b的值。得到以下兩個方程：

因此得到b = 0；k = 1/360；最后得到的線性函數可以表示為：

最后融入f （n）式子中為：

3.2" 三維模型

在三維模型中，可以采用相同的方法計算轉向角度和轉向懲罰因子，確保計算的角度適用于三維空間，并將角度值代入相同的線性函數中計算轉向懲罰因子。這種轉向懲罰因子的計算仍然遵循相同的線性函數，只需在三維空間中應用。可以將三維模型分解為z-x和x-y或其他兩個二維模型組合，通過計算轉向角度和轉向懲罰因子的方法得到K1（θ）與K2（θ），最后融入三維模型中的f （n）中：

4" 實驗仿真

為驗證改進的A*算法的有效性，在二維和三維模型下分別針對A*算法和融合了實時閾值、二叉堆與優先級隊列、懲罰因子的改進A*算法進行仿真實驗。實驗將在5個不同尺寸的柵格地圖中展開，以全面評估算法在不同場景下的性能表現和適用性。

4.1" 優化路徑實驗仿真

圖9（a）所示的7×7柵格地圖下進行了A*算法的仿真實驗。其中，S代表起始節點，G代表目標節點，黑色柵格表示障礙物，而藍色線段展示了經過A*算法生成的最終路徑。在實驗中，通過引入懲罰因子，進一步優化了路徑的生成，如圖9（b）所示。此外，在50×50的大型柵格地圖中同理，如圖9（c）所示，相比之前的實驗結果（圖8），得到了路徑規劃方面的優化效果。

圖10（a）表示在圖2所建立的三維柵格地圖中進行A*算法的仿真實驗，通過引入三維下的懲罰因子，得到優化的三維路徑，如圖10（b）所示。

4.2" 優化性能實驗仿真

建立一個20×20的二維柵格地圖，起點S（0，0）終點G（19，19），將障礙物的數量設置為自變量，隨機放置在地圖中并每個數量進行2 000次實驗記錄下處理的時間，并且進行死路處理，得到如圖11所示的結果。

其次，5×5×5的三維模型地圖，起點為S（0，0，0），終點為G（4，4，4），并在地圖中隨機放置不同數量的障礙物。進行10次實驗并記錄，計算出處理時間的平均值。表3展示了實驗結果。

通過實驗驗證，在生成相同路徑的基礎上，優化后的自定義優先隊列的A*算法明顯表現出更高的效率和更短的處理時間，甚至在二維模型中平均優化率達到225.98%。這種差距對于實際應用中的實時性和效率至關重要，特別是在需要快速求解的實時路徑規劃和導航等場景中。因此，在大規模或復雜問題的求解中，選擇本文提出的優化方法能夠顯著提升算法的執行效率和性能。

5" 結" 論

A*算法在尋路過程中存在內存開銷大、計算時間長等缺點，不能滿足移動機器人在較大場景路徑規劃中的實時性要求。為了提高路徑規劃的速度，本文分別從性能和路徑優化上進行討論，性能上通過實時閾值、二叉堆優先級隊列和局部A*算法，提高了尋路效率。路徑優化上，通過引進懲罰因子減少拐點數量，從而使。通過在不同規格柵格環境下的仿真實驗證明改進A*算法是可行的、有效的，特別是在較大二維場景和三維模型下效果更加明顯。

參考文獻：

[1] 趙曉，王錚，黃程侃，等.基于改進A*算法的移動機器人路徑規劃 [J].機器人，2018，40（6）：903-910.

[2] 曲道奎，杜振軍，徐殿國，等.移動機器人路徑規劃方法研究 [J].機器人，2008（2）：97-101+106.

[3] 王殿君.基于改進A*算法的室內移動機器人路徑規劃 [J].清華大學學報：自然科學版，2012，52（8）：1085-1089.

[4] JEDDISARAVI K，ALITAPPEH R J，PIMENTA L C A，et al. Multi-Objective Approach for Robot Motion Planning in Search Tasks [J].Applied Intelligence，2016，45（2）：305-321.

[5] 周偉，潘金寶，王林琳.基于改進鯨魚算法和A*算法的地面放線機器人路徑規劃 [J].現代制造工程，2023（12）：68-75+83.

[6] 王洪斌，尹鵬衡，鄭維，等.基于改進的A*算法與動態窗口法的移動機器人路徑規劃 [J].機器人，2020，42（3）：346-353.

[7] 劉建華，楊建國，劉華平，等.基于勢場蟻群算法的移動機器人全局路徑規劃方法 [J].農業機械學報，2015，46（9）：18-27.

[8] 朱大奇，顏明重.移動機器人路徑規劃技術綜述 [J].控制與決策，2010，25（7）：961-967.

[9] 周小鏡.基于改進A*算法的游戲地圖尋徑的研究 [D].重慶：西南大學，2011.

[10] 安彥哲，朱妤晴，王建民.物聯網大數據場景下的分布式哈希表適用條件分析 [J].計算機學報，2021，44（8）：1679-1695.

作者簡介：蔡梓豐（2001—），男，漢族，廣東佛山人，本科在讀，研究方向：移動機器人路徑規劃。