基于離散鴿群算法的無(wú)人機(jī)任務(wù)分配

勾青超，李慶奎

(北京信息科技大學(xué) 自動(dòng)化學(xué)院，北京 100192)

0 引言

多無(wú)人機(jī)協(xié)同[1]在軍事領(lǐng)域和民用領(lǐng)域都具有廣泛的應(yīng)用前景。任務(wù)規(guī)劃是多無(wú)人機(jī)協(xié)同任務(wù)的關(guān)鍵技術(shù)，是實(shí)現(xiàn)多無(wú)人機(jī)協(xié)同完成任務(wù)的指揮系統(tǒng)，主要包括任務(wù)分配和航跡規(guī)劃。任務(wù)分配是在考慮多種約束下，對(duì)同類(lèi)型的無(wú)人機(jī)或者是異構(gòu)無(wú)人機(jī)進(jìn)行任務(wù)指派，是實(shí)現(xiàn)協(xié)同任務(wù)的核心。

多無(wú)人機(jī)任務(wù)分配已經(jīng)成為目前的研究熱點(diǎn)，國(guó)內(nèi)外學(xué)者開(kāi)展了相關(guān)的研究工作。文獻(xiàn)[2]用遺傳算法求解異構(gòu)無(wú)人機(jī)的多機(jī)協(xié)同任務(wù)分配問(wèn)題；文獻(xiàn)[3]介紹了合同網(wǎng)方法的提出及發(fā)展；文獻(xiàn)[4]對(duì)一致性包算法(CBBA)進(jìn)行了擴(kuò)展，提出了基于改進(jìn)沖突消解原則的一致性聯(lián)盟算法(CBCA)，以實(shí)現(xiàn)異構(gòu)多智能體協(xié)同無(wú)沖突任務(wù)分配。智能算法對(duì)于求解任務(wù)分配具有先天的優(yōu)勢(shì)，主要包括基于蟻群算法的任務(wù)分配[5]、基于粒子群算法的任務(wù)分配[6-10]、基于遺傳算法的任務(wù)分配[11]等。

目前，任務(wù)分配的算法模型多是基于多目標(biāo)單任務(wù)進(jìn)行的。而實(shí)際上在真實(shí)環(huán)境中無(wú)人機(jī)需要通過(guò)協(xié)同同時(shí)執(zhí)行多個(gè)任務(wù)。為研究多目標(biāo)多任務(wù)的任務(wù)分配問(wèn)題，本文將鴿群算法進(jìn)行改進(jìn)，并將其離散化，應(yīng)用改進(jìn)后的算法對(duì)多無(wú)人機(jī)的協(xié)同任務(wù)分配問(wèn)題進(jìn)行了求解。鴿群算法[12]具有全局優(yōu)化的特點(diǎn)，對(duì)于多約束多目標(biāo)問(wèn)題具有較大的求解優(yōu)勢(shì)。

1 任務(wù)分配模型

1.1 問(wèn)題描述

假定多無(wú)人機(jī)在執(zhí)行廣域搜索攻擊任務(wù)中，任務(wù)區(qū)域已被其他無(wú)人機(jī)或者偵察平臺(tái)搜索到Nt個(gè)疑似目標(biāo)，需要任務(wù)區(qū)域內(nèi)的多無(wú)人機(jī)對(duì)疑似目標(biāo)依次進(jìn)行偵察、攻擊。令發(fā)現(xiàn)的目標(biāo)集合為T(mén)={T1,T2,…,TNt}，任務(wù)區(qū)域的無(wú)人機(jī)有Nv個(gè)，其集合為V={V1,V2,…,VNv}。對(duì)每個(gè)目標(biāo)需要執(zhí)行的任務(wù)集合為M={M1,M2,…,MNm}。無(wú)人機(jī)的任務(wù)集合為K={K1,K2,…,KNc}，Nc為無(wú)人機(jī)需要執(zhí)行的任務(wù)總數(shù)量，Nc=Nv×Nm。作戰(zhàn)示意圖如圖1所示。

在示例中，三架無(wú)人機(jī)UAV1、UAV2、UAV3執(zhí)行對(duì)target1-target6的攻擊任務(wù)，目的是在滿(mǎn)足約束條件的前提下，找到最優(yōu)的任務(wù)分配方法。示例中的求解結(jié)果為UAV1攻擊target1與target2、UAV2攻擊target3與target4、UAV3攻擊target5與target6的路徑代價(jià)最小，即為最優(yōu)的方案。

1.2 約束條件

在任務(wù)分配問(wèn)題中存在以下約束：

