基于改進人工蜂群算法的多無人機協(xié)同任務(wù)規(guī)劃

劉廣瑞， 王慶海， 姚冬艷

(鄭州大學 機械工程學院，河南 鄭州 450001)

0 引言

多無人機協(xié)同任務(wù)規(guī)劃是根據(jù)無人機所處的地形和環(huán)境因素，為多無人機執(zhí)行多目標任務(wù)制定最佳作戰(zhàn)任務(wù)規(guī)劃方案和各無人機作戰(zhàn)航跡[1].近年來，國內(nèi)外學者對多無人機協(xié)同任務(wù)規(guī)劃做了大量研究.文獻[2]考慮環(huán)境威脅、戰(zhàn)斗毀傷概率等因素提出了并行GAPSO算法對協(xié)同任務(wù)規(guī)劃模型進行了求解，但模型建立未能考慮無人機任務(wù)時間，所規(guī)劃任務(wù)序列實用性差.文獻[3]和文獻[4]在求解無人機任務(wù)調(diào)度問題上未能考慮環(huán)境威脅因素，僅僅是對目標點之間進行任務(wù)規(guī)劃，致使算法所規(guī)劃序列對無人機生存率很難保證.文獻[5]建立了多無人機多目標多任務(wù)模型，模型未能考慮無人機燃油限制和任務(wù)時間約束，致使執(zhí)行任務(wù)效率較低或根本完成不了任務(wù).文獻[6]引入逆向算子改進人工蜂群算法對多無人機單任務(wù)進行了任務(wù)規(guī)劃，提高了任務(wù)規(guī)劃效率，但未考慮無人機執(zhí)行任務(wù)前后時間約束，不能夠做到各無人機協(xié)同執(zhí)行任務(wù).

考慮到多無人機任務(wù)規(guī)劃的協(xié)同性、安全性和任務(wù)時效性，針對無人機信息共享、多任務(wù)能力等特點提高了任務(wù)規(guī)劃難度，考慮戰(zhàn)場威脅分布、目標任務(wù)時序、無人機續(xù)航時間等因素[7]，建立了多無人機協(xié)同執(zhí)行多目標的多任務(wù)規(guī)劃數(shù)學模型.首先采用文獻[8]所提算法對各目標點間和各無人機與目標點間最優(yōu)航跡進行規(guī)劃.之后考慮戰(zhàn)場威脅分布、無人機續(xù)航時間等約束，引入時間窗對無人機執(zhí)行任務(wù)起始時間進行約束建立多無人機任務(wù)規(guī)劃模型，提出一種基于改進人工蜂群算法的多無人機協(xié)同任務(wù)規(guī)劃方法.仿真實驗結(jié)果表明，所設(shè)計多無人機協(xié)同任務(wù)規(guī)劃模型的正確性和有效性得到了很好的驗證.

1 多無人機協(xié)同任務(wù)規(guī)劃模型

1.1 問題描述

以多無人機執(zhí)行多目標任務(wù)為背景，如圖1，無人機執(zhí)行任務(wù)的環(huán)境信息已知，由n架無人機執(zhí)行m個目標的任務(wù)，對每個目標依次執(zhí)行偵查、攻擊和評估3項任務(wù)，每項任務(wù)耗時都為tc.每架無人機對每個目標只能執(zhí)行一項任務(wù).各目標位置、無人機出發(fā)位置和執(zhí)行每項任務(wù)耗時已知.其中U1，U2，…，Un分別表示1#，2#，…，n#無人機；T1，T2，…，Tm分別表示1#，2#，…，m#目標；其中第i個目標被執(zhí)行完偵查任務(wù)、攻擊任務(wù)和評估任務(wù)的結(jié)束時間分別為tiS、tiA和tiE.

圖1 多無人機協(xié)同執(zhí)行任務(wù)示意圖Fig.1 A sketch map of multi-UAV cooperative execute tasks

假設(shè)無人機在二維空間完成規(guī)定任務(wù)，通過6m維向量表示n架無人機執(zhí)行m個目標的任務(wù).無人機根據(jù)任務(wù)時間約束按照時間先后依次執(zhí)行3項任務(wù).為規(guī)劃多無人機任務(wù)分配序列，首先需要根據(jù)文獻[8]所提航跡規(guī)劃算法規(guī)劃出各目標點和各無人機與目標點間最優(yōu)航跡，再根據(jù)所提算法規(guī)劃出最優(yōu)或較優(yōu)任務(wù)序列.

