時間約束下的多無人機任務(wù)分配方法研究

趙佳宜,趙文棟,劉存濤，李艾靜，劉澤原

(陸軍工程大學(xué) 通信工程學(xué)院，南京 210000)

1 引言

無人機因其成本可控、機動性強、控制靈活、環(huán)境適應(yīng)性好及人員傷亡風(fēng)險低等優(yōu)點，在民用和軍事領(lǐng)域均得到了廣泛的應(yīng)用，尤其是執(zhí)行高危環(huán)境下的污染監(jiān)測、緊急搜救、災(zāi)后通信恢復(fù)及數(shù)據(jù)采集等任務(wù)時，與傳統(tǒng)手段相比表現(xiàn)出更顯著的優(yōu)勢。

在時延容忍網(wǎng)絡(luò)(delay tolerant networks,DTN)中，節(jié)點之間的數(shù)據(jù)傳遞具有一定的時間容忍度，在截止時間內(nèi)實現(xiàn)數(shù)據(jù)的最終交付對于用戶來說即是可接受的。當電磁環(huán)境復(fù)雜、基礎(chǔ)通信設(shè)施受損或通信條件較差時，基于多跳的數(shù)據(jù)轉(zhuǎn)發(fā)會出現(xiàn)高誤碼率及高丟包率等問題，影響數(shù)據(jù)轉(zhuǎn)發(fā)的可靠性和有效性。此時，采用無人機充當渡輪(ferry)實現(xiàn)節(jié)點間的數(shù)據(jù)擺渡能夠確保數(shù)據(jù)的可靠交付。與傳統(tǒng)的數(shù)據(jù)傳輸不同，數(shù)據(jù)擺渡可以采取裝載-攜帶-交付(load-carry-and-deliver,LCAD)的方式，即無人機從源地面節(jié)點裝載數(shù)據(jù)，在飛向目的地時攜帶數(shù)據(jù)，最后將數(shù)據(jù)交付給目的節(jié)點，這一方式在源和目的節(jié)點沒有直接通信鏈路的情況下得到了廣泛的應(yīng)用。此外，當多架無人機同時執(zhí)行多個具有不同截止時間約束(時延容忍區(qū)間)的數(shù)據(jù)擺渡任務(wù)時，受限于單無人機自身的任務(wù)執(zhí)行能力，采用“一一對應(yīng)”的任務(wù)分配方式很可能導(dǎo)致部分任務(wù)無法得到有效完成，即無法在任務(wù)截止時間內(nèi)將源節(jié)點的數(shù)據(jù)傳遞至目的節(jié)點，從而直接影響任務(wù)的完成質(zhì)量。在這種情況下，采用“交叉執(zhí)行”的協(xié)同任務(wù)分配方式通常具有更好地適用性。

目前，已有許多文獻圍繞多無人機協(xié)同任務(wù)分配問題展開了研究。文獻[5-8]研究了無人機任務(wù)分配中的成本最小化問題。文獻[9-10]研究了無人機任務(wù)分配中的公平性問題。文獻[11-13]研究了無人機任務(wù)分配中的效用最大化問題。然而，上述研究很少考慮不同任務(wù)的差異化時間約束,僅從無人機能耗或系統(tǒng)收益的角度出發(fā)對任務(wù)進行分配仍可能導(dǎo)致部分任務(wù)完成效果不佳。

在考慮時間約束的情況下，可以將多任務(wù)分配問題建模為帶有時間窗約束的組合優(yōu)化問題，該問題已被證明是NP-hard問題，通常可以通過狀態(tài)壓縮動態(tài)規(guī)劃(狀壓DP)、(混合)整數(shù)規(guī)劃、啟發(fā)式算法、博弈論以及強化學(xué)習(xí)等方法進行求解。

本文考慮了DTN中基于多無人機擺渡的數(shù)據(jù)轉(zhuǎn)發(fā)場景，研究了差異化時間約束下的多任務(wù)分配問題，采用任務(wù)拆解與重組的思想，將其建模為具有右時間窗的車輛路徑問題，并以無人機總能耗最小化為目標對其進行優(yōu)化。通過引入大規(guī)模鄰域搜索(large-scale neighborhood search，LNS)中的“破壞和修復(fù)”思想，有效提高了遺傳算法的全局尋優(yōu)能力，能夠在滿足多任務(wù)時間約束的前提下，降低多無人機系統(tǒng)的總能耗。

