多無人機(jī)協(xié)同任務(wù)規(guī)劃方法

王欽釗，程金勇，李小龍

（陸軍裝甲兵學(xué)院，北京 100072）

0 引言

無人作戰(zhàn)飛機(jī)（Unmanned Combat Aerial Vehicle，簡稱UCAV）是一種能完成壓制防空、實(shí)施對地轟炸與攻擊、執(zhí)行對空作戰(zhàn)任務(wù)的空中無人作戰(zhàn)系統(tǒng)［1］。與單無人機(jī)相比，多無人機(jī)協(xié)同系統(tǒng)在時間、空間、功能、信息和資源上的分布特性，使其具有更強(qiáng)的工作能力和魯棒性。任務(wù)規(guī)劃作為多無人機(jī)協(xié)同的基本問題之一，具有十分重要的地位。作戰(zhàn)環(huán)境下，由于受到各種因素的約束，多無人機(jī)協(xié)同任務(wù)規(guī)劃問題是一個約束眾多而復(fù)雜的NP問題，在算法的求解上比較困難，尤其是在規(guī)模較大時，獲得最優(yōu)解的代價較大，制約了實(shí)際戰(zhàn)場應(yīng)用［2］，因此，合理而有效的任務(wù)規(guī)劃方案對于提高多無人機(jī)的作戰(zhàn)效能具有至關(guān)重要的作用。

目前采用較多的問題模型有多旅行商問題［3-4］（Multiple Traveling Salesman Problem ，MTSP）、車輛調(diào)度和路徑規(guī)劃問題模型（Vehicle Routing Problem，VRP）、混合整數(shù)線性規(guī)劃問題模型（Mixed Integer Linear Programming，MILP）等。任務(wù)分配求解的算法主要有蟻群算法、memetic算法、基于合同網(wǎng)拍賣算法、差分進(jìn)化算法等，大部分算法主要針對傳統(tǒng)的多旅行商問題進(jìn)行求解，無法對具有多約束條件的實(shí)際問題進(jìn)行有效的求解。

本文基于多無人機(jī)協(xié)同作戰(zhàn)問題，構(gòu)建任務(wù)分配模型，針對遺傳算法容易陷入局部最優(yōu)和早熟的缺陷，提出一種基于整數(shù)編碼的多種群混合遺傳算法（Multi-Population Hybrid Genetic Algorithm，MPHGA）進(jìn)行求解，最后以典型的壓制敵防空火力作戰(zhàn)任務(wù)（Suppression of Enemy Air Defences，SEAD）為想定，進(jìn)行matlab仿真實(shí)驗(yàn)和驗(yàn)證。

1 多無人機(jī)任務(wù)分配模型

1.1 問題描述

假設(shè)多個無人作戰(zhàn)飛機(jī)對敵方地面固定目標(biāo)執(zhí)行攻擊的任務(wù)，攻擊前通過前期偵察手段已預(yù)先獲知戰(zhàn)場環(huán)境和目標(biāo)分布信息。綜合考慮實(shí)際作戰(zhàn)環(huán)境中的目標(biāo)種類差異、無人機(jī)個體載荷和協(xié)同約束、實(shí)際戰(zhàn)場環(huán)境威脅約束等條件，對作戰(zhàn)問題進(jìn)行建模：

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

無人機(jī)執(zhí)行作戰(zhàn)任務(wù)目的是消滅目標(biāo)價值最大，自身的損傷代價最小，同時為避免任務(wù)執(zhí)行過程中出現(xiàn)意外情況，任務(wù)完成的時間最少。但實(shí)際作戰(zhàn)過程中很難保證各個指標(biāo)均為最優(yōu)化，需要指戰(zhàn)員在任務(wù)要求的基礎(chǔ)上對各個指標(biāo)賦予相應(yīng)的權(quán)重。本文在下一節(jié)中采用系數(shù)歸一化處理方法引入指揮員決策偏好對目標(biāo)函數(shù)的不同指標(biāo)進(jìn)行處理。

