結(jié)合進(jìn)化算法的稀疏A*算法對(duì)動(dòng)態(tài)目標(biāo)的無(wú)人機(jī)航跡規(guī)劃研究

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

計(jì)算機(jī)時(shí)代 2016年6期

劉群芳　李軍華

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

關(guān)鍵詞：航跡規(guī)劃；稀疏A*算法；文化算法；混合進(jìn)化算法；目標(biāo)跟隨

中圖分類(lèi)號(hào)：TP301.6 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：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)域的科技進(jìn)步和戰(zhàn)場(chǎng)環(huán)境的日漸復(fù)雜，對(duì)無(wú)人機(jī)飛行難度的要求也隨之提高。

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

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

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

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

1 問(wèn)題建模

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

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

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

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

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

1.2 航跡代價(jià)評(píng)估函數(shù)

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

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

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

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

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

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

3 無(wú)人機(jī)動(dòng)態(tài)航跡規(guī)劃

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

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

為方便有限條件下的實(shí)驗(yàn)仿真，本文以無(wú)人機(jī)的最小步長(zhǎng)N*Lmin代替。

由于無(wú)人機(jī)的飛行航跡非常復(fù)雜，因此將目標(biāo)點(diǎn)分兩種情況：固定目標(biāo)點(diǎn)和動(dòng)態(tài)目標(biāo)點(diǎn)，然后對(duì)這兩種情況分別進(jìn)行動(dòng)態(tài)航跡規(guī)劃。

3.1 固定目標(biāo)的智能無(wú)人機(jī)動(dòng)態(tài)航跡規(guī)劃流程

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

4 實(shí)驗(yàn)仿真結(jié)果

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

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

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

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

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

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

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

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

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

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

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

5 結(jié)束語(yǔ)

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

參考文獻(xiàn)（References）：

[1] 張延松.基于遺傳算法的無(wú)人機(jī)航跡規(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*算法的無(wú)人機(jī)四維航跡規(guī)劃研究[J].計(jì)

算機(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é)報(bào)（自然科學(xué)版），2005.33（5）：42-45

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