基于鄰域拓展的靜態路徑規劃A*算法研究

郭曉靜，楊卓橙

中國民航大學 電子信息與自動化學院，天津 300300

路徑規劃指的是在障礙物空間中，快速有效地尋找出一條從起始位置到目標位置的無碰撞的路徑[1-2]。現在廣泛使用的路徑規劃算法有基于概率采樣的RRT算法[3]等，它能夠快速地在障礙空間中搜索出一條路徑，但當環境中的通路狹窄時，算法搜索容易陷入長時間的停滯狀態；文獻[4]將道路約束加入到RRT算法中限制算法的隨機性，以求出符合車輛實際使用的路徑，但是它不適用于動態環境下的路徑規劃；基于圖搜索的Dijkstra算法[5-6]是經典的用于解決最短路徑問題的算法，但是其搜索過程會耗費大量時間和存儲空間；文獻[7]對Dijkstra算法的存儲結構進行了優化，整體降低了算法搜索的時間復雜度，但是在大地圖中其時間花費仍然高于其他算法；文獻[8]考慮實際路徑中存在的必經點限制，并將其加入Dijkstra算法，雖然能獲得滿足要求的路徑，但是也增加了時間花費；具有啟發式思想的A*算法[9-10]被認為是靜態環境中進行最短路徑規劃的最有效方法，但它規劃出的路徑存在拐角過大、遍歷節點較多等缺點；文獻[11]將A*算法應用于機器人路徑規劃問題，傳統方法中，機器人只能向8個方向擴展，由于搜索的節點數目較少，在前期就將更優秀的節點從搜索列表中刪除，將8鄰域拓展至24鄰域搜索，提高了路徑搜索的自由度，并與動態窗口法結合，提高了路徑的平滑度與安全性，但是其在大地圖中計算效率低下；文獻[12]將搜索節點的多輩父節點信息引入啟發函數，以此減少估計代價的局部最優情況，同時融合模擬退火算法優化節點選擇，但是其在大地圖和障礙物復雜的情況下算法將產生很多無用的節點擴展，進而消耗大量時間；文獻[13]針對未知環境中的智能體路徑規劃問題，提出一種多層雙向A*算法，使智能體可以響應環境中的突發障礙，但該方法搜索自由度較低，會使規劃出的路徑出現繞遠的情況；文獻[14]針對傳統A*算法規劃出的路徑碰撞威脅大，不適合智能小車實際使用的問題，將障礙物安全距離引入啟發式函數，從而降低碰撞威脅，但是該方法會使算法搜索更多的節點。

因此本文針對靜態網絡路徑規劃問題，提出一種改進的A*算法，利用A*取評估函數最小節點拓展的性質，生成對應方向向量對額外鄰域的拓展進行引導，使傳統A*算法有更高的自由度，同時也避免大量增加計算量。然后對獲得的路徑節點進行檢查，進一步剔除冗余節點，使最終所得路徑更短、更平滑。將該方法用于大地圖環境的路徑規劃中時，獲得的路徑比8鄰域及24鄰域的A*算法更短，搜索時間花費更少。

1 改進的A＊算法

傳統A*算法是一種啟發式的圖搜索算法[15-16]。它依靠評估函數f(n)來引導它的搜索方向。評估函數含有距離函數g(n)和啟發式函數h(n)兩部分，如式（1）所示：

其中，f(n)是評估函數，表示的是從當前節點n節點到目標點的總路徑長度；g(n)是距離函數，表示的是初始節點到當前節點n的實際最短路徑長度；h(n)為啟發函數，則表示當前節點n到目標點的預估路徑長度。

傳統A*算法通常選取評估函數值最小的點作為下一步計算節點，以優化搜索路徑[17]。即從初始節點開始，計算周圍節點的評估函數，選取其中值最小的一個節點作為當前最優節點進行拓展，直到搜索到目標點，然后由目標點回溯到起始點形成一條全局規劃軌跡。但是由于A*算法本身的特點，其搜索的自由度不足，進而會使得搜索出的路徑不夠平滑。

1.1 A＊算法的鄰域拓展

傳統的A*算法一般采用8鄰域搜索，即每個方向都有45°的夾角，這種方式限制了路徑的規劃形式，容易使最終規劃出的路徑轉折點過多，軌跡不夠平滑。

因此本文先將A*算法的搜索拓展至24鄰域的形式，如圖1所示，在原先8方向的基礎上加入額外的16個鄰域，形成了1～16個搜索的方向，搜索方向角度從原先的45°夾角變為22.5°，增加了搜索的自由度，從而使得路徑更加平滑。該方法適用于靜態網絡路徑規劃問題。

圖1 A*算法的24鄰域拓展Fig.1 24-neighborhood searching of A*

1.2 確定引導向量優化鄰域數量

將A*算法的8鄰域搜索拓展到24鄰域，增加了搜索時間花費。為此提出引導向量概念，對鄰域的拓展方向進行引導，在引導方向上計算額外的拓展鄰域，如圖2所示。因此，搜索算法不再需要計算24個鄰域，也能保證搜索時增加自由度。