1）運(yùn)動總時間。無人機(jī)運(yùn)動距離越長，暴露在敵方威脅下的時間越長，被擊落的可能性越大，因此，為了降低風(fēng)險，要求無人機(jī)的運(yùn)動時間最短。

2）任務(wù)完成時間。戰(zhàn)場環(huán)境瞬息萬變，如何以最短的時間結(jié)束戰(zhàn)斗是勝負(fù)的關(guān)鍵，任務(wù)執(zhí)行時間指標(biāo)為：

3）攻擊目標(biāo)的價值收益。目標(biāo)價值最大化是戰(zhàn)爭的目的，為了方便進(jìn)行計算和適應(yīng)度函數(shù)的確立，采用目標(biāo)的剩余價值量來進(jìn)行評估。

Vall為所有目標(biāo)的總價值；Sij代表第i架無人機(jī)攻擊第j個目標(biāo)，無人機(jī)的生存概率；AKij代表第i架無人機(jī)攻擊第j個目標(biāo)，對于目標(biāo)的損傷概率；Vij表示目標(biāo)毀傷的總價值。

4）無人機(jī)的損傷代價。追求無人機(jī)損傷代價的最小化。

Aij表示第i架無人機(jī)攻擊第j個目標(biāo)時無人機(jī)的損傷概率。

1.3 約束條件

1）多無人機(jī)對目標(biāo)進(jìn)行打擊的過程不能超過目標(biāo)的最大價值：

2）單架無人機(jī)的執(zhí)行能力約束：

n為第i架無人機(jī)的載彈量。

3）目標(biāo)任務(wù)必須被執(zhí)行，各目標(biāo)T的抵抗能力不同，有的可能需要多無人機(jī)進(jìn)行協(xié)同打擊。

4）無人機(jī)的航程約束，無人機(jī)具有油耗限值，不能無限制運(yùn)動，每個無人機(jī)的運(yùn)動總距離越小越好。

2 模型算法求解

2.1 路徑規(guī)劃

實(shí)際環(huán)境中存在障礙物和禁飛區(qū)，為了確保任務(wù)規(guī)劃模型中的路徑可行，在任務(wù)規(guī)劃之前，需要對可行路徑進(jìn)行預(yù)規(guī)劃，增強(qiáng)規(guī)劃過程的準(zhǔn)確性和可行性。

本文首先構(gòu)建描述戰(zhàn)場環(huán)境的禁飛區(qū)和目標(biāo)點(diǎn)的二維平面分布圖，利用MAKLINK圖論算法建立路徑規(guī)劃的二維空間，采用dijkstra算法規(guī)劃初始路徑，在初始路徑基礎(chǔ)上使用蟻群算法生成全局最優(yōu)路徑，保證航路可行并且避障［5］。通過以上算法獲取每架無人機(jī)到每個目標(biāo)點(diǎn)和任意兩目標(biāo)點(diǎn)之間的線路，用于準(zhǔn)確的計算任務(wù)規(guī)劃中的運(yùn)動時間代價。路徑規(guī)劃算法流程如圖1。

2.2 基于整數(shù)編碼的多種群遺傳算法

遺傳算法（Genetic Algorithm，GA）是一種借鑒生物界的自然選擇和進(jìn)化過程發(fā)展起來的高度并行、隨機(jī)、自適應(yīng)的全局優(yōu)化搜索算法，由Holland教授于1975年首先提出［6-7］。遺傳算法能夠自適應(yīng)地控制搜索過程，具有較強(qiáng)的魯棒性和全局搜索能力，但是容易早熟?；谡麛?shù)編碼的多種群遺傳算法能夠確保搜索過程的快速收斂性和多樣有效性。

