基于進(jìn)化算法的多無(wú)人機(jī)協(xié)同航路規(guī)劃

李子杰，劉湘?zhèn)?/p>

（電子工程學(xué)院，合肥230037）

基于進(jìn)化算法的多無(wú)人機(jī)協(xié)同航路規(guī)劃

李子杰，劉湘?zhèn)?/p>

（電子工程學(xué)院，合肥230037）

以突防航路時(shí)域協(xié)同指數(shù)、空域協(xié)同指數(shù)、突防時(shí)長(zhǎng)指數(shù)和受威脅指數(shù)為規(guī)劃目標(biāo)，以最小直線航路段長(zhǎng)度、可飛空域、續(xù)航能力和進(jìn)入任務(wù)航路方向?yàn)榧s束，構(gòu)建了多無(wú)人機(jī)協(xié)同突防航路規(guī)劃模型。結(jié)合模型特點(diǎn)，利用合作型協(xié)同進(jìn)化遺傳算法對(duì)該模型進(jìn)行求解。

無(wú)人機(jī)，協(xié)同航路規(guī)劃，合作型協(xié)同進(jìn)化遺傳算法

0 引言

多無(wú)人機(jī)協(xié)同是未來(lái)無(wú)人機(jī)運(yùn)用的主要樣式，多無(wú)人機(jī)協(xié)同航路規(guī)劃在很大程度上決定了多無(wú)人機(jī)協(xié)同效能的發(fā)揮，是當(dāng)下無(wú)人機(jī)航路規(guī)劃研究的重點(diǎn)。多無(wú)人機(jī)協(xié)同航路規(guī)劃主要是時(shí)間和空間上的協(xié)同［1］?，F(xiàn)有關(guān)于多無(wú)人機(jī)協(xié)同航路規(guī)劃的研究，側(cè)重于首先對(duì)多架無(wú)人機(jī)單獨(dú)進(jìn)行航路規(guī)劃，在較優(yōu)種群中以編隊(duì)預(yù)計(jì)到達(dá)目標(biāo)時(shí)間ETA（Estimated Team Arrival Time）作為協(xié)同變量對(duì)多架無(wú)人機(jī)飛行航路組合評(píng)價(jià)［2-4］，尋求滿足協(xié)同條件的飛行航路組合。本文通過(guò)引入突防航路時(shí)域協(xié)同指數(shù)、突防航路空域協(xié)同指數(shù)，對(duì)遂行干擾任務(wù)的多無(wú)人機(jī)協(xié)同突防航路正面建模，并根據(jù)模型特點(diǎn)，利用合作型協(xié)同進(jìn)化遺傳算法對(duì)模型進(jìn)行求解。

1 協(xié)同航路分析

遂行干擾任務(wù)的無(wú)人機(jī)飛行航路主要包括突防航路和任務(wù)航路，如下頁(yè)圖1所示。發(fā)射陣地YFront1，j發(fā)射兩組無(wú)人機(jī)，沿突防航路AssRoute1，j，1和Ass-Route1，j，2，進(jìn)入任務(wù)航路MisRoute1和MisRoute2；發(fā)射陣地YFronti，j發(fā)射兩組無(wú)人機(jī)，分別沿突防航路Ass-Route1，j，2和AssRoutei，j，r，進(jìn)入任務(wù)航路MisRoute2和MisRouter；發(fā)射陣地YFrontNumFR，j發(fā)射兩組無(wú)人機(jī)，沿突防航路AssRouteNumFR，j，r和AssRouteNumFR，j，NumR，進(jìn)入任務(wù)航路MisRouter和MisRouteNumR。

圖1 無(wú)人機(jī)協(xié)同航路示意圖

突防航路規(guī)劃同時(shí)受發(fā)射陣地中無(wú)人機(jī)的發(fā)射時(shí)間長(zhǎng)度限制和到達(dá)任務(wù)航路時(shí)間區(qū)間限制。多架無(wú)人機(jī)應(yīng)該在確定的時(shí)間區(qū)間內(nèi)到達(dá)任務(wù)航路；由同一發(fā)射陣地起飛的多架無(wú)人機(jī)發(fā)射持續(xù)時(shí)間應(yīng)控制在一定時(shí)間長(zhǎng)度內(nèi)，以避免來(lái)自敵方火力的報(bào)復(fù)性打擊。

