王建峰,賈高偉,辛宏博,郭 正,侯中喜

(國防科技大學(xué) 空天科學(xué)學(xué)院, 湖南 長沙 410073)

無人機作為無人系統(tǒng)的“集大成者”,被廣泛應(yīng)用于不同任務(wù)場景。大型全能型無人機平臺存在任務(wù)效費比低、系統(tǒng)容錯性差和升級周期長等缺陷[1-2],異構(gòu)無人機系統(tǒng)旨在將大型平臺功能分散到空間分布的低成本單元,通過合理調(diào)度實現(xiàn)不同單元的動態(tài)組合和密切協(xié)作,在兼具經(jīng)濟性的基礎(chǔ)上達(dá)到甚至超過大型平臺能力水平。

對敵防空壓制(suppression of enemy air defenses, SEAD)場景是當(dāng)前異構(gòu)無人機協(xié)同應(yīng)用的典型場景,受到了廣泛關(guān)注[3]。當(dāng)前該場景的研究多在給定無人機配置下進(jìn)行,并集中于完善場景建模[3-4]與提升求解效率[5]。無人機配置是確定參與任務(wù)的無人機類型及數(shù)量[6],任務(wù)規(guī)劃是協(xié)調(diào)各單元以獲得執(zhí)行方案,二者存在遞階關(guān)聯(lián)性,合理的無人機配置可以提升機間協(xié)同效率,在滿足任務(wù)需求的同時避免無人機資源浪費[6]。

SEAD場景中無人機配置和任務(wù)規(guī)劃聯(lián)合優(yōu)化問題屬于異構(gòu)車隊車輛路徑問題(heterogeneous fleet vehicle routing problem, HFVRP)范疇,即尋找最佳異構(gòu)車隊組成和任務(wù)路線[7-8]。HFVRP是在車輛路徑問題(vehicle routing problem, VRP)的基礎(chǔ)上將車隊組成也作為變量,較VRP這一NP-hard問題計算復(fù)雜度更高。HFVRP包含多種擴展[9-10]——多次訪問、站點依賴、時間窗口、資源限制、非對稱路徑等,本文問題包含類似限制[3,11]:對同一目標(biāo)順序執(zhí)行多種任務(wù);存在時間窗口約束和資源需求;航程和資源載荷有限,且有返航需求;任務(wù)執(zhí)行要求和動力學(xué)約束使得任務(wù)路徑不對稱。這些限制極大增加了問題求解難度。

考慮無人機配置對任務(wù)執(zhí)行的影響:文獻(xiàn)[12]針對協(xié)同搜索與攻擊場景,選擇不同數(shù)量的無人機組合進(jìn)行仿真,發(fā)現(xiàn)增加無人機可以降低任務(wù)時間但也增加任務(wù)協(xié)調(diào)成本,數(shù)量過多反而降低整體效能;文獻(xiàn)[13]針對協(xié)同對地打擊場景,對比了不同機型組合及數(shù)量配置的體系貢獻(xiàn)率,發(fā)現(xiàn)高速與高隱身無人機體系貢獻(xiàn)率較高,無人機數(shù)量增加會提高貢獻(xiàn)率,但存在飽和?？紤]無人機配置與任務(wù)規(guī)劃的遞階關(guān)聯(lián)性,確定合理的無人機配置:文獻(xiàn)[14]利用分層策略處理無人機配置與任務(wù)分配問題,對比了基于進(jìn)化算法的同時求解和分層求解的效果,證明了分層策略的有效性;文獻(xiàn)[15]針對廣域偵察場景,利用聚類方法將目標(biāo)劃分成簇,根據(jù)簇群數(shù)量確定無人機數(shù)量并進(jìn)行任務(wù)指派;文獻(xiàn)[16]針對無人機武器配置和打擊路徑優(yōu)化問題,設(shè)計了基于局部搜索策略的啟發(fā)式算法,在確定各個目標(biāo)的毀傷需求的基礎(chǔ)上優(yōu)化無人機任務(wù)路徑,驗證了啟發(fā)式算法的計算優(yōu)勢。

