考慮低空運行環(huán)境求解無人機任務(wù)分配問題的研究

李松銳，張明，王蒙蒙，張進，李伯權(quán)

（南京航空航天大學(xué)民航學(xué)院，南京 211106）

0 引 言

在地震等自然災(zāi)害發(fā)生之后，需要及時對災(zāi)情進行探測，無人機能夠利用紅外探測儀，通過感知溫度的差異來探尋目標，可以探測到人體的身體熱量，從而知曉哪里還存在生命跡象，以便拯救更多的受災(zāi)群眾?！包S金72小時”是地質(zhì)災(zāi)害發(fā)生后的黃金救援期，在此期間內(nèi)，人的存活率極高，因而在這個期間內(nèi)需要緊抓時間，開展搜救工作，但是在發(fā)生災(zāi)害的地區(qū)，所提供的電力等能源以及飛行器的架數(shù)都比較有限，通航直升機和無人機搜索是搜救中的關(guān)鍵一環(huán)，是目前公認的有效手段也是當下研究的熱點，救援部門都以最小化飛行路徑的長度為目標，采用建模方法進行飛行器的路徑規(guī)劃。進行無人機任務(wù)分配方法主要有三種，分別是集中式、分布式以及分層級分布式分配。

集中式分配主要針對的是多旅行商問題中的路徑求解問題。K.Dorling等研究了無人機運輸?shù)能囕v路線問題時以集中式任務(wù)分配為基礎(chǔ)來求解分配后的無人機路線問題；C.Murray等考慮了最后1 mile（1 mile=1.609 344 km）的運輸系統(tǒng)；Zhou Z等研究了當移動人群感應(yīng)遇見無人機時，節(jié)能任務(wù)分配和路線規(guī)劃；Han Q等研究了基于多智能體強化學(xué)習的多無人機目標分配與路徑規(guī)劃聯(lián)合優(yōu)化。集中式分配的優(yōu)點是總能給出最優(yōu)解，但是集中式分配也存在著問題規(guī)模較大時非常耗時等缺點。

分布式分配需要無人機可以進行獨立計算、分析和決策，朱曉宇等提出基于一致性差分進化的分布式任務(wù)分配；Zhou C等提出了一種在線隨機激勵機制，用于在實際眾包系統(tǒng)中并行分配延遲容忍任務(wù)；Yu D等提出了運行時平衡聚類算法和依賴關(guān)系的平衡聚類算法。分布式分配的優(yōu)點是在應(yīng)用中無人機能在編隊內(nèi)通信，但是也要求無人機需要進行獨立計算和決策，靈活性要求高。

分層級分布式分配，集集中式分配方式和分布式分配方式的優(yōu)點于一身，Hua M L等提出利用車輛來運載和發(fā)射無人機的方案；Hu Xiaoxuan等研究了多個協(xié)作無人機團隊的任務(wù)分配的分層方法；Yu Jianqiao等通過全面建模解決了考慮不同情況的多重UAV任務(wù)分配問題；Meng Wei等考慮了將多無人機的分散控制用于自主起飛，搜索和跟蹤的問題；Ma Yunhong等提出了一種遺傳和聚類算法相結(jié)合的協(xié)同優(yōu)化算法；Wei Minghan等研究了能源約束下的覆蓋路徑規(guī)劃；林林等設(shè)計了一種基于時間窗的無人機任務(wù)分配方法，利用沖突消解機制防止無人機出現(xiàn)資源死鎖的情況。分層級分布式分配靈活性大，減少了計算時間。

綜上所述，運用集中式任務(wù)分配方法或分布式分配方法各有優(yōu)點和缺點，采用分層級分布式分配方法使得任務(wù)分配能發(fā)揮二者的優(yōu)勢，任務(wù)分配效果更佳。本文在分層級分布式分配方法的基礎(chǔ)上建立多目標多無人機任務(wù)分配模型，在約束上考慮地形繞飛、低空風速對無人機續(xù)航能力的影響，在求解方法上考慮利用改進的遺傳算法進行求解，并在求解中加入對立學(xué)習的方法增加解的多樣性，得出分配結(jié)論。

1 考慮無人機性能及運行環(huán)境的任務(wù)分配模型

1.1 模型假設(shè)

（1）無人機的目標搜索點及釋放位置的具體坐標已知，各節(jié)點之間的距離按照歐氏距離進行計算。

（2）每架無人機可以搜索多個目標點，每個目標搜救點只需要一架無人機進行搜索，但無人機的能耗不超過無人機的滿電電量。