1)任務(wù)時(shí)序約束。多無(wú)人機(jī)對(duì)同一目標(biāo)進(jìn)行偵察和攻擊任務(wù)時(shí)具有時(shí)序約束。對(duì)該目標(biāo)的攻擊任務(wù)必須在對(duì)該目標(biāo)的偵察任務(wù)完成之后，即：

TM1

(1)

2)多機(jī)協(xié)同約束。任務(wù)集合中的任何一個(gè)任務(wù)只能被完成一次，即所有無(wú)人機(jī)對(duì)同一個(gè)目標(biāo)只能依次進(jìn)行一次偵察和攻擊任務(wù)，即：

(2)

3)彈藥數(shù)量約束。設(shè)對(duì)多無(wú)人機(jī)進(jìn)行任務(wù)分配時(shí)，無(wú)人機(jī)1當(dāng)前剩余未使用彈藥數(shù)量為M，則無(wú)人機(jī) 1執(zhí)行攻擊任務(wù)的次數(shù)必須小于或者等于M。即：

(3)

4)任務(wù)時(shí)間約束。定義同一個(gè)目標(biāo)的不同任務(wù)執(zhí)行時(shí)存在時(shí)間間隔，即前一個(gè)任務(wù)完成后需經(jīng)過(guò)一個(gè)最小時(shí)間間隔之后才允許執(zhí)行下一個(gè)任務(wù)，而且時(shí)間間隔不允許超出最大時(shí)間間隔，即

tM(nt)+Δtmin≤tM(nt+1)≤tM(nt)+Δtmax

(4)

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

該類(lèi)問(wèn)題通常選取航程或者航行時(shí)間作為方案決策的重要標(biāo)準(zhǔn)。本文選取所有目標(biāo)被完成后無(wú)人機(jī)航行總距離以及時(shí)間作為衡量指標(biāo)，認(rèn)為總航程最短的任務(wù)分配方案最優(yōu)。假設(shè)Di為第i架無(wú)人機(jī)與目標(biāo)的區(qū)間信息，j為被執(zhí)行任務(wù)的目標(biāo)，即第i架無(wú)人機(jī)對(duì)所有目標(biāo)的航程代價(jià)為

(5)

最優(yōu)方案為

(6)

2 數(shù)學(xué)模型

2.1 基本鴿群算法

鴿群算法是根據(jù)鴿子所特有的導(dǎo)航能力而提出的。將鴿子歸巢行為看作依靠磁場(chǎng)與地標(biāo)的兩階段尋徑。在離巢較遠(yuǎn)距離依賴(lài)地磁場(chǎng)確定歸巢大致方向，在靠近鴿巢時(shí)，根據(jù)附近熟悉的地標(biāo)建筑鎖定鴿巢位置。基本鴿群算法如下。

2.1.1 第一階段：依靠磁場(chǎng)尋徑

鴿群在多維搜索空間中，鴿子的位置和速度在每一次迭代中都會(huì)得到更新，更新過(guò)程如下：

V(t)=V(t-1)×e-Rt+d×(Xgbest-X(t-1))

(7)

X(t)=X(t-1)+V(t)

(8)

式中：R為磁場(chǎng)因子，R∈{0,1}；d為取值范圍在(0,1)的隨機(jī)數(shù)；Nc為目前迭代次數(shù)；經(jīng)過(guò)Nc-1次迭代循環(huán)后，通過(guò)比較所有鴿子的位置得到全局最優(yōu)位置Xgbest。當(dāng)該循環(huán)次數(shù)達(dá)到所要求的迭代次數(shù)后，即停止磁場(chǎng)因子階段的迭代，進(jìn)入地標(biāo)算子中繼續(xù)工作。

2.1.2 第二階段：依靠地標(biāo)尋徑

更新地標(biāo)函數(shù)為

(9)

X(t)=X(t-1)+d×(X(t)-X(t-1))

(10)

式中f(X(t))為當(dāng)前鴿子的適度值函數(shù)，即設(shè)定的目標(biāo)函數(shù)。

舍棄函數(shù)為

(11)

在依靠地標(biāo)尋徑的過(guò)程中，每一次迭代后鴿子的數(shù)量都會(huì)減少一半。那些遠(yuǎn)離目的地的鴿子對(duì)地標(biāo)不熟悉,它們將不再有分辨路徑的能力,因而被舍去。Xc是剩余鴿子的中心位置，將被當(dāng)作地標(biāo)，即作為飛行的參考方向。

基本鴿群算法流程如圖2所示。

2.2 鴿群算法的離散化與改進(jìn)

2.2.1 鴿群算法離散化

