基于A*算法的路徑規劃研究綜述

冉東可 彭富倫 李紅光

（西安應用光學研究所 陜西省西安市 710065）

A*（A-Star）算法是一種靜態路網中求解最短路徑的直接搜索方法，因其靈活簡便和對完整性及最優性的保證得以在機器人低維路徑規劃領域中廣泛應用。但同時也存在以下缺陷：一是在大規模環境中應用時，節點網絡非常龐大，算法運行時間長；二是擴展節點時占用內存開銷較大；三是計算復雜度依賴環境網格分辨率大小。針對這些缺陷，已有很多學者提出了改進。本文首先介紹A*算法原理并進行影響因素分析，然后從啟發函數、搜索策略、數據存儲與查找等方面介紹A*算法的改進方法及研究現狀，進而展望了算法未來發展和面臨的挑戰。

1 A*算法原理

A*算法是一種有序搜索算法，相比于Dijkstra 算法，加入了啟發函數，使其朝著目標點有方向性的擴展節點，因此算法效率有了較大的提升。

A*算法的特點是，對于遍歷的每一個節點，都采用一個評價函數f(n)來計算其通過該節點的代價，在每一次搜索時總是選擇當前位置周圍通行代價f(n)最小的點來擴展，如此從起始節點不斷搜索直到找到目標節點，生成一條通行代價最小的路徑。關于評價函數的計算方式如下式：

其中，h(n)代表從當前點到目標點的估計代價，同時也是啟發函數，g(n)計算方式為從起點到節點n 的實際行走距離。

2 算法分析

由原理分析可知，影響A*算法搜索效率的主要因素是：

2.1 啟發函數的設置

一般來說，從當前節點到目標點的啟發函數一般小于實際路徑代價，這樣才可能得到最優解，但同時會增加擴展的節點數，增大算法時間開銷。理想情況是啟發函數h(n)恰好等于實際路徑代價，這樣擴展節點最少，且剛好能找到最優路徑。

2.2 訪問open表尋找f(n)最小值的時間開銷大

傳統的open 表可能采用Array、List、Queue 等結構來存儲節點信息，隨著搜索深度越深，要查找的節點就越多，每次擴展節點時都需要對open 表排序，查找f 最小值的節點，這會耗費部分時間，所以優化open 表的排序和查找是一個關鍵的改進方向。

2.3 搜索速度慢，時間開銷隨地圖規模增大而增大

路徑規劃搜索算法的效率與地圖搜索空間的規模成反比，A*算法的時間復雜度為O(n2) (n 為節點數)。當地圖規模增大時，待擴展節點增多，算法運行時間也隨之增加。同時，環境越復雜，障礙物較多時，也會導致搜索速度的降低。因此，減少不必要的搜索節點是改善搜索效率的有效方法。

3 算法改進

針對以上缺陷，目前已有學者對其進行了研究和改進，搜索效率已經有所提升。本節主要從啟發函數的設置、搜索策略的選擇、數據存儲與查找及其他方面總結介紹現有的改進方法，概述A*算法的研究現狀。

3.1 啟發函數設置

啟發函數的設置直接影響搜索效率。由A*算法具體搜索過程可知，導致其效率低的一個重要原因是，選擇f 值最小的點作為下一個擴展節點時，總是會出現往返搜索的情況。針對這一問題，文獻增大了啟發函數的權重，使其更偏向目標節點處擴展，如式（2），改進后搜索效率較傳統 A*算法有所提高。文獻[5]在此基礎上在啟發函數中又加入了父節點信息，如式（3），有效減少了往返搜索次數。

式中，a 為權值，h(p)是當前節點n 的父節點p 到目標點的距離。

對于加權A*算法中的權值設置，文獻分別研究了加權曼哈頓距離和切比雪夫距離中權值的選擇對算法效率的影響。文獻提出一種定向加權A*算法，對距離代價的X 軸和Y 軸進行雙軸加權計算，結果表明轉折點數明顯減小。但有時僅用一個常數來表示并不能得到很好的結果。文獻提出了新的設置方法，對當前節點及其父節點的估計路徑代價采用指數衰減方式加權，使得A*算法在離目標點較遠時能夠很快地向目標點靠近，在距目標點較近時能夠局部細致搜索保證目標點附近障礙物較多時目標可達。但缺點是當環境規模較大時，指數權重在路徑搜索初期代價函數會嚴重退化，致使初期得到路徑非最短路徑，增加了路徑長度。

3.2 搜索策略選擇