圖2 引導A*算法的鄰域拓展Fig.2 Searching neighborhood modified by guided vector

定義節點(n.x,n.y)為當前的評估函數值最小節點，節點(pre.x,pre.y)為最近一次評估函數值最小節點，利用它們生成引導向量(Dx,Dy)，如式（2）所示。根據Dx與Dy值的正負，可以將搜索方向分為表1所示的8類。當Dx為負Dy為正時，改進A*算法在傳統A*算法的8鄰域基礎上額外搜索{2、3、4、5、7、9、11}號鄰域；當Dx為零Dy為正時，改進A*算法在傳統A*算法8鄰域的基礎上額外搜索{4、5、7、9、11、15、16}號鄰域。

表1 引導向量對應搜索方向Table 1 Guide vectors and searching direction

由于額外鄰域的數量影響算法的啟發信息含量和計算量，算法的時間復雜度O(closesize×n)與鄰域的數量n相關，其中closesize表示A*算法在完成搜索時對應的已搜索節點的數量。以圖3所示的柵格地圖為例，設定起點為地圖左上角A點，目標點為地圖右下角B點，柵格間一次橫縱移動長度為10步，比較3鄰域、5鄰域、7鄰域、9鄰域、24鄰域下的路徑長度及搜索時間。

圖3 鄰域數量比較柵格地圖Fig.3 Simulated map for number of neighborhood

如表2所示，3鄰域和5鄰域拓展由于自由度不夠，導致路徑長度最長，7鄰域、9鄰域、24鄰域搜索獲得路徑最短，且7鄰域的搜索時間最短，因此選定在引導向量方向上進行額外7鄰域的搜索方式，提高搜索效率。

表2 鄰域數量優化比較Table 2 Neighborhood number and performance items

1.3 路徑平滑處理

為了優化路徑，項目研究采用局部優化策略去除搜索冗余節點。如圖4所示，圖中黑色方塊表示障礙物，白色方塊表示自由通行區域，x1節點為起點，x6節點為目標點，從起點到目標點的黑色實線為初選路徑，橫縱移動一格的長度為10。

圖4 初始路徑示意圖Fig.4 Original results of A*algorithm

依次遍歷各節點，并判斷其與其他節點形成路徑為無碰撞相連，從而建立一個無向圖網絡。經過路徑優化，剔除了x3與x4節點，最終獲得圖5所示{x1,x2,x5}路徑。

圖5 優化路徑示意圖Fig.5 Path smoothing optimization results

具體平滑處理流程如圖6所示：用集合S表示目前節點間最短路徑；用集合Dn表示節點間非最短路徑，n代表路徑數。對集合S和集合D中的數據不斷地迭代更新以便實現路徑平滑處理。當集合S與集合D中的路徑存在起止點一致的，即指對于當前節點，從起點開始有多種不同的方式可以到達。通過選擇兩個集合中起止點一致時路徑長度的較小值，更新集合S中的節點數據，從而保證集合S中存儲的是當前最短路徑節點。當遍歷完所有節點后，即獲得各節點形成的可能路徑方案，找到目前的最優路徑。

圖6 平滑處理流程圖Fig.6 Flow chart of path smoothing algorithm

因此，改進的A*算法實質是在傳統8鄰域A*算法的基礎上，借助引導向量，優化搜索鄰域，從而提高搜索效率；通過平滑處理步驟，剔除冗余的節點，進一步優化路徑長度與平滑度。

2 仿真實驗

2.1 隨機柵格地圖仿真

將改進后A*算法分別在不同地圖、不同障礙率的條件下，進行仿真實驗。選用地圖大小分別為50×50、100×100、300×300的柵格環境來代表小地圖、中等地圖和大地圖，障礙物的隨機生成占比分別為10%、20%、30%、40%，模擬4類12種環境（見圖7～圖10）。在上述地圖環境，選擇中心A點為路徑起點，右下角B點為終止點，定義柵格地圖中一格橫縱移動的長度為10，記錄100次有效實驗的路徑長度和搜索花費時間。

圖7 10%障礙占比三種地圖Fig.7 Three categories of map under 10%obstacle scale

圖8 20%障礙占比三種地圖Fig.8 Three kinds of size of map under 20%obstacle scale

圖10 40%障礙占比三種地圖Fig.10 Three categories of map under 40%obstacle scale

如圖11～圖14所示，比較改進A*算法、24鄰域A*算法、8鄰域A*算法、24鄰域的Dijkstra算法、RRT算法仿真實驗效果。其中RRT算法采用了雙向RRT算法，目標偏向概率為10%，搜索次數上限為30萬次。

圖11 不同地圖10%障礙實驗結果Fig.11 Results under 10%obstacle scale

圖14 不同地圖40%障礙實驗結果Fig.14 Results under 40%obstacle scale

可以看出：

圖9 30%障礙占比三種地圖Fig.9 Three categories of map under 30%obstacle scale