鴿群算法是針對(duì)連續(xù)函數(shù)提出的智能算法。本文在對(duì)任務(wù)分配問(wèn)題進(jìn)行求解時(shí)，首先對(duì)鴿群算法進(jìn)行離散化處理。具體方式是將鴿群的速度和位置坐標(biāo)離散化，通常用0或1來(lái)表示(離散二進(jìn)制)，或者自定義整數(shù)數(shù)組來(lái)表示。

針對(duì)多無(wú)人機(jī)多目標(biāo)任務(wù)的分配問(wèn)題，本文將目標(biāo)的序列與無(wú)人機(jī)的序列進(jìn)行編碼?？紤]到多機(jī)協(xié)同約束，即每個(gè)目標(biāo)任務(wù)均只需要一架無(wú)人機(jī)完成，所以可擬定確定的目標(biāo)序列，通過(guò)隨機(jī)排列無(wú)人機(jī)編碼序列，來(lái)形成不同的任務(wù)分配方案，分配結(jié)果實(shí)例如圖3所示。

圖3描述的是5個(gè)無(wú)人機(jī)針對(duì)8個(gè)目標(biāo)執(zhí)行兩種任務(wù)的一種隨機(jī)編碼序列，圖中數(shù)字即代表第幾個(gè)無(wú)人機(jī)去執(zhí)行對(duì)應(yīng)行目標(biāo)的對(duì)應(yīng)列類(lèi)型任務(wù)。

2.2.2 鴿群算法的改進(jìn)

任務(wù)分配問(wèn)題難以擬合成一個(gè)連續(xù)函數(shù)，而基本鴿群算法針對(duì)離散問(wèn)題難以處理，本文對(duì)鴿群算法進(jìn)行改進(jìn)，改進(jìn)后的模型如下。

1)第一階段,迭代次數(shù)l≤N1時(shí)：

X=e-R×l×X(l-1)+d×(Xgbest-X(l-1))

(12)

式中Xgbest為當(dāng)前全局最優(yōu)解。

2)第二階段，迭代次數(shù)N1≤l≤(N1+N2)時(shí)：

X=e-R×l×X(l-1)+rand(Xc-X(l-1))

(13)

(14)

標(biāo)準(zhǔn)鴿群算法通過(guò)每次剩余鴿群中的中心位置向目標(biāo)靠近來(lái)尋優(yōu)，容易過(guò)早收斂。在進(jìn)行尋優(yōu)搜索時(shí)，前期希望算法擁有較強(qiáng)的全局搜索能力，局部搜索能力影響小，后期更希望算法能夠進(jìn)行精確的局部搜索，因此希望局部更新對(duì)算法的影響更大。因此本文對(duì)式中磁場(chǎng)因子R進(jìn)行了重新設(shè)計(jì)，使其在迭代過(guò)程中呈現(xiàn)非線(xiàn)性衰減的趨勢(shì)，避免過(guò)早收斂：

(15)

式中：

(16)

2.2.3 約束處理

為了更好地處理約束，同時(shí)為了規(guī)避在生成任務(wù)分配方案時(shí)出現(xiàn)生成不可能方案(如負(fù)數(shù)或者超出無(wú)人機(jī)數(shù)量的數(shù)值)的情況，本文對(duì)任務(wù)分配方案序列進(jìn)行了處理，將單列無(wú)人機(jī)編碼數(shù)組轉(zhuǎn)化為目標(biāo)與無(wú)人機(jī)對(duì)應(yīng)關(guān)系的連接矩陣，行數(shù)等于目標(biāo)數(shù)目，列數(shù)等于無(wú)人機(jī)數(shù)目，用0或1表示，方案的對(duì)應(yīng)關(guān)系轉(zhuǎn)化示例如圖4所示。

對(duì)于連接矩陣L，其取值僅有{0，1}，因此，可以生成二進(jìn)制的速度矩陣，利用“與或”邏輯關(guān)系，完成迭代中的迭代結(jié)果離散化。在連接矩陣中，對(duì)以下約束進(jìn)行處理：

1)多機(jī)協(xié)同約束。在連接矩陣中對(duì)應(yīng)每行和為1，即：

∑(A(i),2)=1

(17)

2)彈藥約束。當(dāng)任務(wù)類(lèi)型為攻擊約束時(shí)(定義任務(wù)類(lèi)型變量nt，當(dāng)nt=2時(shí))：

∑(A(i),1)≤2

(18)

