周同樂，陳 謀，韓增亮，王 勤

(南京航空航天大學(xué)自動(dòng)化學(xué)院，南京 210016)

0 引言

在航空航天領(lǐng)域，無人機(jī)(Unmanned Aerial Ve-hicle，UAV)是近年來最有前途和挑戰(zhàn)性的軍事裝備之一。無人機(jī)具有造價(jià)低廉、使用方便、隱蔽性好、作戰(zhàn)范圍廣、能夠避免人員傷亡的特點(diǎn)，在未來空戰(zhàn)中的地位與作用不斷提升，受到了各大軍事強(qiáng)國的廣泛關(guān)注。

為了提高作戰(zhàn)效率，提升無人作戰(zhàn)系統(tǒng)對敵殺傷概率，多無人機(jī)協(xié)同作戰(zhàn)已成為新的發(fā)展趨勢。相較于單機(jī)作戰(zhàn)，多機(jī)協(xié)同作戰(zhàn)的探測范圍更加廣泛、干擾范圍更加廣闊，且殺傷能力更加強(qiáng)大。研究無人機(jī)對敵目標(biāo)的任務(wù)分配，對有效地毀傷敵方目標(biāo)，保障我方無人機(jī)安全，充分發(fā)揮無人作戰(zhàn)飛機(jī)的作戰(zhàn)效能，降低戰(zhàn)爭開銷具有重要的軍事意義。

無人機(jī)協(xié)同任務(wù)分配在現(xiàn)代信息化戰(zhàn)爭中發(fā)揮著極為重要的作用，其相關(guān)技術(shù)得到了國內(nèi)外學(xué)者的廣泛關(guān)注和研究。對于雙機(jī)追逃問題，多采用微分對策和矩陣對策法，文獻(xiàn)[6]將微分對策與機(jī)器博弈相結(jié)合，基于機(jī)器博弈中的變值思想，改進(jìn)了傳統(tǒng)的單純以角度最優(yōu)作為代價(jià)函數(shù)的微分對策模型。文獻(xiàn)[7]研究了基于博弈論的無人機(jī)戰(zhàn)場攻防決策算法，通過零和博弈計(jì)算得到無人作戰(zhàn)飛機(jī)應(yīng)對策略集合。為了有效處理戰(zhàn)場信息的不確定性，貝葉斯網(wǎng)絡(luò)經(jīng)常用于無人機(jī)的任務(wù)分配及其評估技術(shù)研究。動(dòng)態(tài)貝葉斯網(wǎng)絡(luò)基于先驗(yàn)知識進(jìn)行推理和學(xué)習(xí)，能夠有效地處理空戰(zhàn)環(huán)境中的不確定性。文獻(xiàn)[10]對無人空戰(zhàn)整個(gè)過程進(jìn)行分析，基于這些態(tài)勢因素建立無人作戰(zhàn)飛機(jī)任務(wù)分配模糊貝葉斯網(wǎng)絡(luò)，實(shí)現(xiàn)無人機(jī)任務(wù)分配。

除上述方法之外，針對多無人機(jī)協(xié)同多目標(biāo)任務(wù)分配問題，啟發(fā)式搜索算法具有較好的魯棒性、靈活性和分布性，得到了國內(nèi)外學(xué)者的關(guān)注與研究。文獻(xiàn)[12]分析了無人作戰(zhàn)飛機(jī)攻擊排序?qū)θ蝿?wù)總收益和代價(jià)的影響，運(yùn)用遺傳算法(Genetic Algorithm，GA)求解動(dòng)態(tài)環(huán)境下多無人機(jī)協(xié)同任務(wù)分配問題。為了克服粒子群(Particle Swarm Optimization，PSO)算法的不足，避免陷入局部最優(yōu)，文獻(xiàn)[13]提出了基于量子粒子群算法實(shí)現(xiàn)多機(jī)協(xié)同任務(wù)分配。此外，蜂群算法和狼群(Wolf Pack Search，WPS)算法等啟發(fā)式全局智能優(yōu)化算法也在解決無人機(jī)任務(wù)分配問題上得到了廣泛應(yīng)用。WPS算法作為一種新型啟發(fā)式全局智能優(yōu)化算法，基于自然界中狼群的活動(dòng)行為在搜索空間內(nèi)進(jìn)行尋優(yōu)。自然界中，狼群組織嚴(yán)密，等級森嚴(yán)，分工明確，一般情況下分為頭狼、探狼和猛狼三種等級，通過每匹狼各自履行自己的職責(zé)進(jìn)行團(tuán)結(jié)協(xié)作。

