梁國偉，王社偉，趙雪森

（空軍航空大學(xué)，長春 130022）

多無人機協(xié)同任務(wù)分配方法*

梁國偉，王社偉，趙雪森

（空軍航空大學(xué)，長春 130022）

任務(wù)分配是多UCAV協(xié)同控制的核心和有效保證，是一類復(fù)雜的多目標(biāo)優(yōu)化問題。針對一種擴展的混合整數(shù)線性規(guī)劃（MILP）任務(wù)分配模型，通過對模型特點的分析，提出一種基于相似度的遺傳退火算法解決該問題并進行仿真實驗，仿真結(jié)果表明該算法具有較強的收斂性和較好的多樣性，驗證了改進算法解決該問題模型的有效性。

無人作戰(zhàn)飛機，任務(wù)分配，協(xié)同控制，混合整數(shù)線性規(guī)劃模型

引言

無人作戰(zhàn)飛機（UCAV）是無人機和戰(zhàn)斗機的結(jié)合，是下一代戰(zhàn)斗機的發(fā)展方向［1］。UCAV能夠完成多種復(fù)雜的作戰(zhàn)任務(wù)，由于作戰(zhàn)任務(wù)的多重性和復(fù)雜性，常使用多架UCAV協(xié)同作戰(zhàn)。近年來，多機協(xié)同控制已經(jīng)成為無人機領(lǐng)域一個研究熱點，而任務(wù)分配是多無人機協(xié)同控制的保障和基礎(chǔ)。它是一個約束眾多而復(fù)雜的優(yōu)化問題［2-3］，其解空間隨任務(wù)總數(shù)的增加而呈指數(shù)級增加，使其成為一個多參數(shù)、多約束的NP問題。

傳統(tǒng)的方法如枚舉法，算法較為簡單，但問題規(guī)模比較大的時候，沒有很好的解決方法，下文提出一種基于相似度的遺傳退火算法，針對多UCAV任務(wù)分配問題的特點給予求解，最后進行了仿真驗證和分析。

1 多無人機協(xié)同控制任務(wù)分配模型

本文以基于混合整數(shù)線性規(guī)劃（MILP）任務(wù)分配模型［4-5］為基礎(chǔ)，針對多無人機協(xié)同控制的特點，綜合考慮多類復(fù)雜約束條件和多個優(yōu)化指標(biāo)，建立擴展的協(xié)同多任務(wù)分配模型。

1.1 問題描述

假設(shè)無人機編隊在一個二維空間執(zhí)行任務(wù)，無人機執(zhí)行任務(wù)前已預(yù)先獲知戰(zhàn)場地形以及存在于戰(zhàn)場中的一系列目標(biāo)位置。E為戰(zhàn)場環(huán)境；V={V1，V2，…，VNV

}為執(zhí)行任務(wù)的無人機集合，NV為無人機的數(shù)量；T={T1，T2，…，TNT}為待執(zhí)行任務(wù)對應(yīng)的目標(biāo)集合，NT為目標(biāo)數(shù)量；Mt={Mt1，Mt2，…，Mttype}為各目標(biāo)Ti上需要完成的任務(wù)類型集合，Ntype為任務(wù)類型數(shù)；考慮到未來UCAV作戰(zhàn)使用的發(fā)展趨勢，任務(wù)類型集合中包含3類任務(wù)，分別為偵察、攻擊和毀傷評估，即Mt={Classify，Attack，…，Verify}；由此可將任務(wù)集合表達為：

其中，Nm=NTNtype為任務(wù)總數(shù)量。P為UCAV編隊的執(zhí)行路線集合，編隊中的任一無人機Vi均分配一條任務(wù)執(zhí)行路線Pi，對任一時刻t，Vi的水平位置可表示為（xiV（t），yiV（t）），任務(wù)Mi的水平位置（xiM，yiM），有Pi={（xiV（0），yiV（0）），（x1M，y1M），…，（xmM，ymM）}其中（xiV（0），yiV（0））表示Vi的出發(fā)位置，Pi中的其他項表示Vi依次執(zhí)行任務(wù)的位置。

1.2 決策變量的設(shè)計

為建立直觀且易求解的數(shù)學(xué)模型，先定義二進制決策變量xki，j∈{0，1}，其值滿足：

1.3 協(xié)同多任務(wù)分配模型

模型假設(shè)無人機Vi執(zhí)行任務(wù)時的速度恒定為speedi。

（1）任務(wù)總飛行航程最小指標(biāo)f1

由于UCAV是在敵方空域和雷達監(jiān)測下執(zhí)行任務(wù)，則執(zhí)行任務(wù)的路程越長，UCAV損失的可能性越大，所消耗的燃油也越多，因此，縮短UCAV編隊執(zhí)行任務(wù)總航程可以降低UCAV受損的風(fēng)險，也可以減少燃油消耗，指標(biāo)表示如下：