（3）將考慮低空風對無人機電池能耗影響、避障影響以及懸停影響下的能耗換算成無人機在不考慮以上因素勻速飛行狀態(tài)時（如本文算例中機型A的速度為15 m/s）對應(yīng)的航程進行計量。

（4）目標搜索點的探測時間根據(jù)災(zāi)情等級進行確定。

（5）各節(jié)點出發(fā)的UAV的速度均一致，無人機的航程成本與無人機完成任務(wù)換算成的航程成正比。

（6）不考慮無人機充電即多次循環(huán)使用問題，發(fā)射前為滿電量。

1.2 變量說明

無人機任務(wù)分配模型的相關(guān)變量說明如表1所示。

表1 任務(wù)分配變量表Table 1 Task allocation variable table

1.3 目標函數(shù)

目標函數(shù)不僅要考慮無人機搜救產(chǎn)生的費用，還要綜合考慮無人機的使用數(shù)量、總的完成任務(wù)最短時間即無人機任務(wù)的均衡合理性等因素。

首先，目標函數(shù)要使得總的費用最小，包括無人機飛行產(chǎn)生的費用和懸停產(chǎn)生的費用。則該項目標函數(shù)表達式如式（1）所示。

其次，無人機的實際數(shù)量有限，因而要盡量減少無人機的使用數(shù)量，得到第二項目標函數(shù)（其中0節(jié)點表示通航直升機釋放無人機的位置）如式（2）所示。

最后，無人機完成其所分配的搜救任務(wù)的總能耗最小雖然會使得總的費用有所降低，但是在救援過程中，完成任務(wù)的時間也值得考慮，僅考慮費用問題可能會使得每架無人機完成任務(wù)的時間差別很大從而使得整體完成任務(wù)的時間較長，因而還需要在考慮費用的同時也要考慮各無人機完成任務(wù)耗時的最大時差降到最低，如式（3）所示。

1.4 模型約束

模型的約束如下：

式（1）為目標函數(shù)Ⅰ，使總旅行成本最小化，包括在飛行中和懸停產(chǎn)生的成本。

式（2）為目標函數(shù)Ⅱ，考慮了無人機使用數(shù)量最少，使得購置無人機的成本以及養(yǎng)護成本減少。

式（3）為目標函數(shù)Ⅲ，考慮了任務(wù)的均衡性，使得總的完成任務(wù)的時間最短。

約束條件①確保每個搜索點只能由一架UAV進行搜索。

約束條件②表示如果無人機對搜救點進行搜索，則必須經(jīng)過通航直升機釋放無人機的位置點；如果無人機未經(jīng)過通航直升機釋放位置，則不會搜索任何搜救點。

約束條件③確保每條路線的連續(xù)性，即：訪問節(jié)點的無人機必須離開節(jié)點。

約束條件④指出，如果存在從節(jié)點到節(jié)點的UAV飛行，則它們將由同一架UAV搜索。

約束條件⑤是經(jīng)典子回路消除約束。

約束條件⑥是無人機的架數(shù)限制。

約束條件⑦表示無人機的電量限制為最大航程限制，即在考慮風和避障條件下將無人機飛行消耗的電量和懸停消耗的電量之和，換算為理想狀態(tài)下勻速飛行的航程進行計算，不得大于無人機的最大航程。

約束條件⑧～約束條件⑨定義了航程的換算公式，為低空風對電池能耗影響系數(shù)、為無人機能耗預(yù)留系數(shù)、無人機飛行與懸停能耗比。

約束條件⑩定義了第架UAV完成分配給它的任務(wù)花費的總時間。

約束條件?～約束條件?定義了變量的取值范圍。

2 NSGA-Ⅱ算法求解無人機任務(wù)分配

本文基于（Nondominated Sorting Genetic Algorithm-Ⅱ，簡稱NSGA-Ⅱ算法），采用快速非支配排序算法，引進精英策略和采用擁擠度及擁擠度比較算子，使得NSGA-Ⅱ運行速度快，求得的解的收斂性好。該算法求解UAV任務(wù)分配問題依賴于其進化機制。

2.1 雙染色體編碼方式

運用一種雙染色體編碼方式，雙染色體均由整數(shù)編碼，第一個染色體（染色體Ⅰ）代表靶序列，第二個（染色體Ⅱ）代表目標序列在染色體Ⅰ上的切割位置。在染色體Ⅰ上，每個基因都代表一個搜索目標的索引，在染色體Ⅱ中，任何基因的值都不得小于其前面的基因值。以四架UAV，10個搜救點為例進行編碼。

例1：染色體Ⅰ（3，8，5，1，4，2，6，10，9，7），染色體Ⅱ（2，5，8）。

