王永成，蔡晨曉

（1.鄭州航空工業(yè)管理學院管理工程學院，河南鄭州 450046；2.南京理工大學自動化學院，江蘇南京 210094）

1 引言

無人機因體積小、安全性高、制造成本低等優(yōu)勢被廣泛應用在軍事、科研和民用等領(lǐng)域，主要分為直升機、飛艇、傘翼機等類型。無人機執(zhí)行任務不受飛行人員身體機能限制，當執(zhí)行危險任務時可避免飛行人員傷亡。從某種意義上來說，無人機可被看作是空中機器人，隨著研究的不斷深入，其應用類型逐漸擴展，完成任務的難度也在增強，有時需要多個無人機共同協(xié)作執(zhí)行某項任務，這對其控制和規(guī)劃能力要求極為嚴格。通常情況下，無人機任務規(guī)劃可表示為：在符合所有作戰(zhàn)指標情況下，以實現(xiàn)任務為目標，為所有參與工作的無人機分配任務，以保證無人機以最小的代價高效完成任務，無人機的任務規(guī)劃效率可影響其任務的完成效率。

目前，越來越多的學者投入到任務規(guī)劃等研究中，文獻［1］中將粒子群優(yōu)化與模擬退火算法相結(jié)合，綜合分析無人機物理約束條件，將航跡長度和威脅代價最小為目標函數(shù)，利用Voronoi圖規(guī)劃航跡，再通過模擬退火粒子群算法求解任務規(guī)劃的最優(yōu)解。文獻［2］中研究一種人工蜂群無人機任務規(guī)劃算法。構(gòu)建目標價值隨時間參數(shù)變化的任務規(guī)劃模型，結(jié)合決策示意圖合理規(guī)劃任務；通過整數(shù)編碼方式優(yōu)化人工蜂群算法，利用該方法求解無人機最佳任務執(zhí)行路徑，實現(xiàn)任務規(guī)劃。

通常情況下上述方法都能獲得理想的任務規(guī)劃效果，但是，無人機的工作環(huán)境動態(tài)性較強，當無人機發(fā)生意外或出現(xiàn)新增任務時，這些方法難以重新規(guī)劃任務?；诖耍瑢⒚庖咚惴ㄓ玫綗o人機任務規(guī)劃中。免疫算法模仿生物免疫系統(tǒng)［3］，其中，包括抗原、抗體等主要結(jié)構(gòu)。抗原即為規(guī)劃問題，抗體就是產(chǎn)生的可行解，利用親和度描述可行解質(zhì)量。結(jié)合飛機動力學約束與任務約束［4］，構(gòu)建算法數(shù)學模型，設(shè)計編碼方式，引入禁忌準則，設(shè)定算法終止條件，將免疫算法有效應用在任務規(guī)劃中，提高無人機任務執(zhí)行效率。

2 免疫算法在多無人機任務最優(yōu)規(guī)劃中的應用研究

2.1 無人機自身動力學約束條件分析

為安全起見，無人機在任務執(zhí)行過程中必須滿足自身動力學系統(tǒng)約束。在三維空間內(nèi)，無人機除了要考慮垂直方向的約束條件外，還需滿足如下幾點約束。

2.1.1 俯仰角度

規(guī)劃無人機任務時，受機動性能、氣候環(huán)境和飛行高度等方面影響［5］，需要著重考慮機身所能承受的大爬升角。如果將最大俯仰角度設(shè)置為θmax，則由某點(x，y，z)爬升到某點(x′，y′，z′) 時爬升角度必須符合如下條件：

式中：a—一個向量。式（1）還可以描述為：

2.1.2 偏航角度

在水平空間內(nèi)無人機滿足的最大角度變化要求，即為偏航角度約束，表示為ηmax。

假設(shè)無人機從點O開始起飛，經(jīng)過O′點，最終到達O′′。向量=(x?x′，y?y′)，則偏航角度有：

2.1.3 飛行高度

無人機在執(zhí)行任務過程中，受到自身物理性能限制，飛行高度上限記做hmax。此外，為避免無人機撞擊到建筑物，設(shè)定飛行的最低限制為hmin。無人機的最佳飛行高度應在二者之間，表示為：

2.2 基于免疫算法的無人機任務最優(yōu)規(guī)劃模型