（2）任務(wù)完成時間最短指標(biāo)f2

由于戰(zhàn)場環(huán)境瞬息萬變，如何在最短時間內(nèi)完成對目標(biāo)的有效打擊是決定一場戰(zhàn)爭勝負的關(guān)鍵因素，因此，要縮短任務(wù)執(zhí)行的時間，指標(biāo)表示如下：

（3）目標(biāo)價值收益最大指標(biāo)f3

不同的任務(wù)具有不同的收益價值，比如可以認為對敵導(dǎo)彈基地實施攻擊的效益將大于對其進行毀傷評估的效益。追求效益最大化一直是多機協(xié)同作戰(zhàn)必須考慮的一個關(guān)鍵，指標(biāo)表示如下：

綜上所述，協(xié)同多任務(wù)分配模型定義為：

根據(jù)協(xié)同任務(wù)分配約束條件，給出其數(shù)學(xué)描述如下：

（1）多機協(xié)同約束，表示一項任務(wù)只能由一架無人機執(zhí)行一次：

（2）表示只有一架無人機飛離該任務(wù)：

（3）確保每個目標(biāo)包含的任務(wù)都能被執(zhí)行：

（4）表示兩個相繼任務(wù)執(zhí)行的時間約束：

式中，tij-1表示無人機Vi執(zhí)行完任務(wù)Mj的前一項Mj-1時的時刻。Vi由任務(wù)Mj-1位置到Mj位置的飛行過程中（xi，j=1），在tij-1+ti，j之前不能執(zhí)行任務(wù)Mj。需要指出的是，無人機在一個任務(wù)上的執(zhí)行時刻等于其前續(xù)任務(wù)執(zhí)行時刻加上兩個任務(wù)之間的飛行時間，這里將等待執(zhí)行任務(wù)的時間歸入飛行時間之內(nèi)。

（5）表示時間窗約束:

（6）表示任務(wù)時序約束：

（7）表示任務(wù)類型能力約束：

其中，Mti，j為無人機Vi待執(zhí)行任務(wù)Mj的任務(wù)類型，MKind（Vi）為Vi所能執(zhí)行的任務(wù)類型。

（8）表示無人機的最大航程限制：

其中，Di無人機Vi的最大航程。

2 基于相似度的遺傳退火算法

由于遺傳算法的局部搜索能力較差，但把握搜索過程總體的能力較強；模擬退火算法具有較強的局部搜索能力，并能使搜索過程避免陷入局部最優(yōu)解。因此，將遺傳算法與模擬退火算法相結(jié)合，互相取長補短，則可能設(shè)計出性能優(yōu)良的新的全局搜索算法［6］，下面介紹算法的實現(xiàn)。

2.1 種群個體編碼

種群個體使用如下雙層整數(shù)編碼方式，假設(shè)2架UCAV攻擊3個目標(biāo)，每個目標(biāo)上都有3項任務(wù)需要執(zhí)行，分別是偵察、攻擊、毀傷評估任務(wù)：

此編碼方式是將種群中的個體表示為1個二維矩陣，矩陣的第1行表示執(zhí)行任務(wù)的無人機的序號，矩陣的第2行表示分配UCAVVi執(zhí)行目標(biāo)Tj的任務(wù)Mt，排列順序表示目標(biāo)被UCAV執(zhí)行的次序和任務(wù)的類型，例如目標(biāo)Tj第1次出現(xiàn)表示執(zhí)行的是偵察任務(wù)，第2次出現(xiàn)表示執(zhí)行的是攻擊任務(wù)，第3次出現(xiàn)表示執(zhí)行的是評估任務(wù)。

2.2 遺傳算子的設(shè)計

算法中主要使用了選擇、交叉、變異3種基本的遺傳算子，它們的具體設(shè)計如下：

（1）將部分精英集中的個體加入到種群POP 0中并進行選擇操作，可以提高種群的收斂速度。

（2）交叉模擬退火操作

由于交叉算子在搜索最優(yōu)解的進程中是一個破壞性同時也是產(chǎn)生新解的過程，因此，遺傳算法常常很快收斂到比較好的解，但是往往不能收斂到最優(yōu)解。而模擬退火算法是對解的周圍進行局部搜索，往往能收斂到最優(yōu)解。

本文考慮到個體必須滿足較多約束條件，雙點和多點交叉（均勻交叉）引起個體違反的約束條件的概率較大，因此，本文采用單點交叉算子。選擇兩個父代個體進行交叉操作得到兩個子代個體，比較父代和子代個體的適應(yīng)度值，若子代個體的適應(yīng)度值大于父代個體的適應(yīng)度值，則子代代替父代成為下一代個體；否則根據(jù)模擬退火中的Boltzmann概率選擇機制來選擇下一代個體，具體方法為：