基因編碼方式如表2所示。

表2 例1染色體編碼圖Table 2 Chromosome coding of example 1

從表2可以看出：染色體Ⅱ是（2，5，8），因此染色體Ⅰ中的基因（3，8，5，1，4，2，6，10，9，7）在切割后分為四個子序列。四個子序列（3，8），（5，1，4），（2，6，10）和（9，7）分別代表UAV1、UAV2、UAV3和UAV4的目標序列。

2.2 基于對立的學(xué)習策略

在無人機任務(wù)分配中，一個染色體Ⅰ是被視為計算對立面的多維點。

2.3 種群初始化

染色體Ⅰ上的基因總數(shù)為（搜救點的總數(shù)），染色體Ⅱ（切割位置）上的基因數(shù)目為(-1)，即無人機總架數(shù)減一。根據(jù)所建立無人機任務(wù)分配模型中的約束條件以及本文提出的編碼方式，隨機產(chǎn)生一定數(shù)量滿足約束條件的個體即滿足每架無人機電池容量約束，完成種群的初始化，產(chǎn)生初始種群數(shù)量為，通過對立學(xué)習的方式擴充種群數(shù)量為2，得到初始種群。

2.4 快速非支配排序

本文對于第代種群P 中每個個體，首先對基因進行解碼得到無人機任務(wù)分配結(jié)果，根據(jù)式（1）～式（3）計算其對應(yīng)的三個目標函數(shù)值，依據(jù)各目標函數(shù)值，對于每個個體都會得到兩個參數(shù)n 和s （n 為在種群中支配個體的解的數(shù)量，s 為被個體所支配的解的集合），從而進行分層和排序，進而得到不同等級的帕累托前沿。不斷地重復(fù)上述操作，直到所有個體都設(shè)置為前沿。

2.5 擁擠度比較算子

個體的擁擠度距離()計算公式如式（6）所示。

經(jīng)過快速非支配排序之后，種群中的每個個體都具有非支配排序得到的非支配序列和擁擠度i 兩個屬性，根據(jù)這兩個屬性設(shè)定擁擠度比較算子，對于個體和個體，滿足以下任意一個條件，則獲勝。

（1）個體所在非支配層優(yōu)于個體所在非支配層，有＜。

（2）和具有相同等級，同時個體的擁擠距離較大，即=且i =j 。

2.6 選擇和精英保留

種群初始化以及每次迭代得到新的種群后，運用二元競標法選擇合適的父本進行交叉和變異操作。交叉和變異之后再對種群進行對立學(xué)習，擴充種群的規(guī)模。

2.7 交叉

本文只將交叉算子應(yīng)用于染色體Ⅰ，而染色體Ⅱ在交叉過程中保持不變。這項工作使用了部分映射交叉運算符，其中一個親本基因的一部分與另一親本基因的一部分進行交換，其余基因則通過作圖進行復(fù)制或再生。

2.8 多重變異

對于染色體Ⅰ，變異總共有四種操作方式，即保持、翻轉(zhuǎn)、交換和滑動，一次可以產(chǎn)生四個后代。

3 算例分析

3.1 數(shù)據(jù)獲取

無人機任務(wù)分配算例選取獲取到的釋放位置進行分析，該位置負責13個搜索點。

3.2 求解過程和結(jié)果分析

（1）種群初始化

首先需要進行種群的初始化，由于要滿足電池容量約束，為計算簡便，設(shè)置初始解為“一機一點”，即每架無人機搜索一個搜救點，總共有13個搜索點，則初始解使用了13架無人機，染色體Ⅱ編碼為［1 2 3 4 5 6 7 8 9 10 11 12 13］。染色體Ⅰ通過隨機的方式產(chǎn)生初始種群。

（2）參數(shù)設(shè)置

求解參數(shù)設(shè)置如表3所示。

表3 求解參數(shù)設(shè)置表Table 3 Solving parameter setting table

（3）求解結(jié)果及分析

在正式求解前首先利用NSGA-Ⅱ和PSO算法以費用最小為目標函數(shù)進行求解，如圖1所示，可以看出：NSGA-Ⅱ算法相比較于PSO算法求解任務(wù)分配的問題具有收斂速度快，并且得到的結(jié)果更優(yōu)，求得的費用減少了2.08%。

圖1 NSGA-Ⅱ和其他算法迭代對比圖Fig.1 Iterative comparison diagram of NSGA-Ⅱand other algorithms

