結合進化算法的稀疏A*算法對動態目標的無人機航跡規劃研究

2016-06-17 15:49:08劉群芳李軍華

計算機時代 2016年6期

劉群芳　李軍華

摘要：針對移動目標的無人機航跡規劃問題，結合文化算法改進稀疏A*算法解決靜態航跡的繞徑問題，然后進一步使用混合算法解決目標跟隨過程中動態航跡的規劃速度和最優路徑的平衡選擇問題，最終實現不確定環境下跟隨目標和威脅躲避的動態航跡實時規劃。通過采用靜態和動態兩級分層規劃結構，使用基于稀疏A*算法與文化算法的混合算法實現了動態目標和動態威脅的無人機航跡規劃。

關鍵詞：航跡規劃；稀疏A*算法；文化算法；混合進化算法；目標跟隨

中圖分類號：TP301.6 文獻標志碼：A 文章編號：1006-8228（2016）06-17-05

Abstract： In order to solve the problem of unmanned aerial vehicle （UAV） dynamic target path planning， this paper uses the two-level hierarchical planning structure and the hybrid evolutionary algorithm of the sparse A* algorithm and the cultural algorithm （CA） to realize the dynamic UAV path real-time planning under the dynamic target， solves the dynamic path planning problem of avoiding threats and following the target， improves the planning speed and reliability of the track， strengthens the flight safety of UAV.

Key words： path planning； sparse A* algorithm； culture algorithm； hybrid evolutionary algorithm； target follow

0 引言

隨著現代航空領域的科技進步和戰場環境的日漸復雜，對無人機飛行難度的要求也隨之提高。

航跡規劃作為無人機任務規劃系統（Mission Planning System）的一項關鍵技術，目前已有多種進化算法應用于求解航跡規劃問題，主要有遺傳算法（GA）[1]、蟻群算法（Ant）[2]及其混合改進形式。A*算法[3]以其較快的搜速度而突出，是一種經典的最優啟發式搜索算法，但其缺點是存儲數據會隨著搜索區間的增大而增加，導致規劃耗時過長。為加快搜索速度，Szczerba[4]、周成平[5]、穆中林[6]等人均提出了改進方法，在一定程度上提高了算法的規劃速度，但得到的路徑往往不是最優解，存在繞徑問題[7]。

傳統的無人機動態航跡規劃，要求能實時規避突發威脅并安全到達指定目標點，但因受到各種因素的影響、約束條件限制和任務的改變等，目標點往往是多變的。因而針對動態目標以及動態威脅需要一種更為可行的動態規劃方法，以適應實際環境和任務的需求，實現對動態目標跟隨的無人機航跡規劃。

文化算法（Cultural Algorithm，CA）是Reynolds[8]于1994提出的，它是一種基于種群的多進化過程的計算模型，為進化搜索機制和知識存儲的結合提供了一個構架。傳統生物進化算法由于受種群個體經驗知識的保存和表示限制，只能提供有限的進化經驗知識，而近年來興起的文化算法打破了這種局限性，因為文化算法在宏觀層面及微觀層面上可以對種群進化進行指導與交流，突破了種群個體的限制，可以極大地促進種群的進化和發展，因此將文化算法應用于無人機航跡規劃具有一定的研究價值和意義。

本文將稀疏A*算法與文化算法相結合，應用于動態航跡規劃，并在解決稀疏A*算法的繞徑問題基礎上，面對遠近動態威脅時以安全為第一目標，平衡重規劃的規劃速度和航跡質量，最終實現動態目標跟隨的最優航跡規劃。

1 問題建模

無人機動態目標跟隨的航跡規劃是指無人機根據目標的改變而實時進行的航跡重規劃，規劃過程中需要考慮各種約束條件以及突發威脅以及動態變化的目標點的影響，以實現無人機更高要求的動態航跡規劃。

根據規劃內容可分為三大部分：地圖模型的建立、全局靜態航跡規劃、動態實時航跡規劃。

第一部分將各種已知威脅源按其威脅模型等效為地形，與已知地形信息融合，建立全概率綜合數字地圖；第二部分是在數字地圖上結合各種約束條件及任務要求規劃出一條全局靜態預航跡；第三部分是將預航跡作為參考航跡，若探測到有突發威脅出現或者目標點改變，則依據目標點和突發威脅的情況實時修改航跡，無人機航跡規劃系統框圖如圖1所示。