2 系統(tǒng)模型及問題形式化

2.1 系統(tǒng)模型

如圖1所示，本文考慮了DTN中基于多無人機的數(shù)據(jù)擺渡場景，包括一個信息中心，個目標點和架可用擺渡無人機。信息中心接收到多個用戶的數(shù)據(jù)獲取需求后，為無人機分配數(shù)據(jù)擺渡任務(wù)；無人機根據(jù)分配到的數(shù)據(jù)擺渡任務(wù)，飛往任務(wù)目標點處，采用懸停的方式采集任務(wù)目標點的信息，而后將其攜帶回信息中心；信息中心接收到無人機獲取的信息后，根據(jù)用戶的需求向用戶分發(fā)信息。假設(shè)用戶與信息中心之間通信條件良好，且不考慮兩者之間的通信時延問題，信息中心獲取到無人機所采集信息的時間即為用戶獲取到所需信息的時間。

初始數(shù)據(jù)擺渡任務(wù)是根據(jù)用戶的不同信息獲取需求來區(qū)分的，記={,,…,}表示個任務(wù)的集合，其中，=<,>表示第個任務(wù)，是完成任務(wù)需要訪問的目標點集合，是任務(wù)的截止時間。

如圖1(a)所示，采用“一一對應(yīng)”的任務(wù)分配方式時，由于不同用戶的信息獲取需求不同，可能導(dǎo)致不同無人機訪問目標點的數(shù)量存在較大差異(如UAV2和UAV3)，這一方面影響了無人機之間的能耗公平性，另一方面也造成無人機資源的浪費；同時，由于單個無人機飛行能力有限，當其需要訪問的目標點數(shù)量過多時，任務(wù)完成時間通常會比較長，會導(dǎo)致對應(yīng)的數(shù)據(jù)擺渡任務(wù)無法有效完成。

圖1 系統(tǒng)模型示意圖

為此，主要考慮如圖1(b)所示的“交叉執(zhí)行”任務(wù)分配方式，即一架無人機可以執(zhí)行多個數(shù)據(jù)擺渡任務(wù)，每個數(shù)據(jù)擺渡任務(wù)可以由多架無人機執(zhí)行。具體過程如下：首先將初始數(shù)據(jù)擺渡任務(wù)進行分解，把每個目標點看作一個任務(wù)碎片，并根據(jù)其所屬的初始擺渡任務(wù)，使用作為時間戳對其進行標記；而后對任務(wù)碎片進行重組，并將重組后的數(shù)據(jù)擺渡任務(wù)分配給不同的無人機。碎片重組的有效性會直接影響任務(wù)的完成質(zhì)量，為此，需要對碎片重組策略進行優(yōu)化。這種基于碎片重組的任務(wù)分配問題可以歸屬于組合優(yōu)化問題，下面對具體的約束和優(yōu)化目標進行詳細描述。

2.2 能耗約束

在考慮能耗約束的情況下，無人機任務(wù)分配與路徑規(guī)劃之間具有高度耦合性，因為無人機的能耗很大程度上取決于其在任務(wù)執(zhí)行過程中的飛行路徑。為此，通常會將任務(wù)分配與路徑規(guī)劃一同進行考慮：在確定了任務(wù)分配策略之后，無人機的飛行路徑可以建模為完全無向圖(,)，其中，是節(jié)點集合，表示無人機需要訪問的所有目標點的集合；是節(jié)點之間邊的集合，當2個節(jié)點之間有邊時表示這兩個節(jié)點由同一架無人機進行訪問，即屬于同一架無人機的任務(wù)目標點集合。此外，無人機在整個數(shù)據(jù)擺渡任務(wù)中的能耗包含采集目標點信息時的懸停能耗和飛行消耗兩部分，將無人機的懸停能耗和飛行能耗分別表示為節(jié)點和邊的權(quán)重：對于節(jié)點∈，點權(quán)重記為()，對于邊(,+1)∈，邊權(quán)重記為(,+1)。下面對無人機的飛行能耗和懸停能耗進行詳細描述。