本文在已知無(wú)人機(jī)任務(wù)航路基礎(chǔ)上開(kāi)展無(wú)人機(jī)協(xié)同突防航路規(guī)劃研究，多無(wú)人機(jī)協(xié)同突防航路可表示為：

2 協(xié)同突防航路規(guī)劃建模

2.1 協(xié)同突防航路規(guī)劃目標(biāo)函數(shù)

多無(wú)人機(jī)協(xié)同突防航路規(guī)劃主要考慮4個(gè)規(guī)劃目標(biāo)函數(shù)：突防航路時(shí)域協(xié)同指數(shù)、突防航路空域協(xié)同指數(shù)、受威脅指數(shù)、突防時(shí)長(zhǎng)指數(shù)。

2.1.1 突防航路時(shí)域協(xié)同指數(shù)

在同一條任務(wù)航路上遂行壓制干擾任務(wù)的無(wú)人機(jī)可由同一發(fā)射陣地發(fā)射升空，也可由不同發(fā)射陣地發(fā)射升空，這些來(lái)自不同發(fā)射陣地的無(wú)人機(jī)最終需要在任務(wù)航路上等間距飛行。為了防止不必要的沖突，有必要對(duì)來(lái)自不同發(fā)射陣地的不同無(wú)人機(jī)到達(dá)任務(wù)航路時(shí)間窗進(jìn)行明確。在確定各無(wú)人機(jī)到達(dá)任務(wù)航路時(shí)間窗之前，首先應(yīng)該確定不同無(wú)人機(jī)到達(dá)任務(wù)航路的先后順序。這一順序可由指揮員根據(jù)任務(wù)分配方案予以指定。來(lái)自不同發(fā)射陣地的無(wú)人機(jī)相繼到達(dá)任務(wù)航路，調(diào)整無(wú)人機(jī)間距，以滿足對(duì)雷達(dá)干擾要求。

圖2 無(wú)人機(jī)到達(dá)任務(wù)航路時(shí)間窗分解示意圖

如圖2所示，無(wú)人機(jī)任務(wù)航路長(zhǎng)度為L(zhǎng)ength（MisRoute），對(duì)應(yīng)的任務(wù)航路周期為Tstd，無(wú)人機(jī)分別來(lái)自NFr個(gè)發(fā)射陣地，每個(gè)發(fā)射陣地NumUn架無(wú)人機(jī)。來(lái)自發(fā)射陣地YFrontn的無(wú)人機(jī)到達(dá)任務(wù)航路的時(shí)間窗寬度為：

如圖1所示，設(shè)發(fā)射陣地YFront1，j起飛的兩批無(wú)人機(jī)到達(dá)任務(wù)航路的時(shí)間區(qū)間分別為和，突防航路耗時(shí)分別為△t1，j，1和△t2，j，2，與之對(duì)應(yīng)的發(fā)射時(shí)間窗為：

如圖3所示，一個(gè)發(fā)射陣地發(fā)射兩個(gè)批次無(wú)人機(jī)至任務(wù)航路MisRoute1和MisRoute2。假設(shè)航路相同的多架無(wú)人機(jī)被連續(xù)發(fā)射，只需計(jì)算第1架無(wú)人機(jī)提前到達(dá)的時(shí)間或最后一架無(wú)人機(jī)推遲到達(dá)的時(shí)間即可。本文以無(wú)人機(jī)編隊(duì)推遲時(shí)間（提前時(shí)間）之和的最小值△tmin來(lái)評(píng)價(jià)是否協(xié)同。

圖3 無(wú)人機(jī)發(fā)射時(shí)長(zhǎng)計(jì)算示意圖

將起始于發(fā)射陣地Fronti的突防航路時(shí)域協(xié)同指數(shù)表述為：

將所有發(fā)射陣地對(duì)應(yīng)突防航路時(shí)域協(xié)同指數(shù)累加，即可得到多無(wú)人機(jī)的時(shí)域協(xié)同指數(shù)：

2.1.2 突防航路空域協(xié)同指數(shù)

航路如果存在交叉，則有可能發(fā)生碰撞，交叉部分越多，無(wú)人機(jī)發(fā)生碰撞的概率就越大。突防航路空域協(xié)同指數(shù)是對(duì)飛行航路在空間發(fā)生交叉情況的度量。對(duì)于突防航路AssRoutei，j，r，其空域協(xié)同指數(shù)就是其航程點(diǎn)數(shù)，減去與其他突防航路交叉點(diǎn)后的數(shù)量，占自己航程點(diǎn)總數(shù)的比值：