1.1 地圖環境建模

地圖環境是無人機航跡規劃的基礎，主要由地形障礙、導彈、雷達、高炮、天氣、未探測區域等內容構成。將所有環境組成部分視為威脅源處理，并按其作用方式、強度及位置疊加于數字地圖中，生成包含地形信息和各種威脅信息的全概率綜合數字地圖，同時在等效過程中將三維地圖等效映射成為二維地圖。

1.2 航跡代價評估函數

在航跡規劃中，航跡代價評估函數是用于指導算法尋找最優航跡的重要工具，其內容主要包括評價航跡的重要指標：航跡長度和航跡威脅代價，需要按比例協調兩者的權重關系。本文根據稀疏A*算法設計航跡評價函數如下：

其中，公式⑴的第一個項為實際代價部分，li為節點i-1到節點i之間的航跡長度，fi為節點i-1到節點i之間受到的威脅值，w1、w2為相應權重系數。公式⑴最后一項為啟發函數部分，d（n）表示當前節點n到目標點之間的航跡估計長度，w3為相應權重系數。

2 無人機靜態航跡規劃

2.1 基于稀疏A*算法靜態實現航跡規劃流程

基于稀疏A*算法的靜態航跡規劃流程如圖2所示，規劃的核心內容為稀疏A*算法實現部分，算法的改進也主要在該部分進行設計。

基于稀疏A*算法與混合算法的靜態航跡規劃流程如圖3所示，規劃的核心部分為：首先采用稀疏A*算法進行規劃，然后使用文化算法進行修徑。

3 無人機動態航跡規劃

由于在實際飛行中，突發威脅的出現需要無人機重新規劃航跡以快速躲避威脅，但重規劃航跡需要一定的時間，在該時間段內無人機還是按原來的航跡飛行直至航跡重規劃完成，因此需要提出將該時間段內無人機的飛行航跡長度作為航跡重規劃的距離標準，判斷是以快速規劃優還是路徑最優解優先。

其中，D表示安全飛行規劃距離，v表示無人機的飛行速度，t表示理想算法重規劃航跡所需的最大平均時間。

為方便有限條件下的實驗仿真，本文以無人機的最小步長N*Lmin代替。

由于無人機的飛行航跡非常復雜，因此將目標點分兩種情況：固定目標點和動態目標點，然后對這兩種情況分別進行動態航跡規劃。

3.1 固定目標的智能無人機動態航跡規劃流程

在目標固定的情況下，基于稀疏A*算法與混合算法的混合進化算法，實現規避突發威脅的無人機動態航跡規劃，其流程如圖4所示，針對飛行過程中的遠近突發威脅，采取最佳算法方案進行規劃。

4 實驗仿真結果

實驗仿真平臺：基于XP操作系統的計算機，主頻為3.20GHz，內存為3.21GB，使用matlable 7.10.0（R2010a）軟件進行編程實現仿真。假定無人機在100X100km的區域內執行任務，按1：5的比例將規劃區域轉換為500x500的坐標區域，出發點坐標為（21，144），目標點坐標為（446，446），最大轉彎角θ=60?，Lmin=4km，M取6，則擴展節點為7個，航跡代價評價函數的權重系數w1、w2、w3分別取0.001、300、0.1，靜態航跡規劃仿真實驗結果如圖6所示。

圖6（a）為基于稀疏A*算法規劃出的靜態預航跡，圖6（b）中實線為基于稀疏A*算法與文化算法的混合進化算法規劃出的靜態預航跡。為方便對比，將圖6（a）中的航跡以虛線加入圖6（b）中，其余圖形為各威脅源。

對比圖6中（a）、（b）兩圖可知，加入文化算法后有效改善了稀疏A*算法的繞徑問題，縮短了航跡長度。表1展示了兩種算法的時間性能參數。

從表1可知，稀疏A*算法具有最快的計算速度，而基于稀疏A*算法與文化算法的混合進化算法規劃出的航跡總威脅代價最小，且航跡長度短。