產(chǎn)生一個（0，1）上均勻分布的隨機數(shù)δ，計算在給定當(dāng)前迭代點Xk和溫度Tk下接受試探點Yk的概率，即：

如果δ≤P，則令Yk代替Xk成為下一代進化個體，否則父代個體作為下一代個體。

（3）基于相似度的自適應(yīng)變異算子

由于本文編碼方式區(qū)別于傳統(tǒng)的二進制串編碼方式，因此，本文設(shè)計的變異算子必須充分考慮整數(shù)編碼特點，同時充分利用約束條件來提高變異效率，因此，設(shè)計的變異算子是在滿足小組約束條件的整數(shù)范圍內(nèi)隨機取一整數(shù)來取代原基因位的變量值。本文提出了一種基于相似度的自適應(yīng)變異算子。

定義1 任取兩個體u={u1，u2，…，un}和v={v1，v2，…，vn}，設(shè)個體適應(yīng)度分別為fu和fv，取兩個適當(dāng)小的正常數(shù)β1和β2，若有

成立，則稱兩個個體相似，式（15）表示個體結(jié)構(gòu)相似性的指標(biāo)，式（16）表示個體品質(zhì)相似性指標(biāo)。

圖1 算法流程圖

定義2 在規(guī)模為n的種群中，個體k的濃度ck表示為與k相似個體數(shù)m與n的比值，即：

定義3 基于相似度的自適應(yīng)變異概率［7］

η、θ為區(qū)間［0，1］內(nèi)可調(diào)參數(shù)，γ為濃度閾值，MaxFit為種群最大適應(yīng)度值，F(xiàn)it（k）為個體k的適應(yīng)度值。

2.3 外部精英集

由圖1可知，最初的精英集由初始群體中適應(yīng)度最高的個體填充，隨后由交叉模擬退火操作和變異操作產(chǎn)生的最優(yōu)個體對精英集進行更新，如果個體的數(shù)量超過檔案規(guī)模，則依據(jù)適應(yīng)度值大小對精英集進行修剪。在種群外設(shè)置一個精英集合用于保存種群進化每一步搜索到的非支配解。精英集合的使用將有效防止算法在搜索過程中由于隨機因素而丟失最優(yōu)解，并且能加快算法收斂速度。

2.4 基于相似度的遺傳退火算法算法的步驟（如圖1）

（1）初始化算法的參數(shù)：包括種群規(guī)模POP0、初始溫度T、迭代次數(shù)等。

（2）隨機產(chǎn)生POP0個雙層編碼的種群，每個個體對應(yīng)一種任務(wù)分配方案，即隨機產(chǎn)生POP0個初始解。

（3）按2.1節(jié)所示的方法進行解碼并計算各個個體的適應(yīng)度，將適應(yīng)度最高的個體存入精英集1中。

（4）將精英集中的部分個體加入到種群中，進行選擇操作得到種群POP1。

（5）對POP1進行交叉模擬退火操作得到種群POP2，將POP2中適應(yīng)度最高的個體存入精英集2中。

（6）對POP2進行基于相似度的自適應(yīng)變異操作得到種群POP3，將POP3中適應(yīng)度最高的個體存入精英集3中。

（7）更新精英集，如果個體數(shù)量超過檔案規(guī)模，則對精英集進行修剪。

（8）如果滿足終止條件，執(zhí)行步驟（9），否則，轉(zhuǎn)到步驟（3）。

（9）輸出任務(wù)分配方案。

2.5 算法性能分析

算法將模擬退火算法融入到遺傳算法的交叉算子當(dāng)中［8］，避免早熟現(xiàn)象的發(fā)生，提高了局部搜索能力；采用基于相似度的自適應(yīng)變異操作，克服了算法由于變異概率不變導(dǎo)致的求解過程長，解的多樣性差的缺陷；引入外部精英集，避免了最優(yōu)解的丟失。

3 基于相似度的遺傳退火算法在無人機任務(wù)分配的研究

3.1 適應(yīng)度函數(shù)的建立

3.1.1 罰函數(shù)的確定

通過以上的編碼并不能完全滿足約束條件，在出現(xiàn)如下幾種情況時，需要對適應(yīng)度函數(shù)施加一個懲罰項將帶約束問題轉(zhuǎn)變?yōu)闊o約束問題。需要施加懲罰的情況如下：

（1）超越無人機最大航程。

（2）不滿足時間窗約束。

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

通過上分析可以得出適應(yīng)度函數(shù)如下：其中，系數(shù)a，b，c用于對不同類型的懲罰進行一個尺度變換。

3.2 仿真實驗