本文針對SEAD場景特點,建立了異構(gòu)無人機編隊路徑問題(heterogeneous UAV fleet vehicle routing problem, HUFVRP)模型,在任務(wù)規(guī)劃問題基礎(chǔ)上將各類型無人機數(shù)量也作為決策變量,充分表征目標(biāo)、任務(wù)和無人機的多種約束,優(yōu)化無人機使用數(shù)量與任務(wù)執(zhí)行時間指標(biāo)。建立了雙層聯(lián)合優(yōu)化方法求解模型:上層調(diào)整無人機配置,設(shè)計了任務(wù)銜接參數(shù)引導(dǎo)無人機數(shù)量調(diào)整;下層求解任務(wù)規(guī)劃,改進(jìn)遺傳算法能夠有效處理多種約束,并根據(jù)無人機數(shù)量變化針對性調(diào)整執(zhí)行方案;雙層相互協(xié)調(diào)以獲得無人機配置和執(zhí)行方案。

1 聯(lián)合優(yōu)化問題建模

本節(jié)首先介紹SEAD場景想定,然后建立目標(biāo)、任務(wù)和無人機模型,最后給出HUFVRP模型相關(guān)數(shù)學(xué)描述。

1.1 SEAD任務(wù)場景想定

場景目標(biāo)為位置已知的雷達(dá)站,毀傷要求和時間窗口已經(jīng)明確,為簡化計算做出如下想定:

1)任務(wù)場景為二維區(qū)域,不考慮地形障礙、禁飛區(qū)、突發(fā)威脅等干擾因素,目標(biāo)和無人機均視為點目標(biāo)。

2)目標(biāo)包含多個任務(wù),每個任務(wù)由一架無人機執(zhí)行,不能忽略任務(wù)執(zhí)行時間。

3)無人機存在資源和航程限制,不能無限執(zhí)行任務(wù),任務(wù)完成后需返回起飛點。

1.2 基礎(chǔ)模型構(gòu)建

1.2.1 目標(biāo)與任務(wù)模型

T={T1,…,Ti,…,TNTarget}為目標(biāo)集合,數(shù)量為NTarget。MTi表示目標(biāo)Ti所屬任務(wù)集合,包含偵察C、攻擊A和評估V三類任務(wù),c∈{1,2,3}為對應(yīng)類型序號。

MTi?{C,A,V}

(1)

全部任務(wù)按照目標(biāo)序號排列形成任務(wù)總集合MAll={MT1,…,MTi,…,MTNTarget},任務(wù)總數(shù)量為:

(2)

1.2.2 任務(wù)耦合關(guān)系

對于某一任務(wù),關(guān)聯(lián)矩陣中對應(yīng)列的非零項為其依賴的任務(wù),稱為前序任務(wù),前序任務(wù)全部完成后該任務(wù)方可執(zhí)行;關(guān)聯(lián)矩陣中對應(yīng)行的非零項為受其影響的任務(wù),稱為后續(xù)任務(wù),該任務(wù)完成后后續(xù)任務(wù)方可執(zhí)行。式(3)為偵察、攻擊和評估任務(wù)的關(guān)聯(lián)矩陣,第3列表示評估任務(wù)的前序任務(wù)為偵察和攻擊任務(wù)。

(3)

1.2.3 無人機模型

(4)

1.3 問題求解模型

在上述模型的基礎(chǔ)上,借鑒異構(gòu)車隊車輛路徑問題[7,10]與無人機任務(wù)規(guī)劃[3-4]的部分研究建立HUFVRP模型。定義圖模型G(V,A),其中V={T0,T1,…,Ti,…,TNTarget}為起飛點和目標(biāo)點的集合;A={(i,j)|0≤i,j≤NTarget,i≠j}為無人機目標(biāo)間轉(zhuǎn)移順序的集合,(i,j)表示無人機從目標(biāo)Ti轉(zhuǎn)移至目標(biāo)Tj。模型相關(guān)變量如下:

該問題需要尋找合理的無人機配置方案和對應(yīng)執(zhí)行方案,因此針對性設(shè)置無人機數(shù)量F1和任務(wù)平均完成時間F2兩個優(yōu)化目標(biāo),具體如下:

F1=NUAV

(5)

(6)

模型約束包含任務(wù)執(zhí)行要求、任務(wù)時序耦合約束和無人機能力限制三類,建模如下:

(7)

(8)

(9)

(10)

(11)

(12)

(13)

(14)

(15)

(16)

(17)