其中，NumNi，j，r為突防航路AssRoutei，j，r航程點(diǎn)數(shù)；NumJCi，j，r為AssRoutei，j，r與其他航路發(fā)生交叉的航程點(diǎn)數(shù)。

多無(wú)人機(jī)協(xié)同突防航路空域協(xié)同指數(shù)可表述為：

2.1.3 突防時(shí)長(zhǎng)指數(shù)

突防航路是無(wú)人機(jī)飛行航路的一部分，為了減少燃料消耗，將更多的滯空時(shí)間用于遂行干擾任務(wù)，引入突防時(shí)長(zhǎng)指數(shù)，用于引導(dǎo)無(wú)人機(jī)選擇耗時(shí)較短的突防航路。突防時(shí)長(zhǎng)指數(shù)最短指標(biāo)可表述為：

其中，length（AssRoutei，j，r）為突防航路AssRoutei，j，r長(zhǎng)度；vi，j，r為航路AssRoutei，j，r上相應(yīng)無(wú)人機(jī)飛行速度最小值（m/s）。

2.1.4 受威脅指數(shù)

受威脅指數(shù)與無(wú)人機(jī)自身性能相關(guān)，在突防航路AssRoutei，j，r上的無(wú)人機(jī)受威脅程度thi，j，r為被發(fā)現(xiàn)概率和被毀傷概率之和。無(wú)人機(jī)受威脅指數(shù)可表述為：

2.2 協(xié)同突防航路規(guī)劃約束

協(xié)同支援偵察突防航路規(guī)劃約束包括最小直線航路段長(zhǎng)度約束、可飛空域約束、續(xù)航能力約束和進(jìn)入任務(wù)航路方向約束。其中，最小直線航路段長(zhǎng)度約束與一般無(wú)人機(jī)相同；進(jìn)入任務(wù)航路方向約束是為了保證無(wú)人機(jī)突防航路末端時(shí)，無(wú)需調(diào)整，直接進(jìn)入任務(wù)航路直線段而提出的。在具體操作中，在任務(wù)航路直線段延長(zhǎng)線上取一點(diǎn)作為突防航路航程點(diǎn)。下面主要介紹可飛空域約束和續(xù)航能力約束。

2.2.1 可飛空域約束

無(wú)人機(jī)飛行空域內(nèi)包括不可穿越威脅、雷達(dá)探測(cè)威脅和火力毀傷威脅。不可穿越威脅包括兩類：第1類是地形障礙、禁飛區(qū)、氣象威脅、電子干擾威脅區(qū)等；第2類是其他飛行器已經(jīng)占據(jù)且不可共用的空域，如空中進(jìn)攻編隊(duì)所占據(jù)空域等。在本文的討論中，將第1類不可穿越威脅區(qū)等效為一定半徑的圓形區(qū)域，將第2類不可穿越威脅區(qū)等效為該區(qū)域的最小外接多邊形區(qū)域。

突防航路以保證無(wú)人機(jī)按時(shí)、安全到達(dá)任務(wù)區(qū)域?yàn)槟繕?biāo)，其可飛空域應(yīng)盡量避免防空威脅。但是，在某些特殊情況下，仍然可以一定被毀傷概率進(jìn)入防空火力威脅區(qū)，防空火力威脅區(qū)一般等效為一定半徑的圓形區(qū)域。設(shè)可飛空域?yàn)镴oiAss Deploy，可飛空域約束可表述為：

2.2.2 續(xù)航能力約束

已知無(wú)人機(jī)任務(wù)航路和干擾任務(wù)持續(xù)時(shí)間要求，無(wú)人機(jī)續(xù)航能力約束可表述為：

2.3 協(xié)同突防航路規(guī)劃模型

前述規(guī)劃目標(biāo)中存在取大和取小兩種類型，為表述方便，本文統(tǒng)一對(duì)4個(gè)規(guī)劃目標(biāo)分量取小，首先對(duì)規(guī)劃目標(biāo)1和規(guī)劃目標(biāo)2做如下處理：

綜合前述關(guān)于無(wú)人機(jī)協(xié)同突防航路規(guī)劃目標(biāo)函數(shù)和約束的分析，建立其協(xié)同突防航路規(guī)劃模型如下所示：

3 基于合作型協(xié)同進(jìn)化遺傳算法的協(xié)同航路規(guī)劃模型求解

3.1 算法結(jié)構(gòu)

