改進A*算法在突防航跡規劃中的應用

宋斌斌，金慧琴，李啟超

(1.海軍航空工程學院 電子信息工程系，山東 煙臺　264001；2.海軍航空工程學院 航空訓練基地，山東 青島　266000)

?

改進A*算法在突防航跡規劃中的應用

宋斌斌1，金慧琴1，李啟超2

(1.海軍航空工程學院 電子信息工程系，山東 煙臺264001；2.海軍航空工程學院 航空訓練基地，山東 青島266000)

摘要：針對實際應用中傳統A*算法存在搜索時間長、占用空間大和生成的航跡可飛性低等問題，對傳統A*算法進行了改進。通過引入啟發函數選擇因子，并結合航跡約束條件改進節點擴展策略，有效減小了算法搜索時間和所占用的內存空間；采用索引矩陣和無序數組的混合數據結構實現對Open表和數據的管理，顯著提高了算法效率；通過對航跡進行后期平滑處理，使生成的航跡滿足飛機機動性能要求。仿真結果表明，改進后的A*算法有效提高了規劃效率且生成的航跡更具可飛性，在突防航跡規劃中具有一定的實際應用價值。

關鍵詞：A*算法；航跡規劃；啟發函數；搜索空間；航跡平滑

本文引用格式：宋斌斌，金慧琴，李啟超.改進A*算法在突防航跡規劃中的應用[J].兵器裝備工程學報，2016(7):85-89.

Citationformat:SONGBin-bin,JINHui-qin,LIQi-chao.ApplicationofImprovedA*AlgorithminPenetratingPathPlanning[J].JournalofOrdnanceEquipmentEngineering,2016(7):85-89.

突防航跡規劃是飛行器任務規劃的重要組成部分之一，其作用是在綜合考慮地形、氣象、威脅以及飛機自身性能等因素的前提下，為突防飛機制定出一條從初始位置到目標位置的最優航跡，最大限度提高飛機的生存率，以保證任務的圓滿完成[1]。航跡規劃中常用的算法以人工智能算法為主，包括啟發式搜索算法、遺傳算法、人工神經網絡算法、蟻群算法以及模擬退火算法等。A*算法是一種簡單靈活的啟發式搜索算法，它能充分利用已有知識和數據，只要選擇合適的啟發函數，就能提高算法效率并得到全局最優解[2]。但是在實際應用中，標準A*算法還存在一些問題，比如算法收斂時間較長、占用內存空間較大、生成的航跡不滿足飛機機動性能要求等。

針對這些問題，本文對標準A*算法進行了實用性改進。通過引入啟發函數選擇因子，并結合航跡約束條件改進節點擴展策略，有效縮減了算法搜索區域，減小了算法搜索時間和所占用的內存空間；其次，采用索引矩陣和無序數組的混合數據結構實現對Open表和數據的管理，大大減小了算法在Open表和Close表操作以及內存分配上的耗時；最后，通過對航跡進行后期平滑處理，使生成的航跡滿足飛機機動性能要求并且更加真實。

1標準A*算法

啟發式搜索算法就是在狀態空間中對每一個搜索的位置進行評估，得到最好的位置，再從這個位置進行搜索直到找到目標。這樣可以省略大量無用的搜索路徑，提高搜索的效率。A*算法是一種典型的啟發式搜索算法，它采用的代價函數為

(1)

1) 將出發點放入Open表并估計從出發點到目標點的代價；

2) 判斷Open表是否為空，是則規劃失敗，結束循環，否則繼續；

3) 從Open表中取出 fn值最小的節點作為當前節點，將其添加進Close表并從Open表中刪除；

4) 判斷當前節點是否為目標點，是則規劃成功，退出循環，否則繼續；

5) 對當前節點的相鄰節點進行擴展，判斷相鄰節點是否在Close表中，若是則放棄該節點，否則作為當前節點的擴展子節點；

6) 對每一個擴展子節點，判斷其是否在Open表中，如果不在，計算該節點gn和hn，將其添加進Open表中，并把當前節點作為該節點的父節點，跳轉到第2步；若在Open表中，檢查新路徑的gn是否更小，是則將該節點的父節點改為當前節點，并重新計算gn和hn，跳轉到第2步，否則直接跳轉到第2步。

2標準A*算法的改進

2.1啟發函數的設計

啟發函數設計的好壞直接關系到算法效率的高低和能否找到最優解。假設狀態空間中存在可行解，分析下面幾種情況：

1) 當hn=0時，A*算法退化為Dijkstra算法，雖然它能保證找到最優解，但是算法效率最低；