其中:式(7)約束目標(biāo)包含的任務(wù)均分配給無人機執(zhí)行;式(8)～(9)約束無人機從起飛點出發(fā),執(zhí)行完任務(wù)后返回出發(fā)點;式(10)約束無人機按方案順序執(zhí)行任務(wù);式(11)確保無人機在任務(wù)開始前到達(dá)目標(biāo)位置;式(12)確保任務(wù)時間滿足時間窗約束;式(13)確保任務(wù)時間滿足時序耦合約束,其中Y為無窮大值;式(14)確保無人機有能力執(zhí)行所分配的任務(wù);式(15)確保無人機所執(zhí)行任務(wù)的資源需求不超過其機載資源限制;式(16)確保無人機不超過航程限制;式(17)確保各類無人機使用數(shù)量不超過最大數(shù)量。

2 雙層聯(lián)合優(yōu)化方法

2.1 聯(lián)合優(yōu)化問題求解分析

無人機配置與任務(wù)規(guī)劃聯(lián)合優(yōu)化問題包含多種類型的變量,且變量之間存在遞階關(guān)聯(lián)性,求解十分困難[14]。因此,本文設(shè)計了雙層聯(lián)合優(yōu)化方法,上層進(jìn)行無人機配置計算,下層進(jìn)行多無人機任務(wù)規(guī)劃計算,具體見圖1。

圖1 雙層聯(lián)合優(yōu)化方法結(jié)構(gòu)Fig.1 Structural diagram of the two-level joint optimization method

在上層中,根據(jù)任務(wù)時間表和無人機使用率設(shè)計了任務(wù)銜接參數(shù),精確評估各類型無人機需求,指導(dǎo)無人機配置方案調(diào)整。在下層中,使用改進(jìn)遺傳算法在給定無人機配置下進(jìn)行任務(wù)規(guī)劃計算,能結(jié)合無人機數(shù)量變化精確調(diào)整執(zhí)行方案,在有限時間內(nèi)能夠以更高概率獲得高質(zhì)量執(zhí)行方案,提升對無人機配置方案的評估準(zhǔn)確性。

雙層聯(lián)合優(yōu)化方法可以通過有限次數(shù)的迭代獲得滿足要求的無人機配置及任務(wù)執(zhí)行方案,避免了無人機配置與任務(wù)規(guī)劃同時求解造成的問題空間非線性擴展,在有限的計算時間內(nèi)可以獲得更高質(zhì)量結(jié)果。

2.2 上層:無人機配置計算

2.2.1 任務(wù)銜接參數(shù)

(18)

(19)

(20)

(21)

本文在任務(wù)等待時間的基礎(chǔ)上設(shè)計了任務(wù)銜接參數(shù)指標(biāo)δCI,以評估各類型無人機需求情況。某類任務(wù)的銜接參數(shù)高,說明對應(yīng)的無人機數(shù)量不足,計算如下:

(22)

可以根據(jù)任務(wù)銜接參數(shù)的變化判斷無人機數(shù)量是否飽和:無人機增加會影響對應(yīng)任務(wù)完成時間,進(jìn)而影響其后續(xù)任務(wù)的最早允許開始時間。若后續(xù)任務(wù)對應(yīng)無人機數(shù)量不足,參數(shù)將上升;若無人機數(shù)量充足,參數(shù)將不變,此時不需增加該類無人機。

2.2.2 無人機配置調(diào)整流程

無人機配置將在給定的初始配置方案基礎(chǔ)上進(jìn)行調(diào)整,每次增加1架無人機,如圖2所示,具體流程如下:

圖2 無人機配置調(diào)整流程Fig.2 Flow chart of UAV configuration adjustment

步驟1：輸入初始無人機配置方案。

步驟2：調(diào)用下層任務(wù)規(guī)劃,計算當(dāng)前無人機配置方案下的最優(yōu)執(zhí)行方案。

步驟3：根據(jù)式(18)～(22)計算任務(wù)銜接參數(shù),根據(jù)參數(shù)對各類型無人機進(jìn)行倒序排列,形成無人機增加列表。

步驟4：判斷各類型無人機是否達(dá)到其最大數(shù)量限制,若達(dá)到則從列表中刪除該類無人機。

步驟5：若上次無人機配置迭代時,任務(wù)的前序任務(wù)對應(yīng)無人機增加后,該任務(wù)銜接參數(shù)沒有變化,則將對應(yīng)無人機從列表中刪除。

步驟6：選擇列表中排在首位的無人機,在當(dāng)前無人機配置方案的基礎(chǔ)上增加1架該類無人機,然后更新無人機配置方案。

