冉東可 彭富倫 李紅光

（西安應(yīng)用光學(xué)研究所 陜西省西安市 710065）

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

1 A*算法原理

A*算法是一種有序搜索算法，相比于Dijkstra 算法，加入了啟發(fā)函數(shù)，使其朝著目標(biāo)點有方向性的擴(kuò)展節(jié)點，因此算法效率有了較大的提升。

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

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

2 算法分析

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

2.1 啟發(fā)函數(shù)的設(shè)置

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

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

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

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

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

3 算法改進(jìn)

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

3.1 啟發(fā)函數(shù)設(shè)置

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

式中，a 為權(quán)值，h(p)是當(dāng)前節(jié)點n 的父節(jié)點p 到目標(biāo)點的距離。

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

3.2 搜索策略選擇

選擇合適的搜索策略有助于讓搜索快速收斂到最優(yōu)路徑。文獻(xiàn)[10]引入雙向搜索機(jī)制，在環(huán)境規(guī)模較大時體現(xiàn)出其搜索速度快的優(yōu)勢。文獻(xiàn)采用移動窗口法獲取搜索網(wǎng)格候選集，每次擴(kuò)展節(jié)點時只選取代價最小的5 個方向，縮小搜索范圍。

文獻(xiàn)提出了JPS 跳點搜索策略，根據(jù)一定規(guī)則從網(wǎng)格中選擇性地擴(kuò)展某些點，“跳躍”不影響搜索的最優(yōu)性。結(jié)果表明JPS 跳點搜索在搜索效率方面比傳統(tǒng)A*算法提升了一個數(shù)量級。在此基礎(chǔ)上，文獻(xiàn)提出雙向跳點搜索算法，進(jìn)一步減少了跳點的數(shù)量，加快搜索速度。

針對傳統(tǒng)8 鄰域搜索范圍規(guī)劃的路徑不平滑問題，文獻(xiàn)在此基礎(chǔ)上又增加了外層8個節(jié)點，即對當(dāng)前節(jié)點來說有16個待擴(kuò)展節(jié)點，使得規(guī)劃的路徑更加平滑。

3.3 數(shù)據(jù)存儲與查找改進(jìn)

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

3.4 其他方面改進(jìn)

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

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

4 面臨的挑戰(zhàn)與研究方向

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

4.1 擴(kuò)展A*算法的應(yīng)用環(huán)境

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

4.2 合理剪枝縮小搜索范圍

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

4.3 與其他算法融合

隨著現(xiàn)代設(shè)備無人化智能化的應(yīng)用需求，對于規(guī)劃技術(shù)的要求也越來越高。單一算法有時不能很好地解決問題，因此將多個算法融合起來將是一個新的發(fā)展趨勢。A*算法作為一種傳統(tǒng)規(guī)劃方法應(yīng)用廣泛，可與近年來出現(xiàn)的智能算法相結(jié)合，取長補(bǔ)短，更好的發(fā)揮優(yōu)勢。

5 總結(jié)與展望

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