(2)

式中：li和ti分別表示第i段航跡的長度和威脅值；ω為代價權系數(0<ω<1)，通過調節ω的大小可以選擇飛機是穿越威脅還是回避威脅。大多數文獻對于啟發函數的計算方法是直接采用歐式距離乘以權系數

(3)

(4)

這樣，通過增大p值便可提高算法速度，但是不一定能得到最優解，因此在實際應用中可以根據對速度和精度的要求對p值進行選擇。

2.2搜索空間的優化

標準A*算法在進行節點擴展時，一般考慮以當前節點為中心的周圍8個相鄰網格，這樣要收斂到最優解可能需要很長的時間和巨大的內存，通常隨規劃區域的增大呈指數增長[1]。為了解決這個問題，Szczerba等人提出基于稀疏A*搜索(SparseA*Search，SAS)的航跡搜索方法，通過將約束條件與搜索算法相結合，有效剪裁了搜索空間[4]。本文借鑒SAS的思想，通過加入飛機的航向信息和最大轉彎角、最小航跡段長度的限制，對節點擴展方法加以改進，可以有效減少不必要的擴展節點數量，從而加快算法速度和減小內存占用。

改進算法只需要在標準A*算法的第5步中，將考察8鄰域節點變為如圖1所示的節點擴展方式。

設飛機最大轉彎角為θ，最小航跡段長度為L，最大擴展節點數為M，當前節點A(xA,yA)的航向角為α。以α為對稱軸，L為半徑作一個張角為2θ扇形，以角度Δθ=2θ/(M-1)等分這個扇形，得到M個擴展點，每一個擴展節點Ai(xi,yi)的坐標為

(5)

(6)

式中i=1,2,…,M。計算完擴展節點的坐標后，還要計算從當前節點到擴展節點的航向，以便在后續節點擴展中繼續使用航向信息。

圖1　改進A*算法的節點擴展方式

2.3數據結構的優化

在標準A*算法中，需要頻繁對Open表和Close表進行查找、添加和刪除操作，主要包括：第3步從Open表中查找、刪除最佳節點并插入Close表，第5步判斷擴展節點是否在Close表，第6步判斷擴展節點是否在Open表并將新的擴展節點插入Open表。這些操作隨著搜索的持續進行，兩個表中節點數的迅速增大，耗費時間會越來越長，嚴重影響算法效率。此外，第6步中，如果新路徑的 fn值更小，還需要調整Open表中的值。最后，在回溯查找航跡點時，標準A*算法使用一個數組記錄那些被檢查過的節點，通過從目標點開始，遍歷該數組查找其父節點直至找到起始點，這樣的查找也很耗時。

對于Open表的查找、插入和刪除操作，實質上是優先隊列問題。最簡單的方式是采用無序數組，這種方式插入很快，時間花費為O(1)，而查找和刪除很慢，時間花費為O(n)。為了加快查找和刪除操作，A*算法一般采用排序數組或鏈表，但是插入又比較慢，最壞情況下需要遍歷Open表。文獻[4-6]采用最小二叉堆對Open表進行管理，查找花費為O(1)，插入和刪除操作的花費均為O(logn)。使用二叉堆管理Open表效率較高，但是算法比較復雜，而且忽略了對Open表的調整操作，雖然調整操作并不經常發生，但也是必須考慮的。當新路徑的代價值更小時，需要更改Open表中對應節點的 fn值，使用以上所有方式都需要遍歷Open表定位該節點，時間復雜度為O(n)。綜合以上分析，本文使用索引矩陣和無序數組的混合數據結構來實現對A*算法所有數據的維護管理。

索引矩陣是一個與搜索空間一一對應的固定矩陣，它記錄所有節點的相關信息，每一個點包含以下內容：

1) 到達該節點的代價(floatgn)；

2) 通過該節點到達目標的總代價(floatfn)；

3) 該節點的航向(floatalpha)；

4) 該節點的父節點坐標(intx_parent，inty_parent)；

5) 標示該節點是否在Open表和Close表的布爾型變量(BoolInopen，BoolInclose)；

6) 標示該節點是否被檢查過的布爾型變量(BoolCheck)

7) 該節點在Open表中的位置(intLocOpen)