步驟7：判斷是否滿足迭代終止條件,若滿足則停止迭代,否則返回步驟2進(jìn)行計算。

2.3 下層:任務(wù)規(guī)劃計算

下層改進(jìn)遺傳算法主要包含任務(wù)編碼與調(diào)整、任務(wù)時間表計算、局部搜索算子三部分,計算流程見圖3。

圖3 任務(wù)規(guī)劃計算流程Fig.3 Flow chart of mission planning calculation

2.3.1 任務(wù)編碼與調(diào)整

任務(wù)編碼包含目標(biāo)序列、任務(wù)序列和無人機序列三部分,編碼長度與任務(wù)總數(shù)量相同,按照編碼順序從左至右計算。多層編碼情況如圖4所示,第一列表示目標(biāo)T2的攻擊任務(wù)A由無人機U1執(zhí)行。

圖4 多層編碼示意圖Fig.4 Multi-layer coding schematic

由于存在時序耦合約束,若某一任務(wù)先于其前序任務(wù)執(zhí)行,可能出現(xiàn)“死鎖”情況,導(dǎo)致無人機陷入無休止的等待[11]。如圖4所示,第1列和第4列分別為目標(biāo)T2的攻擊和偵察任務(wù),任務(wù)執(zhí)行順序與任務(wù)時序耦合約束矛盾,導(dǎo)致前四個任務(wù)陷入“死鎖”。對此,本文設(shè)計了基于任務(wù)關(guān)聯(lián)矩陣的“死鎖”調(diào)整流程,具體如下:

步驟1：在原編碼基礎(chǔ)上生成空白的新編碼。

步驟2：根據(jù)編碼順序?qū)υ季幋a中的任務(wù)逐一進(jìn)行判斷——其關(guān)聯(lián)矩陣對應(yīng)列是否全部為0。

步驟3：若出現(xiàn)任務(wù)滿足上述條件,則立即停止判斷。將該任務(wù)從原始編碼中刪除并將其關(guān)聯(lián)矩陣對應(yīng)行設(shè)為0。

步驟4：將該任務(wù)插入新編碼的當(dāng)前第一空位,若編碼為空則放置于首位,無人機映射關(guān)系不變。

步驟5：判斷原始編碼是否為空,若是則輸出新編碼,否則返回步驟2。

該方法只對存在時序耦合約束的任務(wù)進(jìn)行調(diào)整,其他任務(wù)的對應(yīng)順序不變。

2.3.2 任務(wù)時間表計算

任務(wù)時間表將根據(jù)調(diào)整后的編碼順序進(jìn)行計算,每個任務(wù)的計算過程包含無人機選擇、任務(wù)執(zhí)行路徑和任務(wù)時間協(xié)調(diào)三部分。

(23)

2)任務(wù)執(zhí)行路徑:采用末端航向松弛的Dubins方法[17]計算任務(wù)路徑,在滿足無人機動力學(xué)約束和任務(wù)執(zhí)行需求的基礎(chǔ)上,將任務(wù)規(guī)劃尋優(yōu)和任務(wù)路徑計算部分解耦,降低整體計算復(fù)雜度。計算過程如圖5所示,偵察無人機(A點)和攻擊無人機(B點)對目標(biāo)T1和T2執(zhí)行偵察和攻擊任務(wù)。藍(lán)色實線為偵察路徑:無人機需繞目標(biāo)盤旋(紅色區(qū)域)搜集信息,其轉(zhuǎn)移路徑為當(dāng)前位置進(jìn)入盤旋航線的最短路徑,可以使用幾何切線方法計算其轉(zhuǎn)移路徑,評估任務(wù)與偵察任務(wù)計算相同。攻擊無人機路徑為紅色實線:無人機需要到達(dá)目標(biāo)上方進(jìn)行攻擊,目標(biāo)位置將作為無人機轉(zhuǎn)移路徑的終點進(jìn)行計算。

圖5 無人機任務(wù)路徑計算示意圖Fig.5 UAV path calculation schematic

3)任務(wù)時間協(xié)調(diào):根據(jù)上述路徑可以獲得無人機到達(dá)時間,然后根據(jù)式(18)與前序任務(wù)時間和時間窗口進(jìn)行協(xié)調(diào)計算任務(wù)開始時間。計算完成后需要判斷是否滿足無人機航程約束,若不滿足就選擇無人機列表中下一架無人機進(jìn)行計算,若滿足則按照編碼順序計算下一項任務(wù)。