選擇合適的搜索策略有助于讓搜索快速收斂到最優路徑。文獻[10]引入雙向搜索機制，在環境規模較大時體現出其搜索速度快的優勢。文獻采用移動窗口法獲取搜索網格候選集，每次擴展節點時只選取代價最小的5 個方向，縮小搜索范圍。

文獻提出了JPS 跳點搜索策略，根據一定規則從網格中選擇性地擴展某些點，“跳躍”不影響搜索的最優性。結果表明JPS 跳點搜索在搜索效率方面比傳統A*算法提升了一個數量級。在此基礎上，文獻提出雙向跳點搜索算法，進一步減少了跳點的數量，加快搜索速度。

針對傳統8 鄰域搜索范圍規劃的路徑不平滑問題，文獻在此基礎上又增加了外層8個節點，即對當前節點來說有16個待擴展節點，使得規劃的路徑更加平滑。

3.3 數據存儲與查找改進

由A*算法原理知，搜索時需要不斷訪問open 表和closed 表，為了找某個節點，每次訪問時，都需要遍歷多個節點才能找到指定的節點，并執行添加節點和刪除節點的操作，這會耗費部分時間。關于如何設計表的結構以及訪問方式已有一些研究成果。文獻提出了Lambda*算法，令open 表僅保存當前擴展節點的后續節點，丟掉了當前擴展節點的父節點和子節點，這在很大程度上減少了open 表保存的節點數量，減少了計算量和時耗，但會導致算法獲得的路徑規劃方案質量降低。文獻采用二叉堆方法對open 表中節點進行排序，優化f(n)最小值的查找速度，進一步提升地圖路徑搜索的速度。文獻提出一種改進存儲數組的方法，通過訪問結構化數據，可以一次找到節點，并確定節點的狀態，不需要遍歷多個節點才能找到指定元素。這一方法有效保留算法的優點，提升運行效果。

3.4 其他方面改進

針對算法耗時長問題，文獻提出了稀疏A*搜索算法（SAS），將不滿足約束條件的不可行區域剔除，將可行區域分為若干子區域，利用代價函數尋找各子區域中的最優路徑。該方法通過將約束條件與搜索算法結合起來，有效剪裁搜索空間，節省了搜索時間。

針對動態環境實時規劃需求，文獻提出了D*(Dynamic A*)算法，即從目標點開始反向搜索，并存儲其到各個節點的最短路徑及代價信息，在向目標點移動時，只檢查最短路徑上下一節點或臨近節點的變化情況，這使得遇到未知障礙進行重規劃時效率大大提升。該算法適用于動態場景，被應用于美國火星探測器的尋路規劃。

4 面臨的挑戰與研究方向

A*算法發展至今，取得了大量研究成果。但依然存在以下問題亟待解決：地圖精度與算法搜索效率的平衡、搜索范圍與最優性保證的權衡。本文對現存問題進行總結，并對未來研究方向提出了以下幾點建議。

4.1 擴展A*算法的應用環境

目前針對A*算法的研究主要集中在平坦路面上，障礙物單純表示為能通過或不能通過需繞行。然而在實際應用中，例如野外環境，存在斜坡等可以跨越的障礙。A*算法在二維簡單環境中表現良好，但在復雜環境及三維環境中的應用還有待優化。

4.2 合理剪枝縮小搜索范圍

A*算法在搜索過程中會訪問擴展大量節點，避免陷入局部最優，但是許多距最優路徑較遠的無關節點也會被擴展。現有的改進方法是以犧牲路徑最優性為代價減少待擴展節點。如何剪枝縮小搜索范圍，同時保證能夠找到最優路徑是未來一個關鍵挑戰。

4.3 與其他算法融合

隨著現代設備無人化智能化的應用需求，對于規劃技術的要求也越來越高。單一算法有時不能很好地解決問題，因此將多個算法融合起來將是一個新的發展趨勢。A*算法作為一種傳統規劃方法應用廣泛，可與近年來出現的智能算法相結合，取長補短，更好的發揮優勢。

5 總結與展望

A*算法自提出以來，因其直接簡便、搜索能力強、保證路徑最優性等優點被應用于無人駕駛、醫療給藥、災后救援、采礦探測等領域，能夠完成從起點到目標點的路徑規劃任務。對于其運行時間長、占用內存大、轉折點較多的缺點，已涌現出許多改進方法。雖然在一定程度上使得算法性能得以提升，但在實際應用中還不夠成熟，存在改進空間，尤其是針對野外無路網環境的規劃研究相對較少。因此為了更好的實現路徑規劃和無人駕駛，使其能應用于各種需求場景，對A*算法的進一步改進與優化，具有重要的現實意義。