在搜索開始之前，系統預先分配一塊內存空間來存儲索引矩陣并對矩陣進行初始化。在開始搜索后，通過坐標索引便可以快速將節點信息存入索引矩陣中的相應位置，這樣便解決了內存的頻繁分配問題。在判斷節點是否在Open表或Close表中時，只需通過索引矩陣快速定位，判斷該節點的Inopen和Inclose兩個變量為True還是False，而不需要遍歷兩個表進行查找，時間復雜度由原來的O(n)縮減為O(1)。在回溯航跡時，從目標點開始在索引矩陣中循環查找父節點坐標直到起始點，這樣循環的次數僅為航跡點的數量。并且，使用索引矩陣后不再需要實際意義上的Close表，消除了對Close表插入操作的耗時。采用無序數組結合索引矩陣對Open表進行管理，在索引矩陣中有1bit變量用來存儲節點在Open表中的位置，在執行刪除操作時，并非真正將節點從Open表中刪除，而是將Open表中該節點的 fn值置為無窮大。使用這種方式對Open進行管理，查找操作的耗時為O(n)，插入、刪除和調整的耗時也均為O(1)，比單獨采用二叉堆效率更高且算法更簡單。

2.4航跡優化

1) 平滑航跡

標準A*算法在生成航跡時會產生Z字形航跡，而為了減小導航誤差，飛行器在遠距離飛行時，一般不希望迂回行進和頻繁轉彎，因此需要對這種Z字形航跡進行平滑處理，使其盡量保持直線飛行。一種處理方式是對每一次變更航向加入處罰，即在代價函數中引入轉向代價，但是這種處理方式并不十分有效，而且會增加算法的運算量。

本文使用一種簡單的平滑算法，在A*算法生成航跡之后對航跡進行后期處理，通過刪除一些不必要的航跡點減少轉彎。

在平滑算法中定義了一個平滑函數Smooth(A,B)，該函數在當前航跡點C的兩個相鄰航跡點A和B之間以固定間隔(一般以1/5個網格長度)進行采樣，如圖2所示，檢查是否存在一個采樣點的威脅值高于某個給定的閾值，若存在，則函數返回值為0，表示當前航跡點C不可刪除，否則返回1，表示當前航跡點C可刪除。

2) 平滑轉向

雖然在2.2節中算法加入了最大轉彎角的限制，不會出現直角或銳角轉彎的情況，但由于各個航跡點之間直接以直線連接，生成的航跡看起來還是太過“生硬”，缺乏平滑的過渡，而且由于飛行器機動性能的限制，這些“突然”的轉彎對飛行器難以實現。一般的處理方式是使用樣條函數(Spline)對轉彎點進行平滑，但是這種方法僅僅從視覺上使得航跡看似平滑，從現實角度來講還是不夠真實。因此，本文通過引入飛機的轉彎半徑(TurningRadius)對轉向點進行平滑處理，使得生成的航跡能滿足飛機機動性能要求，更具可飛性。

圖2　平滑航跡算法

圖3　平滑轉向

由此可得到圓心O的坐標為

(9)

(10)

求得圓心后，可以用2.2節計算擴展節點的方法求圓弧上若干點的坐標，將這些點順次連接起來就得到了符合最小轉彎半徑要求的平滑轉彎航跡。

3仿真與分析

本文仿真的硬件平臺為PC機，處理器為AMDAlthlonIIX2，主頻2.90GHz，仿真軟件采用MatlabR2014a。航跡規劃所使用的仿真飛行區域采用文獻[7-8]中提出的基于概率地圖的方法建立一個500×500網格的威脅地圖，其中包括地形障礙區、雷達威脅區、防空導彈威脅區、氣象威脅區和禁飛區等。分別采用標準A*算法、稀疏A*算法和本文改進A*算法在此威脅地圖上進行突防航跡規劃。對這3種算法說明如下：

1) 標準A*算法采用8鄰域的節點擴展方式，稀疏A*算法和本文改進的A*算法均采用2.2節所述節點擴展策略，其約束條件為：最大轉彎角θ=60°，最小步長Lmin=10網格長度，最大節點擴展數M=7，最小轉彎半徑Rmin=5Lmin；

2) 標準A*算法和稀疏A*算法使用無序數組和單向鏈表分別對Open表和Close表進行管理，本文改進的A*算法采用索引矩陣和無序數組管理Open表和數據；

3) 3種算法的代價函數和啟發函數均采用2.1節所述的方法，代價權系數ω=0.1，選擇因子p=0.1。

仿真的起始點坐標為(21,150)，目標點坐標為(450,450)，3種算法得到的突防航跡如圖4所示。圖4中，實線、點線和虛點線分別為本文改進的A*算法、標準A*算法和稀疏A*算法規劃出的航跡。

圖4　航跡規劃示意圖

