王超 于德洋 王子強(qiáng) 呂松天 牟洋

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

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

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

1 相關(guān)理論

1.1 遺傳算法

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

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

（2）個(gè)體評(píng)價(jià)：計(jì)算群體P(t)中各個(gè)個(gè)體的適應(yīng)度。

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

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

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

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

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

1.2 A*算法

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

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

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

h(n)的選取

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

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

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

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

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

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

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

2.1 任務(wù)問(wèn)題描述

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

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

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

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

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

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

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

（3）每個(gè)機(jī)場(chǎng)調(diào)度的無(wú)人機(jī)數(shù)量不能超過(guò)其所擁有的最大無(wú)人機(jī)數(shù)；

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

（5）每個(gè)任務(wù)目標(biāo)必須且只能由一架無(wú)人機(jī)完成；

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

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

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

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

目標(biāo)函數(shù)：

約束條件：

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

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

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

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

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

3 仿真分析

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

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

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

表2：機(jī)場(chǎng)信息

表3：目標(biāo)信息

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

圖1：復(fù)雜真實(shí)場(chǎng)景圖

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

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

圖2：仿真模擬真實(shí)復(fù)雜任務(wù)場(chǎng)景

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

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

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

4 結(jié)論

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