2.3.3 局部搜索算子

局部搜索算子將根據(jù)無人機配置變化對前序無人機配置下的完成時間較短的方案進(jìn)行調(diào)整。主要將原方案中的部分未完成任務(wù)和等待時間較大任務(wù)添加至新增無人機執(zhí)行列表,流程如下:

步驟1：選擇一個完成時間較短的任務(wù)方案,將其作為基礎(chǔ)方案進(jìn)行調(diào)整。

步驟2：選擇新增無人機可執(zhí)行的全部任務(wù),將其中未完成任務(wù)和等待時間大于0的任務(wù)加入待調(diào)整任務(wù)列表。

步驟3：為新增無人機增加一個任務(wù)——按照待調(diào)整任務(wù)列表順序,分別將任務(wù)列表中的任務(wù)調(diào)整至基礎(chǔ)方案中新增無人機的執(zhí)行列表末尾,形成多種新執(zhí)行方案。

步驟4：計算生成的全部執(zhí)行方案,選擇最優(yōu)方案。

步驟5：判斷最優(yōu)方案是否優(yōu)于基礎(chǔ)方案,若占優(yōu)則執(zhí)行步驟6,否則執(zhí)行步驟7。

步驟6：將此時最優(yōu)方案作為基礎(chǔ)方案,并從待調(diào)整任務(wù)列表刪除最優(yōu)方案中已調(diào)整的任務(wù),返回步驟3。

步驟7：輸出此時的基礎(chǔ)方案。

3 場景仿真驗證

本節(jié)對無人機配置和任務(wù)規(guī)劃聯(lián)合優(yōu)化方法進(jìn)行仿真。分析了無人機配置過程和不同場景下的普適性;驗證了任務(wù)規(guī)劃方案的可行性與規(guī)劃方法的求解效率。

3.1 場景及參數(shù)配置

仿真場景區(qū)域范圍為150 km×150 km,起飛點為[0,0],目標(biāo)隨機分布在[10,140] km×[10,140] km的區(qū)域?？紤]到任務(wù)背景,目標(biāo)會遠(yuǎn)離起飛點,因此限制目標(biāo)與起飛點的最小距離為60 km,目標(biāo)間最小距離為20 km。目標(biāo)所屬任務(wù)集合包含偵察、攻擊和評估三個任務(wù)。攻擊任務(wù)存在時間窗口,資源消耗數(shù)量為1;評估任務(wù)與攻擊任務(wù)需間隔一定時間以避免煙塵干擾。表1為無人機的性能數(shù)據(jù)[4]。任務(wù)銜接參數(shù)中等待時間調(diào)節(jié)參數(shù)為1/3,平均任務(wù)數(shù)控制系數(shù)為0.01。

表1 無人機性能數(shù)據(jù)

3.2 無人機配置方法仿真驗證

3.2.1 無人機配置過程分析

場景包含8個目標(biāo),初始無人機配置為5架無人機(1偵察、3攻擊、1評估),上層無人機配置迭代次數(shù)為10。攻擊任務(wù)時間窗前端分布在[10,30] min,后端分布在[150,180] min,評估任務(wù)與攻擊任務(wù)間隔為1 min。

為驗證本文無人機配置方法的有效性,設(shè)計了一種對比方法:在迭代時增加銜接參數(shù)最小任務(wù)所對應(yīng)無人機,生成一組對比方案。結(jié)果如下:

1)無人機配置與任務(wù)銜接參數(shù):圖6為兩種方法的無人機配置方案對比,兩種方法的無人機總數(shù)量相同,不同類型的無人機數(shù)量存在差異。圖7表示本文方法的任務(wù)銜接參數(shù)變化。如圖6和圖7所示,隨著無人機數(shù)量增加,任務(wù)銜接參數(shù)呈下降趨勢,第2次迭代時增加了偵察無人機,對應(yīng)銜接參數(shù)下降,其后續(xù)的攻擊和評估任務(wù)的參數(shù)上升且變化較大,說明兩類無人機數(shù)量不足,同樣情況也在第4、6、8和9次迭代時出現(xiàn),但后續(xù)任務(wù)的銜接參數(shù)波動持續(xù)減小,說明無人機數(shù)量已經(jīng)較為充足。這表明無人機配置過程中觀察無人機增加對任務(wù)銜接參數(shù)的影響是有意義的。