狼群算法相較于粒子群算法、遺傳算法等啟發(fā)式算法，求解精度更高，收斂速度更快。文獻(xiàn)[17]提出了基于領(lǐng)導(dǎo)者策略的狼群算法，在尋優(yōu)過程中由領(lǐng)導(dǎo)者指引搜尋全局最優(yōu)解，通過實(shí)驗(yàn)證明了基于領(lǐng)導(dǎo)者策略的狼群算法具有更高的搜索效率。文獻(xiàn)[18]將狼群置于文化算法種群空間，并依據(jù)頭狼位置建立信仰空間，仿真實(shí)驗(yàn)表明該算法收斂速度與尋優(yōu)精度均得到加強(qiáng)。為了保持WPS算法的隨機(jī)性和多樣性，文獻(xiàn)[19]增加了隨機(jī)生存更新規(guī)則，并將算法應(yīng)用于求解PID控制問題。文獻(xiàn)[20]在傳統(tǒng)WPS算法的基礎(chǔ)上，融入非線性單純形法，增強(qiáng)局部搜索能力。文獻(xiàn)[21]基于改進(jìn)狼群算法解決無人機(jī)路徑規(guī)劃問題，該方法由頭狼利用映射、擴(kuò)展和收縮產(chǎn)生新的航路點(diǎn)，不斷向最優(yōu)航路點(diǎn)靠近，取得較好的優(yōu)化效果。傳統(tǒng)改進(jìn)群智能算法的措施雖然能夠在特定問題中發(fā)揮一定的作用，但在多無人機(jī)協(xié)同多目標(biāo)任務(wù)分配問題中依然存在著魯棒性差、泛化能力弱以及易陷入局部最優(yōu)等問題。

鑒于狼群算法的優(yōu)越性，本文提出了一種基于多策略規(guī)則的新型狼群算法，主要?jiǎng)?chuàng)新點(diǎn)如下：

1)根據(jù)狼群的不同分工以及搜索屬性，建立了基于自主游走機(jī)制的頭狼產(chǎn)生規(guī)則；

2)設(shè)計(jì)了基于多策略知識庫的探狼游走機(jī)制和基于自適應(yīng)動(dòng)態(tài)調(diào)整步長的猛狼奔襲和圍攻方式，取代了傳統(tǒng)狼群算法單一的搜索機(jī)制。

從而對狼群算法的隨機(jī)性進(jìn)行智能化約束與控制，保證算法能夠高效智能地解決多無人機(jī)協(xié)同多目標(biāo)任務(wù)分配問題。

1 問題描述

本文研究了架無人機(jī)對個(gè)敵方目標(biāo)場景下的任務(wù)分配問題。分配原理如圖1所示。

圖1 多無人機(jī)協(xié)同多目標(biāo)任務(wù)分配原理圖Fig.1 Schematic diagram of multi-UAV cooperative multiple targets task assignment

當(dāng)確定無人機(jī)集合和目標(biāo)集合后，在空戰(zhàn)環(huán)境的影響下，分析執(zhí)行各個(gè)任務(wù)的收益和代價(jià)，形成無人機(jī)任務(wù)分配方案，確定每架無人機(jī)具體的任務(wù)集合。

首先，定義決策變量為

(1)

在此基礎(chǔ)上，針對實(shí)際空戰(zhàn)中戰(zhàn)場環(huán)境以及無人機(jī)性能，結(jié)合任務(wù)目標(biāo)，建立多無人機(jī)協(xié)同多目標(biāo)任務(wù)分配目標(biāo)函數(shù)。任務(wù)分配目標(biāo)函數(shù)主要考慮以下幾個(gè)方面：

1)空戰(zhàn)態(tài)勢。即環(huán)境中目標(biāo)與無人機(jī)的相對態(tài)勢因素，空戰(zhàn)態(tài)勢函數(shù)設(shè)計(jì)為

=++

(2)

