谷旭平, 唐大全

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

0 引 言

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

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

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

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

1 模型建立

1.1 模型描述

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

1.2 約束條件

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

(1)

(2)

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

(3)

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

(4)

式(4)表示目標(biāo)Ai的任務(wù)執(zhí)行次序為偵察、攻擊、評估。

(4)機載彈藥約束

(5)

1.3 任務(wù)分配評價指標(biāo)

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

C1=UAVVALUE·(1-TASKTHI)

(6)

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

(2)UAV航程代價

(7)

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

(3)UAV攻擊收益

(8)

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

(4)總體收益

(9)

2 細菌覓食算法

2.1 細菌覓食算法

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

2.1.1 趨向操作

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

(10)

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

2.1.2 繁殖操作

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

(11)

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

2.1.3 遷徙操作

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

2.2 BFO的改進措施

2.2.1 趨向操作的改進

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

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

(12)

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

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

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

C(i)=C(i)V

(13)

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

(14)

2.2.2 繁殖操作的改進

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

(15)

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

2.2.3 遷徙操作的改進

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

(16)

2.3 改進細菌覓食算法流程

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

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

步驟 2若i

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

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

步驟 5進行Nc次趨向操作,并返回步驟4。

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

3 基于Lyapunov向量場的航程估計

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

3.1 UAV的運動模型

UAV的動力學(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向量場的航跡規(guī)劃

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

導(dǎo)航向量場保證UAV以一定距離進行目標(biāo)的偵查、攻擊和評估。假定UAV最小觀測距離為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)航向量場f(x,y):

(20)

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

(21)

3.2.2 基于Lyapunov的避障向量場

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

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

(22)

(23)

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

(24)

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

3.2.3 基于Lyapunov的融合向量場

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

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

(25)

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

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

4.1.1 細菌位置編碼

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

圖2 細菌編碼

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

圖3 任務(wù)隊列

4.1.2 細菌的趨向操作

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

步驟 1初始化:k=0;

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

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

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

4.1.3 細菌的遷徙操作

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

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

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

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

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

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

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

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

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

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

步驟 4若i

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

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

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

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

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

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

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

5 仿真分析

5.1 BFO算法性能測試

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

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

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

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

圖4 算法比較示意圖

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

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

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

表3 UAV屬性信息

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

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

圖5 融合向量場

圖6 UAV1航跡

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

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

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

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

表7 運行時間對比

圖8 收益曲線

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

5.2.3 任務(wù)重分配

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

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

6 結(jié) 論

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