圖6 無人機配置方案對比(左側(cè)為本文方法,右側(cè)為對比方法)Fig.6 Comparison of UAV configuration plans (left is the method in this article, right is the comparison method)

圖7 任務(wù)銜接參數(shù)變化圖Fig.7 Chart of connection impact indicator

2)無人機配置與無人機使用率:圖8為攻擊無人機使用率的變化(其余無人機均全部使用):除初始配置外,本文方法中無人機均全部使用;而對比方法在第2～4次迭代時攻擊無人機未全部使用,這是由于無人機比例不合理,偵察無人機數(shù)量過少影響偵察任務(wù)執(zhí)行,使得后續(xù)攻擊任務(wù)錯過時間窗口,造成攻擊無人機資源浪費。在本文方法生成的無人機配置方案中,偵察型多于評估型,攻擊型最少。偵察型和評估型無人機性能相同,但偵察任務(wù)影響整體任務(wù)的執(zhí)行,故數(shù)量較多;攻擊無人機速度最快,可以承擔(dān)更多任務(wù),故數(shù)量較少;配置方案與無人機性能參數(shù)相符。

圖8 攻擊無人機使用率對比Fig.8 Comparison of attack UAV usage rates

3)無人機配置與任務(wù)平均完成時間:圖9為任務(wù)平均完成時間對比,隨無人機數(shù)量增加,任務(wù)平均完成時間持續(xù)減小,前期下降快,后期平緩,說明無人機數(shù)量增加呈現(xiàn)邊際效應(yīng)。本文方法始終占優(yōu),第2次迭代時本文方法中任務(wù)已全部完成,但對比方法中存在未完成任務(wù),因此差距較小;迭代后期,兩種方法調(diào)整基礎(chǔ)相同,增加無人機的影響降低,使得差距逐漸減小。

圖9 任務(wù)平均完成時間對比Fig.9 Comparison of average mission completion time

4)無人機配置與未完成任務(wù):表2為未完成任務(wù)情況,圖10為未完成數(shù)量對比圖。在第1次迭代時存在部分攻擊和評估任務(wù)未完成,本文方法在第2次迭代時增加了偵察無人機,調(diào)整后任務(wù)全部完成;對比方法增加了攻擊無人機,但任務(wù)依舊未完成,說明本文方法中分類處理未完成任務(wù)的策略是有效的。

表2 未完成任務(wù)情況

圖10 未完成任務(wù)數(shù)量對比Fig.10 Comparative chart of uncompleted missions

3.2.2 多場景下無人機配置方法驗證

為驗證本文方法在不同場景的有效性,進(jìn)行如下仿真:在目標(biāo)和任務(wù)數(shù)量不變的情況下,隨機生成100組目標(biāo)位置和對應(yīng)時間窗口,在無人機總數(shù)量為7～16這十種情況下隨機生成無人機配置方案(這一范圍內(nèi)變化明顯),運行本文方法和對比方法,對比任務(wù)平均完成時間變化。

圖11為不同場景下調(diào)整后與原方案時間比值的平均值,圖中數(shù)字為調(diào)整前無人機總數(shù)量?？梢钥闯霰疚姆椒ㄝ^對比方法始終占優(yōu),說明本文方法不同場景中均能夠?qū)崿F(xiàn)對無人機配置的高效調(diào)整。在無人機數(shù)量為7～9之間時,對比方法的數(shù)據(jù)存在波動,這是由于此時無人機數(shù)量較少且配置方案隨機生成,存在部分未完成任務(wù)。隨著無人機數(shù)量增多,增加無人機的積極效果逐漸降低,這與圖9中任務(wù)平均完成時間的變化趨勢相似。

圖11 任務(wù)時間比值對比Fig.11 Comparative chart of the task time ratio

3.3 多無人機SEAD任務(wù)規(guī)劃仿真驗證

3.3.1 任務(wù)規(guī)劃方法可行性分析