如圖4所示為求解無(wú)人機(jī)協(xié)同航路規(guī)劃模型的合作型協(xié)同進(jìn)化遺傳算法結(jié)構(gòu)。隨機(jī)生成多條飛行航路，構(gòu)成無(wú)人機(jī)飛行航路子種群，即圖4中的“無(wú)人機(jī)子種群1”、“無(wú)人機(jī)子種群2”……。無(wú)人機(jī)子種群個(gè)數(shù)取決于遂行任務(wù)的無(wú)人機(jī)組數(shù)，當(dāng)僅有一組無(wú)人機(jī)時(shí)，合作型協(xié)同進(jìn)化遺傳算法退化為普通遺傳算法。

圖4 合作型協(xié)同進(jìn)化遺傳算法結(jié)構(gòu)

合作型協(xié)同進(jìn)化遺傳算法不同于普通遺傳算法，主要體現(xiàn)在種群構(gòu)成和適應(yīng)度計(jì)算。合作型協(xié)同進(jìn)化遺傳算法將長(zhǎng)的染色體編碼分組為多個(gè)短的染色體編碼，即將決策變量分組，每一個(gè)短編碼各自形成一個(gè)子種群，子種群獨(dú)立進(jìn)化。在個(gè)體評(píng)價(jià)時(shí)，由于一個(gè)子種群的基因只代表航路規(guī)劃決策變量的一部分，需要將一個(gè)子種群的基因與其他子種群的基因結(jié)合，形成一個(gè)完整的航路規(guī)劃解。如圖4所示，在對(duì)無(wú)人機(jī)子種群1內(nèi)的個(gè)體進(jìn)行評(píng)價(jià)時(shí)，首先分別從無(wú)人機(jī)子種群2、無(wú)人機(jī)子種群3和無(wú)人機(jī)子種群4中選擇一部分個(gè)體作為代表個(gè)體，與子種群1中個(gè)體結(jié)合，根據(jù)目標(biāo)函數(shù)，對(duì)結(jié)合后的個(gè)體進(jìn)行評(píng)價(jià)，評(píng)價(jià)結(jié)果作為子種群1內(nèi)個(gè)體的適應(yīng)度值；爾后依次計(jì)算無(wú)人機(jī)子種群2、3、 4內(nèi)個(gè)體適應(yīng)度值，并據(jù)此作為子種群遺傳操作的依據(jù)［5］。由于存在多個(gè)目標(biāo)函數(shù)，在求解個(gè)體適應(yīng)度值時(shí)要綜合考慮個(gè)體的多個(gè)目標(biāo)函數(shù)。構(gòu)建效用函數(shù)，將多目標(biāo)函數(shù)轉(zhuǎn)化為單目標(biāo)函數(shù)，進(jìn)而求出個(gè)體適應(yīng)度值。

3.2 算法流程

求解多無(wú)人機(jī)協(xié)同航路規(guī)劃模型合作型協(xié)同進(jìn)化遺傳算法流程如圖5所示。

圖5 無(wú)人機(jī)協(xié)同航路規(guī)劃的合作型協(xié)同進(jìn)化遺傳算法流程

求解無(wú)人機(jī)協(xié)同航路規(guī)劃模型的合作型協(xié)同進(jìn)化遺傳算法步驟如下［5］：

步驟1：初始化無(wú)人機(jī)子種群；

步驟2：從其他無(wú)人機(jī)子種群中選擇代表個(gè)體，與待評(píng)價(jià)無(wú)人機(jī)子種群個(gè)體構(gòu)成合作團(tuán)隊(duì)，對(duì)無(wú)人機(jī)個(gè)體進(jìn)行評(píng)價(jià)；

步驟3：對(duì)無(wú)人機(jī)子種群進(jìn)行選擇、交叉和變異等進(jìn)化操作，生成新的無(wú)人機(jī)子種群；

步驟4：判斷算法終止條件是否滿足，若滿足，終止種群進(jìn)化，將所有無(wú)人機(jī)飛行航路綜合，輸出優(yōu)化結(jié)果；否則，轉(zhuǎn)步驟2。

3.3 仿真分析

無(wú)人機(jī)協(xié)同突防航路規(guī)劃，在已知任務(wù)分配方案和任務(wù)航路基礎(chǔ)上展開(kāi)［6］。無(wú)人機(jī)突防航路的起點(diǎn)是發(fā)射陣地，終點(diǎn)是任務(wù)航路上的任務(wù)轉(zhuǎn)換點(diǎn)。設(shè)無(wú)人機(jī)發(fā)射陣地和任務(wù)轉(zhuǎn)換點(diǎn)如表1所示。

