多無(wú)人機(jī)多目標(biāo)協(xié)同近距任務(wù)分配研究*

張 哲，吳 劍，何 誠(chéng)

(南昌航空大學(xué)信息工程學(xué)院， 南昌 330063)

0 引言

在復(fù)雜的戰(zhàn)場(chǎng)環(huán)境中，當(dāng)單架無(wú)人機(jī)常常難以完成指定的任務(wù)時(shí)，需要多架無(wú)人機(jī)進(jìn)行協(xié)同任務(wù)分配以保證無(wú)人機(jī)的作戰(zhàn)效能和作戰(zhàn)自主性[1]。當(dāng)無(wú)人機(jī)同時(shí)面對(duì)雷達(dá)威脅源和大量近距的目標(biāo)群時(shí)，如何快速準(zhǔn)確地進(jìn)行協(xié)同任務(wù)分配更是當(dāng)前的一大難題[2-4]。

針對(duì)多無(wú)人機(jī)協(xié)同任務(wù)分配問(wèn)題，諸多文獻(xiàn)提出了一系列的模型及算法。在模型方面，如運(yùn)籌學(xué)中的多旅行商(MTSP)模型[5-6]和混合整數(shù)線性規(guī)劃(MILP)模型[7-8]等。然而，MTSP模型并未討論任務(wù)的異構(gòu)性，忽略了任務(wù)與不同時(shí)間節(jié)點(diǎn)的關(guān)系。MILP模型僅適用于范圍小、任務(wù)目標(biāo)數(shù)量少的任務(wù)分配問(wèn)題。在算法方面，文獻(xiàn)[9]提出了一種周期性快速搜索的遺傳算法來(lái)解決任務(wù)分配問(wèn)題，但是該算法僅僅驗(yàn)證了在目標(biāo)數(shù)量少、范圍小的環(huán)境下有較快的收斂速度，而當(dāng)目標(biāo)范圍和數(shù)量較大時(shí)，并不能體現(xiàn)該算法的優(yōu)越性。文獻(xiàn)[10-13]研究了一系列智能優(yōu)化算法及其改進(jìn)方法等，如蟻群算法、模擬退火算法和量子粒子群算法等，這些算法在求解過(guò)程中仍存在陷入局部最優(yōu)、計(jì)算時(shí)間較長(zhǎng)、解空間規(guī)模大和收斂速度較慢等局限性。

文中建立了基于混合粒子群算法的多機(jī)協(xié)同任務(wù)分層分配模型。將任務(wù)分解為3層，即多目標(biāo)群之間任務(wù)分配、各群內(nèi)目標(biāo)搜索路線分配和無(wú)人機(jī)載荷約束下的路線優(yōu)化，從而將多目標(biāo)規(guī)劃問(wèn)題轉(zhuǎn)化為單目標(biāo)規(guī)劃。利用混合粒子群算法(GA-PSO)去求解模型，該算法摒棄了傳統(tǒng)粒子群算法中的通過(guò)跟蹤極值來(lái)更新粒子位置，而是引入了遺傳算法中的交叉變異操作來(lái)搜索最優(yōu)解。

1 分層任務(wù)分配模型

1.1 問(wèn)題描述

多無(wú)人機(jī)多目標(biāo)近距協(xié)同任務(wù)分配問(wèn)題的實(shí)質(zhì)是多約束條件的多目標(biāo)優(yōu)化與決策問(wèn)題。針對(duì)這類(lèi)問(wèn)題，考慮無(wú)人機(jī)執(zhí)行任務(wù)時(shí)的飛行總時(shí)間、個(gè)體載荷、自身協(xié)同約束和環(huán)境威脅約束[14]等進(jìn)行建模分析。

假設(shè)有7個(gè)無(wú)人機(jī)基地，各基地均配備若干數(shù)量的FY-1型無(wú)人機(jī)，主要完成目標(biāo)偵察和作戰(zhàn)攻擊。根據(jù)任務(wù)要求，無(wú)人機(jī)需完成偵察和打擊的目標(biāo)群為A01～A10，每個(gè)目標(biāo)群包含多個(gè)地面目標(biāo)，周?chē)溆欣走_(dá)站。無(wú)人機(jī)基地的相關(guān)信息如表1。

