基于細(xì)菌覓食算法的多異構(gòu)無(wú)人機(jī)任務(wù)規(guī)劃

谷旭平, 唐大全

(海軍航空大學(xué)航空作戰(zhàn)勤務(wù)學(xué)院, 山東 煙臺(tái) 264001)

0 引 言

隨著無(wú)人機(jī)(unmanned aerial vehicle,UAV)軍用和民用價(jià)值日益顯著。UAV遍及地形勘測(cè)[1-2]、電力巡檢[3]、軍事行動(dòng)[4-5]、環(huán)境監(jiān)測(cè)和災(zāi)難響應(yīng)[6-7]、智能農(nóng)業(yè)[8-9]、商業(yè)運(yùn)輸[10-11]等行業(yè)。隨著作戰(zhàn)任務(wù)日益繁瑣以及作戰(zhàn)環(huán)境的復(fù)雜多變,單UAV已經(jīng)不能滿足日益復(fù)雜的任務(wù)需求,因而集群作戰(zhàn)成為主流。任務(wù)規(guī)劃對(duì)釋放UAV潛力提高集群性能起著關(guān)鍵作用。

任務(wù)規(guī)劃包括任務(wù)分配與航跡規(guī)劃兩方面。任務(wù)分配的求解包括任務(wù)分配模型和算法，任務(wù)分配模型分為集中式和分布式。集中式包括:多旅行商問(wèn)題模型[12]、通用分配問(wèn)題模型[13]、車輛路徑問(wèn)題模型[14]、混合整數(shù)線性規(guī)劃模型[15]、多UAV協(xié)同任務(wù)分配模型[16]、隨機(jī)博弈論任務(wù)分配模型[17]等。集中式算法包括:蟻群算法[18]、粒子群算法[19]、遺傳算法[20]、捆綁算法[21]等。分布式任務(wù)分配模型主要為合同網(wǎng)協(xié)議模型，相應(yīng)算法為智能拍賣算法[22]。集中式特點(diǎn)在于全局性強(qiáng),對(duì)于強(qiáng)耦合的任務(wù)分配具有優(yōu)勢(shì),但計(jì)算量大、魯棒性差、實(shí)時(shí)性不高。分布式的特點(diǎn)在于環(huán)境適應(yīng)度好、計(jì)算量小、魯棒性高,但全局性差,適合于實(shí)時(shí)性要求高、動(dòng)態(tài)特性強(qiáng)的任務(wù)環(huán)境。

航跡規(guī)劃算法包括群體智能算法[23]、人工勢(shì)場(chǎng)法[24]、基于幾何學(xué)的路徑規(guī)劃算法[25]、基于控制理論的路徑規(guī)劃算法等。勢(shì)場(chǎng)法是通過(guò)建立作戰(zhàn)區(qū)域的勢(shì)場(chǎng)環(huán)境,UAV在勢(shì)場(chǎng)導(dǎo)向中完成航跡規(guī)劃。

本文針對(duì)多UAV任務(wù)規(guī)劃問(wèn)題,綜合考慮航跡規(guī)劃對(duì)整個(gè)編隊(duì)任務(wù)分配的影響,一方面融合Lyapunov導(dǎo)航向量場(chǎng)以及避障向量場(chǎng),在動(dòng)態(tài)和靜態(tài)障礙干擾下,尋求最優(yōu)可飛航跡;另一方面,改進(jìn)細(xì)菌覓食算法,尋求最優(yōu)任務(wù)分配結(jié)果;在任務(wù)分配過(guò)程中,基于合同網(wǎng)拍賣算法,進(jìn)行UAV故障環(huán)境中的任務(wù)重分配。

1 模型建立

1.1 模型描述

