面向多無(wú)人機(jī)協(xié)同對(duì)地攻擊的雙層任務(wù)規(guī)劃方法

余 婧, 雍恩米, 陳漢洋, 郝 東, 張顯才

(1. 中國(guó)空氣動(dòng)力研究與發(fā)展中心計(jì)算空氣動(dòng)力研究所, 四川 綿陽(yáng) 621000;2. 中國(guó)空氣動(dòng)力研究與發(fā)展中心空天技術(shù)研究所, 四川 綿陽(yáng) 621000)

0 引 言

飛行器任務(wù)規(guī)劃是隨著航空技術(shù)和制導(dǎo)/控制技術(shù)的進(jìn)步及其在軍事上的應(yīng)用而形成的一個(gè)新的研究領(lǐng)域。無(wú)人機(jī)(unmanned aerial vehicles, UAVs)的任務(wù)規(guī)劃問(wèn)題包含任務(wù)分配、執(zhí)行順序規(guī)劃以及航跡規(guī)劃等。任務(wù)分配是指確定哪些任務(wù)由哪些UAVs執(zhí)行;執(zhí)行順序確定是指在已知任務(wù)集合的條件下,確定UAVs執(zhí)行任務(wù)的先后順序;航跡優(yōu)化即確定UAVs執(zhí)行任務(wù)的具體飛行航跡。任務(wù)分配與執(zhí)行順序規(guī)劃都是典型的復(fù)雜約束下的組合優(yōu)化問(wèn)題,航跡規(guī)劃的優(yōu)化方式則因建模方式的不同而有所差別。一般而言,3個(gè)層次的優(yōu)化問(wèn)題相互嵌套、相互影響。執(zhí)行順序規(guī)劃需要以任務(wù)分配方案為輸入;航跡規(guī)劃需要以任務(wù)執(zhí)行順序?yàn)檩斎?執(zhí)行任務(wù)的航程或飛行時(shí)間又進(jìn)一步影響任務(wù)分配方案的決策。為了達(dá)到任務(wù)規(guī)劃的全局最優(yōu),需要全盤(pán)梳理3個(gè)層次的優(yōu)化關(guān)系,提出高效的優(yōu)化策略。

目前已存在多種UAVs任務(wù)規(guī)劃的建模方法,包括旅行商模型、車(chē)輛路由模型、網(wǎng)絡(luò)流模型、混合整數(shù)模型等,其中混合整數(shù)模型具有較強(qiáng)的可擴(kuò)展性,車(chē)輛路由模型可以更好地處理帶約束問(wèn)題。針對(duì)優(yōu)化模型,可以選擇很多種搜索算法進(jìn)行求解。傳統(tǒng)的優(yōu)化方法有枚舉法、動(dòng)態(tài)規(guī)劃法、圖搜索算法等,但隨著問(wèn)題維數(shù)的增加,時(shí)間消耗呈指數(shù)增長(zhǎng),不利于復(fù)雜問(wèn)題的求解。隨后,智能優(yōu)化方法因具備易于實(shí)現(xiàn)、計(jì)算復(fù)雜度低等特點(diǎn),被廣泛應(yīng)用。目前常用的智能優(yōu)化算法有遺傳算法(genetic algorithm, GA)、粒子群優(yōu)化(particle swarm optimization, PSO)算法、模擬退火(simulated-annealing, SA)算法等。在當(dāng)前研究中,任務(wù)分配與執(zhí)行順序規(guī)劃因內(nèi)在行為的緊耦合性,通常被作為一個(gè)整體考慮,因此任務(wù)規(guī)劃問(wèn)題大多側(cè)重前兩者的優(yōu)化,而忽略航跡的影響。在優(yōu)化算法方面,SA算法因在理論上有完備的證明,可以達(dá)到全局極小值,而備受研究者的青睞。在任務(wù)規(guī)劃問(wèn)題中,SA算法已有很多成功應(yīng)用,但其亦存在一個(gè)致命的缺點(diǎn),即容易陷入局部最優(yōu),因此研究者也一直在嘗試諸多改進(jìn)方法。

