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

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

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

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

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

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

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

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

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

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

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

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

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

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

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和評(píng)估V三類任務(wù),c∈{1,2,3}為對(duì)應(yīng)類型序號(hào)。

MTi?{C,A,V}

(1)

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

(2)

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

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

(3)

1.2.3 無人機(jī)模型

(4)

1.3 問題求解模型

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

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

F1=NUAV

(5)

(6)

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

(7)

(8)

(9)

(10)

(11)

(12)

(13)

(14)

(15)

(16)

(17)

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

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

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

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

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

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

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

2.2 上層:無人機(jī)配置計(jì)算

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

(18)

(19)

(20)

(21)

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

(22)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.3.2 任務(wù)時(shí)間表計(jì)算

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

(23)

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

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

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

2.3.3 局部搜索算子

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

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

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

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

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

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

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

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

3 場(chǎng)景仿真驗(yàn)證

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

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

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

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

3.2 無人機(jī)配置方法仿真驗(yàn)證

3.2.1 無人機(jī)配置過程分析

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

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

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

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

圖8 攻擊無人機(jī)使用率對(duì)比Fig.8 Comparison of attack UAV usage rates

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

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

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

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

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

3.2.2 多場(chǎng)景下無人機(jī)配置方法驗(yàn)證

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

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

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

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

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

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

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

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

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

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

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

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

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

圖14 多場(chǎng)景下算法效果對(duì)比Fig.14 Comparison of the algorithms in multiple scenarios

4 結(jié)論

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

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