1.2 約束條件

式(1)約束所有目標的所需任務(wù)必須按照任務(wù)順利要求執(zhí)行；式(2)約束每架無人機只能執(zhí)行每個目標其中一項任務(wù)；式(3)約束所有目標的任務(wù)必須全部被執(zhí)行完畢；無人機由一個位置移動到另一個位置需躲避所有威脅且航跡較優(yōu)，最大航程須小于一上限；式(4)和(5)分別表示無人機i開始任務(wù)時間和結(jié)束任務(wù)時間.

tiS≤tiA-tc≤tiE-tc;

(1)

(2)

(3)

tsjk=tlj(k-1)+tc+twjk;

(4)

tljk=tsjk+tc,

(5)

式中,xij為第i個目標被第j個無人機執(zhí)行任務(wù)則為1，否則為0；tsjk和tljk分別為第j個目標第k項任務(wù)開始和結(jié)束時間;twjk為執(zhí)行第j個目標第k項任務(wù)的等待時間[8].

1.3 目標函數(shù)建立

假設(shè)無人機飛行速度為v，在已知無人機和目標位置的前提下，無人機以最優(yōu)或較優(yōu)時間完成所有任務(wù)的任務(wù)分配計劃.目標函數(shù)為：

F=max(S/v),

(6)

其中S=[S1,S2,…,Si,…,Sn]，Si為第i個無人機完成分配的任務(wù)飛行航跡長度.

2 人工蜂群算法的改進

2.1 初始化蜜源

將一個任務(wù)序列集合X=(x1,x2, …,x6m)視作一個蜜源，初始化蜜源需滿足約束條件，其中奇數(shù)位為無人機序號，偶數(shù)位為前一位奇數(shù)位對應(yīng)的無人機所執(zhí)行任務(wù)的目標序號.如圖2，表示的是3架無人機執(zhí)行2個目標任務(wù)的任務(wù)序列編碼.圖中表示的任務(wù)分配計劃為：3架無人機同時出發(fā)，U1對T2執(zhí)行偵察任務(wù)；U2對T1執(zhí)行偵察任務(wù)；等待無人機執(zhí)行完T2的偵察任務(wù)后，U3對T2執(zhí)行攻擊任務(wù)；等待U2對T1執(zhí)行完偵察任務(wù)后，U1對T1執(zhí)行攻擊任務(wù)；等待U3對T2執(zhí)行完攻擊任務(wù)后，U2對T2執(zhí)行評估任務(wù)；等待U1對T1執(zhí)行完攻擊任務(wù)后，U3對T1執(zhí)行評估任務(wù)[9].

圖2 任務(wù)序列編碼方式
Fig.2 Encoding of a sequence of tasks

2.2 選擇機制

傳統(tǒng)ABC算法是通過目標函數(shù)值決定的蜜源適應(yīng)度比例來判定所要跟隨的采蜜蜂，該方法雖然提高了算法收斂速度，但是容易導(dǎo)致蜂群向適應(yīng)度值較高的蜜源聚攏，使算法極易陷入局部最優(yōu).采用動態(tài)評價選擇策略[10]取代傳統(tǒng)選擇機制，通過采蜜蜂動態(tài)變化狀況決定被跟隨的概率，極大地提高了蜂群多樣性，避免了算法陷入局部最優(yōu).

動態(tài)評價指標為w1(i)和w2(i),蜜源i被優(yōu)化時w2(i)按式(8)計算，w1(i)為0；蜜源i未被優(yōu)化時w1(i)按式(7)計算，w2(i)為0.動態(tài)評價函數(shù)F(i)為式(9).

(7)

(8)

(9)

式中：w1(i) 為蜜源i被優(yōu)化連續(xù)不變的次數(shù);w2(i)為蜜源i被優(yōu)化連續(xù)變化次數(shù);Limit為算法的限制參數(shù).

通過動態(tài)評價函數(shù)計算單個蜜源得分，采蜜蜂被選擇概率Pi的計算公式為(10)，通過Pi計算累計第i個采蜜蜂被選擇概率，將生成的0～1的隨機數(shù)與各累計選擇概率匹配，決定觀察蜂選擇哪個采蜜蜂.

(10)

2.3 鄰域搜索

