梁國偉，王社偉，趙雪森

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

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

梁國偉，王社偉，趙雪森

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

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

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

引言

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

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

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

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

1.1 問題描述

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

}為執(zhí)行任務(wù)的無人機(jī)集合，NV為無人機(jī)的數(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ù)集合表達(dá)為：

其中，Nm=NTNtype為任務(wù)總數(shù)量。P為UCAV編隊(duì)的執(zhí)行路線集合，編隊(duì)中的任一無人機(jī)Vi均分配一條任務(wù)執(zhí)行路線Pi，對任一時(shí)刻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中的其他項(xiàng)表示Vi依次執(zhí)行任務(wù)的位置。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

（5）表示時(shí)間窗約束:

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

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

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

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

其中，Di無人機(jī)Vi的最大航程。

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

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

2.1 種群個(gè)體編碼

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

此編碼方式是將種群中的個(gè)體表示為1個(gè)二維矩陣，矩陣的第1行表示執(zhí)行任務(wù)的無人機(jī)的序號，矩陣的第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è)計(jì)

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

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

（2）交叉模擬退火操作

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

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

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

如果δ≤P，則令Yk代替Xk成為下一代進(jìn)化個(gè)體，否則父代個(gè)體作為下一代個(gè)體。

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

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

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

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

圖1 算法流程圖

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

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

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

2.3 外部精英集

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

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

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

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

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

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

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

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

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

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

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

2.5 算法性能分析

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

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

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

3.1.1 罰函數(shù)的確定

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

（1）超越無人機(jī)最大航程。

（2）不滿足時(shí)間窗約束。

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

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

3.2 仿真實(shí)驗(yàn)

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

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

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

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

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

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

表5 仿真實(shí)驗(yàn)結(jié)果統(tǒng)計(jì)

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

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

4 結(jié)論

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

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

［2］倪 謠，周德云，馬云紅，等.基于MILP模型的多無人機(jī)對地攻擊任務(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］.計(jì)算機(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］龍國慶，祝小平，周 洲.多無人機(jī)系統(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é)基金資助項(xiàng)目（61203355）

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