多種群遺傳算法是從保持和增強(qiáng)種群多樣性的角度出發(fā)而提出的進(jìn)化模型，編碼方式采用單染色體整數(shù)編碼方式，所有的個體被分組成若干個分種群，每個分種群按照設(shè)定好的進(jìn)化策略獨(dú)立地在可行解空間內(nèi)進(jìn)行搜索，從各個分種群中迭代進(jìn)化的子代中選擇精英個體，融合共同組成新一代精英種群，新一代種群重復(fù)上述過程，繼續(xù)獨(dú)立進(jìn)化，直到迭代過程滿足終止條件為止，圖2為該算法的流程圖。該算法極大地避免了傳統(tǒng)遺傳算法容易陷入未成熟收斂的缺陷［8］，擴(kuò)大了搜索范圍，保證了尋優(yōu)過程的收斂性和任務(wù)規(guī)劃效果。

2.2.1 個體編碼

種群個體采用單染色體整數(shù)編碼方式，每條染色體代表待優(yōu)化問題的一個可行解。如表1所示，r1r2r3分別代表3架無人機(jī)，1～9代表待攻擊目標(biāo)。該染色體含義是 r1攻擊 1，2；r2攻擊 5，3，7，4；r3攻擊8，6，9。

表1 編碼方式

2.2.2 選擇和變異算子

基因交換算子：以一定的概率隨機(jī)交換染色體中兩個基因的位置，基因交換算子包含單點(diǎn)換位和多點(diǎn)換位。單點(diǎn)交換每次只交換一對基因的位置，多點(diǎn)交換一次交換N對基因?；虿迦胨阕樱簩⑷旧w中的某一個或者某一串基因移除，并隨機(jī)地插入該染色體其他位置。基因倒轉(zhuǎn)算子：以一定的概率將染色體中某一串基因序列反轉(zhuǎn)，在一條染色體中進(jìn)行基因倒轉(zhuǎn)的基因長度隨機(jī)選取。選擇算子好壞直接影響到遺傳算法收斂性，選擇壓力過大容易導(dǎo)致未成熟收斂，選擇壓力過小則會導(dǎo)致收斂速度過慢。本文采用輪盤賭方法進(jìn)行篩選，適應(yīng)度值越大的個體被選中的概率越大。

2.2.3 適應(yīng)度目標(biāo)函數(shù)的確定

多目標(biāo)組合優(yōu)化問題求解過程中，根據(jù)指揮員決策意圖確定不同指標(biāo)的權(quán)重，將不同的指標(biāo)函數(shù)歸一化處理，使得多目標(biāo)的整數(shù)規(guī)劃問題（Multi-Objective Programming，MOP）轉(zhuǎn)化為單目標(biāo)的整數(shù)規(guī)劃問題。式（11）中不同的值取決于指揮員的決策意圖。設(shè)計函數(shù)如下：

其中：

2.3 算法流程

1）初始化。設(shè)置打擊區(qū)域的目標(biāo)點(diǎn)數(shù)目n，區(qū)域中節(jié)點(diǎn)位置，無人機(jī)數(shù)目m，無人機(jī)的武器載荷q（攻擊目標(biāo)數(shù)目的最大值）；2）使用2.1節(jié)中的路徑規(guī)劃算法進(jìn)行路徑的預(yù)先規(guī)劃；3）初始化多種群算法參數(shù)：包括種群數(shù)量、分種群組數(shù)、迭代次數(shù)、分種群遺傳算子參數(shù)等，隨機(jī)生成初始種群；4）根據(jù)2.2節(jié)所述，種群進(jìn)行進(jìn)化更新；5）檢驗(yàn)是否滿足終止條件，滿足則輸出最終分配方案，不滿足則重復(fù) 3）。

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

