基于并行蟻群算法的無(wú)人機(jī)協(xié)同任務(wù)/航跡規(guī)劃應(yīng)用研究

吳蕊

（中國(guó)電子科技集團(tuán)公司第二十研究所，西安 710068）

0 引言

多無(wú)人機(jī)協(xié)同作戰(zhàn)是未來(lái)戰(zhàn)場(chǎng)使用的主要形式，例如廣域搜索和摧毀，情報(bào)監(jiān)視和偵察，壓制敵防空火力等[1]。它包括任務(wù)分配和航跡規(guī)劃兩方面，其目的是在滿(mǎn)足各項(xiàng)戰(zhàn)術(shù)和技術(shù)指標(biāo)的前提下，針對(duì)不同用戶(hù)提出的多任務(wù)需求，確定出各無(wú)人機(jī)的目標(biāo)任務(wù)執(zhí)行序列，并尋找從當(dāng)前位置到目標(biāo)的可行飛行航跡，使得整個(gè)無(wú)人機(jī)編隊(duì)的整體作戰(zhàn)收益最大，代價(jià)最小[2]。

現(xiàn)階段，針對(duì)任務(wù)分配問(wèn)題，主要有A*算法、遺傳算法和基于合同網(wǎng)的方法等[3-4]。針對(duì)航跡規(guī)劃問(wèn)題，目前的研究成果主要有基于圖論的方法、進(jìn)化算法和Hopfield網(wǎng)絡(luò)算法等[5-8]。但是無(wú)人機(jī)協(xié)同執(zhí)行任務(wù)的過(guò)程中，由于作戰(zhàn)任務(wù)的復(fù)雜性，任務(wù)分配和航跡規(guī)劃是不可分割的，多無(wú)人機(jī)之間往往同時(shí)存在多類(lèi)協(xié)同約束關(guān)系，包括任務(wù)偏序關(guān)系、時(shí)間協(xié)同約束和空間協(xié)同約束[9-10]，現(xiàn)有方法并未對(duì)此進(jìn)行綜合考慮，因此規(guī)劃的結(jié)果并不能很好的反映多無(wú)人機(jī)協(xié)同作戰(zhàn)需求。

針對(duì)無(wú)人機(jī)協(xié)同任務(wù)/航跡規(guī)劃問(wèn)題的特點(diǎn)，綜合考慮多類(lèi)復(fù)雜約束條件，本文采用混合蟻群算法求解，利用蟻群算法構(gòu)造備選航跡集合，設(shè)計(jì)了一種基于整數(shù)編碼的遺傳算法求解方法，對(duì)無(wú)人機(jī)、目標(biāo)、航跡采用整數(shù)編碼、優(yōu)化操作。文中將其應(yīng)用于SEAD的單任務(wù)和多任務(wù)作戰(zhàn)中，仿真結(jié)果顯示采用 ACS-GA算法優(yōu)化得到的方案組合能更好地、更快地找到全局最優(yōu)解。

1 任務(wù)/航跡規(guī)劃數(shù)學(xué)模型

1.1 問(wèn)題描述

多機(jī)協(xié)同作戰(zhàn)控制結(jié)構(gòu)如圖1所示，其中，最底層為無(wú)人機(jī)實(shí)體，它接收自主導(dǎo)航模塊產(chǎn)生的對(duì)于給定目標(biāo)給定任務(wù)的一系列導(dǎo)航點(diǎn)。在總體作戰(zhàn)規(guī)劃中，目標(biāo)分配模塊、航跡規(guī)劃模塊、多機(jī)協(xié)調(diào)模塊一起完成任務(wù)分配和航跡生成。目標(biāo)分配模塊完成所有作戰(zhàn)計(jì)劃中的目標(biāo)分配工作；航跡規(guī)劃模塊輸出無(wú)人機(jī)到達(dá)各目標(biāo)的航跡點(diǎn)、燃油代價(jià)估計(jì)和威脅代價(jià)估計(jì)；多機(jī)協(xié)調(diào)模塊確保在同一任務(wù)中無(wú)人機(jī)同時(shí)到達(dá)指定目標(biāo)的雷達(dá)探測(cè)區(qū)域。

圖1 無(wú)人機(jī)群協(xié)同作戰(zhàn)控制結(jié)構(gòu)

壓制敵防空火力(Suppression of Enemy Air Defense，SEAD)任務(wù)是研究多UAV協(xié)同作戰(zhàn)的典型模式，其中一個(gè)重要目標(biāo)就是避開(kāi)威脅到達(dá)指定的目標(biāo)位置。因此該問(wèn)題可由表示，其中E為基于Voronoi圖的戰(zhàn)場(chǎng)環(huán)境；V為由NV架UAV組成的飛機(jī)編隊(duì)；為待執(zhí)行的NT個(gè)目標(biāo)集合；為各目標(biāo)上需要完成的任務(wù)類(lèi)型集合，一般包括m1=偵察(detection)、m2=攻擊(destruction)和m3=毀傷評(píng)估(verification)三類(lèi)；P為UAV的可選航跡集合；C為約束條件集合。

1.2 約束條件