本文綜合考慮任務(wù)規(guī)劃中任務(wù)分配、執(zhí)行順序規(guī)劃以及航跡規(guī)劃3個(gè)層面的優(yōu)化需求和相互間影響,從優(yōu)化框架出發(fā),設(shè)計(jì)了雙層互耦的任務(wù)規(guī)劃求解策略,而后將優(yōu)化模型求解分為上層任務(wù)分配和下層任務(wù)序列優(yōu)化,并對(duì)每一層的優(yōu)化方法和優(yōu)化步驟進(jìn)行了詳細(xì)設(shè)計(jì);在任務(wù)分配問(wèn)題中,基于SA算法,提出了可跳出局部最優(yōu)的SA-撒點(diǎn)(SA-shooting, SAS)算法,并詳細(xì)探討了算法參數(shù)的設(shè)計(jì)原則。最后，通過(guò)仿真分析,驗(yàn)證了所提出的規(guī)劃框架和優(yōu)化算法的有效性。

1 任務(wù)描述

假設(shè)有無(wú)人攻擊機(jī)架和待打擊目標(biāo)個(gè),UAVs起飛后需要飛行至待打擊目標(biāo)位置進(jìn)行對(duì)地攻擊。一架UAV最多攜帶的武器數(shù)量為,即一架UAV最多攻擊個(gè)目標(biāo)，且一個(gè)目標(biāo)只能被一架UAV攻擊。任務(wù)分配的目的是優(yōu)化出哪些UAVs需要打擊哪些目標(biāo)，以及實(shí)施打擊的具體作戰(zhàn)順序、飛行路徑,最大化對(duì)地攻擊效益。圖1給出了多UAV協(xié)同對(duì)地打擊的示意圖。

圖1 多UAV協(xié)同對(duì)地打擊示意圖Fig.1 Sketch map for multi-cooperative UAV air-to-ground attack

2 多UAVs協(xié)同對(duì)地攻擊任務(wù)分配建模

本文的UAVs對(duì)地攻擊任務(wù)分配問(wèn)題,可用四元組〈,,,〉來(lái)描述:

表示戰(zhàn)場(chǎng)環(huán)境態(tài)勢(shì),包含了戰(zhàn)場(chǎng)威脅分布、天氣情況、地形等戰(zhàn)場(chǎng)信息。為了方便討論,本文將所有環(huán)境態(tài)勢(shì)分為兩部分,一部分為禁飛區(qū),即由于雷達(dá)威脅、惡劣天氣、不利地形所導(dǎo)致的UAV不可駛?cè)氲膮^(qū)域;另一部分即為UAV可以機(jī)動(dòng)的區(qū)域。

即UAV狀態(tài),已知UAV集合={UAV,UAV,…,UAV},其中UAV={loc,},表示第架UAV的初始位置和所攜帶的武器數(shù)量,為UAV數(shù)量。

為待攻擊目標(biāo)集合={tar,tar,…,tar},為目標(biāo)數(shù)量,且≤。

表示任務(wù)分配中的約束,包括任務(wù)時(shí)長(zhǎng)約束、匹配約束、數(shù)量約束等,將在建模中詳細(xì)討論。

任務(wù)規(guī)劃的本質(zhì)是一個(gè)優(yōu)化問(wèn)題,包含設(shè)計(jì)變量、任務(wù)約束和評(píng)價(jià)指標(biāo)3個(gè)關(guān)鍵因素。下面將對(duì)本文研究問(wèn)題的關(guān)鍵要素進(jìn)行分析和建模。

2.1 設(shè)計(jì)變量

(1)

2.2 評(píng)價(jià)指標(biāo)

(1) 毀傷效果

假設(shè)UAV對(duì)tar的殺傷概率為 ,則整個(gè)攻擊任務(wù)的毀傷效果為

(2)

(2) 損傷程度

假設(shè)UAV對(duì)tar進(jìn)行打擊,生存概率為 ,則該UAV被擊毀的概率為 =1- ,整個(gè)攻擊任務(wù)的損耗可表示為

(3)

(3) 航程代價(jià)

UAV到達(dá)目標(biāo)的航程越短,完成任務(wù)的時(shí)間代價(jià)就越小,航程代價(jià)需要在任務(wù)序列確定后,經(jīng)過(guò)航跡規(guī)劃給出,因此該評(píng)價(jià)指標(biāo)僅在航跡規(guī)劃時(shí)使用。令表示第架UAV的飛行距離,則整個(gè)任務(wù)的航路代價(jià)可表示為

(4)

2.3 任務(wù)約束

在整個(gè)任務(wù)分配過(guò)程中,需要考慮以下任務(wù)約束:

:任務(wù)時(shí)長(zhǎng)約束,UAV最長(zhǎng)航行距離不得超過(guò)其航程限制。