分別設(shè)置種群規(guī)模=30，迭代次數(shù)為1 000、500、300、200，和=1 000，為100、50、30、20進行8次實驗得到帕累托解，如圖2～圖3所示，藍、品紅、黃、黑色圓點分別表示在=30，=1 000、500、300、200下得到的帕累托解，在圖3中，紅、綠、藍、青色圓點分別表示在=1 000，=100、50、30、20下得到的帕累托解?？梢钥闯觯寒敺N群規(guī)模為30，迭代次數(shù)為1 000時能得到較多的帕累托解。取兩個帕累托解以及遺傳算法求解單目標的兩組迭代得到的解，結(jié)果對比如表4所示，其中單目標模型求解后只能得到目標，即搜救的費用，為了便于比較，將其對應(yīng)使用的無人機架數(shù)即，以及無人機執(zhí)行任務(wù)時間極差求出。

圖2 P op=30，G en為1 000、500、300、200得到的帕累托前沿Fig.2 The petro frontier obtained by P op=30 and G en=1 000、500、300、200

圖3 G en=1 000，P op為100、50、20、30得到的帕累托前沿Fig.3 The petro frontier obtained with G en=1 000 and P op=100、50、20、30

表4 多目標模型與單目標模型結(jié)果對比Table 4 Comparison of results between multi-objective model and single-objective model

分析單目標求解得到的分配結(jié)果，顯然與多目標模型得到的帕累托解相比，在使用的無人機數(shù)量上差別不大，單目標模型未考慮任務(wù)的均衡性，使得無人機之間的任務(wù)完成時間差別較大，但是在費用上具有明顯優(yōu)勢。多目標求解的結(jié)果在費用上不具有優(yōu)勢，但是在完成任務(wù)的均衡性上具有明顯優(yōu)勢。

而對于多目標求解結(jié)果，也可以根據(jù)實際需求獲得需要的帕累托解。分別取側(cè)重于搜救總費用最小、搜救無人機的數(shù)量最小和無人機任務(wù)差異性最小的結(jié)果進行靈敏度分析，無人機任務(wù)分配多目標模型的靈敏度分析側(cè)重不同目標得到的結(jié)果如表5所示。

表5 多目標模型靈敏度分析側(cè)重目標結(jié)果Table 5 Multi-target model sensitivity analysis focuses on target results

如果側(cè)重的目標函數(shù)是Z (∈)并且={1，2，3}，則當Z 是側(cè)重于目標時，Z (∈)可以表示為目標值矩陣，Z 為

如果Z (∈{})是側(cè)重于Z 的目標值，φ 表示側(cè)重Z 與側(cè)重Z 的目標值變化率，則φ 可以表示為

如果φ 為正，則目標趨勢上升；否則，趨勢是下降的。有關(guān)重點目標結(jié)果的比較分析，如表6所示。

表6 多目標模型中側(cè)重目標結(jié)果對比分析（根據(jù)均值計算求得）Table 6 Focus on the comparative analysis of target results in the multi-target model（calculated according to the mean value）

從表6可以看出：當帕累托解側(cè)重于搜救成本時，相比側(cè)重于UAV數(shù)量和搜救時差最小，成本有所下降，且UAV任務(wù)最大時差都有大幅上升，其中相比側(cè)重于UAV使用數(shù)量目標，成本目標的值下降不明顯；當側(cè)重于UAV使用數(shù)量時，相比側(cè)重于另外兩個目標函數(shù)，UAV使用數(shù)量有所下降，其中相比側(cè)重于成本目標，UAV使用數(shù)量下降也不明顯；當帕累托解側(cè)重于UAV搜救最大時差最小時，相比側(cè)重于另外兩個目標函數(shù)，時差有所下降，且下降幅度特別大，另外兩個目標函數(shù)的值卻均有所上升。

在實際搜索救援中，需要綜合平衡搜救時間、費用和無人機數(shù)量三個指標，使得搜救工作更加有效。一般更多是在考慮搜救均衡時間最少這個指標的基礎(chǔ)上，帶來成本和無人機數(shù)量的增加；但當實際搜救無人機的數(shù)量十分有限時，則需要加大時間或成本的投入；以經(jīng)濟利益為導(dǎo)向時，則會導(dǎo)致搜救時間的增加。

4 結(jié) 論

（1）在進行模型的求解計算時，利用了改進的NSGA-Ⅱ算法進行求解，相比較于PSO算法求解任務(wù)分配的問題具有收斂速度快的特點，并且得到的結(jié)果更優(yōu)，費用減少了2.08%。

（2）通過算例得出考慮多目標的無人機任務(wù)分配模型的優(yōu)異性，本模型可以根據(jù)搜救情況的現(xiàn)實需要，對于側(cè)重于不同的目標，給出對應(yīng)的分配方案。