為了驗證模型及算法的有效性，下面針對3架UCAV 5個目標(biāo)的任務(wù)想定進行仿真分析，需要對各個目標(biāo)進行偵察、攻擊以及毀傷評估3類共計15個待執(zhí)行任務(wù)，并設(shè)定飛行航路為直線。無人機性能參數(shù)、任務(wù)的價值和任務(wù)時間窗約束如表1～表3所示。算法主要參數(shù)設(shè)置［9］如下：初始溫度T=100，濃度閾值r=0.2，交叉概率PC=0.9，變異概率迭代次數(shù)L=600。仿真實驗得到任務(wù)分配計劃的Pareto最優(yōu)解，如下頁表4所示，仿真結(jié)果統(tǒng)計如表5所示。

表1 任務(wù)目標(biāo)設(shè)置信息表

表2 無人機性能參數(shù)表

表3 任務(wù)時間約束表

由下頁圖2可以看出，任務(wù)總航程代價隨著迭代次數(shù)迅速減小，說明算法具有較強的尋優(yōu)能力和較快的收斂速度。

表4 Pareto最優(yōu)解任務(wù)分配計劃

表5 仿真實驗結(jié)果統(tǒng)計

圖2 任務(wù)總航程代價曲線圖

由表4和表5可以看出，Pareto最優(yōu)解對應(yīng)的3個任務(wù)分配計劃，以及實驗結(jié)果統(tǒng)計表中的目標(biāo)函數(shù)和任務(wù)執(zhí)行時間存在很大差別，說明Pareto解可以滿足決策者不同的任務(wù)需求，而且解的濃度均低于0.2，說明Pareto解有較好的多樣性，符合算法最初的預(yù)想。

4 結(jié)論

針對多無人機協(xié)同任務(wù)分配問題，通過引入擴展的混合整數(shù)線性規(guī)劃模型，提出了一種基于相似度的遺傳退火算法，并將該算法應(yīng)用于靜態(tài)多無人機任務(wù)分配中，通過仿真實驗，可以看出算法具有較快的收斂速度和較好的多樣性，驗證了算法的有效性。

［1］陳 黎.軍用無人機技術(shù)的發(fā)展現(xiàn)狀及未來趨勢［J］. 2013（2）：11-14.

［2］倪 謠，周德云，馬云紅，等.基于MILP模型的多無人機對地攻擊任務(wù)分配［J］.火力與指揮控制，2008，33（11）：62-65.

［3］ Shima T S，Rasmussen S J，Sparks A G.UAV Cooperative Control Multiple Task Assignments using Genetic Algorithms［M］.In Proceedings of American Control Conference，Porland，OR，2005.

［4］ Gerkey B P，Mataric M J.A Framework for Studying MultirobotTask Allocation ［C］//Proceedings ofthe Multirobot Systems.Washington，USA，2003:15-26.

［5］王新增，王愛軍，周 文.多UCAV協(xié)同任務(wù)規(guī)劃層次分解及約束處理方法研究［J］.現(xiàn)代電子技術(shù)，2013，36（5）：6-9.

［6］Ombuki B，Nakamura M，Osamu M.A Hybrid Search Based on Genetic Algorithms and Tabu Search for Vehicle Routing［C］//6th International Conference on Artificial Intelligence and Soft Computing.Banff，Canada，2002:176-181.

［7］王 潔，高家全.一種新的的免疫遺傳算法及應(yīng)用［J］.計算機應(yīng)用與軟件，2010，27（12）：89-91.

［8］TAN B T G，LIM S M.Automated Parameter Optimization for Double Frequency Modulation Synthesis Using the Genetic Annealing Algorithm［J］.Audio Eng Soc，1996，44（1）：25-28.

［9］龍國慶，祝小平，周 洲.多無人機系統(tǒng)協(xié)同多任務(wù)分配模型與仿真［J］.飛行力學(xué)，2011，29（4）：68-76.

Method Research on Cooperative Task Allocation for Multiple UCAVs

LIANG Guo-wei，WANG She-wei，ZHAO Xue-sen
（Aviation University of Air Force，Changchun 130022，China）

Task allocation is the core of the multiple Unmanned Combat Aerial Vehicle（UCAV）coordination control and the effecttive guarantee.It is a completed multi-objective optimization problem. Based on an extension of mixed integer line-ar programming（MILP）model of the task assignment，through the analysis of the characteristics of the model，the paper puts forward a genetic-anneal ing algorithm based on similarity is applied tosolve the problem and the simulation exper-iment.The simulation results show that the algorithm has strong convergence and better diversity，verify the effectiveness of the improved algorithm to solve the problem model.

UCAV，task allocation，coordination control，MILP

V279；V24

A

1002-0640（2014）11-0013-05

2013-09-01

2013-11-17

國家自然科學(xué)基金資助項目（61203355）

梁國偉（1989- ），男，吉林公主嶺人，碩士研究生。研究方向：多無人機路徑規(guī)劃及任務(wù)分配。