2.2.1 飛行能耗

無人機的飛行能耗主要取決于的飛行路徑長度。本文只考慮二維平面的無人機，記無人機的飛行速度為，則可以表述為

=·

(1)

(2)

2.2.2 懸停能耗

(3)

其中，表示單位時間內(nèi)的懸停能耗。

基于上述分析，如式(4)所示，的總能耗可以表示為

(4)

(5)

2.3 時間約束

主要與的飛行時間和懸停時間有關(guān)，可表示為

(6)

綜上所述，時間約束可以表示為

(7)

2.4 目標函數(shù)

以無人機總能耗最小化為目標對多無人機協(xié)同任務(wù)分配問題進行優(yōu)化，優(yōu)化目標表示為

(8)

其中:表示任務(wù)分配策略集，表示策略集中的一個可行解。由于目標函數(shù)的非凸性，問題是一個非凸優(yōu)化問題，很難通過直接求解得到問題的最優(yōu)解。為此，我們提出了一種基于大規(guī)模鄰域搜索算法改進的遺傳算法對該問題進行求解。

3 算法描述

3.1 遺傳算法概述

遺傳算法是借鑒生物進化過程而提出的一種啟發(fā)式搜索算法，通過選擇、交叉和變異等操作產(chǎn)生下一代的解，并逐步淘汰掉適應(yīng)度函數(shù)值低的解，增加適應(yīng)度函數(shù)值高的解，從而通過進化演變，逐步逼近問題的最優(yōu)解。該算法具有簡單通用，魯棒性強，適于并行處理等優(yōu)勢。但是，遺傳算法的局部搜索能力較差，且對初始種群的選擇具有一定依賴性。

3.2 基于改進遺傳算法的協(xié)同任務(wù)分配算法

本算法以遺傳算法為基礎(chǔ)，在進化算子中引入了大規(guī)模鄰域搜索中的“破壞和修復(fù)”思想，有效彌補了遺傳算法容易陷入局部最優(yōu)解的缺陷，提高了解的質(zhì)量，算法的具體描述如下。

3.2.1 染色體結(jié)構(gòu)

如圖2所示，采用整數(shù)編碼的形式將一個染色體描述為(1,2,3,…,,+1,+2,…,+-1)，其中，數(shù)字1～表示對應(yīng)序號的目標點，數(shù)字(+1)～(+-1)表示1～號無人機。如果無人機序號第一次出現(xiàn)在數(shù)字1-之間時，則表明第一條路徑生成，以此類推。

圖2 染色體結(jié)構(gòu)示意圖

3.2.2 適應(yīng)度函數(shù)

考慮可能出現(xiàn)違反任務(wù)時間窗約束的情況，設(shè)計了如式(9)所示的懲罰函數(shù)()，表示為

()=·()

(9)

其中，表示單位懲罰成本，本實驗中設(shè)置為10；()表示在采用任務(wù)分配策略時，違反任務(wù)時間窗約束的目標點信息的累積超時時間，表示為

(10)

其中，()表示目標點的時間戳，若標點的信息到達信息中心的時間尚未超過其時間戳，則()為0；否則，將()記為該信息的超時時間。

記()為所有無人機的總能耗，則適應(yīng)度函數(shù)表示為

()=1(()+())

(11)

3.2.3 種群初始化

采用啟發(fā)式方法構(gòu)造初始種群，其中，單個初始解的構(gòu)造方法如算法1所示。

1基于貪婪思想的初始解生成算法

無人機數(shù)目，個目標點的坐標，截止時間集合{}

初始可行解

1.路徑序號：_←1；

2.從個目標點中隨機選擇一個點；

3.以為初始點，生成一個目標點遍歷序列：←[,+1,…,,1,…,-1]；

4.按依次遍歷目標點，如果將添加到當前路徑中，不會導(dǎo)致路徑中的節(jié)點(含)出現(xiàn)違背能耗約束的情況，則添加到路徑中，并將從剔除；否則更新路_=_+1；

5.重復(fù)步驟4，直至為空，根據(jù)生成路徑的數(shù)量_。

