結(jié)合進化算法的稀疏A*算法對動態(tài)目標的無人機航跡規(guī)劃研究

劉群芳　李軍華

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

關(guān)鍵詞： 航跡規(guī)劃； 稀疏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 引言

隨著現(xiàn)代航空領(lǐng)域的科技進步和戰(zhàn)場環(huán)境的日漸復(fù)雜，對無人機飛行難度的要求也隨之提高。

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

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

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

本文將稀疏A*算法與文化算法相結(jié)合，應(yīng)用于動態(tài)航跡規(guī)劃，并在解決稀疏A*算法的繞徑問題基礎(chǔ)上，面對遠近動態(tài)威脅時以安全為第一目標，平衡重規(guī)劃的規(guī)劃速度和航跡質(zhì)量，最終實現(xiàn)動態(tài)目標跟隨的最優(yōu)航跡規(guī)劃。

1 問題建模

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

根據(jù)規(guī)劃內(nèi)容可分為三大部分：地圖模型的建立、全局靜態(tài)航跡規(guī)劃、動態(tài)實時航跡規(guī)劃。

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

1.1 地圖環(huán)境建模

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

1.2 航跡代價評估函數(shù)

在航跡規(guī)劃中，航跡代價評估函數(shù)是用于指導(dǎo)算法尋找最優(yōu)航跡的重要工具，其內(nèi)容主要包括評價航跡的重要指標：航跡長度和航跡威脅代價，需要按比例協(xié)調(diào)兩者的權(quán)重關(guān)系。本文根據(jù)稀疏A*算法設(shè)計航跡評價函數(shù)如下：

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

2 無人機靜態(tài)航跡規(guī)劃

2.1 基于稀疏A*算法靜態(tài)實現(xiàn)航跡規(guī)劃流程

基于稀疏A*算法的靜態(tài)航跡規(guī)劃流程如圖2所示，規(guī)劃的核心內(nèi)容為稀疏A*算法實現(xiàn)部分，算法的改進也主要在該部分進行設(shè)計。

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

3 無人機動態(tài)航跡規(guī)劃

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

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

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

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

3.1 固定目標的智能無人機動態(tài)航跡規(guī)劃流程

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

4 實驗仿真結(jié)果

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

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

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

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

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

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

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

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

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

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

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

5 結(jié)束語

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

參考文獻（References）：

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

碩士學(xué)位論文，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*算法的無人機四維航跡規(guī)劃研究[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*算法的三維航跡并行規(guī)劃

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

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

法研究[J].彈箭與制導(dǎo)學(xué)報，2007.27（1）：297-300

[7] 占偉偉，王偉，陳能成等.一種利用改進A*算法的無人機航跡

規(guī)劃[J].武漢大學(xué)學(xué)報（信息科學(xué)版），2015.40（3）：315-320

[8] 齊仲紀，劉漫丹.文化算法研究[J].計算機技術(shù)與發(fā)展，2008.5

（1）：26-30