定義由D架強(qiáng)擊機(jī)、E架偵察機(jī)、F架轟炸機(jī)構(gòu)成的UAV集群:U={U1,…,UD,UD+1,…,UD+E,UD+E+1…,UN},N=D+E+F,其中前D架為強(qiáng)擊機(jī),中間E架為偵察機(jī),后F架為轟炸機(jī)。定義M個(gè)作戰(zhàn)目標(biāo)集合:AIM={A1,A2,…,AM},每個(gè)作戰(zhàn)目標(biāo)都需進(jìn)行偵察(Classify, C)、攻擊(attack, A)、評(píng)估(verify, V)任務(wù),任務(wù)集合T={T1,T2,…,TG},G=3×M。UAV依據(jù)其功能,執(zhí)行相應(yīng)任務(wù),具體情況為:①?gòu)?qiáng)擊機(jī)C、A、V；②偵察機(jī)C和V；③轟炸機(jī)A。

1.2 約束條件

(1)任務(wù)數(shù)量約束

(1)

(2)

(2)任務(wù)執(zhí)行情況約束

(3)

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

(4)

式(4)表示目標(biāo)Ai的任務(wù)執(zhí)行次序?yàn)閭刹?、攻擊、評(píng)估。

(4)機(jī)載彈藥約束

(5)

1.3 任務(wù)分配評(píng)價(jià)指標(biāo)

(1)UAV完成任務(wù)付出代價(jià):

C1=UAVVALUE·(1-TASKTHI)

(6)

式中:UAVVALUE∈[0,1]為UAV的價(jià)值;TASKTHI∈[0,1]為目標(biāo)威脅系數(shù)。

(2)UAV航程代價(jià)

(7)

式中:dmax為UAV執(zhí)行任務(wù)的最遠(yuǎn)距離; Dist(Tij)為UAV執(zhí)行任務(wù)Tj的航程。

(3)UAV攻擊收益

(8)

式中:TASKVALUE∈[0,1]為目標(biāo)價(jià)值。

(4)總體收益

(9)

2 細(xì)菌覓食算法

2.1 細(xì)菌覓食算法

細(xì)菌覓食算法[26](bacterial foraging optimization, BFO)依據(jù)細(xì)菌的趨向、繁殖和遷徙行為,實(shí)現(xiàn)種群優(yōu)化。為方便描述引入符號(hào):S為種群大小,Nc為趨向操作次數(shù),Ns為趨向操作在任一方向上游動(dòng)的最大步數(shù),Nre為繁殖行為次數(shù),Ne為遷徙行為次數(shù),Ped為遷徙概率。

2.1.1 趨向操作

趨向方式:細(xì)菌任選一方向游動(dòng),若適應(yīng)度增加,則繼續(xù)朝該方向游動(dòng),直到達(dá)到最大步數(shù)Ns,否則轉(zhuǎn)換方向游動(dòng),直到達(dá)到趨向次數(shù)Nc。細(xì)菌i的趨向操作表示為

(10)

式中:Δ表示隨機(jī)方向上的單位向量;C(i)為游動(dòng)步長(zhǎng);θi(j,k,l)表示細(xì)菌i在第j次趨向操作、第k次復(fù)制操作、第l次遷徙操作后的位置。

2.1.2 繁殖操作

繁殖方式:依據(jù)式(11)衡量細(xì)菌趨向后的適應(yīng)度,并進(jìn)行排序,淘汰掉Sr=S/2個(gè)能量較小的細(xì)菌,復(fù)制剩余Sr個(gè)細(xì)菌。

(11)

式中:J(i,j,k,l)表示細(xì)菌i在第j次趨向操作、第k次復(fù)制操作、第l次遷徙操作之后的適應(yīng)度。

2.1.3 遷徙操作

細(xì)菌以給定概率Ped進(jìn)行遷徙操作,即若細(xì)菌i滿足遷徙概率,則隨機(jī)分布到尋優(yōu)空間中。

2.2 BFO的改進(jìn)措施

2.2.1 趨向操作的改進(jìn)

為提高算法前期的全局收斂能力,C(i)應(yīng)較大,為增強(qiáng)后期局部收斂能力,C(i)應(yīng)較小。改進(jìn)的趨向操作如下。

步驟 1依據(jù)式(12)進(jìn)行細(xì)菌靈敏度賦值，可表示為

(12)

式中：V是靈敏度；J為適應(yīng)度；rand為隨機(jī)數(shù)。