（1）改進的A*算法對比8鄰域和24鄰域的A*算法獲得的路徑更短，在每一類實驗中均可以獲得最短長度的路徑。

（2）改進A*算法、8鄰域A*算法、24鄰域A*算法、Dijkstra算法每次搜索獲得的路徑長度固定，且A*類的算法搜索花費時間波動不大，說明這些算法性能較為穩定。

（3）在上述的12類環境下，RRT算法搜索花費時間以及獲得的路徑長度均有較大的波動，該算法性能不穩定。

路徑優化目標包含兩個方面，一是降低隨機性影響，提升其路徑查找的成功率，二是減少路徑長度，提高路徑搜索效率。因此，選擇成功率(p)、100次平均路徑長度(dˉ)、100次路徑長度標準差(sˉ)、搜索最小花費時間(tmin)、搜索最大花費時間(tmax)等5個指標作為算法評價指標。為了驗證實際地圖下不同算法的性能，在300×300地圖，不同障礙率下，計算各性能指標（見表3～表6）。

表3 300×300地圖10%障礙物Table 3 10%obstacle scale in 300×300 map

表6 300×300地圖40%障礙物Table 6 40%obstacle scale in 300×300 map

圖12 不同地圖20%障礙實驗結果Fig.12 Results under 20%obstacle scale

圖13 不同地圖30%障礙實驗結果Fig.13 Results under 30%obstacle scale

可以看出：

表4 300×300地圖20%障礙物Table 4 20%obstacle scale in 300×300 map

表5 300×300地圖30%障礙物Table 5 30%obstacle scale in 300×300 map

（1）當障礙物占比較小，分別為10%和20%時，改進的A*算法（額外7鄰域）具有100%的成功率，其每次均可求得最短長度的路徑，因此路徑長度標準差均為0，該算法在兩種環境下對應的最大最小搜索時間差別不大，分別為0.11和0.08，說明該算法性能穩定。24鄰域A*算法的最小搜索時間花費分別為2.55 s和2.56 s，與同條件下的8鄰域搜索相比搜索時間更長。RRT算法的成功率可以保持在100%，其在兩種情況下的路徑長度標準差都是最大的，分別是191.18和413.84，說明隨著地圖障礙物占比的上升它表現得愈發不穩定，其最小搜索時間是最快的，但與最大搜索時間的差值較大，說明該算法性能不穩定。

（2）當障礙物占比為30%時。改進的A*算法有100%的成功率，且其每次均可求得最短長度的路徑，其最小搜索時間是最快的。RRT算法的成功率急劇下降至6.3%，說明該算法不適用于此環境，其路徑長度標準差依然最高，但是相比之前環境的結果下降至了362.74，原因是障礙物占比的提高對RRT算法的隨機性起到了一定的限制作用，其算法的最小搜索時間是最慢的，與最大搜索時間的差值變大，說明該算法性能不穩定。

（3）當障礙物占比為40%時。改進的A*算法仍然可以保證100%的成功率，且求得的路徑長度依然是最短的，其最小搜索時間略慢于8鄰域A*算法。RRT算法在長時間的運行下仍不能獲得至少一組解，因此不討論其性能。

綜上所述，在改變地圖大小以及障礙物占比模擬出的12種環境下，改進的A*算法可以穩定地在各種環境下求出最短路徑。在障礙物占比和地圖大小增大后，RRT算法的性能均會受到影響，且障礙物占比的提升對它的影響更明顯。Dijkstra算法也對應進行24鄰域搜索。

2.2 實際地圖仿真實驗

模擬機場特種車輛的路徑規劃實驗。將機場衛星地圖進行柵格化處理，用于實際地圖仿真實驗。如圖15所示，左上角A點為路徑起點，右下角B點為目標點，獲取20個有效實驗結果（圖16），其他實驗條件與2.1節同。不同算法下指標量化計算見表7。

圖15 實際地圖柵格化Fig.15 Rasterization of real scene map

圖16 實際地圖實驗結果Fig.16 Results in real scene map

表7 實際地圖仿真結果Table 7 Results in real scene map

可以看出RRT算法在該環境下搜索成功率為100%，它的路徑長度標準差最大，為412.88，有最快的搜索速度，但是其搜索時間波動較大，為52.038 s，說明其性能不穩定；改進的A*算法可以穩定搜索出最短的路徑，長度為6 732.78，且其時間花費波動較小，為0.699 s，搜索性能較為穩定。

實驗結果表明在實際地圖的仿真實驗中，改進的A*算法依然能夠穩定地求得最短的路徑。

3 結論

改進A*算法是基于圖搜索原理尋求路徑最優的方法，該算法將傳統A*算法的搜索鄰域拓展至24鄰域，提高算法搜索的自由度，引入引導向量，優化鄰域數量減少無用探索，以便提高搜索效率，加入平滑處理步驟，減少冗余節點，進一步優化路徑長度與平滑度。不同實驗環境下，本文算法都可以穩定高效規劃路徑。