由圖4可以看出，在代價權系數ω相同的情況下，3種算法規劃出的航跡基本是一致的。為了更清楚地顯示航跡優化的效果，對圖4中的部分航跡進行放大，如圖5所示。

由圖5可以看出，采用本文的航跡平滑算法對航跡進行了拉直處理，刪除了不必要的航跡點，避免了頻繁的轉彎，同時縮減了航跡長度；采用轉向平滑算法對轉向點進行了平滑過渡，避免了突然的轉向，使生成的航跡更加真實。

圖5　部分航跡放大示意圖

設置代價權系數ω不變，p分別為0，0.1和0.2，進行多次仿真實驗，得到實驗結果如表1所示。

表1　不同算法航跡規劃結果

由表1可見，雖然3種算法得到最優航跡基本是一致的，但算法性能卻有很大差別。通過實驗1-6對比可以看出，稀疏A*算法通過將航跡約束條件融合到搜索算法中，減小了擴展節點數量，從而降低了算法搜索時間；此外，通過在啟發函數中引入選擇因子p，明顯減小了搜索區域，提高了算法效率。通過實驗4-9對比可以看出，本文改進的A*算法在檢查節點數量上與稀疏A*算法完全相同，但由于改進A*算法采用索引矩陣和無序數組實現對Open表和數據的管理，優化了數據結構，算法效率提高了4～5倍，且擴展節點數越多效率提升越明顯。

4結論

針對實際應用中A*算法存在搜索時間長、占用空間大和生成的航跡可飛性低等問題，本文在啟發函數、搜索空間、數據結構和航跡平滑等方面對A*算法進行了改進。仿真結果表明，改進后的A*算法有效提高了算法效率并更具可飛性，在飛行器突防航跡規劃中具有一定的實際應用價值。

參考文獻：

[1]沈林成，陳璟，王楠.飛行器任務規劃技術綜述[J].航空學報，2014，35(3)：593-606.

[2]鄭昌文，嚴平，丁明躍，等.飛行器航跡規劃[M].北京：國防工業出版社，2008.

[3]HARTPE,NILSSONNJ,RAPHAELB.Aformalbasisfortheheuristicdeterminationofminimumcostpaths[J].IEEETrans.SystemScienceandCybernetics,1968,4(2):100-107.

[4]SZCZERBARJ.Robustalgorithmforreal-timerouteplanning[J]．IEEETransactionsonAerospaceandElectronicSystem,2000,36(3):869-878.

[5]李世曉，朱凡，張健，等.改進A*算法的多約束航跡規劃[J].電光與控制，2014，21(7)：36-40.

[6]CAZENAVETRISTAN.Optimizationsofdatastructures,heuristicsandalgorithmsforpath-findingonmaps[C]//Proceedingsofthe2006IEEESymposiumonComputationalIntelligenceandGames.[S.l.]:[s.n.],2007:27-33.

[7]NANNICINIG,DELLINGD,LIBERTIL,etal.BidirectionalA*SearchforTime-DependentFastPaths[J].ExperimentalAlgorithms,2008,5038:334-346.

[8]張煜，陳璟，沈林成.基于概率地圖的軍用飛行器航跡規劃方法研究[J].計算機仿真，2007,24(9)：62-66.

(責任編輯楊繼森)

收稿日期：2016-01-06；修回日期：2016-02-03

作者簡介：宋斌斌(1979—)，男，博士研究生，講師，主要從事通信與導航研究。

doi:10.11809/scbgxb2016.07.019

中圖分類號：TP301.6

文獻標識碼：A

文章編號：2096-2304(2016)07-0085-05

ApplicationofImprovedA*AlgorithminPenetratingPathPlanning

SONGBin-bin1,JINHui-qin1,LIQi-chao2

(1.DepartmentofElectronicandInformationEngineering,NavyAeronauticalAerospaceUniversity,Yantai264001,China;2.AviationTrainingBase,NavyAeronauticalAerospaceUniversity,Qingdao266000,China)

Abstract:For the disadvantage of long search time, large space usage and low validity of path in practical application, the traditional A* algorithm was improved. By introducing heuristic choice factor and combining the restrictions for path planning to modify the node extension strategy, the improved A* algorithm effectively reduced the search time and memory space. Mixed data structure of index matrix and non-priority array was applied to manage the Open list and data which significantly improved the efficiency of the algorithm. The post-processing solution for smoothing the path met the requirements of aircraft’s moving capability. Simulation results show that the improved A* algorithm could improve the plan efficiency and path validity and have certain actual application value in the penetrating path planning.

Key words：A* algorithm; path planning; heuristic; search space; path smoothing

【信息科學與控制工程】