基于粒子群算法的多無人機(jī)任務(wù)分配

李士波

摘要：多無人作戰(zhàn)飛機(jī)任務(wù)分配是無人機(jī)協(xié)同控制的一項關(guān)鍵技術(shù)。綜合無人機(jī)后續(xù)攻擊任務(wù)和影響無人機(jī)作戰(zhàn)效能評估的各種因素，按照分階段分配方法建立了多UCAV任務(wù)分配模型，并使用粒子群算法對建立的任務(wù)分配模型進(jìn)行求解，將每個粒子的位置使用兩個多維向量表示，兩個向量分別采用兩種不同方式同時進(jìn)化。該方法解決了分配模型復(fù)雜性帶來的分配難題，取得了良好的分配效果。

關(guān)鍵詞：任務(wù)分配；協(xié)同控制；無人作戰(zhàn)飛機(jī)；粒子群優(yōu)化

DOI：10.11907/rjdk.173133

中圖分類號：TP319

文獻(xiàn)標(biāo)識碼：A文章編號：1672-7800（2018）007-0193-03

Abstract：Multi-UCAVmissionallocationisthekeytechniqueforcoordinatecontrol.Consideringtheconsequentattackmissionandthemainfactorsthataffectcombatefficiencyassessment，themissionallocationmodelthatbasedondifferentstagesisestablished.Particleswarmoptimizationalgorithmisproposedtosolvetheproblem，eachparticlespositionisexpressedintwomulti-dimensionvectorsandthevectorsevolveindifferentmannerssynchronously，theevolvevalueisusedincostevaluationsubsequently.Thismethodhassolvedtheallocationproblemthatbroughtaboutthecomplexityoftheallocationmodelandreceivedgoodallocationresults.

KeyWords：missionallocation；coordinatecontrol；unmannedcombataerialvehicle；particleswarmoptimization（PSO）

0引言

無人作戰(zhàn)飛機(jī)（UnmannedCombatAerialVehicles，UCAV）從事的任務(wù)具有很大的危險性和復(fù)雜性，因此通常采用多架無人機(jī)共同執(zhí)行任務(wù)的策略[1-3]。在多架無人機(jī)共同執(zhí)行任務(wù)過程中，多UCAV任務(wù)規(guī)劃技術(shù)是實現(xiàn)多無人機(jī)協(xié)同控制的關(guān)鍵技術(shù)[4-6]。因此，多UCAV任務(wù)分配技術(shù)研究尤其重要。

多無人機(jī)任務(wù)分配問題是一個多目標(biāo)組合優(yōu)化問題，即通過一定的分配策略給無人機(jī)分配不同的任務(wù)。分配原則是在保護(hù)無人機(jī)的前提下，增大對目標(biāo)的殺傷概率，避免重復(fù)攻擊和遺漏。

多UCAV任務(wù)分配問題是研究熱點[7-9]，學(xué)者們先后提出了匈牙利算法、線性規(guī)劃法、禁忌搜索方法、市場交易模型等方法，這些方法在分配規(guī)模較大時會導(dǎo)致求解困難，并且往往未能充分考慮影響無人機(jī)作戰(zhàn)效能的各種因素和后續(xù)攻擊任務(wù)，很難適應(yīng)動態(tài)復(fù)雜環(huán)境下無人機(jī)任務(wù)分配需求。

本文提出按階段分配的方法建立多UCAV任務(wù)分配模型，在建模過程中充分考慮影響無人機(jī)作戰(zhàn)效能評估的各種因素，并提出使用粒子群算法對建立的復(fù)雜任務(wù)分配模型進(jìn)行求解。該分配方法對無人機(jī)數(shù)目和攻擊目標(biāo)數(shù)目均沒有限制，無人機(jī)可先后對多個目標(biāo)進(jìn)行攻擊，在分配過程中并不簡單地要求每一架無人機(jī)都執(zhí)行攻擊任務(wù)，更好地反映了任務(wù)分配的實際情況和要求。

1多UCAV任務(wù)分配模型建立