免疫算法包括抗原、抗體、親和力計算、免疫記憶和種群更新等方面組成。要想將免疫算法合理的應用在無人機任務規(guī)劃中，必須分別對這些模塊進行詳細分析。

2.2.1 抗原生成

抗原即為待解決問題的數(shù)學模型［6］，通過構(gòu)造任務規(guī)劃問題的各類約束條件和目標函數(shù)，初始化部分參數(shù)，構(gòu)建任務最優(yōu)規(guī)劃的數(shù)學模型。

假設(shè)利用描述多無人機任務規(guī)劃問題，E表示任務所處環(huán)境，V代表所有無人機集合，無人機從起點起飛完成任務后返回到指定地點。假設(shè)起點總數(shù)量為m，其中第a個起點的無人機集合為Va={，，...，}。T={T1，T2，...，TN}描述Nv個目標任務集合，且每個目標的價值γj也不同，C是全部約束條件的集合。將這些任務規(guī)劃給無人機時，必須確保整體效益最大。則構(gòu)建的目標函數(shù)如下：

式中：A—屬于權(quán)重系數(shù)；B—屬于權(quán)重系數(shù)；f1—整體利益；f2—路徑；f3—威脅代價；α—調(diào)節(jié)因子。f1、f2和f3的表達式如下：

式中：Nv—目標任務個數(shù)；γj—目標j的價值；—第a個起點中無人機i完成任務Tj之后是否繼續(xù)執(zhí)行目標任務Tk；—第a個起點處，無人機i完成任務Tj后是否返回到起點。

rmax—最大風險。

—目標Tj和起始點之間的距離。

任務規(guī)劃除了將上述函數(shù)作為目標外，還需要滿足如下幾個要求：

（1）某架無人機在完成目標j后，后續(xù)目標僅能有一個，通過下述公式表示：

（2）無人機不能執(zhí)行已經(jīng)執(zhí)行完的任務：

（3）所有無人機的飛行距離必須小于或等于工作半徑：

式中：R—無人機工作半徑。

（4）必須確保全部任務都被規(guī)劃到：

2.2.2 抗體群生成

抗體即為通過合理的編碼方式，結(jié)合先驗知識生成初始抗體群。無人機在工作過程中，需要分析運動狀況。為方便分析，通過柵格法將三維空間分割為若干個層次［7］，每一次僅分析單個層次內(nèi)的運動狀況。主要目的是在符合無人機動力學約束條件下，確保航程最小。

編碼是否合理直接關(guān)系到操作算子性能，根據(jù)無人機航線規(guī)劃特征，利用數(shù)字符串編碼方法。算法的主要思想是利用字符串表示抗體，保證其中所有元素都與某坐標點(L，H)相對應，L與H分別代表維度和高度。通過構(gòu)建數(shù)字高程地圖，確定編碼長度是42，并使用（2×42）矩陣構(gòu)成的基因描述無人機航線。矩陣首列是[1，42 ]區(qū)間內(nèi)的整數(shù)Lat= 29 + 0.01(L?1)，利用公式將具體數(shù)值變換為維度。同理，也可解碼高度，達到地理信息與基因編碼相互轉(zhuǎn)換的目的［8］。

通過隨機數(shù)生成原始種群，網(wǎng)格數(shù)量決定了編碼長度，因少數(shù)網(wǎng)格節(jié)點在地形下方，所以建立失效節(jié)點列表來存放無效網(wǎng)格點。當有種群生成時，基因節(jié)點必須為有效節(jié)點才能加入，基因編碼方式如下：

式（13）所示的矩陣能夠表示出完整的飛行軌跡。

抗體生成后，需計算抗體之間的親和度，也就是空間距離，距離越近表示抗體間相似程度越高，種群多樣性特征不明顯，容易陷入局部最優(yōu)。例如抗體p和q的親密度公式如下：

式中：Qp—抗體p在解集空間中的點解；

Qq—抗體q在解集空間中的點解。

2.2.3 免疫記憶種群更新