（1）任務(wù)偏序關(guān)系

無(wú)人機(jī)群的一次作戰(zhàn)任務(wù)，可以簡(jiǎn)述為，NV架無(wú)人機(jī)協(xié)同完成NT個(gè)作戰(zhàn)目標(biāo)上的M集合中的部分或全部任務(wù)類(lèi)型。則作戰(zhàn)目標(biāo)ti中的mj任務(wù)表示為所需無(wú)人機(jī)架次表示為將每架次任務(wù)可以進(jìn)一步表示為為了反映不同任務(wù)之間的偏序關(guān)系，為每個(gè)任務(wù)定義一個(gè)任務(wù)序號(hào)設(shè)置原則為：即

（2）時(shí)間協(xié)同約束

對(duì)于多無(wú)人機(jī)執(zhí)行單一任務(wù)如同時(shí)攻擊，時(shí)間約束是必要的。為此定義執(zhí)行時(shí)間窗表示序號(hào)的任務(wù)的時(shí)間窗表示任務(wù)的起始時(shí)間表示任務(wù)的結(jié)束時(shí)間。則表示該任務(wù)的執(zhí)行時(shí)間。當(dāng)某任務(wù)需要多架無(wú)人機(jī)協(xié)同完成時(shí)，則多架次飛機(jī)的任務(wù)需要同時(shí)執(zhí)行。即：當(dāng)滿(mǎn)足：

（3）空間協(xié)同約束

無(wú)人機(jī)攻擊目的是擾亂敵方目標(biāo)的防御系統(tǒng)，要求至少兩架無(wú)人機(jī)同時(shí)集結(jié)目的地，以提高攻擊毀傷率。當(dāng)某任務(wù)需要多架無(wú)人機(jī)協(xié)同完成時(shí)，到達(dá)目的地時(shí)各無(wú)人機(jī)之間保持一定的夾角Ω。即：

1.3 協(xié)同作戰(zhàn)的評(píng)價(jià)指標(biāo)

協(xié)同作戰(zhàn)包括單機(jī)航跡代價(jià)評(píng)估和多機(jī)協(xié)同時(shí)間約束兩方面，

（1）單機(jī)航跡綜合代價(jià)評(píng)估

式中：lr,s是L(r,s)的航程，dr,k、ds,k、d1/2,k分別是第k個(gè)威脅距該航跡端點(diǎn)r、s和1/2處的距離。

其中，系數(shù)k表示威脅代價(jià)的權(quán)重，它反映了航跡規(guī)劃時(shí)決策人的傾向性選擇。

（2）協(xié)同時(shí)間代價(jià)評(píng)估

評(píng)估多機(jī)單次作戰(zhàn)任務(wù)：首先計(jì)算單架次無(wú)人機(jī)到達(dá)目標(biāo)的時(shí)間TOTk,i

式中，Lk,i,Vk,max和Vk,min分別表示第k架無(wú)人機(jī)到達(dá)目標(biāo)Ti的航程、最大速度和最小速度。則TOTi為到達(dá)目標(biāo)Ti的ni架無(wú)人機(jī)的時(shí)間的交集：

評(píng)估多機(jī)連續(xù)作戰(zhàn)任務(wù)：定義為同一目標(biāo)的任務(wù)mn-1和任務(wù)mn的時(shí)間間隔。根據(jù)任務(wù)的偏序關(guān)系，從起始時(shí)刻到依次完成m1、m2、m3任務(wù)的結(jié)束時(shí)刻，存在以下關(guān)系：

因此綜合代價(jià)可以表示為：

其中f1為多機(jī)協(xié)同性能評(píng)估，衡量多機(jī)協(xié)同任務(wù)時(shí)間代價(jià)，并以協(xié)同變量作為每架無(wú)人機(jī)之間交流的內(nèi)容；f2為單機(jī)航跡綜合代價(jià)評(píng)估，直接衡量了各個(gè)無(wú)人機(jī)航跡綜合代價(jià)之和，多 UAV協(xié)同作戰(zhàn)的評(píng)價(jià)目標(biāo)是同時(shí)最小化f1和f2。

2 并行蟻群算法的任務(wù)/航跡規(guī)劃

2.1 并行蟻群的建立

根據(jù)上一節(jié)所討論的問(wèn)題模型，本文設(shè)計(jì)一種并行多子群蟻群算法。根據(jù)任務(wù)計(jì)劃將不同的任務(wù)映射為人工蟻群中的不同螞蟻?zhàn)尤?，各子群搜索尋找?zhí)行某一任務(wù)的無(wú)人機(jī)組及其飛行航跡。設(shè)人工蟻群為其中為對(duì)應(yīng)的第i次任務(wù)的螞蟻?zhàn)尤?，且不同子群間滿(mǎn)足式（10）