由于所優(yōu)化問題為離散問題，對任務(wù)序列X=(x1,x2, …,x6m)進行鄰域搜索時，由于任務(wù)序列奇數(shù)位置和偶數(shù)位置表示不同的含義，需進行不同的鄰域搜索策略.設(shè)鄰域搜索位為I，若I為奇數(shù)，隨機選取沒有在I位對應(yīng)的目標執(zhí)行過任務(wù)的無人機替代I位對應(yīng)的無人機；若I為偶數(shù)，隨機選取I位對應(yīng)的無人機未執(zhí)行過的其他偶數(shù)位對應(yīng)的目標位進行位置交換.之后采取文獻[6]的方法引入逆向算子的方式對任務(wù)序列進行變異.鄰域搜索完成后對任務(wù)序列進行可行性判定，該方式提高了鄰域搜索解的可行性，提高了算法收斂速度.

2.4 判定準則

在航跡尋優(yōu)過程中，由于尋優(yōu)域較寬，傳統(tǒng)ABC算法全局尋優(yōu)性能劣化，尋優(yōu)收斂速度前快后慢.為提高算法收斂速度和精度，引入Metropolis準則[11]對新舊蜜源進行進一步判定.當前航跡向新航跡轉(zhuǎn)化概率表達如式(11).通過改進，算法尋優(yōu)初期對較差航跡具有較高接受概率，使算法不易陷入局部最優(yōu)；算法尋優(yōu)后期對較差航跡具有較小接受概率，蜜蜂可在較優(yōu)航跡附近進行細致搜索.

(11)

式中:o代表舊航跡；n代表新航跡；下降函數(shù)T(t)=T(t-1)·σ，退火系數(shù)σ一般取0.8.

2.5 算法流程圖

基于改進人工蜂群算法(IABC)的多無人機協(xié)同任務(wù)規(guī)劃算法流程圖如圖3所示，其中q為當前迭代次數(shù)，Lmax為最大迭代次數(shù).

圖3 IABC算法流程圖Fig.3 The flow diagram of IABC algorithm

3 算例分析

在Inter(R) Core(TM) i3-2130 CPU，3.4 Ghz，Matlab R2014a環(huán)境下進行仿真分析，假設(shè)在1 000 km×1 000 km的戰(zhàn)場環(huán)境內(nèi)，5架無人機對10個目標執(zhí)行任務(wù)，無人機參數(shù)和威脅參數(shù)設(shè)置如表1和表2所示.目標T1，T2，…，T10位置分別為(100,300)，(310,240)，(210,700)，(620,610)，(250,500)，(620,350)，(450,470)，(600,150)，(820,350)，(420,750).人工蜂群算法參數(shù)：蜜蜂總數(shù)為NP=60，采蜜蜂總數(shù)為NP/2，Limit=10，Lmax=300.

表1 無人機參數(shù)設(shè)置

表2 威脅參數(shù)設(shè)置

采用ABC和IABC算法分別進行了20次仿真實驗，通過IABC算法仿真得出的最優(yōu)任務(wù)分配計劃對應(yīng)的其中一架無人機的航跡見圖4.通過20次試驗仿真數(shù)據(jù)分析得出兩種算法的目標函數(shù)最優(yōu)值收斂曲線對比圖見圖5，目標函數(shù)均值收斂曲線對比圖見圖6.其中ABC、ROABC和IABC分別代表基本人工蜂群算法、逆向算子人工蜂群算法和改進人工蜂群算法多無人機多任務(wù)規(guī)劃仿真實驗?zāi)繕撕瘮?shù)值.圖7為通過IABC算法仿真得出的最優(yōu)任務(wù)分配計劃的無人機任務(wù)執(zhí)行時間表.表3為對應(yīng)的無人機任務(wù)分配表，其中C、A和E分別對應(yīng)無人機執(zhí)行的偵查、攻擊和評估任務(wù)，例如，1C對應(yīng)無人機對目標1執(zhí)行偵察任務(wù).

圖4 無人機航跡圖Fig.4 Flight path of UAV

圖5 目標函數(shù)最優(yōu)值收斂曲線對比圖Fig.5 Comparison convergent curve of target function′s optimal value

圖6 目標函數(shù)均值收斂曲線對比圖Fig.6 Comparison convergent curve of target function′s mean value

圖7 UAV任務(wù)執(zhí)行時刻表Fig.7 UAV’s assignment schedule

UAV編號航跡長度/km任務(wù)耗時/h任務(wù)分配計劃U115791510903C→10C→4A→2A→1A→5EU215541611271C→5C→7A→4E→6A→8E→9EU315681310844C→7C→2C→8A→9A→6EU417417211273A→10A→5A→1E→2EU514809310408C→9C→6C→7E→3E→10E