:任務(wù)分配約束,每一架UAV都必須分配一個(gè)任務(wù),每一個(gè)任務(wù)僅由一架UAV執(zhí)行。

:禁飛區(qū)約束,UAV在航行過(guò)程中,不可經(jīng)過(guò)禁飛區(qū)域。

:任務(wù)數(shù)量約束,第架UAV最多攜帶個(gè)武器。

:飛行姿態(tài)角約束,UAV進(jìn)行機(jī)動(dòng)時(shí),有最大偏航角。

2.4 任務(wù)規(guī)劃模型

綜上,本文所研究的UAVs任務(wù)分配問(wèn)題,可表示為如下優(yōu)化模型:

(5)

式中:和分別表示毀傷效果與損傷程度指標(biāo)的權(quán)重系數(shù),反映了二者的重要程度;可稱(chēng)為任務(wù)效益指標(biāo);為航路指標(biāo);至描述了需要滿(mǎn)足的約束。

3 模型求解

3.1 求解框架

求解上述模型,理論上需要嵌套的兩層規(guī)劃去完成(見(jiàn)圖2)。上層規(guī)劃用于進(jìn)行任務(wù)分配,即確定哪些UAVs執(zhí)行哪些任務(wù),主要滿(mǎn)足優(yōu)化指標(biāo);下層規(guī)劃用于解決任務(wù)順序和航路規(guī)劃問(wèn)題,即在已知UAVs需要打擊的目標(biāo)集合的前提下,優(yōu)化出最優(yōu)的任務(wù)序列和對(duì)應(yīng)的飛行航路,主要關(guān)心優(yōu)化指標(biāo)。為了達(dá)到全局最優(yōu),上層規(guī)劃和下層規(guī)劃往往是相互聯(lián)系和相互影響的,且在一定程度上,上層和下層的優(yōu)化指標(biāo)是相互矛盾的。當(dāng)任務(wù)收益達(dá)到最大,可能航路代價(jià)并非最優(yōu);當(dāng)選取了航路代價(jià)最優(yōu),則需要犧牲一些任務(wù)收益指標(biāo)。

圖2 雙層任務(wù)規(guī)劃框架Fig.2 Bi-level mission planning framework

本文認(rèn)為,整個(gè)任務(wù)分配的效益指標(biāo)遠(yuǎn)比航路指標(biāo)重要。為提高規(guī)劃效率,本文根據(jù)問(wèn)題特點(diǎn),對(duì)問(wèn)題進(jìn)行了簡(jiǎn)化,即上層規(guī)劃僅考慮效益指標(biāo),下層規(guī)劃僅考慮航路指標(biāo),規(guī)劃策略如圖3所示。

圖3 雙層任務(wù)規(guī)劃策略Fig.3 Strategy for Bi-level mission planning

在下層航路優(yōu)化中,根據(jù)已知的任務(wù)目標(biāo)集合進(jìn)行任務(wù)序列窮搜,而后采用已有蟻群算法,進(jìn)行點(diǎn)對(duì)點(diǎn)航路規(guī)劃,選取航路最優(yōu)的任務(wù)序列為最終的任務(wù)執(zhí)行方案,并給出對(duì)應(yīng)的航路信息。

3.2 基于SAS的任務(wù)分配

任務(wù)分配為上層優(yōu)化,任務(wù)分配的目的是優(yōu)化出每一架UAV需要執(zhí)行的具體任務(wù)的集合,而對(duì)具體的執(zhí)行順序和飛行航路不關(guān)心。任務(wù)分配模型,可以從公式中分解得出:

find= ,=1,2,…,;=1,2,…,

(6)

max=-

(7)

(8)

(9)

(10)

(11)

式(6)表示任務(wù)分配的決策變量,式(7)表示任務(wù)效益指標(biāo),式(8)表示每個(gè)目標(biāo)只能被分配給一架UAV,式(9)表示每架UAV都必須被分配目標(biāo),式(10)表示UAV具有多目標(biāo)攻擊能力,最大攻擊數(shù)取決于自身攜帶的武器數(shù)量,式(11)表示所有目標(biāo)都必須被分配給UAVs。