表1 無(wú)人機(jī)基地的相關(guān)信息

1.2 多目標(biāo)群間任務(wù)分配模型

1.2.1 目標(biāo)函數(shù)

1)飛行總路程

設(shè)一個(gè)賦權(quán)無(wú)向完全圖G=(C,X,D),目標(biāo)群集合、邊集合分別為C={c1,c2,…,cn}和X={Xij|i,j=0,1,2,…,n},Xij為目標(biāo)群Ci到目標(biāo)群Cj的邊,表示該條飛行線路是否應(yīng)該執(zhí)行。距離集合D={dij|i,j=1,2,…,n}表示目標(biāo)群Ci到目標(biāo)群Cj的距離。

給定m架無(wú)人機(jī)，無(wú)人機(jī)從任一基地bi出發(fā)。首先飛向目標(biāo)群Ci，沿一條路徑偵察并且從目標(biāo)群Cj(Ci≠Cj)離開(kāi)。每架無(wú)人機(jī)都至少到達(dá)一個(gè)目標(biāo)群，任意目標(biāo)群都需要被無(wú)人機(jī)偵察且僅被偵察一次。求m條路徑，使得m架無(wú)人機(jī)的飛行總路程L1最小。在討論雷達(dá)對(duì)無(wú)人機(jī)協(xié)同飛行的影響時(shí)，可以將問(wèn)題抽象為二維平面的路線規(guī)劃問(wèn)題，使得無(wú)人機(jī)在敵方雷達(dá)探測(cè)范圍內(nèi)的飛行路徑最短。由于多架無(wú)人機(jī)從不同的基地起飛，且每架無(wú)人機(jī)到達(dá)第一個(gè)目標(biāo)群和離開(kāi)最后一個(gè)目標(biāo)群都會(huì)增加滯留在雷達(dá)探測(cè)區(qū)內(nèi)的路程2R(R為雷達(dá)探測(cè)半徑)。

令Si={cin,c2,…,cout}為第i架無(wú)人機(jī)飛行路線，其中cin和cout為第i架無(wú)人機(jī)偵查路線的起點(diǎn)和終點(diǎn)。求總路線S={s1,s2,…,sm}，使得:

(1)

2)攻擊目標(biāo)收益

攻擊目標(biāo)收益是指多無(wú)人機(jī)在協(xié)同完成任務(wù)時(shí)對(duì)目標(biāo)造成的毀傷價(jià)值。它可定義為目標(biāo)價(jià)值和毀傷概率的函數(shù)。該函數(shù)指向了無(wú)人機(jī)協(xié)同任務(wù)攻擊時(shí)的作戰(zhàn)效能最大化。記第i架無(wú)人機(jī)攻擊目標(biāo)群Cj所帶來(lái)的效益為P，則

P=Vtj·P(Ai)

(2)

式中：Vtj為目標(biāo)群Cj的價(jià)值，P(Ai)為第i架無(wú)人機(jī)對(duì)目標(biāo)群Cj的擊毀概率。即：

minL2=1-Vtj·P(Ai)

(3)

3)完成任務(wù)所需時(shí)間

完成任務(wù)所需時(shí)間定義為:

t=maxti

(4)

式中：ti為第i架無(wú)人機(jī)完成規(guī)劃任務(wù)所花費(fèi)的時(shí)間，考慮各無(wú)人機(jī)間任務(wù)分配和載荷資源的合理性，給出時(shí)間代價(jià)函數(shù)L3，則

(5)

4)執(zhí)行任務(wù)時(shí)造成的威脅

當(dāng)無(wú)人機(jī)協(xié)同飛行時(shí)，假設(shè)第i架無(wú)人機(jī)經(jīng)過(guò)目標(biāo)群Cj后的生存概率為P(Bi),則P(Bi)=1-P(Kj)。對(duì)任一無(wú)人機(jī)來(lái)說(shuō)，執(zhí)行n個(gè)任務(wù)時(shí)造成的威脅代價(jià)L4符合：

(6)