其中，為角度優(yōu)勢；為距離優(yōu)勢；為能量優(yōu)勢；、、為權(quán)值因子。

2)攻擊代價(jià)。攻擊代價(jià)包括威脅代價(jià)、航程代價(jià)和目標(biāo)意圖代價(jià)。

威脅代價(jià)，指無人機(jī)攻擊任務(wù)目標(biāo)時(shí)，可能受到對應(yīng)目標(biāo)的攻擊被毀傷而產(chǎn)生的代價(jià)，無人機(jī)攻擊目標(biāo)的威脅代價(jià)1具體設(shè)計(jì)為

(3)

式中：為與目標(biāo)最近的威脅源的威脅程度；為與作戰(zhàn)目標(biāo)最近的威脅源之間的距離；為無人機(jī)被目標(biāo)擊毀的概率。

無人機(jī)攻擊目標(biāo)的航程代價(jià)2具體設(shè)計(jì)為

(4)

式中：為無人機(jī)與目標(biāo)的距離；為無人機(jī)集合與目標(biāo)的最大距離。

目標(biāo)意圖代價(jià)，目標(biāo)對無人機(jī)的意圖越危險(xiǎn)，其對無人機(jī)的意圖代價(jià)越大。具體如表1所示。

表1 目標(biāo)意圖代價(jià)表

3)攻擊收益。攻擊收益主要由無人機(jī)對應(yīng)目標(biāo)的價(jià)值決定，無人機(jī)攻擊目標(biāo)的攻擊收益為

(5)

式中：為無人機(jī)對目標(biāo)的毀傷概率；為目標(biāo)的戰(zhàn)略價(jià)值，由目標(biāo)本身的類型及戰(zhàn)略重要程度決定。

4)無人機(jī)性能。無人機(jī)相對于目標(biāo)的性能優(yōu)勢設(shè)計(jì)為

式中：和分別為無人機(jī)和目標(biāo)的性能參數(shù)，與無人機(jī)運(yùn)動(dòng)能力、通信能力、載荷能力及攻擊范圍相關(guān)。

綜上所述，充分考慮空戰(zhàn)環(huán)境態(tài)勢、攻擊收益代價(jià)及無人機(jī)性能，建立如下目標(biāo)函數(shù)

=

(6)

式中：為無人機(jī)完成所有任務(wù)的時(shí)間。

約束條件為

(7)

(8)

max{}≤

(9)

約束條件(7)保證所有敵方目標(biāo)均會(huì)被攻擊到；約束條件(8)為無人機(jī)使能約束，即分配給無人機(jī)的任務(wù)總量不應(yīng)超過其載彈量；約束條件(9)為時(shí)間約束，即無人機(jī)需在指定時(shí)間內(nèi)完成所有任務(wù)，其中為無人機(jī)的飛行速度。

2 WPS算法搜索策略

對多無人機(jī)協(xié)同多目標(biāo)任務(wù)分配模型的求解可以抽象成對目標(biāo)函數(shù)(6)及約束條件(7)、(8)與(9)的優(yōu)化問題。本文基于多策略規(guī)則的新型狼群算法，通過多種規(guī)則提升了WPS算法的搜索效率，以獲得最終的任務(wù)分配結(jié)果。

狼群行為示意圖如圖2所示。

圖2 狼群行為示意圖Fig.2 Schematic diagram of wolf pack behaviors

頭狼具有領(lǐng)導(dǎo)作用，需要指揮狼群的各個(gè)成員盡快捕捉到優(yōu)質(zhì)的獵物；探狼負(fù)責(zé)打探游獵，通過感知獵物氣味判定與獵物的距離，并把獵物信息實(shí)時(shí)匯報(bào)給頭狼；狼群中剩下的所有狼稱為猛狼，主要負(fù)責(zé)圍攻獵物，當(dāng)頭狼接收到探狼發(fā)送的獵物信息后，召喚猛狼對獵物發(fā)起圍攻。當(dāng)狼群捕獲到獵物后，將根據(jù)發(fā)現(xiàn)并抓捕獵物的順序?qū)ΛC物進(jìn)行分配，能力越強(qiáng)的狼將優(yōu)先分配到充足食物而能夠繼續(xù)保持強(qiáng)健體魄，少數(shù)弱小且貢獻(xiàn)小的狼則會(huì)因?yàn)槭澄锞o缺而被自然淘汰，保證了狼群的優(yōu)質(zhì)性。

