復(fù)雜任務(wù)環(huán)境下多無人機多任務(wù)規(guī)劃技術(shù)研究

王超 于德洋 王子強 呂松天 牟洋

（1.中國航天空氣動力技術(shù)研究院 北京市 100074 2.中國人民解放軍陸軍裝甲兵學(xué)院 北京市 100072）

無人機（Unmanned Aerial Vehicle, UAV）在1991年海灣戰(zhàn)爭中得到了成功的應(yīng)用。經(jīng)過了長時間的發(fā)展，UAV技術(shù)在各個領(lǐng)域已發(fā)揮出獨特的作用，但是也產(chǎn)生了許多新的問題[1]。例如在復(fù)雜的戰(zhàn)場環(huán)境下，需要多無人機有序地執(zhí)行多個任務(wù)，才能有效地提高作戰(zhàn)效能[2]。

多無人機的多任務(wù)規(guī)劃問題與多約束條件下的多車場車輛路徑規(guī)劃問題有很多相似之處。在研究了多約束下多車場車輛路徑問題時，傳統(tǒng)尋優(yōu)方法效率低、耗時長，找不到滿意解，導(dǎo)致工作效率過低。為了提高尋優(yōu)效率，往往都需要引入一個能解決復(fù)雜問題的算法。遺傳算法[3]是一種通過模擬自然進化過程搜索最優(yōu)解的方法?；诖颂匦晕簞P[4]曾使用改進的遺傳算法解決軟時間窗車輛路徑問題。本文設(shè)計參考多車場車輛路徑問題的數(shù)學(xué)模型，建立了多無人機多任務(wù)帶軟時間窗的數(shù)學(xué)模型。并在傳統(tǒng)的多無人機多任務(wù)規(guī)劃模型的基礎(chǔ)上，考慮到無人機在飛行過程中受到的雷達探測威脅和地面火力威脅，增加了威脅約束，再對無人機飛行路徑進行精細規(guī)劃，使其能繞過威脅區(qū)域。并利用改進的遺傳算法對多無人機多任務(wù)規(guī)劃模型函數(shù)進行求解，使無人機可以高效快速的執(zhí)行復(fù)雜任務(wù)。

1 相關(guān)理論

1.1 遺傳算法

遺傳算法是計算機科學(xué)人工智能領(lǐng)域中用于解決最優(yōu)化的一種搜索啟發(fā)式算法，從問題解的串集開始搜索，而不是從單個解開始。區(qū)別于傳統(tǒng)優(yōu)化算法，使其搜索覆蓋面大，利于全局擇優(yōu)。這種啟發(fā)式通常用來生成有用的解決方案來優(yōu)化和搜索問題。進化算法包括遺傳、突變、自然選擇以及雜交等步驟[5-8]。其基本運算過程如下：

（1）初始化：設(shè)置進化代數(shù)計數(shù)器t=0，設(shè)置最大進化代數(shù)T，隨機生成M個個體作為初始群體P(0)。

（2）個體評價：計算群體P(t)中各個個體的適應(yīng)度。

（3）選擇運算：將選擇算子作用于群體。選擇的目的是把優(yōu)化的個體直接遺傳到下一代或通過配對交叉產(chǎn)生新的個體再遺傳到下一代。選擇操作是建立在群體中個體的適應(yīng)度評估基礎(chǔ)上的。

（4）交叉運算：將交叉算子作用于群體。遺傳算法中起核心作用的就是交叉算子。

（5）變異運算：將變異算子作用于群體。即是對群體中的個體串的某些基因座上的基因值作變動。群體P(t)經(jīng)過選擇、交叉、變異運算之后得到下一代群體P(t+1)。

（6）終止條件判斷：若t=T，則以進化過程中所得到的具有最大適應(yīng)度個體作為最優(yōu)解輸出，終止計算。

本文利用遺傳算法在多無人機多任務(wù)規(guī)劃模型中通過遺傳、突變、自然選擇以及雜交等步驟尋找到最優(yōu)任務(wù)分配方式，使多無人機多任務(wù)規(guī)劃模型所收到的懲罰值最小。

1.2 A*算法

A*(A-Star)算法是一種靜態(tài)路網(wǎng)中求解最短路徑最有效的直接搜索方法，也是解決許多搜索問題的有效算法。算法中的距離估算值與實際值越接近，最終搜索速度越快。其公式表示為[9-15]：

F(n)=g(n)+h(n) （1）

式（1）中，F(xiàn)(n) 是從初始狀態(tài)經(jīng)由狀態(tài)n到目標狀態(tài)的代價估計，g(n)是在狀態(tài)空間中從初始狀態(tài)到狀態(tài)n的實際代價，h(n)是從狀態(tài)n到目標狀態(tài)的最佳路徑的估計代價。對于路徑搜索問題，狀態(tài)就是圖形的中心點，代價就是距離。

h(n)的選取

保證找到最短路徑（最優(yōu)解的）條件，關(guān)鍵在于估價函數(shù)f(n)的選?。ɑ蛘哒fh(n)的選?。?。