3)任務(wù)時(shí)序約束。通過(guò)定義任務(wù)類(lèi)型變量nt，取值{1,2},分別對(duì)應(yīng)目標(biāo)的偵察與攻擊任務(wù)。程序通過(guò)擴(kuò)展矩陣維數(shù)來(lái)解決目標(biāo)的多任務(wù)類(lèi)型，并依次對(duì)任務(wù)類(lèi)型進(jìn)行迭代。

4)任務(wù)間隔約束。定義時(shí)間序列組，分別記錄目標(biāo)任務(wù)的完成時(shí)刻Tt與無(wú)人機(jī)完成任務(wù)時(shí)刻Tu(前者需要通過(guò)后者數(shù)值來(lái)計(jì)算)，判斷同一目標(biāo)的不同任務(wù)類(lèi)型完成時(shí)間是否滿(mǎn)足約束條件。

① 若任務(wù)間隔時(shí)間Δt小于最小間隔時(shí)間Δtmin，則認(rèn)為無(wú)人機(jī)通過(guò)盤(pán)旋來(lái)延長(zhǎng)飛行時(shí)間，即此段距離認(rèn)為是：

D=v×Δtmin

(19)

② 若任務(wù)間隔時(shí)間Δt大于最大間隔時(shí)間Δtmax，則通過(guò)罰函數(shù)進(jìn)行處罰，定義罰函數(shù)因子PT：

F=D+M×PT

(20)

式中M是較大值，當(dāng)滿(mǎn)足約束時(shí)，PT=0；當(dāng)不滿(mǎn)足約束時(shí)，PT=1。

2.2.4 適應(yīng)度函數(shù)

適應(yīng)度函數(shù)的選取直接影響到算法的收斂速度以及能否找到最優(yōu)解。本文通過(guò)計(jì)算鴿群中各粒子的適應(yīng)度函數(shù)來(lái)判斷個(gè)體適應(yīng)程度。即通過(guò)計(jì)算多無(wú)人機(jī)完成多目標(biāo)任務(wù)的總航程，來(lái)判斷個(gè)體的優(yōu)秀程度，選取航程最短的作為最優(yōu)方案：

1)對(duì)于單任務(wù)類(lèi)型問(wèn)題，不需要考慮復(fù)雜的多任務(wù)條件約束，不利用外部信息，僅以適應(yīng)度函數(shù)為依據(jù)，利用鴿群中每個(gè)粒子的適應(yīng)度來(lái)進(jìn)行搜索，最優(yōu)適應(yīng)度即為任務(wù)分配結(jié)果中粒子的總航程累加結(jié)果。

2)對(duì)于多任務(wù)類(lèi)型問(wèn)題，需要考慮到任務(wù)間隔約束。最優(yōu)適應(yīng)度需要比較多種任務(wù)階段適應(yīng)度值的累加結(jié)果得出，并對(duì)不滿(mǎn)足約束的某段航程進(jìn)行處理，即延長(zhǎng)或者懲罰。

3 離散鴿群算法流程

程序運(yùn)行流程框架如圖5所示。

其中constraints_solve函數(shù)對(duì)迭代后得到的速度矩陣進(jìn)行處理，處理多機(jī)協(xié)同約束和彈藥約束。其思路是：

第一步：對(duì)多于目標(biāo)任務(wù)數(shù)量的坐標(biāo)進(jìn)行隨機(jī)去除(初步滿(mǎn)足多機(jī)協(xié)同約束，總無(wú)人機(jī)執(zhí)行任務(wù)數(shù)等于目標(biāo)需要執(zhí)行任務(wù)數(shù))。

第二步：進(jìn)一步處理多機(jī)協(xié)同約束，將和不為1的行中多余的點(diǎn)進(jìn)行轉(zhuǎn)移。首先要搜索行和大于1的行，利用random_choose函數(shù)隨機(jī)選取多余的點(diǎn)(增加了種群多樣性)，然后搜索同列中可轉(zhuǎn)移的位置(行和為0的位置)，在搜索結(jié)果中隨機(jī)選取轉(zhuǎn)移位置進(jìn)行轉(zhuǎn)移，轉(zhuǎn)移只改變行數(shù)，不改變列數(shù)。

第三步：處理彈藥約束。首先搜索列和大于2的列，隨機(jī)選取多余的點(diǎn)，然后隨機(jī)選取其他列可轉(zhuǎn)移的位置進(jìn)行轉(zhuǎn)移，轉(zhuǎn)移只改變列數(shù)，不改變行數(shù)。