6.如果_小于，則選擇1～_號無人機作為任務(wù)無人機，將+1,+2,…,+_依次插入到各個路徑的起始點，并將各路徑合并得到初始解；否則，當前解為不可行解，從步驟1開始重新構(gòu)造初始解。

3.2.4 進化算子

選擇算子：采用輪盤賭算法作為選擇算子，基于個體的適應(yīng)度選擇若干個個體參與后續(xù)的交叉、變異以及局部搜索操作。

交叉算子：采用順序交叉的方式實現(xiàn)，如圖3所示，系統(tǒng)隨機生成2個交叉位置，用以選擇父代交叉的片段，如圖3中標黃部分為例。隨后將父代2的交叉片段移動到父代1的前面，將父代1的交叉片段移動到父代2的前面。接著從前到后把第2個重復(fù)的基因位刪除，形成2個子代個體。

變異算子：采用了2種變異算子，一是基于two-element swap算子實現(xiàn)染色體變異，即隨機生成2個位置，將父代染色體相應(yīng)位置上的基因進行交換，形成子代染色體。二是引入LNS中的局部搜索算法，通過破壞算子和修復(fù)算子實現(xiàn)染色體變異，具體步驟如算法2所示。

圖3 交叉算子示意圖

2LNS算法

當前的解

進化后的解

1.初始化需要移出的目標點數(shù)量為=5；

2.從原有目標點集合中隨機選出一個目標點；

3.根據(jù)相關(guān)性計算公式(,)=1(+)，由高到低依次移出中的個目標點，放入集合；

4.分別找出中的目標點在中的可行插入點集合，并記錄此時的最小的能耗增量；

5.按照從大到小的順序，將中的目標點在不違反約束的情況下依次插入當前解中，并計算此時的最小能耗；

6.重復(fù)該操作直至中的個目標點都被重新插回解集合。

基于上述分析，得到基于改進遺傳算法的協(xié)同任務(wù)分配算法，具體步驟入算法3所示。

3基于改進遺傳算法的協(xié)同任務(wù)分配算法

無人機數(shù)目，個目標點的坐標，截止時間集合{}

最優(yōu)解

1.初始化種群，種群規(guī)模=100，最大迭代次數(shù)max=100；

2.根據(jù)算法1構(gòu)造初始解，輸出隨機初始解的路線，即產(chǎn)生路徑點集合，并計算初始解中的UAV使用數(shù)目，UAV飛行總能耗以及違反約束目標點數(shù)目；

3.計算(,+1),和()，和矩陣；

5.當≤max時，執(zhí)行步驟6，否則，執(zhí)行步驟10；

6.計算適應(yīng)度函數(shù)=()；

7.進行選擇，交叉和變異操作；

8.利用破壞和修復(fù)算子，根據(jù)算法2對染色體進行局部搜索操作；

9=+1；

10.輸出當前最優(yōu)解。

4 仿真結(jié)果及分析

為了評價算法的性能，除了本文提出的協(xié)同任務(wù)分配算法(cooperation task redistribution algorithm,CTRA)之外，同時對“一一對應(yīng)”任務(wù)分配方式下的性能和傳統(tǒng)的遺傳算法性能進行了仿真。仿真結(jié)果均為在Matlab 2019a環(huán)境下進行了10次實驗后，求取的平均值。

4.1 仿真參數(shù)設(shè)置

仿真過程中，目標點分布于大小為3 000 m*3 000 m的二維平面，信息中心位置固定，且為(0，0)，可用無人機數(shù)量為25，目標點的默認數(shù)量為100。圖4顯示了目標點的分布情況和任務(wù)需求。此外，任務(wù)截止時間如表4所示，其他主要仿真參數(shù)如表5所示。

圖4 目標點分布及任務(wù)需求示意圖

表4 任務(wù)截止時間

表5 參數(shù)設(shè)置

4.2 仿真結(jié)果

4.2.1 算法收斂性

圖5顯示了CTRA的收斂性。從仿真結(jié)果可以看出，該算法經(jīng)過約86次迭代后，已經(jīng)基本收斂。

圖5 算法CTRA的收斂性曲線

4.2.2 算法性能比較分析