式中，Anti,j為第i個(gè)子群中第j個(gè)人工螞蟻，螞蟻?zhàn)尤篈Ci中每個(gè)螞蟻構(gòu)造執(zhí)行目標(biāo)i上的任務(wù)的無(wú)人機(jī)組及其對(duì)應(yīng)飛行航跡，因此所有目標(biāo)的任務(wù)集合需要來(lái)自不同螞蟻?zhàn)尤旱腘T×M個(gè)人工螞蟻構(gòu)造的無(wú)人機(jī)組序列。構(gòu)造一個(gè)滿(mǎn)足各類(lèi)約束條件的任務(wù)/航跡分配方案的NT×M個(gè)人工螞蟻，稱(chēng)為人工螞蟻簇AGi是人工蟻群中構(gòu)造一個(gè)完整的分配方案的最小螞蟻群落，且不同的人工螞蟻簇之間滿(mǎn)足：

2.2 任務(wù)分配方案的構(gòu)造

構(gòu)造方案的基本群落是人工螞蟻簇。人工螞蟻簇AGi中的每一個(gè)人工螞蟻依次為對(duì)應(yīng)的任務(wù)構(gòu)造無(wú)人機(jī)組合。每個(gè)人工螞蟻根據(jù)狀態(tài)轉(zhuǎn)移規(guī)則在候選集合中選擇無(wú)人機(jī)組。

2.3 螞蟻?zhàn)尤旱臓顟B(tài)轉(zhuǎn)移規(guī)則

每個(gè)子群建立啟發(fā)因子矩陣，根據(jù)綜合代價(jià)建立啟發(fā)因子矩陣。

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

假設(shè)NV=6，NE=50，NT=3，威脅代價(jià)的權(quán)重k=0.5，無(wú)人機(jī)飛行速度取值范圍為[4,6]，螞蟻數(shù)m=30，ρ=0.3，Q=2，α=1，β=1，限定螞蟻尋徑循環(huán)次數(shù) NC_max=100，遺傳迭代次數(shù) Generation=500，交叉因子PC=0.9，變異因子Pm=0.2。

圖2 SEAD任務(wù)模型

對(duì)于單任務(wù)作戰(zhàn)的任務(wù)/航跡規(guī)劃問(wèn)題，采用本文中的混合算法，最終任務(wù)分配方案如表 1所示，6架UAV兩兩編隊(duì)同時(shí)到達(dá)各目的地。

表1 單任務(wù)作戰(zhàn)的分配方案

圖3 單任務(wù)仿真結(jié)果

圖 3(a)~(c)分別是各目標(biāo)的任務(wù)分配和航跡規(guī)劃結(jié)果，可以看出，采用混合算法所得結(jié)果可以滿(mǎn)足無(wú)人機(jī)協(xié)同的諸多約束條件，滿(mǎn)足協(xié)同任務(wù)的需求。圖4為采用該方案所得無(wú)人機(jī)到達(dá)目標(biāo)的距離時(shí)間曲線(xiàn)，不同無(wú)人機(jī)同時(shí)到達(dá)同一目標(biāo)執(zhí)行任務(wù)。由于該方案是多次執(zhí)行500次迭代所得，因此協(xié)同時(shí)間*

TOT最小。圖 5表示該任務(wù)的收斂曲線(xiàn)，隨著算法的迭代，各目標(biāo)任務(wù)逐漸收斂得到最小代價(jià)值，總?cè)蝿?wù)的平均代價(jià)也逐漸趨于穩(wěn)定，圖中所示的實(shí)驗(yàn)在算法迭代 36次后，總協(xié)同代價(jià)達(dá)到收斂時(shí)的水平。

4 結(jié)論

本文所述利用混合 ACS-GA算法在解決無(wú)人機(jī)協(xié)同任務(wù)/航跡規(guī)劃問(wèn)題時(shí)，發(fā)揮了各自的優(yōu)點(diǎn)。仿真結(jié)果表明，利用蟻群算法求得的航跡能夠回避各種威脅，并構(gòu)造出初始解空間；利用遺傳算法對(duì)無(wú)人機(jī)、目標(biāo)、航跡編碼設(shè)計(jì)，并能夠在較少的迭代次數(shù)內(nèi)獲得較優(yōu)的作戰(zhàn)方案。

圖4 無(wú)人機(jī)到達(dá)目標(biāo)的距離隨時(shí)間變化曲線(xiàn)

圖5 綜合協(xié)同評(píng)價(jià)指標(biāo)收斂曲線(xiàn)

參考文獻(xiàn)：

[1]Eun Y, Bang H.Cooperative Task Assignment/Path Planning of Multiple Unmanned Aerial Vehicles Using Genetic Algorithms [J].Journal of Aircraft, 2009,46(1):338-343.

[2]Barabto G.Uninhabited combat air vehicle controls and displays for suppression of enemy air defenses [J].CSER IAC Gateway, 2000, 11(1):1-4.

[3]Atkinson M L.Contract nets for controls of distributed agents in unmanned air vehicles[R].AIAA-2003-6532,2003.

[4]MacKenzie D C.Collaborative tasking of tightly constrained multi-robot missions[C].Proceedings of the Second International Workshop on Multi-Robot Systems.2003:39-50.

[5]McLain T,Beard R.Trajectory Planning for Coordinated Rendezous of Unmanned Air Vehicles[J].AIAA Guidance, Navigation and Control,2000:2000-4369.