式中：Vui為第i架無(wú)人機(jī)的價(jià)值；P(Kj)為目標(biāo)群Cj擊毀無(wú)人機(jī)的概率。

1.2.2 任務(wù)分配模型

通過(guò)建模分析,可以得到第一層任務(wù)規(guī)劃，即多目標(biāo)群任務(wù)規(guī)劃模型為：

minf=ω1·L1+ω2·L2+ω3·L3+ω4·L4

(7)

約束條件為：

(8)

式中：ω1,ω2,ω3,ω4為各目標(biāo)函數(shù)所占的權(quán)重；dis( )表示無(wú)人機(jī)從目標(biāo)群飛回基地的距離；M為無(wú)人機(jī)最大航程；s為燃料安全系數(shù)；xij∈{0,1}為決策變量，xij=1表示第i架無(wú)人機(jī)對(duì)第j個(gè)目標(biāo)群執(zhí)行任務(wù)；N表示目標(biāo)群數(shù)量；Oi為第i架無(wú)人機(jī)的任務(wù)載荷。約束條件使得無(wú)人機(jī)至少偵察一個(gè)目標(biāo)群，并且所有目標(biāo)群有且僅有一次被無(wú)人機(jī)偵察。因此各無(wú)人機(jī)之間軌跡無(wú)重合。

1.3 各群內(nèi)目標(biāo)搜索路線分配

在確定了無(wú)人機(jī)對(duì)多目標(biāo)群的任務(wù)路線后，對(duì)單個(gè)目標(biāo)群內(nèi)部進(jìn)行路線規(guī)劃，即第二層任務(wù)規(guī)劃。對(duì)于單個(gè)目標(biāo)群內(nèi)的多個(gè)目標(biāo)點(diǎn)，使得無(wú)人機(jī)遍歷所有目標(biāo)點(diǎn)，且每個(gè)目標(biāo)點(diǎn)只被偵察一次。具體路線分配策略如下：

Step1:分別規(guī)劃所有目標(biāo)群內(nèi)的路線，并確定出入口。

Step2:計(jì)算在第一層規(guī)劃獲得的路線中相鄰的兩個(gè)目標(biāo)群質(zhì)心距離。

Step3:相鄰兩個(gè)目標(biāo)群的出入口有4個(gè)，計(jì)算4個(gè)出入口在兩質(zhì)心連線上的投影。

Step4:選擇兩質(zhì)心連線上投影距離最短的兩個(gè)出入口作為兩個(gè)目標(biāo)群之間的路線。

1.4 載荷約束下的路線優(yōu)化

確定了無(wú)人機(jī)在各目標(biāo)群內(nèi)的路線順序后，針對(duì)無(wú)人機(jī)分別加載的S-1型和S-2型載荷進(jìn)行路線優(yōu)化。具體如圖1和圖2。

圖1 加載S-1型載荷航跡示意圖

圖2 加載S-2型載荷航跡示意圖

兩圖中虛線為目標(biāo)點(diǎn)間規(guī)劃的結(jié)果，實(shí)線為根據(jù)兩種不同載荷限制而規(guī)劃的無(wú)人機(jī)航跡。對(duì)于加載S-1型載荷：無(wú)人機(jī)從基地飛向目標(biāo)1過(guò)程中，直接到達(dá)目標(biāo)1所在圓的切點(diǎn)，然后依次飛向目標(biāo)2、3對(duì)應(yīng)的切點(diǎn)直至偵察任務(wù)完成后飛回基地。對(duì)于加載S-2型載荷：無(wú)人機(jī)從基地直接到達(dá)與目標(biāo)1所在圓的交點(diǎn)，完成對(duì)目標(biāo)1的攻擊后，飛往目標(biāo)2，直接到達(dá)目標(biāo)2所在圓的交點(diǎn)，直至最終飛回基地。線段a和線段b分別為無(wú)人機(jī)根據(jù)最短線飛向目標(biāo)1和目標(biāo)2的路徑。線段c是無(wú)人機(jī)完成對(duì)目標(biāo)1攻擊任務(wù)后飛向目標(biāo)2的路徑。

2 混合粒子群算法