步驟 2翻轉(zhuǎn),產(chǎn)生隨機(jī)向量Δ(i),依據(jù)式(10)進(jìn)行方向調(diào)整。

步驟 3游動(dòng),若適應(yīng)度得到改善,則按翻轉(zhuǎn)方向游動(dòng),直到適應(yīng)度不變,游動(dòng)步長(zhǎng)變?yōu)?/p>

C(i)=C(i)V

(13)

步驟 4按照式(14)線性遞減靈敏度

(14)

2.2.2 繁殖操作的改進(jìn)

為提高算法前期收斂速度,繁殖數(shù)要大;為避免中期陷入局部極值,繁殖數(shù)要小;為提高后期全局收斂能力,繁殖數(shù)要大。自適應(yīng)繁殖數(shù)為

(15)

式中：k為繁殖算子當(dāng)前迭代數(shù)；q為遷徙算子當(dāng)前迭代數(shù)。

2.2.3 遷徙操作的改進(jìn)

對(duì)全局最優(yōu)附近的細(xì)菌而言,遷徙為解的退化。采用遺傳算法的輪盤賭局作為選擇機(jī)制,適應(yīng)度較小的細(xì)菌遷徙,適應(yīng)度較大的細(xì)菌遷徙概率小。自適應(yīng)遷徙概率為

(16)

2.3 改進(jìn)細(xì)菌覓食算法流程

改進(jìn)精度的細(xì)菌覓食算法(IBFO-1)流程:

步驟 1初始化參數(shù)S,Nc,Ns,Nre,Ned,Ped,定義算法迭代次數(shù)為iter,i=0;

步驟 2若i

步驟 3判斷是否達(dá)到遷徙次數(shù)Ned,達(dá)到則i=i+1,并返回步驟2,否則進(jìn)行一次遷徙操作并進(jìn)入步驟4;

步驟 4判斷是否達(dá)到繁殖次數(shù)Nre,達(dá)到則返回步驟3,否則進(jìn)行一次繁殖操作并進(jìn)入步驟5;

步驟 5進(jìn)行Nc次趨向操作,并返回步驟4。

BFO易跳出局部極值,但為一個(gè)3層循環(huán),且所需要參數(shù)較多,不利于解決大規(guī)模問(wèn)題。故采用改進(jìn)實(shí)時(shí)性的細(xì)菌覓食算法(IBFO-2),按照繁殖、遷徙、趨向進(jìn)行細(xì)菌覓食,并循環(huán)迭代。

3 基于Lyapunov向量場(chǎng)的航程估計(jì)

任務(wù)規(guī)劃通常將任務(wù)分配和航跡規(guī)劃分開(kāi)研究,本文通過(guò)建立UAV動(dòng)力學(xué)模型,在Lyapunov融合向量場(chǎng)[27-29]中,將UAV的真實(shí)航跡轉(zhuǎn)化具體航程信息融入到任務(wù)分配收益函數(shù)中,將任務(wù)分配與航跡規(guī)劃融合到一起。

3.1 UAV的運(yùn)動(dòng)模型

UAV的動(dòng)力學(xué)方程為

(17)

式中：(x,y)T為UAV坐標(biāo)；u1為UAV航速；θ∈[0,2π)為航向角；u2為UAV轉(zhuǎn)彎控制輸入量。

若UAV橫坐標(biāo)集合為X={x1,x2,…,xn},縱坐標(biāo)集合Y={y1,y2,…,yn},則UAV的航程可以為

(18)

3.2 基于Lyapunov向量場(chǎng)的航跡規(guī)劃

3.2.1 基于Lyapunov的導(dǎo)航向量場(chǎng)

導(dǎo)航向量場(chǎng)保證UAV以一定距離進(jìn)行目標(biāo)的偵查、攻擊和評(píng)估。假定UAV最小觀測(cè)距離為Rs,目標(biāo)位于(xA,yA),UAV位于(xU,yU),則以(xA,yA)為中心的Lyapunov函數(shù)為

(19)

式中：R2=(xA-xU)2+(yA-yU)2為UAV與目標(biāo)距離。