初始化5個(gè)無(wú)人機(jī)航路子種群、每個(gè)子種群個(gè)體數(shù)量50，迭代代數(shù)50，交叉概率0.75，變異概率0.1，仿真結(jié)果如圖6、圖7所示：

圖6 第30代和第50代最優(yōu)個(gè)體

如圖6（b）所示，5條無(wú)人機(jī)突防航路均能繞開(kāi)敵地面防空火力威脅，到達(dá)指定終點(diǎn)。表2所示為第50代種群中最優(yōu)的5條無(wú)人機(jī)協(xié)同突防航路航程點(diǎn)坐標(biāo)。

表2 第50代最優(yōu)航路航程點(diǎn)坐標(biāo)

圖7所示為無(wú)人機(jī)協(xié)同突防航路種群各目標(biāo)函數(shù)值隨迭代代數(shù)的變化關(guān)系。其中，突防航路時(shí)域協(xié)同指數(shù)平均值趨近于4的水平，突防航路空域協(xié)同指數(shù)呈上升趨勢(shì)，且保持在很高水平，反映出無(wú)人機(jī)突防航路表現(xiàn)出良好的時(shí)域協(xié)同和空域協(xié)同關(guān)系。受威脅指數(shù)隨迭代代數(shù)逐漸降低。突防時(shí)長(zhǎng)指數(shù)通過(guò)一定代數(shù)的起伏，最后收斂于一個(gè)穩(wěn)定值。

圖7 目標(biāo)函數(shù)值與迭代代數(shù)關(guān)系

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

共同遂行壓制干擾任務(wù)的多架無(wú)人機(jī)突防航路在時(shí)域和空域上存在協(xié)同關(guān)系。本文從這種時(shí)域和空域上的協(xié)同關(guān)系入手，構(gòu)建了多無(wú)人機(jī)協(xié)同突防航路規(guī)劃模型。結(jié)合模型特點(diǎn)，利用合作型協(xié)同進(jìn)化遺傳算法對(duì)該模型進(jìn)行求解，得到的多無(wú)人機(jī)突防航路表現(xiàn)出良好的時(shí)域、空域協(xié)同效果。

［1］黃長(zhǎng)強(qiáng)，翁興偉，王勇，等.多無(wú)人機(jī)協(xié)同作戰(zhàn)技術(shù)［M］.北京：國(guó)防工業(yè)出版社，2012.

［2］朱收濤，曹林平，翁興偉，等.采用改進(jìn)粒子群算法的無(wú)人機(jī)協(xié)同航跡規(guī)劃［J］.電光與控制，2012，19（12）：29-33.

［3］楊力.無(wú)人機(jī)航路規(guī)劃技術(shù)研究［D］.南京：南京航空航天大學(xué)，2009.

［4］辛亭.多無(wú)人機(jī)協(xié)同作戰(zhàn)關(guān)鍵技術(shù)研究［D］.南京：南京航空航天，2009.

［5］鞏敦衛(wèi)，孫曉燕.協(xié)同進(jìn)化遺傳算法理論及應(yīng)用［M］.北京：科學(xué)出版社，2009.

［6］李少華，魏海光，周成平，等.一種海上無(wú)人飛行器的快速航跡規(guī)劃方法［J］.四川兵工學(xué)報(bào)，2011，32（12）：73-76.

Cooperative Path Planning of Multi-UAV Based on Evolutionary Algorithm

LI Zi-jie,LIU Xiang-wei
（Electronic Engineering Institute,Hefei 230037，China）

Aiming at maximizing penetration path time synergy index and penetration path airspace synergy index,minimizing penetration time length index and intimidate index,restricted by the minimum length of straight path,flyable space,endurance and intro-mission route direction,the penetration path planning model of Multiple Unmanned Serial Vehicle（Multi-UAV）is constructed. Combining its characteristic,the model is solved by use of Cooperative Co-evolutionary Genetic Algorithms（CCGA）

Unmanned AerialVehicle（UAV），cooperativepath planning，CooperativeCo-evolutionary GeneticAlgorithms（CCGA）

TN974

A

1002-0640（2015）02-0085-05

2013-12-21

2014-01-23

李子杰（1986-），男，湖南常德人，博士研究生。研究方向：信息對(duì)抗裝備作戰(zhàn)運(yùn)用與運(yùn)籌分析。