根據(jù)狼群的這些特征，WPS算法將尋優(yōu)過程與狼群捕食獵物過程相對應(yīng)，通過游走、召喚、圍攻三種智能行為對目標(biāo)進(jìn)行尋優(yōu)。為了提高WPS算法的搜索效率及避免陷入局部最優(yōu)，本文在以下幾個(gè)方面進(jìn)行了改進(jìn)。

2.1 基于自主游走機(jī)制的頭狼產(chǎn)生規(guī)則

頭狼即具有最佳目標(biāo)函數(shù)值的人工狼。在迭代過程中，若出現(xiàn)具有更高目標(biāo)函數(shù)值的人工狼，則需要對頭狼位置進(jìn)行更新。

為了加快狼群算法的收斂速度，在圍攻行為結(jié)束之后，頭狼進(jìn)行自主游走。即對頭狼附近區(qū)域進(jìn)行進(jìn)一步開拓與搜索，保證頭狼的優(yōu)越性。

2.2 基于多策略的探狼游走規(guī)則

探狼游走是狼群算法中搜索行為的核心，為了提高狼群算法的解算效率與優(yōu)化質(zhì)量，設(shè)計(jì)了一個(gè)包含多策略游走規(guī)則的專家知識庫，取代傳統(tǒng)狼群算法中的探狼隨機(jī)游走行為。多策略探狼游走規(guī)則示意圖如圖3所示。

圖3 多策略探狼游走規(guī)則示意圖Fig.3 Schematic diagram of multi-strategy search wolves scouting rules

基于個(gè)體知識的探狼游走規(guī)則

傳統(tǒng)的探狼游走規(guī)則是WPS算法最基本的搜索規(guī)則，能夠保證算法最基本的搜索能力。因此，為了維持新算法的基本搜索能力，仍保留原有的探狼游走規(guī)則。第個(gè)搜索空間內(nèi)探狼第個(gè)游走位置,為

,=,+rand(1,-1)·(,-,)

(10)

式中：,為第個(gè)探狼的位置，,∈{1,2,…，}且≠。

基于歷史知識的探狼游走規(guī)則

為了提高算法的收斂速率，探狼會(huì)優(yōu)先向記憶中的最佳位置進(jìn)行探索，具體形式為

(11)

基于信息交互的探狼游走規(guī)則

為了提高探狼的尋優(yōu)能力，與當(dāng)前局部最優(yōu)解進(jìn)行信息交互，具體形式為

(12)

式中：,為取值范圍[0,1]的隨機(jī)數(shù)；,為取值范圍[-1,1]的隨機(jī)數(shù)，且≠。

基于反向精英策略的探狼游走規(guī)則

為了避免WPS算法陷入局部最優(yōu)，一部分探狼向遠(yuǎn)離頭狼的位置對新的獵物進(jìn)行探索。

(13)

最終，探狼按式(14)更新自己的位置。

(14)

式中：為概率因子，依照均勻分布[0,1]隨機(jī)取值。

2.3 基于自適應(yīng)步長的猛狼奔襲和圍攻方式

頭狼發(fā)起召喚，吸引猛狼靠近，當(dāng)猛狼距離頭狼還有一定距離時(shí)，猛狼以較大奔襲步長向頭狼迅速靠近；當(dāng)猛狼逐漸靠近頭狼后，以較小步長在獵物附近進(jìn)行小范圍精細(xì)搜索。自適應(yīng)步長調(diào)整示意圖如圖4所示。

圖4 自適應(yīng)步長調(diào)整示意圖Fig.4 Schematic diagram of adaptive step length adjustment

隨著迭代次數(shù)值的增加，狼群搜索步長將基于線性變化進(jìn)行自適應(yīng)調(diào)整，具體形式為

(15)

3 基于多策略狼群算法的多無人機(jī)協(xié)同多目標(biāo)任務(wù)分配

在多無人機(jī)協(xié)同多目標(biāo)任務(wù)分配中，搜尋最優(yōu)解的過程即是為無人機(jī)搜尋最優(yōu)的任務(wù)目標(biāo)集合。因此，無人機(jī)序列編號以與目標(biāo)序列編號相對應(yīng)的方式來表示無人機(jī)的分配方案。