在多UCAV任務(wù)分配問題中，每架無人機(jī)可賦予攻擊多個目標(biāo)，因此可將多無人機(jī)任務(wù)分配過程劃分為多個階段，如圖1所示。在每個階段中，選擇一架無人機(jī)去攻擊一個目標(biāo)，在每個分配階段不僅要考慮選擇無人機(jī)攻擊目標(biāo)，還要考慮選擇執(zhí)行攻擊任務(wù)的無人機(jī)。

無人機(jī)任務(wù)分配要考慮的因素包括執(zhí)行攻擊任務(wù)的次序、無人機(jī)對目標(biāo)殺傷的概率、無人機(jī)對抗威脅的能力（生存概率）、攻擊路徑最短等。執(zhí)行攻擊任務(wù)的次序指在攻擊目標(biāo)確定后，為每架無人機(jī)首先確定攻擊哪一個目標(biāo)，之后確定要攻擊的第二目標(biāo)，依次類推，直至所有攻擊目標(biāo)均被確定。任務(wù)分配目標(biāo)是使無人機(jī)對目標(biāo)的殺傷概率達(dá)到最大而自身的損失最低，并盡可能地使所有無人機(jī)攻擊路徑總和最短[10-11]。

式（3）表示在每個階段中只有一架無人機(jī)從事攻擊任務(wù)，并只對一個目標(biāo)發(fā)起攻擊。式（4）表示無人機(jī)攻擊的目標(biāo)數(shù)目最多不能超過其自身能力的限制。

2粒子群算法

粒子群算法是Kennedy和Eberhart[12-13]于1995年提出的一種優(yōu)化算法，該算法被證明在優(yōu)化問題方面具有很大潛力。與傳統(tǒng)算法相比，PSO算法有一定的智能性，具有適用范圍廣、搜索能力強(qiáng)、不易陷入局部最優(yōu)等優(yōu)點，在路徑規(guī)劃領(lǐng)域效果非常好[14]。

粒子群算法本質(zhì)是一種基于群體和適應(yīng)度的優(yōu)化算法[15-16]。在求解優(yōu)化問題時，每個粒子代表問題的一個潛在解。粒子群算法使用適應(yīng)度函數(shù)評估粒子優(yōu)劣，適應(yīng)度函數(shù)的大小由粒子的具體位置坐標(biāo)決定。每個粒子記憶、追隨當(dāng)前的最優(yōu)粒子，在解空間中搜索。每次迭代過程不完全隨機(jī)，如果找到較優(yōu)解，將會以此為依據(jù)尋找下一個解。

每個粒子用3個指標(biāo)表征：位置、速度、適應(yīng)度。在進(jìn)化前，粒子的初始位置和速度根據(jù)問題限制在一定區(qū)間內(nèi)任意取值。粒子在每次迭代過程中需要記憶更新兩個極值。第一個極值是粒子自身歷史上的最優(yōu)位置，另一個極值是整個種群目前的最優(yōu)解。所有粒子通過這兩個極值修正粒子自身的位置，對下一步行為進(jìn)行調(diào)節(jié)，使之迅速向最優(yōu)值方向收斂。每個粒子在多維空間中不斷改變位置，直到一個相對穩(wěn)定的位置被找到，或者到達(dá)設(shè)定的進(jìn)化次數(shù)限制。所有粒子按照下式演化：

Rand1（）函數(shù)和Rand2（）函數(shù)在[0，1]之間產(chǎn)生隨機(jī)數(shù)。C1和C2是一個正常數(shù)，作為權(quán)重因子。權(quán)值ω用于控制粒子以前的速度對現(xiàn)在粒子速度的影響，在一定程度上，該參數(shù)平衡全局和局部粒子搜索能力。

用Vpbest表示粒子過去經(jīng)歷的所有位置中的最好位置時產(chǎn)生的速度矢量，用Vgbest表示在所有粒子中經(jīng)歷的最好位置所產(chǎn)生的速度矢量，繪制粒子自身位置變化原理如圖2所示。