構(gòu)造導(dǎo)航向量場(chǎng)f(x,y):

(20)

對(duì)式(19)求導(dǎo)得

(21)

3.2.2 基于Lyapunov的避障向量場(chǎng)

圖1 UAV目標(biāo)感知域

避障勢(shì)能函數(shù)V(X,XU)為

(22)

(23)

在上述基礎(chǔ)上,當(dāng)ds>Ra時(shí),避碰勢(shì)場(chǎng)函數(shù)g(x,y)=0,當(dāng)Rc

(24)

式中:ds為障礙物與UAV之間距離；dm為最小UAV安全距離；γ為UAV航向控制量。

3.2.3 基于Lyapunov的融合向量場(chǎng)

作戰(zhàn)目標(biāo)產(chǎn)生導(dǎo)航向量場(chǎng)引導(dǎo)UAV趨近,障礙物產(chǎn)生避碰向量場(chǎng)引導(dǎo)UAV避障。UAV的融合向量場(chǎng)為

V(x,y)=f(x,y)+g(x,y)

(25)

4 多異構(gòu)UAV任務(wù)分配

4.1 基于IBFO-2的任務(wù)分配

4.1.1 細(xì)菌位置編碼

細(xì)菌采用圖2所示的矩陣編碼,第1行為任務(wù)序列,第2行為執(zhí)行任務(wù)的UAV,即一個(gè)細(xì)菌代表一種任務(wù)調(diào)度方案。

圖2 細(xì)菌編碼

圖2中Tij∈T,表示第i個(gè)細(xì)菌的第j個(gè)任務(wù),Uij∈U表示執(zhí)行Tij的UAV。為保證細(xì)菌生成時(shí),滿足約束條件,按圖3所示的任務(wù)隊(duì)列,每個(gè)目標(biāo)任務(wù)按照偵查、打擊、評(píng)估依次排序。從目標(biāo)隊(duì)列中任選一目標(biāo),依次選取任務(wù),并選取功能匹配的UAV,當(dāng)該目標(biāo)任務(wù)分配完畢,將該目標(biāo)清除,當(dāng)隊(duì)列為空時(shí),即完成初始化。

圖3 任務(wù)隊(duì)列

4.1.2 細(xì)菌的趨向操作

以目標(biāo)為單位,借鑒遺傳算法的交叉變異[30]進(jìn)行趨向操作。C(i)為目標(biāo)個(gè)數(shù)，細(xì)菌i的趨向操作如下：

步驟 1初始化:k=0;

步驟 2任選一個(gè)目標(biāo)x=randperm(M,1),若k>C(i),轉(zhuǎn)到步驟4,否則轉(zhuǎn)入步驟3;

步驟 3將當(dāng)前細(xì)菌種群中適應(yīng)度最大的個(gè)體中目標(biāo)x對(duì)應(yīng)的任務(wù)所在的每一列都復(fù)制到細(xì)菌i相應(yīng)目標(biāo)任務(wù)所在列,k=k+1,轉(zhuǎn)步驟2;

步驟 4得到趨向后細(xì)菌i′適應(yīng)度J′,如果J′>J,則輸出趨向后細(xì)菌i′,否則返回步驟1。

4.1.3 細(xì)菌的遷徙操作

細(xì)菌遷徙時(shí)以目標(biāo)為單位的,借鑒遺傳算法中染色體的交叉變異操作,遷徙流程為:

步驟 1初始化目標(biāo)值x為1;

步驟 2若x>M,轉(zhuǎn)步驟5,否則進(jìn)入步驟3;

步驟 3生成一個(gè)(0,1)之間的隨機(jī)數(shù)rand,若rand>Pself(i),轉(zhuǎn)入步驟4,否則x=x+1返回步驟2;

步驟 4將細(xì)菌i中目標(biāo)x對(duì)應(yīng)的列元素刪除,隨機(jī)選擇符合功能的UAV,按照任務(wù)時(shí)序要求,插入到細(xì)菌i中,x=x+1返回步驟2;

