劉廣瑞， 王慶海， 姚冬艷

(鄭州大學(xué) 機(jī)械工程學(xué)院，河南 鄭州 450001)

0 引言

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

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

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

1.1 問(wèn)題描述

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

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

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

1.2 約束條件

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

tiS≤tiA-tc≤tiE-tc;

(1)

(2)

(3)

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

(4)

tljk=tsjk+tc,

(5)

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

1.3 目標(biāo)函數(shù)建立

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

F=max(S/v),

(6)

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

2 人工蜂群算法的改進(jìn)

2.1 初始化蜜源

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

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

2.2 選擇機(jī)制

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

動(dòng)態(tài)評(píng)價(jià)指標(biāo)為w1(i)和w2(i),蜜源i被優(yōu)化時(shí)w2(i)按式(8)計(jì)算，w1(i)為0；蜜源i未被優(yōu)化時(shí)w1(i)按式(7)計(jì)算，w2(i)為0.動(dòng)態(tài)評(píng)價(jià)函數(shù)F(i)為式(9).

(7)

(8)

(9)

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

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

(10)

2.3 鄰域搜索

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

2.4 判定準(zhǔn)則

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

(11)

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

2.5 算法流程圖

基于改進(jìn)人工蜂群算法(IABC)的多無(wú)人機(jī)協(xié)同任務(wù)規(guī)劃算法流程圖如圖3所示，其中q為當(dāng)前迭代次數(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)境下進(jìn)行仿真分析，假設(shè)在1 000 km×1 000 km的戰(zhàn)場(chǎng)環(huán)境內(nèi)，5架無(wú)人機(jī)對(duì)10個(gè)目標(biāo)執(zhí)行任務(wù)，無(wú)人機(jī)參數(shù)和威脅參數(shù)設(shè)置如表1和表2所示.目標(biāo)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 無(wú)人機(jī)參數(shù)設(shè)置

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

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

圖4 無(wú)人機(jī)航跡圖Fig.4 Flight path of UAV

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

圖6 目標(biāo)函數(shù)均值收斂曲線(xiàn)對(duì)比圖Fig.6 Comparison convergent curve of target function′s mean value

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

UAV編號(hào)航跡長(zhǎng)度/km任務(wù)耗時(shí)/h任務(wù)分配計(jì)劃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

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

4 結(jié)論

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

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

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

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

參考文獻(xiàn)：

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

[2] 鄧道靖,馬云紅,龔潔,等. 基于并行GAPSO算法的多無(wú)人機(jī)協(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] 張曉敏,馬培蓓,紀(jì)軍,等. 具有時(shí)間約束的多無(wú)人機(jī)協(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)場(chǎng)環(huán)境下多無(wú)人機(jī)調(diào)度問(wèn)題[J]. 火力與指揮控制,2015,40(10):31-36.

[10] 徐向平,魯海燕,程畢蕓. 基于動(dòng)態(tài)評(píng)價(jià)選擇策略的改進(jìn)人工蜂群算法[J]. 計(jì)算機(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.