3任務(wù)分配問題粒子群算法

針對復(fù)雜任務(wù)分配模型的粒子群方法需要構(gòu)造一個2Nt維空間，每個粒子都包含兩個Nt維向量，分別定義為Target和Vehicle向量。Target向量對應(yīng)于在不同階段所要攻擊的目標(biāo)，Vehicle向量則對應(yīng)于不同階段攻擊時所使用的無人機(jī)。例如使用3架無人機(jī)去打擊5個目標(biāo)，則某個粒子的位置向量如表1所示。

攻擊過程劃分為5個階段：①序號為3的無人機(jī)攻擊目標(biāo)2；②序號為1的無人機(jī)攻擊目標(biāo)4；③序號為2的無人機(jī)攻擊目標(biāo)3；④序號為3的無人機(jī)攻擊目標(biāo)1；⑤序號為1的無人機(jī)攻擊目標(biāo)5。要保證所有目標(biāo)均分配給一架無人機(jī)攻擊，無人機(jī)可使用多次但不能超過其最大攻擊次數(shù)。

在粒子群進(jìn)化中，Target向量和Vehicle向量采用兩種不同的方式同時進(jìn)化。由于Target向量代表不同階段要攻擊的目標(biāo)，每個目標(biāo)只能攻擊一次，因此Target向量定義為有序整數(shù)數(shù)列：

其進(jìn)化可通過離散PSO算法進(jìn)行。Vehicle向量對應(yīng)于不同階段攻擊時使用的無人機(jī)，將其定義為序列Y=（u1，u2…uNv），ui∈U。

Vehicle向量與Target向量的區(qū)別在于Vehicle向量允許重復(fù)，并且有最大攻擊目標(biāo)數(shù)的限制。因此，Vehicle向量的進(jìn)化采用標(biāo)準(zhǔn)PSO算法變形，實現(xiàn)方法及過程如下：

（1）每個粒子的位置中Vehicle向量的每一維隨機(jī)取1-Nv（目標(biāo)數(shù)）之間的整數(shù)，其中1-Nv代表無人機(jī)序號。

（2）為了保證滿足約束條件（4），考察生成的序列，若Vehicle向量中某個無人機(jī)的序號出現(xiàn)次數(shù)超過無人機(jī)最大攻擊的目標(biāo)數(shù)目，則重新生成該向量，直到滿足約束條件為止。

（3）與Vehicle向量相對應(yīng)的速度向量V2為-（Nv-1）～（Nv-1）之間任意值。

（4）結(jié)合Target向量，按照代價評估函數(shù)（2）計算個體歷史最優(yōu)解和群體全局最優(yōu)解。

（5）按照速度更新公式和位置更新公式計算Y和V2，對Y取整，當(dāng)Y和V2超過邊界限制時按邊界取值。若更新后某個粒子的位置Y不滿足約束條件（4），則恢復(fù)更新前的原值。

（6）重復(fù)執(zhí)行步驟（4）和步驟（5），直到滿足終止條件或達(dá)到最大迭代次數(shù)。

4任務(wù)分配問題仿真實現(xiàn)

例：若使用3架無人機(jī)去攻擊5個目標(biāo)，無人機(jī)當(dāng)前位置和目標(biāo)位置已知，如圖3所示。

其中□代表無人機(jī)，◇代表目標(biāo)，無人機(jī)攻擊每個目標(biāo)的殺傷概率、生存概率以及目標(biāo)價值如表2、表3所示，最大攻擊目標(biāo)數(shù)目Nmax為3。

按照式（2）給出的任務(wù)分配模型進(jìn)行建模，將模型中的各參數(shù)分別取值為Nt=Ns=5，Nu=3，加權(quán)系數(shù)w1=w2=w3=1/5，即將各個子目標(biāo)賦予相同的重要程度。分配過程使用PSO算法，使分配代價按照評估函數(shù)計算達(dá)到最大值。

5結(jié)語