通過20次仿真實驗數(shù)據(jù)分析，隨著進化代數(shù)的增加，目標函數(shù)值不斷降低，種群不斷向更優(yōu)的方向進化，兩種改進算法較傳統(tǒng)算法不但收斂的快，而且收斂精度也高很多.IABC算法、ROABC算法和ABC算法耗時均值分別為24.75 s、25.04 s和24.03 s，最優(yōu)收斂值分別為11.72 h、12.16 h和14.33 h.在耗時相當?shù)那闆r下，IABC算法最優(yōu)收斂值比ABC算法低16.5%，比ROABC算法收斂值低3.6%，種群均值更是優(yōu)于ABC算法.根據(jù)圖5，隨著進化代數(shù)增加，所提算法優(yōu)化種群目標函數(shù)均值較另兩種算法更低，可知，所提算法比另外兩種算法種群更優(yōu).表3給出的無人機任務(wù)分配表就是所提IABC算法優(yōu)化的全局最優(yōu)解.

4 結(jié)論

針對無人機信息共享、多任務(wù)能力等特點提高了任務(wù)規(guī)劃難度，考慮戰(zhàn)場威脅分布、目標任務(wù)時序、無人機續(xù)航時間等因素，建立了多無人機協(xié)同執(zhí)行多目標的多任務(wù)規(guī)劃數(shù)學模型.采用改進人工蜂群算法對該模型求解通過仿真結(jié)果表明：

(1) 引入時間窗對無人機執(zhí)行任務(wù)起始時間進行約束建立多無人機任務(wù)規(guī)劃模型，增強了多無人機任務(wù)規(guī)劃模型實用性；

(2) 通過引入動態(tài)評價選擇策略、Metropolis 準則等方式提出改進人工蜂群算法對該模型求解，仿真結(jié)果表明了該方法的有效性；

(3) 算法優(yōu)化過程中很難取得一個全局最優(yōu)解，只能優(yōu)化得到一個相對較優(yōu)的解，每次優(yōu)化結(jié)果很難保證完全一致，算法穩(wěn)定性還有待進一步提高.

參考文獻：

[1] 沈林成,陳璟,王楠. 飛行器任務(wù)規(guī)劃技術(shù)綜述[J]. 航空學報, 2014, 35(3): 593-606.

[2] 鄧道靖,馬云紅,龔潔,等. 基于并行GAPSO算法的多無人機協(xié)同任務(wù)規(guī)劃[J]. 電光與控制, 2014, 23(11): 1-6.

[3] 杜繼永,張鳳鳴,楊驥,等. 多UCAV協(xié)同任務(wù)分配模型及粒子群算法求解[J]. 控制與決策, 2012, 27(11): 1751-1755.

[4] LIN L, SUN Q B, WANG S G, et al. Research on PSO based multiple UAVs real-time task assignment[C]//2013 25th Chinese Control and Decision Conference (CCDC). Guiyang, China:IEEE, 2013: 1530-1536.

[5] GENG L, ZHANG Y, WANG J J, et al. Cooperative task planning for multiple autonomous UAVs with graph representation and genetic algorithm[C]//2013 10th IEEE International Conference on Control and Automation (ICCA). Hangzhou, China:IEEE, 2013: 394-399.

[6] WANG Z T, ZHENG M F, GUO J S,et al.Uncertain UAV ISR mission planning problem with multiple correlated objectives[J]. Journal of intelligent & fuzzy systems, 2017,32(1):321-335.

[7] 張曉敏,馬培蓓,紀軍,等. 具有時間約束的多無人機協(xié)同航跡控制研究[J]. 電光與控制, 2015,22(9): 42-45.

[8] LI B, GONG L G, YANG W L. An improved artificial bee colony algorithm based on balance-evolution strategy for unmanned combat aerial vehicle path planning[J]. Scientific world journal, 2014, 2014(1): 95-104.

[9] 馬純超,尹棟,朱華勇. 網(wǎng)絡(luò)化戰(zhàn)場環(huán)境下多無人機調(diào)度問題[J]. 火力與指揮控制,2015,40(10):31-36.

[10] 徐向平,魯海燕,程畢蕓. 基于動態(tài)評價選擇策略的改進人工蜂群算法[J]. 計算機應(yīng)用, 2015, 35(7): 1969-1974.

[11] MIAO H, TIAN Y C. Dynamic robot path planning using an enhanced simulated annealing approach[J]. Applied mathematics and computation, 2013, 222: 420-437.