具體編碼方式如圖5所示。

圖5 多無人機(jī)協(xié)同多目標(biāo)任務(wù)分配編碼方式示意圖Fig.5 Schematic diagram of multi-UAV cooperative multiple targets task assignment coding scheme

圖5中，每一個(gè)雙向箭頭表示將對應(yīng)編號的目標(biāo)分配給相應(yīng)編號的無人機(jī)。

針對多無人機(jī)協(xié)同多目標(biāo)任務(wù)分配問題，分別定義人工狼距離、游走算子和召喚算子。

人工狼距離，人工狼與之間的距離定義為

(16)

式中：⊕表示異或操作。

游走算子(,)，設(shè)人工狼的位置為=(1,2,…,,…,)，根據(jù)探狼游走規(guī)則，取其中兩個(gè)互不相同的元素和，組成一個(gè)二維數(shù)組(,)，,∈{1,2,…,}且≠，執(zhí)行游走算子(,)操作,即隨機(jī)生成個(gè)二維數(shù)組，并按順序?qū)⑾鄳?yīng)位置編碼的數(shù)值進(jìn)行交換。

召喚算子(,,)，設(shè)人工狼的位置為=(1,2,…,,…,)，頭狼的位置為=(,,…,lead,…,lead)，召喚算子(,,)表示從中隨機(jī)選取長度的子序列替換中相同位置的編碼值，并對其他位置編碼值進(jìn)行調(diào)整,以保證所有編碼值僅出現(xiàn)一次。

基于狼群算法的多無人機(jī)協(xié)同多目標(biāo)任務(wù)分配具體步驟如下。

3.1 初始化

將狼群捕獵空間即任務(wù)分配方案的搜索空間抽象為×的歐式空間，其中為人工狼群初始化后的人工狼總數(shù)，為我方無人機(jī)序列與目標(biāo)無人機(jī)序列的編碼長度，以人工狼的位置=(1,2,…,,…,)表示任務(wù)分配方案，元素表示第個(gè)人工狼第位編碼的值，當(dāng)=時(shí)表示將目標(biāo)納入無人機(jī)的任務(wù)集合。人工狼通過目標(biāo)函數(shù)值調(diào)整位置，進(jìn)行尋優(yōu)，這里選用式(6)的目標(biāo)函數(shù)，即

(17)

選擇當(dāng)前具有最高目標(biāo)函數(shù)值的人工狼作為頭狼，頭狼位置記為。除頭狼外，最佳的匹人工狼視為探狼。計(jì)算頭狼位置的目標(biāo)函數(shù)值()。

3.2 探狼游走

3.3 頭狼召喚和猛狼奔襲與圍攻

3.4 優(yōu)勝劣汰狼群更新機(jī)制

狼群按照優(yōu)勝劣汰的更新機(jī)制進(jìn)行群體更新，從而保證狼群具有更高的質(zhì)量。具體實(shí)現(xiàn)為，每次狼群行動(dòng)后，淘汰一定數(shù)量目標(biāo)適應(yīng)度值較差的人工狼，并隨機(jī)生成相同數(shù)量的人工狼。

3.5 終止

判斷是否達(dá)到終止條件，若達(dá)到則輸出本次迭代頭狼的位置及對應(yīng)的目標(biāo)函數(shù)值()，否則繼續(xù)進(jìn)行搜索行為直至達(dá)到最大限定次數(shù)。

基于多策略狼群(Multi Strategy-WPS，MS-WPS)算法的多無人機(jī)協(xié)同多目標(biāo)任務(wù)分配方法流程圖如圖6所示。

圖6 基于多策略狼群算法的多無人機(jī)協(xié)同多目標(biāo)任務(wù)分配方法流程圖Fig.6 Flow diagram of multi-UAV cooperative multiple targets task assignment based on multi-strategy wolf pack method

4 仿真分析

為了驗(yàn)證所提算法的有效性，下面進(jìn)行仿真驗(yàn)證。首先設(shè)置狼群規(guī)模為50，算法最大迭代次數(shù)為=50，探狼最大游走步長=5，初始奔襲步長=3，頭狼游走步長=1，探狼比例因子=3，更新比例因子=005。