任務(wù)分配是一個(gè)典型的組合優(yōu)化問(wèn)題,SA算法是其求解方法之一。SA算法是一種通用的隨機(jī)搜索算法,是對(duì)局部搜索算法的擴(kuò)展。與一般局部搜索算法不同,SA以一定的概率選擇鄰域中目標(biāo)值相對(duì)較小的狀態(tài),是一種理論上的全局最優(yōu)算法。在實(shí)際應(yīng)用中,SA算法易于陷入局部最優(yōu),因此需要根據(jù)具體問(wèn)題進(jìn)行有針對(duì)性的改進(jìn),以跳出局部最優(yōu)。

本文主要用SA算法進(jìn)行任務(wù)分配優(yōu)化,并在基本算法基礎(chǔ)上拓展撒點(diǎn)算子,以跳出局部最優(yōu),下面對(duì)其關(guān)鍵步驟進(jìn)行介紹。

(1) 編碼設(shè)計(jì)

如果直接以決策變量編碼,則是一個(gè)×維的矩陣,比較浪費(fèi)空間,且不利于尋優(yōu)搜索。為了便于鄰域搜索,本文的編碼設(shè)計(jì)為1×維的向量,為待打擊目標(biāo)的數(shù)量。假如向量中第個(gè)元素的值為,則表示 =1。假如求解的規(guī)劃問(wèn)題有5個(gè)任務(wù),則一個(gè)狀態(tài)編碼如圖4所示。

圖4 狀態(tài)編碼示例Fig.4 Example for encoding

圖4中的編碼表示,任務(wù)1分配給UAV,任務(wù)2分配給UAV,任務(wù)3分配給UAV,任務(wù)4分配給UAV,任務(wù)5分配給UAV。

(2) 鄰域搜索

算法的編碼為整數(shù)編碼,且編碼需要滿(mǎn)足模型中的各種約束。在領(lǐng)域搜索的過(guò)程中,采取概率賦值的方式。具體方法如下(見(jiàn)圖5)。

圖5 鄰域搜索示例Fig.5 Neighborhood searching

隨機(jī)選取編碼中的個(gè)位置;

依次將個(gè)位置上的值,隨機(jī)賦予一個(gè)不同的值,賦值范圍為1～。

(3) 撒點(diǎn)算子設(shè)計(jì)

SA算法的缺點(diǎn)是易于陷入局部最優(yōu),因此在迭代的過(guò)程中,本文引入撒點(diǎn)算子,其基本原理是,在整個(gè)搜索空間隨機(jī)選取若干候選編碼,通過(guò)目標(biāo)函數(shù)值計(jì)算,選取最優(yōu)編碼為鄰域編碼。在傳統(tǒng)的SA算法中,僅根據(jù)當(dāng)前編碼選取一個(gè)鄰域解作為候選點(diǎn),不僅搜索空間有限,而且候選點(diǎn)數(shù)量很少。加入撒點(diǎn)算法后,首先鄰域搜索范圍擴(kuò)展到了整個(gè)尋優(yōu)空間,不局限于鄰域,即跳出了鄰域局部空間的束縛,其次撒點(diǎn)操作一次性并行地搜索多個(gè)候選點(diǎn),有利于提高搜索效率,盡快找到更優(yōu)的候選點(diǎn)。通過(guò)隨機(jī)撒點(diǎn),可以盡快跳出局部最優(yōu),提高傳統(tǒng)算法的全局尋優(yōu)能力。具體步驟如下:

判斷優(yōu)化過(guò)程是否滿(mǎn)足無(wú)條件轉(zhuǎn)移,如果滿(mǎn)足,繼續(xù)下一步;

隨機(jī)生成pop個(gè)編碼(pop稱(chēng)為撒點(diǎn)算子規(guī)模);

對(duì)編碼進(jìn)行目標(biāo)函數(shù)值計(jì)算,選取目標(biāo)值最優(yōu)的編碼為鄰域編碼,并賦值給當(dāng)前編碼。

(4) 算法流程

SAS算法的具體流程如圖6所示。

圖6 SAS算法流程Fig.6 Flowchart for SAS

(5) 算法復(fù)雜度分析