步驟 5將執(zhí)行遷徙操作細(xì)菌i′輸出,計(jì)算其適應(yīng)度值J′,如果J′>J,則保留遷徙后細(xì)菌i′,否則取(0,1)之間的隨機(jī)數(shù)rand2,若rand2

綜上,任務(wù)分配步驟如下:

步驟 1初始化參數(shù)S,Nc,Ns,Nre,Ne,Ped,iter,i=0;

步驟 2依據(jù)第1.2節(jié)約束條件進(jìn)行細(xì)菌初始化;

步驟 3依次進(jìn)行繁殖操作,遷徙操作,趨向操作,i=i+1;

步驟 4若i

4.2 基于合同網(wǎng)拍賣算法的任務(wù)重分配

假設(shè)在UAVUi的任務(wù)集合為{T2c,T3c,T4c,T4v,T6v,T7c},Ui在執(zhí)行完T3c后被對(duì)方UAV擊毀,則剩余任務(wù)集為{T4c,T4v,T6v,T7c},由于任務(wù)執(zhí)行順序的要求,實(shí)際剩余任務(wù)集T={T4c,T4a,T4v,T6v,T7c,T7a,T7v},根據(jù)任務(wù)分配的約束條件,剩余任務(wù)可用最小表示集Tmin={T4c,T6v,T7c}表示。

當(dāng)UAV墜毀時(shí),采用合同網(wǎng)拍賣算法[31],集群對(duì)剩余任務(wù)的最小表示集進(jìn)行競(jìng)標(biāo),具體流程如下:

步驟 1基站將Tmin中任務(wù)對(duì)剩余UAV公布;

步驟 2各UAV計(jì)算在執(zhí)行完本身任務(wù)后繼續(xù)執(zhí)行Tmin每一任務(wù)所需代價(jià),對(duì)完成代價(jià)最小的任務(wù)進(jìn)行競(jìng)標(biāo),每一個(gè)UAV只能對(duì)一個(gè)任務(wù)進(jìn)行競(jìng)標(biāo),并向基站發(fā)出合同請(qǐng)求；

步驟 3基站對(duì)比所有合同,選擇每一項(xiàng)任務(wù)最小代價(jià)的UAV執(zhí)行該任務(wù),并更新T,Tmin;

步驟 4若T為空,結(jié)束競(jìng)標(biāo),否則進(jìn)行步驟1。

5 仿真分析

5.1 BFO算法性能測(cè)試

依據(jù)如表1所示的測(cè)試函數(shù)對(duì)算法的性能進(jìn)行測(cè)試,其中f1、f2為單峰測(cè)試函數(shù),f3、f4、f5為多峰測(cè)試函數(shù),f6、f7、f8為固定多峰測(cè)試函數(shù)。參與測(cè)試的函數(shù)有BFO、IBFO-1、IBFO-2,遺傳算法[30](genetic algorithm,GA)、粒子群算法[31](particle swarm optimization,PSO)、社會(huì)蜘蛛群優(yōu)化算法[32](social-spider optimization,SSO)。對(duì)6種優(yōu)化算法進(jìn)行30次獨(dú)立運(yùn)行試驗(yàn)的結(jié)果如表2所示,圖4是測(cè)試函數(shù)的進(jìn)化曲線圖。

表1 測(cè)試函數(shù)及其相關(guān)屬性

從表2以及圖4可以看出在較少迭代次數(shù)下,BFO算法及其改進(jìn)算法較其他算法而言有較好的收斂能力。就BFO算法而言,IBFO-1算法的收斂性能要強(qiáng)于BFO以及IBFO-2,但在運(yùn)行時(shí)間方面,IBFO-2要明顯強(qiáng)于BFO算法以及IBFO-1算法。就UAV編隊(duì)的任務(wù)分配而言,對(duì)算法的實(shí)時(shí)性要求較高,因此這里采用IBFO-2算法。

表2 測(cè)試函數(shù)運(yùn)行結(jié)果

圖4 算法比較示意圖

5.2 基于IBFO-2的多UAV任務(wù)分配

5.2.1 融合向量場(chǎng)的構(gòu)建