本文采用分階段分配方法建立無人機(jī)任務(wù)分配模型，該模型充分考慮了無人機(jī)對目標(biāo)的殺傷概率、目標(biāo)對抗威脅能力和攻擊路徑長度等重要戰(zhàn)術(shù)指標(biāo)，并考慮了無人機(jī)對后續(xù)目標(biāo)的攻擊任務(wù)。建立的復(fù)雜任務(wù)分配模型使用粒子群算法求解，將每個粒子的位置使用兩個多維向量表示，兩個向量采用兩種不同方式同時進(jìn)化。仿真結(jié)果證明了該方法的可行性，本文提出的建模方法和分配算法可直接應(yīng)用到多無人機(jī)自主控制體系中。

參考文獻(xiàn)：

[1]劉重，高曉光，符小衛(wèi)，等.未知環(huán)境下異構(gòu)多無人機(jī)協(xié)同搜索打擊中的聯(lián)盟組建[J].兵工學(xué)報，2015（12）：2284-2297.

[2]龍濤，沈林成，朱華勇.面向協(xié)同任務(wù)的多UCAV分布式任務(wù)分配與協(xié)調(diào)技術(shù)[J].自動化學(xué)報，2007（7）：731-737.

[3]曹文靜，徐勝紅.多無人機(jī)協(xié)同方法研究[J].飛航導(dǎo)彈，2007（1）：44-48.

[4]肖作林，田鴻堂，秦楓.多UCAV協(xié)同任務(wù)規(guī)劃技術(shù)研究[J].戰(zhàn)術(shù)導(dǎo)彈技術(shù)，2013（6）：53-57.

[5]張紅，盧廣山，朱榮剛.無人作戰(zhàn)飛機(jī)任務(wù)系統(tǒng)技術(shù)研究[J].電光與控制，2006（1）：55-59.

[6]邸斌，周銳，丁全心.多無人機(jī)分布式協(xié)同異構(gòu)任務(wù)分配[J].控制與決策，2013（2）：274-278.

[7]閔桂龍，端木京順，張冰，等.軍事后勤中的多目標(biāo)無人機(jī)任務(wù)規(guī)劃[J].計算機(jī)仿真，2016（3）：85-89.

[8]TAKENOT，TSUJIMURAY，YAMAZAKIG.Asingle-phasemethodbasedonevolutioncalculationforvehicleroutingproblem[C].ConferenceofComputationalIntelligenceandMultimediaApplications，2001：103-107.

[9]UCHIMURAK，SAKAGUCHIH，NAKASHIMAT.Geneticalgorithmsforvehicleroutingproblemindeliverysystem[C].Yokohama：VehicleNavigationandInformationSystemsConference，1994.

[10]TANK，LEEL，ZHUQ，etal.Heuristicmethodsforvehicleroutingproblemwithtimewindows[J].ArtificialIntelligenceinEngineering，2001，15（3）：281-295.

[11]葉媛媛，閔春平，朱華勇，等基于整數(shù)規(guī)劃的多任務(wù)分配問題研究[J].信息與控制，2005，34（5）：548-552.

[12]EBERHARTRC，KENNEDYJ.ANewOptimizerusingparticleswarmtheory[C].Proceedingofthe6thInternationalSymposiumMicroMachineandHumanScience，1995：39-43.

[13]KENNEDYJ，EBERHARTRC.Particleswarmoptimization[C].ProceedingsofIEEEInternationalConferenceonNeutralNetwork，1995：1942-1948.

[14]張建南，劉以安，王剛.基于優(yōu)化粒子群算法的無人機(jī)航路規(guī)劃[J].傳感器與微系統(tǒng)，2017（3）：1-4.

[15]吳曉軍，楊戰(zhàn)中，趙明.均勻搜索粒子群算法[J].電子學(xué)報，2011（6）：1261-1266.

[16]王東風(fēng)，孟麗，趙文杰.基于自適應(yīng)搜索中心的骨干粒子群算法[J].計算機(jī)學(xué)報，2016（12）：2652-2667.

（責(zé)任編輯：杜能鋼）