與傳統(tǒng)的SA算法相比，本文所改進(jìn)的SAS算法，主要是在鄰域搜索結(jié)束后，多了一個(gè)撒點(diǎn)算子操作，撒點(diǎn)操作過(guò)程中，需要進(jìn)行目標(biāo)函數(shù)值計(jì)算，且計(jì)算過(guò)程是并行的。假設(shè)計(jì)算一次目標(biāo)函數(shù)的計(jì)算代價(jià)為，時(shí)間代價(jià)為，記傳統(tǒng)SA算法的計(jì)算代價(jià)為SA ()，時(shí)間代價(jià)為SA ()，則可推知，從時(shí)間上看，本文改進(jìn)的SAS算法的時(shí)間代價(jià)為SA ()+iter·，即每一次迭代僅比傳統(tǒng)算法多了一個(gè)時(shí)間單位的代價(jià)。這是由于，盡管撒點(diǎn)算子過(guò)程中進(jìn)行了多次目標(biāo)函數(shù)值計(jì)算，但計(jì)算過(guò)程是并行的，總時(shí)間消耗僅多出一次目標(biāo)函數(shù)值的計(jì)算時(shí)間。從計(jì)算復(fù)雜度上看，改進(jìn)算法的計(jì)算代價(jià)為SA ()+iter·pop·，比傳統(tǒng)算法略高，且復(fù)雜度與撒點(diǎn)算子規(guī)模有關(guān)。

3.3 任務(wù)序列優(yōu)化

當(dāng)每個(gè)UAV的攻擊任務(wù)集合已知,則可進(jìn)行下層優(yōu)化,即任務(wù)序列優(yōu)化。任務(wù)序列優(yōu)化的目的是規(guī)劃出UAVs執(zhí)行任務(wù)的順序以及對(duì)應(yīng)的航路。下層優(yōu)化的模型,可表述為

(12)

min=

(13)

s.t.∩∩

(14)

本文采用已有的蟻群算法進(jìn)行航路規(guī)劃,蟻群算法在此不再贅述。下層優(yōu)化的具體步驟如下:

針對(duì)第架UAV,根據(jù)已知的任務(wù)集合,窮搜可能的排序組合;

針對(duì)每一組任務(wù)序列組合,調(diào)用已有的蟻群算法,進(jìn)行航路規(guī)劃,并記錄最優(yōu)航路代價(jià);

選取所有排序組合中航路代價(jià)最優(yōu)的組合,作為最優(yōu)任務(wù)序列輸出,并同時(shí)輸出飛行航跡。

4 仿真分析

本文的仿真不考慮UAV間的通信與在線(xiàn)協(xié)同問(wèn)題，戰(zhàn)場(chǎng)環(huán)境威脅均簡(jiǎn)化為數(shù)學(xué)模型，且假設(shè)UAV飛行為勻速飛行，不考慮飛行高度等因素。

4.1 任務(wù)分配仿真

(1) 算例配置

假設(shè)UAVs數(shù)量=6,任務(wù)目標(biāo)數(shù)量=10,每架UAV攜帶的最大武器數(shù)量為=4(=1,2,…,),UAVs的毀傷概率和生存概率隨機(jī)給出,具體數(shù)值如表1和表2所示。定義==05。SA算法的參數(shù)值由表3給出。

表1 毀傷概率Table 1 Destructive probability

表2 生存概率Table 2 Survival probability

表3 SA算法參數(shù)設(shè)置Table 3 Parameter configuration for SA algorithm

(2) 優(yōu)化參數(shù)影響分析

假設(shè)撒點(diǎn)算子規(guī)模始終為50,改變鄰域搜索過(guò)程中元素位置搜索數(shù)目,連續(xù)運(yùn)行5次優(yōu)化程序,其優(yōu)化結(jié)果如表4所示。

表4 鄰域搜索參數(shù)對(duì)優(yōu)化結(jié)果的影響Table 4 Optimization results with different neighborhood searching parameters

從表4可以看出,不論參數(shù)設(shè)置為1還是10,算法的搜索結(jié)果都相對(duì)穩(wěn)定,總體上趨于較好的優(yōu)化結(jié)果,且優(yōu)化結(jié)果的方差不大。從表4還可看出,鄰域搜索的位置數(shù)目并不是越多越好,當(dāng)搜索數(shù)目為1和3時(shí),都能夠得到最優(yōu)解4.025,當(dāng)搜索數(shù)目變大時(shí),雖然也能得到較好的優(yōu)化結(jié)果,但不容易得到相對(duì)最優(yōu)的結(jié)果。這是由于隨著搜索數(shù)目的增大,鄰域搜索空間也增大,在有限的搜索次數(shù)內(nèi),并不能保證搜到鄰域的最優(yōu)值。從表4可以推斷出,當(dāng)編碼有10個(gè)值時(shí),鄰域搜索位置數(shù)目設(shè)置在3比較合適。

