基于A*算法的路徑規(guī)劃研究綜述

冉東可 彭富倫 李紅光

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

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

1 A*算法原理

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

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

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

2 算法分析

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

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

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

2.2 訪問(wèn)open表尋找f(n)最小值的時(shí)間開(kāi)銷(xiāo)大

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

2.3 搜索速度慢，時(shí)間開(kāi)銷(xiāo)隨地圖規(guī)模增大而增大

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

3 算法改進(jìn)

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

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

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

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

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

3.2 搜索策略選擇

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

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

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

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

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

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

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

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

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

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

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

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

4.2 合理剪枝縮小搜索范圍

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

4.3 與其他算法融合

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

5 總結(jié)與展望

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