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

（電子工程學院，合肥230037）

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

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

（電子工程學院，合肥230037）

以突防航路時域協(xié)同指數、空域協(xié)同指數、突防時長指數和受威脅指數為規(guī)劃目標，以最小直線航路段長度、可飛空域、續(xù)航能力和進入任務航路方向為約束，構建了多無人機協(xié)同突防航路規(guī)劃模型。結合模型特點，利用合作型協(xié)同進化遺傳算法對該模型進行求解。

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

0 引言

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

1 協(xié)同航路分析

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

圖1 無人機協(xié)同航路示意圖

突防航路規(guī)劃同時受發(fā)射陣地中無人機的發(fā)射時間長度限制和到達任務航路時間區(qū)間限制。多架無人機應該在確定的時間區(qū)間內到達任務航路；由同一發(fā)射陣地起飛的多架無人機發(fā)射持續(xù)時間應控制在一定時間長度內，以避免來自敵方火力的報復性打擊。

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

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

2.1 協(xié)同突防航路規(guī)劃目標函數

多無人機協(xié)同突防航路規(guī)劃主要考慮4個規(guī)劃目標函數：突防航路時域協(xié)同指數、突防航路空域協(xié)同指數、受威脅指數、突防時長指數。

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

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

圖2 無人機到達任務航路時間窗分解示意圖

如圖2所示，無人機任務航路長度為Length（MisRoute），對應的任務航路周期為Tstd，無人機分別來自NFr個發(fā)射陣地，每個發(fā)射陣地NumUn架無人機。來自發(fā)射陣地YFrontn的無人機到達任務航路的時間窗寬度為：

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

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

圖3 無人機發(fā)射時長計算示意圖

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

將所有發(fā)射陣地對應突防航路時域協(xié)同指數累加，即可得到多無人機的時域協(xié)同指數：

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

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

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

多無人機協(xié)同突防航路空域協(xié)同指數可表述為：

2.1.3 突防時長指數

突防航路是無人機飛行航路的一部分，為了減少燃料消耗，將更多的滯空時間用于遂行干擾任務，引入突防時長指數，用于引導無人機選擇耗時較短的突防航路。突防時長指數最短指標可表述為：

其中，length（AssRoutei，j，r）為突防航路AssRoutei，j，r長度；vi，j，r為航路AssRoutei，j，r上相應無人機飛行速度最小值（m/s）。

2.1.4 受威脅指數

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

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

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

2.2.1 可飛空域約束

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

突防航路以保證無人機按時、安全到達任務區(qū)域為目標，其可飛空域應盡量避免防空威脅。但是，在某些特殊情況下，仍然可以一定被毀傷概率進入防空火力威脅區(qū)，防空火力威脅區(qū)一般等效為一定半徑的圓形區(qū)域。設可飛空域為JoiAss Deploy，可飛空域約束可表述為：

2.2.2 續(xù)航能力約束

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

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

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

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

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

3.1 算法結構

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

圖4 合作型協(xié)同進化遺傳算法結構

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

3.2 算法流程

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

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

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

步驟1：初始化無人機子種群；

步驟2：從其他無人機子種群中選擇代表個體，與待評價無人機子種群個體構成合作團隊，對無人機個體進行評價；

步驟3：對無人機子種群進行選擇、交叉和變異等進化操作，生成新的無人機子種群；

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

3.3 仿真分析

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

初始化5個無人機航路子種群、每個子種群個體數量50，迭代代數50，交叉概率0.75，變異概率0.1，仿真結果如圖6、圖7所示：

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

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

表2 第50代最優(yōu)航路航程點坐標

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

圖7 目標函數值與迭代代數關系

4 結束語

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

［1］黃長強，翁興偉，王勇，等.多無人機協(xié)同作戰(zhàn)技術［M］.北京：國防工業(yè)出版社，2012.

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

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

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

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

［6］李少華，魏海光，周成平，等.一種海上無人飛行器的快速航跡規(guī)劃方法［J］.四川兵工學報，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-），男，湖南常德人，博士研究生。研究方向：信息對抗裝備作戰(zhàn)運用與運籌分析。