本文的作戰(zhàn)區(qū)域?yàn)? 000 m×1 000 m、6架UAV、12個(gè)作戰(zhàn)目標(biāo)、4個(gè)障礙物,具體屬性如表3～表5所示。建立以A1為中心融合向量場(chǎng)，如圖5所示,在A1的向量場(chǎng)下,1號(hào)UAV(UAV1)的航跡如圖6所示。

表3 UAV屬性信息

表4 作戰(zhàn)目標(biāo)屬性信息

表5 障礙物相關(guān)信息

圖5 融合向量場(chǎng)

圖6 UAV1航跡

5.2.2 UAV編隊(duì)任務(wù)規(guī)劃仿真

為了滿足實(shí)戰(zhàn)化需求,加入動(dòng)態(tài)障礙物對(duì)UAV執(zhí)行任務(wù)進(jìn)行干擾。假設(shè)UAV可以在盤旋一周過(guò)程中完成任務(wù),當(dāng)UAV到達(dá)目標(biāo)時(shí),目標(biāo)的前提任務(wù)沒(méi)有完成,則UAV在以目標(biāo)為圓心,以Rs為半徑的圓上盤旋;等待前提任務(wù)完成,進(jìn)行下一步任務(wù)操作。UAV的任務(wù)分配結(jié)果如表6所示;目標(biāo)的任務(wù)執(zhí)行情況如圖7所示,S、E代表開(kāi)始和結(jié)束時(shí)刻;任務(wù)分配的總體收益曲線如圖8所示,不同算法的運(yùn)行時(shí)間如表7所示,其中UAV1～UAV6表示1號(hào)～6號(hào)UAV。

表6 任務(wù)分配結(jié)果

圖7 任務(wù)執(zhí)行情況示意圖

表7 運(yùn)行時(shí)間對(duì)比

圖8 收益曲線

從任務(wù)分配結(jié)果可以看出,1號(hào)和2號(hào)強(qiáng)擊機(jī)單獨(dú)完成1、3、4、5、6、7號(hào)任務(wù);3號(hào)偵察機(jī)與6號(hào)轟炸機(jī)協(xié)同完成9、11、12號(hào)任務(wù),4號(hào)偵察機(jī)與5號(hào)轟炸機(jī)協(xié)同完成2、8、11號(hào)任務(wù)。從圖8可以看出任務(wù)分配的整體收益曲線在較少的迭代次數(shù)下,收益逐漸平穩(wěn),IBFO-2算法在收斂精度強(qiáng)于其他算法;從表7可以看出在運(yùn)行時(shí)間上,IBFO-2優(yōu)于其他算法。綜上,選取IBFO-2算法是合適的。

5.2.3 任務(wù)重分配

假設(shè)2號(hào)UAV在執(zhí)行完T3任務(wù)后被敵方摧毀,現(xiàn)根據(jù)合同網(wǎng)拍賣算法[33],對(duì)剩余任務(wù)進(jìn)行重新超標(biāo),則任務(wù)重分配結(jié)果如圖9所示。6號(hào)任務(wù)由1號(hào)UAV執(zhí)行,7號(hào)任務(wù)由1號(hào),4號(hào)UAV協(xié)同完成。

圖9 任務(wù)重分配路徑曲線

6 結(jié) 論

本文基于BFO算法進(jìn)行多異構(gòu)UAV的任務(wù)規(guī)劃,首先對(duì)BFO算法,提出了針對(duì)精度與實(shí)時(shí)性的改進(jìn)策略,依據(jù)任務(wù)分配的特點(diǎn),選取IBFO-2并結(jié)合遺傳算法的交叉變異操作,進(jìn)行任務(wù)初分配。同時(shí),依據(jù)Lyapunov融合導(dǎo)航以及避障向量場(chǎng),將UAV路徑規(guī)劃實(shí)況融入任務(wù)分配中。最后，依據(jù)合同網(wǎng)拍賣算法,進(jìn)行任務(wù)重分配。仿真實(shí)驗(yàn)驗(yàn)證,基于IBFO-2算法,在實(shí)時(shí)性和收斂精度方面強(qiáng)于其他算法。