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

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

0 引 言

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

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

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

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

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

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

1.1 模型假設(shè)

（1）無(wú)人機(jī)的目標(biāo)搜索點(diǎn)及釋放位置的具體坐標(biāo)已知，各節(jié)點(diǎn)之間的距離按照歐氏距離進(jìn)行計(jì)算。

（2）每架無(wú)人機(jī)可以搜索多個(gè)目標(biāo)點(diǎn)，每個(gè)目標(biāo)搜救點(diǎn)只需要一架無(wú)人機(jī)進(jìn)行搜索，但無(wú)人機(jī)的能耗不超過(guò)無(wú)人機(jī)的滿電電量。

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

（4）目標(biāo)搜索點(diǎn)的探測(cè)時(shí)間根據(jù)災(zāi)情等級(jí)進(jìn)行確定。

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

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

1.2 變量說(shuō)明

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

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

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

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

首先，目標(biāo)函數(shù)要使得總的費(fèi)用最小，包括無(wú)人機(jī)飛行產(chǎn)生的費(fèi)用和懸停產(chǎn)生的費(fèi)用。則該項(xiàng)目標(biāo)函數(shù)表達(dá)式如式（1）所示。

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

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

1.4 模型約束

模型的約束如下：

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

式（2）為目標(biāo)函數(shù)Ⅱ，考慮了無(wú)人機(jī)使用數(shù)量最少，使得購(gòu)置無(wú)人機(jī)的成本以及養(yǎng)護(hù)成本減少。

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

約束條件①確保每個(gè)搜索點(diǎn)只能由一架UAV進(jìn)行搜索。

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

約束條件③確保每條路線的連續(xù)性，即：訪問(wèn)節(jié)點(diǎn)的無(wú)人機(jī)必須離開(kāi)節(jié)點(diǎn)。

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

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

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

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

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

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

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

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

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

2.1 雙染色體編碼方式

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

例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）在切割后分為四個(gè)子序列。四個(gè)子序列（3，8），（5，1，4），（2，6，10）和（9，7）分別代表UAV1、UAV2、UAV3和UAV4的目標(biāo)序列。

2.2 基于對(duì)立的學(xué)習(xí)策略

在無(wú)人機(jī)任務(wù)分配中，一個(gè)染色體Ⅰ是被視為計(jì)算對(duì)立面的多維點(diǎn)。

2.3 種群初始化

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

2.4 快速非支配排序

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

2.5 擁擠度比較算子

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

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

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

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

2.6 選擇和精英保留

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

2.7 交叉

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

2.8 多重變異

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

3 算例分析

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

無(wú)人機(jī)任務(wù)分配算例選取獲取到的釋放位置進(jìn)行分析，該位置負(fù)責(zé)13個(gè)搜索點(diǎn)。

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

（1）種群初始化

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

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

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

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

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

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

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

圖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 多目標(biāo)模型與單目標(biāo)模型結(jié)果對(duì)比Table 4 Comparison of results between multi-objective model and single-objective model

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

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

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

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

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

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

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

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

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

4 結(jié) 論

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

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