免疫記憶即為將現(xiàn)階段種群內(nèi)親和力較高的抗體添加到記憶種群中［9］。在迭代過程中，將親和力最佳的抗體與記憶種群對比，若適應值高于記憶種群的適應度，則進行替換，反之不變。具體方法如下：（1）選取抗體適應度最佳的o個抗體，將其保存到外部抗體群Mbest中，若種群規(guī)模沒有達到標準，則繼續(xù)接受更新。（2）將網(wǎng)格內(nèi)適應度最佳的o個抗體加入到記憶種群內(nèi)，當種群規(guī)模高于設(shè)定規(guī)模Ko時，將超出部分中適應度較低的抗體刪除，始終保持|Mbest|=Ko。

2.2.4 高頻變異

在免疫算法中，要想保證抗體的成熟與多樣性等特征，需通過高頻變異的形式實現(xiàn)。此種操作的實質(zhì)是結(jié)合抗體間親和度的大小，克隆抗體細胞［10］。該過程可利用下述公式描述：

式中：Gc—經(jīng)過克隆的抗體種群規(guī)模；

Int( )—取整函數(shù)；

f(Xu)—第u個個體親和度。

經(jīng)高頻變異后，親和度高的抗體產(chǎn)生多個鏡像，保持原有抗體良好的特征，改善了規(guī)劃空間的搜索性能。

2.2.5 禁忌準則與終止條件確定

為改善算法收斂速度，設(shè)置禁忌準則，核心思想就是標記局部最優(yōu)解，在下一輪迭代時避開這些最優(yōu)解，將親和度沒有變化的個體加入到禁忌項中。如果項中的個體禁忌數(shù)量高于設(shè)定閾值，則特赦個體，擴大搜索空間，保證持續(xù)的搜索能力，避免迂回搜索。

算法停止條件通常為滿足設(shè)定的迭代次數(shù)。此外，在某迭代周期內(nèi)，如果沒有尋找到適應度更好的抗體，算法也會停止。停止算法后，當前模型輸出的結(jié)果即為最終規(guī)劃方案。

3 實驗分析

3.1 實驗環(huán)境設(shè)置

為驗證所提方法在無人機多任務規(guī)劃中的應用性能，選取根據(jù)無人機具體結(jié)構(gòu)建立數(shù)據(jù)模型，進行多任務規(guī)劃模擬，掌握無人機的位置與姿態(tài)。本次實驗在一臺運行內(nèi)存為8GB 的Win?dows 10 系統(tǒng)中實施，利用matlab軟件中的simunik動態(tài)仿真組件完成控制模型的建立及仿真，通過傳輸指令控制無人機運動。

無人機相關(guān)參數(shù)，如表1所示。

表1 無人機參數(shù)指標Tab.1 Parameter Index of UAV

免疫算法參數(shù)設(shè)置，如表2所示。

表2 免疫算法參數(shù)指標Tab.2 Parameters of Immune Algorithm

除對無人機參數(shù)及免疫算法參數(shù)進行設(shè)置，還需要對其環(huán)境參數(shù)、任務數(shù)目及任務地點進行設(shè)置。本次設(shè)置當天溫度在（20~22）℃之間，其風速達到（5.5~6.1）m/s，待執(zhí)行的任務總數(shù)為10個，1~10 的坐標依次為（29.4，103.1，345.5）、（29.35，103.2，150.7）、（29.35，103.3，220.8）、（29.25，103.1，250.3）、（29.25，103.3，280.9）、（29.2，103.35，205.2）、（29.15，103.1，189.2）、（29.15，103.15，170.9）、（29.15，103.2，220.7）、（29.1，103.3，160.5），本次共派出三架無人機執(zhí)行任務，無人機（1~3）號起始點坐標依次為（29.15，103.0，0）、（29.25，103.0，0）、（29.30，103.0，0）。

3.2 可行性實驗驗證

在無意外發(fā)生情況下，利用所提方法進行任務規(guī)劃得到規(guī)劃結(jié)果，如圖1所示，圖中星型表示任務。

圖1 無意外發(fā)生情況下任務規(guī)劃結(jié)果圖Fig.1 Task Planning Results Without Accidents

由圖1可以看出，無人機1執(zhí)行任務1、2和3，無人機2則執(zhí)行任務4、5和6，無人機3執(zhí)行的任務相對較多，這是因為這些任務之間距離較短。從規(guī)劃的航線上來看，無人機飛行的總距離最短，基本按照最近原則分配任務，減少路徑代價。