我們以d(n)表達狀態(tài)n到目標狀態(tài)的距離，那么h(n)的選取大致有如下三種情況：

如果h(n)＜d(n)到目標狀態(tài)的實際距離，這種情況下，搜索的點數(shù)多，搜索范圍大，效率低。但能得到最優(yōu)解。

如果h(n)=d(n)，即距離估計h(n)等于最短距離，那么搜索將嚴格沿著最短路徑進行， 此時的搜索效率是最高的。

如果 h(n)>d(n)，搜索的點數(shù)少，搜索范圍小，效率高，但不能保證得到最優(yōu)解。

本文利用A*(A-Star)算法解決無人機規(guī)避危險區(qū)域時的路徑最優(yōu)問題，在眾多路徑當中快速準確的選擇一條最優(yōu)路徑。在無人機執(zhí)行任務(wù)時可以安全快速的到達任務(wù)目標地點并安全順利的返航。

2 多無人機多任務(wù)模型的建立

2.1 任務(wù)問題描述

某地區(qū)擁有M個軍用機場，機場分布在不同的地理位置，每個機場均擁有Km(m=1,2,…,M)架無人機。機場m(m=1,2,…,M)的第k(k=1,2,…,Km)架飛機的載彈量為Qmk，平均速度Vmk。在T0時刻，在軍用機場周邊分布N個任務(wù)目標，且某些（個）任務(wù)對執(zhí)行時間有較嚴格的要求，任務(wù)i的執(zhí)行時間窗為[ETi, LTi]，執(zhí)行任務(wù)i需要的彈藥數(shù)量為Wi(i=0,1,2,…,F)。其中ETi表示任務(wù)目標i的最早執(zhí)行時間，LTi表示任務(wù)目標i最晚執(zhí)行時間。pmk1表示提前完成損失系數(shù)，即機場m的無人機k每提前單位時間到達的時間成本；mk2p表示延期完成懲罰系數(shù)，即機場m的無人機k每推遲單位時間到達的時間成本。當該地區(qū)收到對多個目標進行攻擊的任務(wù)時，可調(diào)用該地區(qū)所有的軍用無人機，且目標的數(shù)量、位置及時間窗是確定的；軍用機場的數(shù)量、位置，飛機的類型是已知的。

2.2 任務(wù)問題的分析

該問題不僅需要確定每個目標應(yīng)該由哪個軍用機場以及無人機去執(zhí)行，同時還要確定執(zhí)行任務(wù)的先后順序，且在不違反各個任務(wù)時間窗限制，飛機航程限制、火力威脅、探測威脅等約束條件下滿足代價最小化。具體符號如表1所示。

表1：模型中各參數(shù)的定義和范圍

根據(jù)上述描述，問題有如下的假設(shè)：

（1）軍用機場的位置及無人機種類、無人機數(shù)量、無人機時間窗已知。任務(wù)目標位置、完成任務(wù)所需彈藥量、任務(wù)執(zhí)行時間窗已知；

（2）每架無人機從機場起飛出發(fā)執(zhí)行任務(wù)最終又回到原機場；

（3）每個機場調(diào)度的無人機數(shù)量不能超過其所擁有的最大無人機數(shù)；

（4）每次任務(wù)中每架無人機能調(diào)度一次，且不得超過其最大載彈量；

（5）每個任務(wù)目標必須且只能由一架無人機完成；

（6）假設(shè)無人機飛行的高度有航管中心統(tǒng)一分配，不考慮飛機碰撞等特殊狀況。

構(gòu)建數(shù)學(xué)模型時，同時考慮多無人機多任務(wù)時間窗和客戶軟時間窗約束，根據(jù)違反客戶要求時間的長短施以相應(yīng)的懲罰，從而在目標函數(shù)增加相應(yīng)的時間成本。

2.3 建立數(shù)學(xué)模型

根據(jù)上述分析，設(shè)計帶時間窗和任務(wù)軟時間窗的多車場車輛路徑問題的數(shù)學(xué)模型為：

目標函數(shù)：

約束條件：

在上述模型中，式（6）表示無人機執(zhí)行任務(wù)航程與時間成本之和最小化；式（7）表示各個機場派出的無人機數(shù)不超過該機場的無人機總數(shù)；式（8）表示每一機型載彈量不超過其最大載彈量限制；式（9）表示一個任務(wù)目標只分配一個機場的一架無人機；式（10）、（11）表示兩個決策變量的關(guān)系；式（12）表示無人機從機場出發(fā)并最終返回原機場；式（13）表示分別考慮無人機運行狀態(tài)時，無人機到達任務(wù)點j的時間。

本文在傳統(tǒng)模型（6）的基礎(chǔ)上,首先考慮了無人機飛行范圍，即在視距范圍內(nèi)，一般無人機在飛行高度為6500米左右，通視距離約為300km，假設(shè)dim為目標點i與機場m之間的距離，則通視距離約束為：