根據(jù)表4結(jié)果,將鄰域搜索位置數(shù)目設(shè)為3,改變?nèi)鳇c(diǎn)算子規(guī)模,連續(xù)運(yùn)行5次優(yōu)化程序,優(yōu)化結(jié)果如表5所示。

表5 撒點(diǎn)算子規(guī)模對(duì)優(yōu)化結(jié)果的影響Table 5 Optimization results with different shooting populations

撒點(diǎn)算子的設(shè)計(jì),是為了解決SA算法容易陷入局部最優(yōu)的問(wèn)題。從表5可以看出,隨著撒點(diǎn)算子規(guī)模的增加,算法的尋優(yōu)效果越來(lái)越好。這是由于撒點(diǎn)算子規(guī)模越大,搜索的空間越大,則跳出局部最優(yōu)的概率越大。

圖7和圖8給出了表4和表5優(yōu)化中最優(yōu)結(jié)果的收斂過(guò)程。

圖7 鄰域搜索參數(shù)變化的收斂過(guò)程Fig.7 Convergence process with different neighborhood searching parameters

圖8 撒點(diǎn)算子規(guī)模變化的收斂過(guò)程Fig.8 Convergence process with different shooting populations

(3) 算法對(duì)比分析

圖9給出了本文的SA算法與傳統(tǒng)SA算法以及PSO算法的收斂對(duì)比。從圖9可以看出,本文提出的SAS算法收斂效果最好,傳統(tǒng)SA算法次之,傳統(tǒng)PSO算法最差。PSO算法更善于處理連續(xù)優(yōu)化問(wèn)題,傳統(tǒng)編碼對(duì)組合優(yōu)化問(wèn)題的適應(yīng)性不強(qiáng),且迭代次數(shù)較少,導(dǎo)致其優(yōu)化效果較差。SAS算法由于設(shè)計(jì)了跳出局部最優(yōu)的撒點(diǎn)算子操作,優(yōu)化效果優(yōu)于傳統(tǒng)SA算法。

圖9 不同優(yōu)化算法的收斂過(guò)程對(duì)比Fig.9 Convergence process for different algorithms

(4) 優(yōu)化結(jié)果與分析

從表4和表5中選取最優(yōu)的一組優(yōu)化結(jié)果,其任務(wù)分配情況如表6所示。

表6 最優(yōu)分配結(jié)果Table 6 Optimal results for assignment

從表6中可以看出,優(yōu)化的結(jié)果均滿(mǎn)足公式約束。任務(wù)大多趨于分配給UAV,這是由于在隨機(jī)給出的毀傷概率和生存概率中,UAV的數(shù)值都比較好。UAV的概率數(shù)值都較差,如果沒(méi)有任務(wù)數(shù)量約束,整個(gè)任務(wù)分配偏于將任務(wù)分配給其他UAVs,而非UAV。

4.2 任務(wù)序列優(yōu)化仿真

本節(jié)根據(jù)表6的任務(wù)分配結(jié)果,進(jìn)行任務(wù)序列優(yōu)化。

(1) 算例配置

在任務(wù)序列規(guī)劃中,涉及到航跡的規(guī)劃,需要給出飛行環(huán)境。本算例中,飛行環(huán)境主要考慮無(wú)人機(jī)、目標(biāo)的位置、飛行區(qū)域以及涉及到的環(huán)境、雷達(dá)和導(dǎo)彈威脅。任務(wù)目標(biāo)的地理位置如表7所示,各威脅的編號(hào)、類(lèi)型與坐標(biāo)如表8所示。整個(gè)任務(wù)的執(zhí)行區(qū)域限制在[0, 0] km到[60, 60] km范圍內(nèi)。為了進(jìn)行航跡規(guī)劃,需要對(duì)飛行區(qū)域進(jìn)行地圖數(shù)字化,本文采用柵格法進(jìn)行地圖建模,柵格離散化間隔為2 km。無(wú)人機(jī)初始位置為[2, 2] km。

表7 任務(wù)目標(biāo)坐標(biāo)Table 7 Coordinates for targets

表8 威脅分布Table 8 Distribution for threats

(2) 任務(wù)序列枚舉