2.1 算法改進(jìn)方案

多機(jī)協(xié)同的任務(wù)分層分配模型的求解實(shí)質(zhì)上可以看成是對(duì)MTSP問(wèn)題的求解。由于MTSP問(wèn)題屬于NP難題[15]，若運(yùn)用精確的求解方法，其計(jì)算量會(huì)隨著網(wǎng)格數(shù)量的增大呈指數(shù)性增長(zhǎng)。因此通常采用一些啟發(fā)式優(yōu)化算法來(lái)進(jìn)行求解。

由于傳統(tǒng)粒子群算法是通過(guò)追隨個(gè)體極值和種群極值完成尋優(yōu)，雖然操作簡(jiǎn)單，且能夠快速收斂，但是隨著迭代次數(shù)的不斷增加，在種群收斂集中的同時(shí)，各粒子也越來(lái)越相似，出現(xiàn)粒子貧化現(xiàn)象，導(dǎo)致陷入局部最優(yōu)解中無(wú)法跳出。對(duì)于標(biāo)準(zhǔn)的遺傳算法來(lái)說(shuō)，在求解MTSP問(wèn)題時(shí)通過(guò)交叉變異，雖然能夠保證解的多樣性，但可行解的數(shù)目為(n+m-1)!，耗時(shí)巨大且全局搜索能力不強(qiáng)。因此，為了提高算法的執(zhí)行效率，增大收斂于全局最優(yōu)解的可能性，保證解空間的多樣性，采用GA-PSO算法來(lái)實(shí)現(xiàn)模型求解。

2.2 算法實(shí)現(xiàn)

2.2.1 個(gè)體編碼

粒子個(gè)體編碼采用整數(shù)編碼的方式，染色體長(zhǎng)度為n+m-1,其中染色體前n位為隨機(jī)的整數(shù)呈亂序排列，按大小排序后即為無(wú)人機(jī)偵察各目標(biāo)點(diǎn)的順序。后(m-1)位為斷點(diǎn)位置的標(biāo)號(hào)，斷點(diǎn)用來(lái)表示目標(biāo)在不同無(wú)人機(jī)之間的分配。

2.2.2 種群初始化

將種群分為多個(gè)組，每個(gè)組的個(gè)體數(shù)量為10，組的數(shù)量根據(jù)模型需要設(shè)置為15個(gè)。每組內(nèi)的個(gè)體之間相互交叉無(wú)障礙，交叉和變異概率pc為0.9，pi為0.01，即組中個(gè)體有很小的幾率逃逸到另一個(gè)組中。

2.2.3 適應(yīng)度計(jì)算及選擇策略

適應(yīng)度函數(shù)為各目標(biāo)函數(shù)，取適應(yīng)度函數(shù)最高(目標(biāo)函數(shù)最小)的個(gè)體為父代。為了加速收斂，直接刪除該群中其他的個(gè)體。

2.2.4 交叉操作和變異操作

采用多種遺傳方式[16-18]來(lái)生成子代，具體規(guī)則如下：1)對(duì)換染色體前半段的任意兩個(gè)數(shù);2)對(duì)換染色體前半段的兩個(gè)數(shù)段，即同時(shí)將多個(gè)數(shù)進(jìn)行對(duì)換;3)對(duì)染色體前半段的數(shù)進(jìn)行左移操作;4)隨機(jī)更新染色體后半段;5)同時(shí)進(jìn)行Step1和Step4;6)同時(shí)進(jìn)行Step2和Step4;7)同時(shí)進(jìn)行Step3和Step4;8)染色體不變。

利用上述8種規(guī)則產(chǎn)生新個(gè)體，得到的新個(gè)體采用了保留優(yōu)秀個(gè)體策略，只有當(dāng)新粒子適應(yīng)度值優(yōu)于舊粒子時(shí)才更新粒子。

2.2.5 算法終止規(guī)則

將最大迭代次數(shù)作為終止條件，設(shè)置最大迭代次數(shù)為200。

2.2.6 算法流程圖

圖3 混合粒子群算法流程圖

3 仿真分析

3.1 分層任務(wù)分配仿真