其次考慮了無人機在執(zhí)行任務(wù)途中可能會遇到地面威脅，如果單純使用傳統(tǒng)模型而不考慮威脅因素的話，會降低整個系統(tǒng)的實用性，同時也不符合實際情況，因此需要增加威脅約束，由于中大型無人機飛行高度一般在海拔5000～8000米，因此暫不考慮地形威脅因素，僅考慮雷達探測威脅和地面火力威脅。威脅區(qū)域的范圍就用一個半徑為R的圓來簡單表示。

因此在考慮威脅約束后，式（6）目標函數(shù)可改進為：

其中THRij代表無人機從目標i點飛到目標j點所收到的威脅值，值越大代表威脅越大，若任務(wù)點之間連線與威脅圓相交，就用弦長度表示威脅值，如果與多個威脅圓相交，那弦長的和作為威脅值。

3 仿真分析

實驗環(huán)境為Windows 10 64 位操作系統(tǒng)，IntelCore i5 處理器，8 GB RAM，實驗工具為 Python 3.6。

3.1 多無人機多任務(wù)模型的仿真建立

在多無人機多任務(wù)模型的仿真建立前，確定機場數(shù)量為2,機場位置，通信覆蓋半徑等相關(guān)信息如表2。多無人機多任務(wù)模型暫定任務(wù)目標數(shù)量為12個，每個任務(wù)目標位置，所需武器量，任務(wù)時間窗口和服務(wù)時間等相關(guān)信息如表3。并確定了威脅區(qū)域位置與其威脅半徑如表4。最后形成了復(fù)雜真實場景圖，如圖1所示。

表2：機場信息

表3：目標信息

表4：威脅區(qū)域信息

圖1：復(fù)雜真實場景圖

3.2 最優(yōu)路徑建立

初始種群的特性對算法效率有著重要的影響，傳統(tǒng) GA 算法常用一種隨機搜索可行路徑的方法，此方法產(chǎn)生可行路徑的速度較快，但初始路徑質(zhì)量較差，而采用篩選法則效率低下，因此本文提出一種基于分段 A*算法的區(qū)域必經(jīng)點選擇策略生成初始種群的方法。根據(jù)以上相關(guān)信息仿真模擬真實復(fù)雜任務(wù)場景如圖2。并利用A-Star算法對無人機飛行路徑進行精細規(guī)劃，使其能繞過威脅區(qū)域的條件。如圖2所示，此仿真模型一共規(guī)劃出七條運行路線，分別由飛機場1規(guī)劃出兩條無人機執(zhí)行任務(wù)時的最優(yōu)路線，由飛機場2規(guī)劃出三條無人機執(zhí)行任務(wù)時的最優(yōu)路線，由飛機場3規(guī)劃出兩條無人機執(zhí)行任務(wù)時的最優(yōu)路線。并且每一組最優(yōu)路線都可以合理的避開模型中的威脅區(qū)域，以保證無人機在執(zhí)行任務(wù)時的安全。

圖2：仿真模擬真實復(fù)雜任務(wù)場景

3.3 多無人機多任務(wù)規(guī)劃模型函數(shù)求解

首先經(jīng)過對遺傳算子、突變算子、自然選擇算子以及雜交算子等一系列遺傳算法的算子進行改進與選擇。并確定合適的適應(yīng)度函數(shù)以保證最優(yōu)任務(wù)任務(wù)分配方式在選擇過程中的方向性。利用常規(guī)的初始種群選擇方式對多無人機多任務(wù)規(guī)劃模型函數(shù)的初始種群進行初始化。最后利用改進的遺傳算法對多無人機多任務(wù)規(guī)劃模型函數(shù)進行求解，以得到無人機的任務(wù)執(zhí)行的最優(yōu)順序。多無人機多任務(wù)規(guī)劃模型函數(shù)利用遺傳算法的求解過程如圖3，在與多無人機多任務(wù)規(guī)劃模型函數(shù)相結(jié)合的遺傳算法在運行到83代時已經(jīng)趨于最優(yōu)值，但此時在遺傳算法并未得到多無人機多任務(wù)規(guī)劃模型函數(shù)的最優(yōu)任務(wù)任務(wù)分配方式，在遺傳算法運行到第260代的時候得到了最優(yōu)任務(wù)任務(wù)分配方式。

圖3：多無人機多任務(wù)規(guī)劃模型函數(shù)求解過程

4 結(jié)論

本文利用多車場車輛路徑規(guī)劃模型，建立了多無人機多任務(wù)帶軟時間窗的規(guī)劃模型。并與實際相結(jié)合對無人機飛行時面臨的威脅的情況進行了考慮，在傳統(tǒng)模型上添加了威脅約束，再對無人機飛行路徑進行精細規(guī)劃，使其能繞過威脅區(qū)域。并利用改進的遺傳算法對所建立的模型進行分析求解，得到無人機的任務(wù)執(zhí)行的先后順序，使其能快速準確的繞過威脅區(qū)域。仿真的結(jié)果驗證了本文中設(shè)計方法的有效性。