在實現靜態預航跡規劃的基礎上，進一步實現動態航跡規劃。首先在目標點固定的情況下，模擬無人機實際飛行過程遇見兩種動態威脅，一種為動態威脅出現在距離無人機飛行當前點小于安全飛行規劃距離的情況，另一種為動態威脅出現在距離當無人機飛行當前點大于安全飛行規劃距離的情況。本文中全飛行規劃距離D統一采用3?Lmin作為仿真標準。這兩種情況中實現的動態航跡規劃仿真結果如圖7所示。

圖7（a）為基于稀疏A*算法與文化算法的混合進化算法規劃出的靜態預航跡；圖7（b）為面臨突發威脅出現時距離當前飛行點小于D的情況下，基于混合進化算法進行的動態實時航跡；圖7（c）為面臨突發威脅出現時距離當前飛行點大于D的情況下，基于混合進化算法進行的動態實時航跡。圖7中虛線航跡表示靜態預航跡，實線表示實時航跡，其中圖7（b）和圖7（c）顯示了無人機遇見突發威脅時動態航跡規劃實驗結果。

通過圖7（b）可以觀察到，在面臨突發威脅距離當前飛行點小于安全飛行規劃距離的情況下，無人機采用稀疏A*算法快速有效地避開了臨近的突發威脅，雖然存在航跡繞徑，但可以保障安全飛行。

通過圖7（c）可以觀察到，在面臨突發威脅距離當前飛行點大于安全飛行規劃距離的情況下，無人機采用稀疏A*算法結合文化算法的混合進化算法規劃，既規避了突發威脅又得到了最優航跡。因此，該基于混合進化算法的動態航跡規劃方法有效地實現了無人機的實時動態航跡規劃，并可以協調分配飛行安全與飛行代價。

為進一步提高無人機自主飛行的智能性，繼續進行仿真，模擬無人機實際飛行過程中規避兩種突發威脅和跟隨動態目標進行的航跡規劃情況。動態航跡規劃仿真結果如圖8所示。

圖8中，（a）和（d）圖為基于混合算法規劃的靜態預航跡，（b）和（c）圖皆為動態目標跟隨時對突然威脅距離無人機當前飛行點小于D的動態航跡規劃。其中（b）圖為突發威脅出現前對動態目標跟隨的航跡規劃結果，（c）圖為突發威脅出現后對動態目標跟隨及規避動態威脅的航跡規劃結果；圖8中，（e）和（f）圖皆為動態目標跟隨時對突然威脅距離無人機當前飛行點大于D的動態航跡規劃結果。圖8中，虛線表示歷史重規劃航跡，實線表示實時行進航跡。

通過觀察圖8航跡規劃結果可知，該基于混合進化算法的智能動態航跡規劃方法有效地實現了對動態目標的跟隨，并在跟隨過程中有效地規避了不同類型的動態威脅，可以保障無人機的安全，還可以實現目標追蹤和監控作用。

5 結束語

本文在解決稀疏A*算法的繞徑問題的基礎上，實現了動態環境下的航跡動態規劃，實現了動態目標跟隨和突發威脅的規避。仿真結果表明，所提出的基于稀疏A*算法與文化算法的混合算法不僅能夠進一步改善稀疏A*算法的航跡，還能提高無人機在不同要求下的靈活自控性，擴大了無人機的應用空間和價值，并使其性能得到更大程度的優化。

參考文獻（References）：

[1] 張延松.基于遺傳算法的無人機航跡規劃研究[D].中南大學

碩士學位論文，2010.

[2] Zhang chao， Zhen Ziyang， Wang DaoBo， et al.UAV path

planning Method Based on Ant Colony Optimization[C]. 2010 Chinese Control and Decision Conference，2010：3790-3792

[3] 周青，李廣文.基于A*算法的無人機四維航跡規劃研究[J].計

算機仿真，2014.31（4）：92-96

[4] Szczerba Robert J. Robust Algorithm for Real-Time Route

Planning[J]. IEEE Transactions on Aero-space and Electronic Systems，2000.36（3）：869-878

[5] 周成平，陳前洋，秦筱.基于稀疏A*算法的三維航跡并行規劃

算法[J].華中科技大學學報（自然科學版），2005.33（5）：42-45

[6] 穆中林，魯藝，任波等.基于改進A*算法的無人機航路規劃方