進(jìn)一步，本文選取了某一地區(qū)實(shí)際地形進(jìn)行仿真驗(yàn)證，場景中存在4個(gè)威脅，具體參數(shù)如表2所示。

表2 場景威脅信息

下面針對不同情況進(jìn)行分析。

1)4架無人機(jī)執(zhí)行8個(gè)任務(wù)情況，無人機(jī)與目標(biāo)的空間分布如圖7所示。

(a)

(b)圖7 場景1無人機(jī)與任務(wù)空間分布圖Fig.7 UAV and target spatial distribution map of scene 1

具體參數(shù)如表3所示。

該場景下分配結(jié)果如表4所示。

表3 場景1參數(shù)信息

表4 場景1多無人機(jī)協(xié)同多目標(biāo)任務(wù)分配結(jié)果

場景1下，由于目標(biāo)數(shù)量多于無人機(jī)數(shù)量，每架無人機(jī)需要執(zhí)行多個(gè)任務(wù)。

2)6架無人機(jī)執(zhí)行4個(gè)任務(wù)情況，無人機(jī)與目標(biāo)的空間分布如圖8所示。

(a)

(b)圖8 場景2無人機(jī)與任務(wù)空間分布圖Fig.8 UAV and target spatial distribution map of scene 2

具體參數(shù)如表5所示。

該場景下分配結(jié)果如表6所示。

場景2下，由于無人機(jī)數(shù)量多于任務(wù)目標(biāo)，需要、協(xié)同完成目標(biāo)，、協(xié)同完成目標(biāo)。

3)10架無人機(jī)執(zhí)行10個(gè)任務(wù)情況，無人機(jī)與目標(biāo)的空間分布如圖9所示。

表5 場景2參數(shù)信息

表6 場景2多無人機(jī)協(xié)同多目標(biāo)任務(wù)分配結(jié)果

(a)

(b)圖9 場景3無人機(jī)與任務(wù)空間分布圖Fig.9 UAV and target spatial distribution map of scene 3

具體參數(shù)如表7所示。

表7 場景3參數(shù)信息

該場景下分配結(jié)果如表8所示。

表8 場景3多無人機(jī)協(xié)同多目標(biāo)任務(wù)分配結(jié)果

為了進(jìn)一步分析本文提出算法的性能，將本文MS-WPS算法與PSO算法、蟻群(Ant Colony Opti-mization，ACO)算法、傳統(tǒng)WPS算法進(jìn)行比較，分別求解場景3多無人機(jī)協(xié)同多目標(biāo)任務(wù)分配結(jié)果，進(jìn)行50次仿真，統(tǒng)計(jì)每種算法運(yùn)行時(shí)間，結(jié)果如表9所示。

表9 不同算法性能比較

各個(gè)算法的收斂曲線如圖10所示。

圖10 迭代曲線圖Fig.10 Iterative graph

由表9和圖10可知，PSO、ACO、WPS和MS-WPS四種算法均能求出多無人機(jī)協(xié)同多目標(biāo)任務(wù)分配最優(yōu)解，MS-WPS相較于其他算法，在求解速度上具有明顯優(yōu)勢，通過多策略探狼游走和自適應(yīng)步長調(diào)整，能夠以更快速度收斂到最優(yōu)解。

5 結(jié)論

1)本文對多無人機(jī)協(xié)同多目標(biāo)任務(wù)分配問題進(jìn)行了研究，針對傳統(tǒng)狼群算法收斂速度慢、易陷入局部最優(yōu)等問題，提出了基于多策略狼群算法的多無人機(jī)協(xié)同多目標(biāo)任務(wù)分配方法。

2)通過分析狼群的不同分工及搜索屬性，本文建立了基于自主游走機(jī)制的頭狼產(chǎn)生規(guī)則、基于多策略知識庫的探狼游走機(jī)制和基于自適應(yīng)步長的猛狼奔襲和圍攻方式，使得狼群算法的隨機(jī)性得到智能化的約束與控制，保證算法的高效性和精確性。

3)由仿真結(jié)果可知，本文提出的方法在多無人機(jī)協(xié)同多目標(biāo)任務(wù)分配問題中是可行有效的。