選擇3.2.1節(jié)第5次迭代時生成的任務(wù)執(zhí)行方案進(jìn)行分析,包含9架無人機(3偵察、3攻擊、3評估)。圖12為任務(wù)執(zhí)行甘特圖,圖中序號6-1中6為目標(biāo)編號,1為任務(wù)類型。相同顏色的色塊為同一目標(biāo)任務(wù),粉色色塊代表任務(wù)執(zhí)行時間,紅色三角表示任務(wù)時間窗口?？梢钥闯鐾荒繕?biāo)的多個任務(wù)按順序執(zhí)行,滿足時序耦合約束;任務(wù)均在時間窗口內(nèi)完成,滿足時間窗約束;無人機在留空時間限制內(nèi)返回出發(fā)點,滿足航程約束。

圖12 任務(wù)執(zhí)行甘特圖Fig.12 Mission execution Gantt chart

3.3.2 任務(wù)規(guī)劃方法求解效率分析

為驗證本文任務(wù)規(guī)劃方法的求解效率,設(shè)置了多種算法進(jìn)行對比。首先在給定無人機配置方案下分析了算法收斂性能,然后對比不同場景下的算法求解性能。相關(guān)算法參數(shù)見表3,算法種群數(shù)量為100,迭代次數(shù)為100。

表3 算法參數(shù)設(shè)置

圖13為四種算法在9架無人機(3偵察、3攻擊、3評估)時的任務(wù)平均完成時間變化,其橫坐標(biāo)為任務(wù)規(guī)劃算法的迭代次數(shù)?？梢钥闯?相較于算法1和算法2,本文算法通過增加局部搜索算子,加速了算法收斂并提升了求解質(zhì)量。本文變異操作主要調(diào)整等待時間較長的任務(wù),相較于算法3,本文算法尋優(yōu)速度更快。

圖14為100組場景下的無人機配置調(diào)整和任務(wù)規(guī)劃計算:橫坐標(biāo)為上層無人機配置迭代次數(shù),縱坐標(biāo)為算法最終解與初始最優(yōu)解的比值,算法使用相同初始種群,比值越小解性能越好。由于第1次迭代時無前序執(zhí)行方案,無法使用局部搜索算子,故不進(jìn)行對比。相較于算法1和算法2,由于存在局部搜索算子,本文算法始終占優(yōu)。計算后期單架無人機承擔(dān)任務(wù)數(shù)量較少,局部搜索算子可調(diào)整任務(wù)數(shù)量下降,因此算法之間差異下降。相較于對比算法3,本文算法整體占優(yōu)但相差很小,與圖13中兩種算法收斂至相同解的情況相符合,為確保任務(wù)規(guī)劃的求解效果,本文使用了較大的變異概率。

圖13 算法收斂性能對比Fig.13 Comparison of the algorithms convergence

圖14 多場景下算法效果對比Fig.14 Comparison of the algorithms in multiple scenarios

4 結(jié)論

本文針對SEAD場景中無人機配置和任務(wù)規(guī)劃聯(lián)合優(yōu)化問題進(jìn)行研究,在任務(wù)規(guī)劃問題基礎(chǔ)上將各類型無人機數(shù)量也作為決策變量,充分表征目標(biāo)、任務(wù)和無人機的多種約束,建立無人機編隊路徑問題模型。設(shè)計了雙層聯(lián)合優(yōu)化方法,將無人機配置與任務(wù)規(guī)劃進(jìn)行分層處理:上層通過分析無人機數(shù)量對任務(wù)時間的影響設(shè)計了任務(wù)銜接參數(shù),評估各類型無人機需求并指導(dǎo)無人機配置調(diào)整;下層利用改進(jìn)遺傳算法進(jìn)行任務(wù)規(guī)劃求解,能夠滿足多類型約束獲得任務(wù)執(zhí)行方案;并設(shè)計了局部搜索算子,能夠結(jié)合無人機數(shù)量變化調(diào)整執(zhí)行方案以提升算法尋優(yōu)效率。

仿真結(jié)果表明,無人機數(shù)量增加呈現(xiàn)邊際效應(yīng),合理的無人機配置能夠充分發(fā)揮各類無人機能力。本文方法能夠通過有限次數(shù)的迭代獲得滿足要求的無人機配置及任務(wù)執(zhí)行方案,可以避免無人機配置與任務(wù)規(guī)劃同時求解造成的問題空間非線性擴展,在同等無人機規(guī)模下執(zhí)行方案效果持續(xù)占優(yōu)。該方法為SEAD場景中無人機資源配置與任務(wù)規(guī)劃提供了一套完整的解決方法,可以提高多無人機協(xié)同的指控效率。