基于細菌覓食算法的多異構無人機任務規(guī)劃

谷旭平, 唐大全

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

0 引 言

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

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

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

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

1 模型建立

1.1 模型描述

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

1.2 約束條件

(1)任務數量約束

(1)

(2)

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

(3)

(3)任務時序約束

(4)

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

(4)機載彈藥約束

(5)

1.3 任務分配評價指標

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

C1=UAVVALUE·(1-TASKTHI)

(6)

式中:UAVVALUE∈[0,1]為UAV的價值;TASKTHI∈[0,1]為目標威脅系數。

(2)UAV航程代價

(7)

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

(3)UAV攻擊收益

(8)

式中:TASKVALUE∈[0,1]為目標價值。

(4)總體收益

(9)

2 細菌覓食算法

2.1 細菌覓食算法

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

2.1.1 趨向操作

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

(10)

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

2.1.2 繁殖操作

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

(11)

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

2.1.3 遷徙操作

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

2.2 BFO的改進措施

2.2.1 趨向操作的改進

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

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

(12)

式中：V是靈敏度；J為適應度；rand為隨機數。

步驟 2翻轉,產生隨機向量Δ(i),依據式(10)進行方向調整。

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

C(i)=C(i)V

(13)

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

(14)

2.2.2 繁殖操作的改進

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

(15)

式中：k為繁殖算子當前迭代數；q為遷徙算子當前迭代數。

2.2.3 遷徙操作的改進

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

(16)

2.3 改進細菌覓食算法流程

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

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

步驟 2若i

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

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

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

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

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

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

3.1 UAV的運動模型

UAV的動力學方程為

(17)

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

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

(18)

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

3.2.1 基于Lyapunov的導航向量場

導航向量場保證UAV以一定距離進行目標的偵查、攻擊和評估。假定UAV最小觀測距離為Rs,目標位于(xA,yA),UAV位于(xU,yU),則以(xA,yA)為中心的Lyapunov函數為

(19)

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

構造導航向量場f(x,y):

(20)

對式(19)求導得

(21)

3.2.2 基于Lyapunov的避障向量場

圖1 UAV目標感知域

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

(22)

(23)

在上述基礎上,當ds>Ra時,避碰勢場函數g(x,y)=0,當Rc

(24)

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

3.2.3 基于Lyapunov的融合向量場

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

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

(25)

4 多異構UAV任務分配

4.1 基于IBFO-2的任務分配

4.1.1 細菌位置編碼

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

圖2 細菌編碼

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

圖3 任務隊列

4.1.2 細菌的趨向操作

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

步驟 1初始化:k=0;

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

步驟 3將當前細菌種群中適應度最大的個體中目標x對應的任務所在的每一列都復制到細菌i相應目標任務所在列,k=k+1,轉步驟2;

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

4.1.3 細菌的遷徙操作

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

步驟 1初始化目標值x為1;

步驟 2若x>M,轉步驟5,否則進入步驟3;

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

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

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

綜上,任務分配步驟如下:

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

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

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

步驟 4若i

4.2 基于合同網拍賣算法的任務重分配

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

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

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

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

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

步驟 4若T為空,結束競標,否則進行步驟1。

5 仿真分析

5.1 BFO算法性能測試

依據如表1所示的測試函數對算法的性能進行測試,其中f1、f2為單峰測試函數,f3、f4、f5為多峰測試函數,f6、f7、f8為固定多峰測試函數。參與測試的函數有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次獨立運行試驗的結果如表2所示,圖4是測試函數的進化曲線圖。

表1 測試函數及其相關屬性

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

表2 測試函數運行結果

圖4 算法比較示意圖

5.2 基于IBFO-2的多UAV任務分配

5.2.1 融合向量場的構建

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

表3 UAV屬性信息

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

表5 障礙物相關信息

圖5 融合向量場

圖6 UAV1航跡

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

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

表6 任務分配結果

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

表7 運行時間對比

圖8 收益曲線

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

5.2.3 任務重分配

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

圖9 任務重分配路徑曲線

6 結 論

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