為了驗(yàn)證上述模型和算法的有效性，在SEAD場景中進(jìn)行仿真實(shí)驗(yàn)。我方4架無人機(jī)R1～R4攻擊敵方的10個目標(biāo)E0～E9。每架無人機(jī)至少打擊1個目標(biāo)，最多打擊5個目標(biāo)。表2和表3分別為各個目標(biāo)和無人機(jī)的價值。目標(biāo)損傷概率和無人機(jī)生存概率為0～1隨機(jī)生成，如表4和表5所示。為了對比算法效果，采用多種群混合遺傳算法和標(biāo)準(zhǔn)遺傳算法分別對問題進(jìn)行求解。

表2 目標(biāo)價值矩陣

表3 我方無人機(jī)價值矩陣

設(shè)定種群規(guī)模為100，子種群數(shù)N=5，最大迭代次數(shù)K=800，分組種群中基因交換、插入、倒轉(zhuǎn)算子的概率參數(shù)不同，采用MATLAB仿真。兩種算法的仿真結(jié)果如圖3和圖4所示。

表4 目標(biāo)損傷概率矩陣

表5 我方無人機(jī)生存概率矩陣

根據(jù)任務(wù)分配模型采用多種群遺傳算法求解得到的最優(yōu)分配方案為：R1（E9—E1），R2（E4—E3—E8），R3（E0），R4（E7—E2—E5—E6）。圖 5 中SGA和MPHGA曲線分別表示傳統(tǒng)遺傳算法和多種群算法的多次實(shí)驗(yàn)的平均結(jié)果?？梢钥闯?，多種群遺傳算法在260代即收斂到最優(yōu)值，而傳統(tǒng)遺傳算法在467代才收斂到較優(yōu)值。實(shí)驗(yàn)結(jié)果表明傳統(tǒng)的遺傳算法陷入未成熟收斂，收斂速度較慢，而多種群遺傳算法的收斂速度和尋優(yōu)能力均優(yōu)于傳統(tǒng)遺傳算法。綜上所述，多種群算法明顯改善了遺傳算法易陷入未成熟收斂的缺陷，提高了收斂速度，性能優(yōu)于傳統(tǒng)遺傳算法。

4 結(jié)論

仿真結(jié)果顯示，多種群遺傳算法具有較快的收斂速度和較高的尋優(yōu)能力，能夠?qū)θ蝿?wù)想定進(jìn)行合理的規(guī)劃，同時算法兼顧了無人機(jī)運(yùn)動距離、目標(biāo)價值等約束條件，在性能、尋優(yōu)能力和速度方面均優(yōu)于傳統(tǒng)遺傳算法。

參考文獻(xiàn)：

［1］王鵬.無人作戰(zhàn)飛機(jī)的特點(diǎn)和未來發(fā)展［J］.國防科技，2011，32（1）：23-29.

［2］KARABOGA D.An idea based on honey bee swarm for numerical optimization ［R］.Kayseri：Engineering Faculty Computer Engineering Department， Ereiyes University，2005.

［3］田菁.多無人機(jī)協(xié)同偵察任務(wù)規(guī)劃問題建模與優(yōu)化技術(shù)研究［D］.長沙：國防科學(xué)技術(shù)大學(xué)，2007：14-20.

［4］ZHOU W.LI Y.An improved genetic algorithm for multiple traveling salesman problem ［C］//2nd International Asia Conference on Informaticsin Control，Automation and Robotics（CAR）.China：Wuhan，2010（3）：493-495.

［5］郁磊，史峰.matlab智能算法［M］.北京：北京航空航天大學(xué)出版社，2015.

［6］劉慧霞，馬麗娜，李大健，等.無人機(jī)多機(jī)協(xié)同偵察系統(tǒng)關(guān)鍵技術(shù)［J］.火力與指揮控制，2017，42（12）：1-4.

［7］HOLLAND J H.Adaptation in natural and artificial systems［M］.Ann Arbor：The University of Michigan Press，1975.

［8］LIU C，KROLL A.On designing genetic algorithms for solving small-and medium-scale traveling salesman problems［C］//International Symposium on Swarm Intelligence and Differential Evolution （SIDE 2012） .Poland：Zakopane，2012（4）：283-291.