1) 能耗效率。如圖6所示，采用“一一對應(yīng)”的任務(wù)分配方式時，由于任務(wù)8和任務(wù)9的信息需求量差異較大，導(dǎo)致無人機8和無人機9消耗的能量差異也較大。而經(jīng)過“交叉執(zhí)行”的任務(wù)碎片化重組之后，如圖7所示，需要的無人機總數(shù)量減少為7架，且無人機的能耗效率和公平性均得到明顯改善。

圖6 “一一對應(yīng)”任務(wù)分配方式的分能耗直方圖

圖7 “交叉執(zhí)行”任務(wù)分配方式的分能耗直方圖

2) 任務(wù)完成時間。圖8顯示了“一一對應(yīng)”任務(wù)分配方式下的任務(wù)完成時間，對于信息需求較大的任務(wù)8而言，任務(wù)完成時間超過了其截止時間，導(dǎo)致對應(yīng)的數(shù)據(jù)擺渡任務(wù)8無法有效完成，任務(wù)2，4，7亦是如此。而在“交叉執(zhí)行”任務(wù)分配方式下，如圖9所示，所有任務(wù)均可在任務(wù)截止時間前完成，有效改善了任務(wù)完成質(zhì)量。

圖8 “一一對應(yīng)”任務(wù)分配方式的分時間直方圖

圖9 “交叉執(zhí)行”任務(wù)分配方式的分時間直方圖

4.2.3 算法適應(yīng)性

1) 截止時間分布對算法性能的影響。默認的截止時間分布是隨機分布，因此圖10研究了截止時間服從泊松分布時變化對目標函數(shù)的影響。當值較小時，由于違法約束的目標點數(shù)目較多，懲罰函數(shù)值較大，因此得到的最優(yōu)解隨之增大。隨著的不斷增大，截止時間均得到滿足，最優(yōu)解趨于穩(wěn)定。

圖10 最優(yōu)值隨截止時間分布變化直方圖

2) 目標區(qū)域大小對算法性能的影響。圖11和圖12的仿真結(jié)果比較了目標區(qū)域大小對算法性能的影響。仿真中將偵察區(qū)域設(shè)置為正方形，圖中的橫坐標代表偵察區(qū)域的邊長。隨著偵察區(qū)域的增大，無人機的飛行距離變大，從而增加了無人機的飛行能耗和飛行時間，因此，需要的無人機數(shù)量隨偵察區(qū)域范圍的擴大產(chǎn)生了變化。另外，如圖12所示，與“一一對應(yīng)”任務(wù)分配方式相比，“交叉執(zhí)行”任務(wù)分配方式在滿足所有任務(wù)截止時間的情況下，系統(tǒng)總能耗可以降低約17.7%～41.9%。

圖11 無人機數(shù)量隨目標區(qū)域大小變化直方圖(CTRA)

圖12 總能耗隨目標區(qū)域大小變化曲線

3) 目標點數(shù)量對算法性能的影響。圖13和圖14對比了CTRA和遺傳算法GA的性能。其中，圖13展示了無人機數(shù)量隨著目標點數(shù)量的變化情況，從仿真結(jié)果可以看出，隨著目標點數(shù)量的增加，為滿足任務(wù)的截止時間，使用的無人機數(shù)目均隨之增加，但是基于CTRA的任務(wù)分配算法能夠在一定程度上獲得更優(yōu)的解，即可以采用更少數(shù)量的無人機來滿足任務(wù)需求。此外，如圖14所示，和遺傳算法GA相比，CTRA平均降低了約12%的系統(tǒng)能耗。

圖13 無人機數(shù)量隨目標點數(shù)量變化直方圖

圖14 總能耗隨目標點數(shù)量變化曲線

5 結(jié)論

針對多無人機執(zhí)行數(shù)據(jù)擺渡任務(wù)時的多任務(wù)協(xié)同分配問題，提出了一種基于任務(wù)碎片的“交叉執(zhí)行”任務(wù)分配方法，將其建模為多約束的組合優(yōu)化問題。通過引入破壞算子和修復(fù)算子提出了一種改進遺傳算法對該模型進行求解，該方法避免了傳統(tǒng)遺傳算法易陷入局部最優(yōu)和過早收斂。

仿真結(jié)果證明了提出的算法CTRA能夠滿足任務(wù)截止時間，有效節(jié)省無人機使用的數(shù)量并降低總能耗。