但是任務環(huán)境具有較強的動態(tài)性，在任務執(zhí)行期間，無人機很有可能出現(xiàn)失聯(lián)等突發(fā)狀況。另外，威脅源的信息也會發(fā)生突變。分別在上述情況下進行任務規(guī)劃。

情況1：無人機失聯(lián)

假設(shè)無人機2在執(zhí)行完任務5后出現(xiàn)失聯(lián)情況，則此時的任務規(guī)劃結(jié)果，如圖2所示。

圖2 無人機失聯(lián)情況下任務規(guī)劃結(jié)果Fig.2 Mission Planning Results in Case of UAV Loss of Contact

由圖2可知，當無人機2失去信號后，無人機1在執(zhí)行完任務2后到達任務5所在地點執(zhí)行任務。這是因為免疫算法在執(zhí)行過程中可以通過反復迭代重新整理任務航線，通過合理的編碼設(shè)計確保無人機航程最短。

情況2：任務信息改變

傳感器可能會造成信息滯后，無人機任務初始分配時的環(huán)境信息與實際信息可能會有誤差。在任務執(zhí)行過程中，會增加任務點，此時需重新規(guī)劃任務。假設(shè)新增任務點為X，獲取免疫算法的規(guī)劃結(jié)果，如圖3所示。

圖3 威脅源信息變化時任務規(guī)劃結(jié)果Fig.3 Mission Planning Results When Threat Source Information Changes

由圖3看出，即便無人機在執(zhí)行任務過程中出現(xiàn)新增任務，所提方法也能合理的將新任務分配給對應的無人機，確保無人機順利完成所有任務的同時，還能滿足設(shè)定的目標函數(shù)要求。

3.3 對比實驗分析

在規(guī)劃合理性方面所提方法表現(xiàn)出優(yōu)越的性能，為測試算法目標函數(shù)的收斂能力，將收斂曲線和模擬退火粒子群算法、人工蜂群算法進行對比，得出比較結(jié)果，如圖4所示。

圖4 不同算法收斂曲線對比圖Fig.4 Comparison of Convergence Curves of Different Algorithms

測試結(jié)果表明，與其他兩種算法相比，免疫算法的收斂速度較快，當?shù)螖?shù)為40次時即可達到最優(yōu)目標值。這是因為該方法運用了高頻變異操作，可避免算法陷入局部最優(yōu)，而編碼過程則是對最優(yōu)解的記憶過程，加快了全局最優(yōu)解的搜索速度。

三種方法規(guī)劃3次運行結(jié)果，如表3所示。

表3 不同方法的規(guī)劃航程及耗時對比Tab.3 Planning Voyages and Time-Consuming Comparison of Different Methods

經(jīng)過對比可知，所提方法三次規(guī)劃以來，其航程最優(yōu)縮減為62.1km，規(guī)劃耗時小于30s，而對比方法的航程全部大于85km，且規(guī)劃耗時大于100s，所提方法具有更好的規(guī)劃效果，其規(guī)劃速率更優(yōu)。

4 結(jié)論

為提升無人機任務規(guī)劃的準確率和規(guī)劃速率，這里將免疫算法應用在多無人機任務最優(yōu)規(guī)劃中。結(jié)合任務規(guī)劃的各類約束條件，構(gòu)建規(guī)劃數(shù)學模型，經(jīng)過編碼設(shè)計、高頻變異等過程輸出最優(yōu)的任務規(guī)劃方案，經(jīng)過仿真實驗證明所提方法的可行性和先進性。（1）可行性實驗結(jié)果如下：在無意外發(fā)生情況下，可按照最近原則分配任務，以減少路徑代價；在某一無人機出現(xiàn)信號失聯(lián)時，可通過反復迭代重新整理任務航線，遵循無人機航程最短原則，就近安排其余無人機完成任務；可在任務點新增時，將新任務分配給對應無人機，就近完成任務，實現(xiàn)規(guī)劃目標。（2）對比實驗結(jié)果如下：所提方法可在迭代40次后完成達到最優(yōu)目標值，且可在規(guī)劃3次后將航程縮減到62.1km，整體規(guī)劃耗時小于30s，優(yōu)于對比方法。