從表6可知每架無(wú)人機(jī)的目標(biāo)任務(wù)集合。第3.3節(jié)已給出了任務(wù)序列規(guī)劃的具體方法,首先需要對(duì)任務(wù)集合中的所有序列組合進(jìn)行枚舉。如表9所示,UAV～UAV都只有一個(gè)目標(biāo)任務(wù),因此可能的任務(wù)序列組合只有一種。UAV有24種可能的組合方法,而UAV有2種。每一種可能的任務(wù)序列組合都將采用蟻群算法對(duì)其進(jìn)行航跡規(guī)劃,記錄航程,其中航程最短的組合將最終被定為UAV需要執(zhí)行的任務(wù)序列方案和飛行航跡方案。

表9 任務(wù)序列枚舉Table 9 Enumeration results for mission sequences

由于UAV～UAV只有一個(gè)任務(wù)目標(biāo),采用航跡規(guī)劃算法進(jìn)行點(diǎn)對(duì)點(diǎn)航跡規(guī)劃即可,具體優(yōu)化結(jié)果如圖10所示。UAV有兩個(gè)任務(wù)需要執(zhí)行,可能的任務(wù)序列為[2, 7]和[7, 2]。當(dāng)任務(wù)序列為[2, 7]時(shí),最優(yōu)飛行航跡如圖11所示,航程為68.08 km。當(dāng)任務(wù)序列為[7, 2]時(shí),最優(yōu)飛行航跡如圖12所示,航程為87.94 km。因此,UAV的最佳任務(wù)序列為[2, 7]。UAV有24種可能的序列組合,經(jīng)過(guò)優(yōu)化,其最優(yōu)任務(wù)序列為[1, 9, 3, 8],飛行航跡如圖13所示,航程為149.05 km。

圖10 UAV1～UAV4飛行航跡Fig.10 Trajectories for UAV1～UAV4

圖11 UAV6執(zhí)行任務(wù)序列[2, 7]的飛行航跡Fig.11 Trajectory for UAV6 attacking targets [2, 7]

圖12 UAV6執(zhí)行任務(wù)序列[7, 2]的飛行航跡Fig.12 Trajectory for UAV6 attacking targets [7, 2]

圖13 UAV5飛行航跡Fig.13 Trajectory for UAV5

5 結(jié)束語(yǔ)

UAVs的任務(wù)規(guī)劃包含任務(wù)分配、執(zhí)行順序確定以及航跡優(yōu)化等。為了達(dá)到任務(wù)規(guī)劃的全局最優(yōu),需要全盤(pán)梳理任務(wù)的各個(gè)方面,提出高效的優(yōu)化策略。本文綜合考慮任務(wù)規(guī)劃過(guò)程中任務(wù)分配、執(zhí)行順序確定以及航跡優(yōu)化等方面的需求和相互間影響,首先從優(yōu)化框架出發(fā),設(shè)計(jì)了雙層互耦的任務(wù)規(guī)劃求解策略,而后將任務(wù)規(guī)劃模型分為上層任務(wù)分配和下層任務(wù)序列優(yōu)化,并對(duì)每一層的優(yōu)化方法和優(yōu)化步驟進(jìn)行了詳細(xì)設(shè)計(jì);在任務(wù)分配問(wèn)題中,基于SA算法,提出了可跳出局部最優(yōu)的SAS算法,并詳細(xì)探討了算法參數(shù)的設(shè)計(jì)原則。通過(guò)仿真分析可知:① 本文提出的雙層規(guī)劃策略,可有效梳理3個(gè)層次的優(yōu)化關(guān)系,利于優(yōu)化求解。但需要注意的是,雙層規(guī)劃策略的應(yīng)用以任務(wù)收益優(yōu)先為前提,當(dāng)航程等指標(biāo)優(yōu)先級(jí)較高時(shí),需要對(duì)規(guī)劃策略進(jìn)行進(jìn)一步改進(jìn)。② 本文提出的SAS算法可以跳出局部最優(yōu),有效進(jìn)行任務(wù)分配優(yōu)化。在算法參數(shù)設(shè)置過(guò)程中,鄰域搜索時(shí)的可變位置數(shù)目并不是越多越好,一般設(shè)置在編碼總數(shù)的1/3左右;而撒點(diǎn)算子規(guī)模的設(shè)置則是越大越好,規(guī)模越大,搜索的空間越大,則跳出局部最優(yōu)的概率越大。

在進(jìn)一步研究中，將更多考慮實(shí)際應(yīng)用場(chǎng)景，考慮UAV間的協(xié)同、通信、復(fù)雜電磁環(huán)境、飛行高度等問(wèn)題。