calFitness函數(shù)通過(guò)累加各無(wú)人機(jī)完成任務(wù)的路程獲得個(gè)體適應(yīng)度值。對(duì)于彈藥數(shù)量大于1的模型，存在單無(wú)人機(jī)對(duì)多個(gè)目標(biāo)進(jìn)行攻擊的情況，在此情況下計(jì)算適應(yīng)度時(shí)，需要選擇該無(wú)人機(jī)攻擊的先后順序，即需要通過(guò)比較不同情況的適應(yīng)度高低，選擇較低的方案。

4 仿真分析

仿真環(huán)境為CPU2.50GHz四核，內(nèi)存8 GB，Matlab R2018b。假設(shè)目標(biāo)數(shù)量8個(gè)；執(zhí)行任務(wù)的無(wú)人機(jī)數(shù)量為5架；彈藥約束為2發(fā)；迭代粒子數(shù)為100；迭代次數(shù)N1=350，N2=150；最小時(shí)間間隔Δtmin=0.25 s，最大時(shí)間間隔Δtmax=1 s。

針對(duì)多目標(biāo)執(zhí)行攻擊任務(wù)，隨機(jī)生成目標(biāo)及無(wú)人機(jī)位置,相同位置下，將離散鴿群算法與遍歷算法及基于Sigmoid函數(shù)慣性權(quán)重自適應(yīng)調(diào)整的粒子群優(yōu)化算法[13-14]對(duì)比。在目標(biāo)數(shù)量較少的情況下，3種算法的分配結(jié)果一致。遍歷算法的運(yùn)行時(shí)間為27.30 s,粒子群算法的運(yùn)行時(shí)間為7.13 s，離散鴿群算法的運(yùn)行時(shí)間為6.87 s。任務(wù)分配結(jié)果如圖6所示。

目標(biāo)數(shù)量增加到16個(gè)，執(zhí)行任務(wù)的無(wú)人機(jī)數(shù)量增加到10架，其他條件無(wú)變化時(shí)，采用粒子群算法與離散鴿群算法的任務(wù)分配結(jié)果如圖7所示。

在目標(biāo)較多的情況下，粒子群算法求解的總路程最小距離為80.75 km，運(yùn)行時(shí)間為13.74 s；離散鴿群算法求解的總路程最小距離為75.01 km，運(yùn)行時(shí)間為11.58 s。可以看出，隨著目標(biāo)數(shù)量增多，離散鴿群算法在尋優(yōu)能力及收斂速度方面有了一定程度的提高。

針對(duì)多目標(biāo)多任務(wù)的情況，初始最優(yōu)分配與離散鴿群算法分配結(jié)果如圖8所示。

多目標(biāo)多任務(wù)的最優(yōu)分配方案如圖9所示。

在多目標(biāo)多任務(wù)的情況下，初始最優(yōu)分配方案的總路程最小距離為352.58 km，運(yùn)行時(shí)間為47.56 s；離散鴿群算法求解的總路程最小距離為162.97 km米，運(yùn)行時(shí)間為23.34 s。從圖8及圖9可以看出，針對(duì)復(fù)雜度很高的多目標(biāo)多任務(wù)問(wèn)題模型，離散鴿群算法可以快速求出一個(gè)較優(yōu)解。不同任務(wù)類(lèi)型的無(wú)人機(jī)方案分配序列大致相同，這符合實(shí)際情況的判斷(不考慮最小時(shí)間約束和彈藥約束差異的情況下，同一個(gè)目標(biāo)的兩個(gè)任務(wù)必然由同一個(gè)無(wú)人機(jī)執(zhí)行完成)。

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

本文在對(duì)復(fù)雜約束條件進(jìn)行預(yù)處理的基礎(chǔ)上，使用改進(jìn)后的離散鴿群算法對(duì)無(wú)人機(jī)的任務(wù)分配問(wèn)題進(jìn)行求解。仿真結(jié)果表明，改進(jìn)后的離散鴿群算法具有較優(yōu)越的全局尋優(yōu)能力，在收斂速度方面要優(yōu)于粒子群算法，大大優(yōu)于遍歷算法，同時(shí)在處理多目標(biāo)任務(wù)的高復(fù)雜度問(wèn)題上也有非常好的表現(xiàn)。

但是對(duì)于多約束問(wèn)題，隨著約束的增加，利用隨機(jī)結(jié)果修正迭代的鴿群算法效率會(huì)大大降低，大量隨機(jī)結(jié)果不符合約束成為無(wú)效解，極不利于算法的快速收斂，此時(shí)需要對(duì)每次迭代的數(shù)據(jù)進(jìn)行預(yù)處理，但是多約束問(wèn)題的約束解耦也存在較大難度，在實(shí)際問(wèn)題中的應(yīng)用還有待進(jìn)一步研究。