為了驗(yàn)證模型和算法的合理性和高效性，在Windows 10操作系統(tǒng)上，PC機(jī)配置為Intel(R) Core i5-4210M @2.60 GHz，基于MatlabR2017a環(huán)境下完成仿真實(shí)驗(yàn)。各基地配置一定數(shù)量的FY-1型無(wú)人機(jī)，機(jī)上加載的S-1、S-2兩種載荷用于對(duì)目標(biāo)群完成偵察和攻擊任務(wù)。設(shè)定無(wú)人機(jī)速度為200 km/h，高度為1 500 m，最大飛行時(shí)間為10 h，無(wú)人機(jī)每次只能加載一種載荷。目標(biāo)群數(shù)量N=10，目標(biāo)點(diǎn)個(gè)數(shù)n=68,各目標(biāo)函數(shù)的權(quán)重ω={0.276,0.182,0.235,0.307}，根據(jù)混合粒子群算法的流程，計(jì)算得到了第一層、第二層和第三層任務(wù)分配如圖4、圖5、圖6。

圖4 各目標(biāo)群之間任務(wù)規(guī)劃

圖5 群內(nèi)目標(biāo)點(diǎn)間任務(wù)規(guī)劃

圖6 載荷約束下的路線優(yōu)化

3.2 全局任務(wù)分配仿真

基于全局優(yōu)化的思想，將所有目標(biāo)點(diǎn)統(tǒng)一規(guī)劃，不考慮目標(biāo)的聚散情況，直接求出各目標(biāo)點(diǎn)之間的任務(wù)分配路線如圖7。

圖7 全局任務(wù)分配的路線

3.3 任務(wù)分配模型和算法對(duì)比

混合粒子群算法和標(biāo)準(zhǔn)粒子群算法對(duì)比如圖8。分層任務(wù)分配的調(diào)度方案見(jiàn)表2，全局任務(wù)分配調(diào)度方案見(jiàn)表3，兩種任務(wù)分配差異見(jiàn)表4。

圖8 適應(yīng)度變化

表2 多機(jī)協(xié)同分層任務(wù)分配方案

表3 多機(jī)協(xié)同全局任務(wù)分配方案

表4 兩種任務(wù)分配模型對(duì)比

4 結(jié)論

研究了多目標(biāo)多無(wú)人機(jī)近距的協(xié)同任務(wù)分配問(wèn)題。在模型上，考慮了雷達(dá)威脅和密集目標(biāo)群對(duì)無(wú)人機(jī)協(xié)同任務(wù)分配的影響，建立了任務(wù)分層分配模型，給出了3層的設(shè)計(jì)方案，即各目標(biāo)群之間任務(wù)分配、各目標(biāo)群內(nèi)的目標(biāo)進(jìn)行了路線分配和在載荷約束條件下的路線優(yōu)化；在算法上，針對(duì)傳統(tǒng)遺傳算法和粒子群算法存在的局限性，提出了一種混合粒子群算法(GA-PSO)來(lái)求解任務(wù)分配模型。仿真結(jié)果表明：1)分層任務(wù)分配模型與全局任務(wù)分配模型相比，任務(wù)分配的效率更高，任務(wù)分配花費(fèi)時(shí)間為全局分配的90.1%，計(jì)算耗時(shí)為全局分配的15.1%。2)分層分配模型適用于解決范圍大、目標(biāo)數(shù)量多和威脅源覆蓋廣的任務(wù)分配問(wèn)題中，不再僅限于前人研究的范圍小和目標(biāo)數(shù)量少的情況。3)提出的混合粒子群算法比傳統(tǒng)的粒子群算法更具優(yōu)越性，加快了解的收斂速度，引入了遺傳算法中的交叉變異操作，搜索最優(yōu)解的能力更強(qiáng)。4)提出的模型和改進(jìn)算法很好地解決了多機(jī)協(xié)同任務(wù)分配問(wèn)題。上述研究對(duì)于無(wú)人機(jī)在復(fù)雜戰(zhàn)場(chǎng)環(huán)境中迅速作出反應(yīng)和戰(zhàn)略調(diào)整具有現(xiàn)實(shí)意義。