基于改進貪心算法的無人機集群協(xié)同任務分配

陳宇恒 陳進朝 陳雪聰

摘要：無人機集群由于其強大的信息共享與行為協(xié)作等優(yōu)勢，在軍事、民用及科研等領域發(fā)揮了重要作用。然而無人機集群在執(zhí)行大規(guī)模任務時，任務的時間約束、時序關系以及性能要求都對集群任務的協(xié)同規(guī)劃與分配提出了巨大的挑戰(zhàn)。針對多無人機協(xié)同飛行約束下的任務分配問題，本文提出了一種基于改進貪心算法的無人機集群協(xié)同任務分配算法，在保證無人機間協(xié)同飛行以及任務間時序約束的前提下，優(yōu)化無人機集群的飛行時間與距離。該算法借鑒圖論中的有向圖來表示任務間協(xié)同飛行約束關系，并依據(jù)改進的貪心算法對任務進行局部最優(yōu)分配、優(yōu)化，有效獲得時間最優(yōu)、距離最優(yōu)兩種策略下的近似最佳飛行路徑。在構(gòu)建的覆蓋掃描任務場景上進行試驗對比，驗證了本文所提算法的有效性，該算法相較于傳統(tǒng)解決方法在時間與距離性能上最高能提升20%。

關鍵詞：無人機集群；任務分配；協(xié)同任務；圖論；改進貪心算法

中圖分類號：V355文獻標識碼：ADOI：10.19452/j.issn1007-5453.2022.04.003

基金項目：國家自然科學基金（62106202）；航空科學基金（2020Z023053004）

無人機具有靈活性高、無人駕駛、自主控制、可操作性強等優(yōu)點，在區(qū)域偵察、快遞投送及農(nóng)業(yè)噴灑等眾多領域優(yōu)勢明顯，其軍用民用的價值愈發(fā)突出，應用也越加廣泛[1]。但是，當使用無人機集群執(zhí)行大規(guī)模任務時，任務中的子任務對無人機的要求以及無人機之間的性能也各不相同，任務的規(guī)劃分配存在挑戰(zhàn)[2]。學者們在無人機任務分配領域做了大量的研究，包括多架同構(gòu)或異構(gòu)無人機的任務分配。從算法的角度來看，任務分配問題是一個NP-hard問題。對于需要大量無人機參與的任務規(guī)劃，由于環(huán)境和無人機的各種限制，往往將任務規(guī)劃通過層次控制的方式劃分為若干層次[3]，將問題簡化為組合優(yōu)化問題，從而提高可行性和規(guī)劃模塊的可擴展性。目前，任務分配的頂層規(guī)劃分為集中式和分布式。

基于集中規(guī)劃的算法可以分為以下幾類：（1）優(yōu)化算法包括動態(tài)規(guī)劃算法[4]、分支定界算法[5]等；（2）啟發(fā)式隨機搜索算法不需要遍歷整個解空間來尋找最優(yōu)解，通常得到次優(yōu)解，遺傳算法[6]、粒子群優(yōu)化算法[7]和模擬退火算法[8]都屬于啟發(fā)式算法；（3）其他相關的算法，如S. Rathinam的常數(shù)因子逼近法[9]等。常見的確定性圖搜索算法，如A*算法[10-11]、Dijkstra算法、BellmanFord算法、廣度優(yōu)先搜索算法。

與集中式任務規(guī)劃相比，分布式規(guī)劃在通信帶寬要求、環(huán)境變化等方面更具優(yōu)勢，因此分布式規(guī)劃策略具有更廣泛的應用。關于分布式混合整數(shù)線性規(guī)劃框架下的任務規(guī)劃有很多研究，該框架對任務規(guī)劃問題描述具有較強的適應性。M. B. Dias等[12]提出的基于拍賣機制的規(guī)劃策略被廣泛應用于任務規(guī)劃。

盡管學者們提出了許多解決任務分配的相關算法，但在多無人機協(xié)同飛行執(zhí)行集群任務的分配問題并沒有得到很好的解決[13]。本文采用圖論表述任務中子任務之間的協(xié)同飛行關系，依據(jù)改進貪心算法提出了基于改進貪心算法的多無人機協(xié)同任務分配算法（MAA）。該算法結(jié)合改進貪心算法，根據(jù)最短時間或最短路徑的要求對任務進行分配，實現(xiàn)了多無人機集群協(xié)同飛行約束下的任務分配。MAA僅適用于具有時間序列協(xié)同飛行約束的任務分配。

1系統(tǒng)模型

1.2任務模型

任務可以根據(jù)任務描述劃分為多個子任務，用于執(zhí)行任務的無人機集群由能力不同的無人機組成，子任務可以由一架或多架無人機執(zhí)行。任務可以分為兩大類：所有無人機都需要執(zhí)行的全局任務和根據(jù)任務需求確定無人機的數(shù)量去執(zhí)行的局部任務。子任務模型如圖2所示。兩類任務又可以分為以下4個子類：

（1）全局點任務：所有無人機都需要執(zhí)行只包含一個坐標點的任務。

（2）局部點任務：只能分配給一架無人機，并且只包含一個坐標點。任務信息包括子任務點的坐標以及無人機在該點需要執(zhí)行的操作。

（3）局部線任務：只能分配給一架無人機，由多個坐標點組成。每個點的執(zhí)行順序已經(jīng)由任務需求確定。任務信息包括每個點的坐標以及無人機在每個點需要執(zhí)行的操作。

（4）局部區(qū)域任務：由一架或多架無人機執(zhí)行。任務信息包括構(gòu)成該區(qū)域的坐標集和無人機在該區(qū)域內(nèi)需要執(zhí)行的操作。

1.3時序協(xié)同約束

1.3.1協(xié)同約束定義

2基于改進貪心算法的多無人機協(xié)同任務分配

多無人機的協(xié)同任務分配需要保證子任務在宏執(zhí)行順序上和任務要求的時序上保持一致，因此將協(xié)同任務分配分為三個階段。子任務分配次序確定遍歷子任務的次序，確保子任務的執(zhí)行次序能夠符合時序要求；無人機的選擇階段是根據(jù)子任務的類型及規(guī)劃策略將子任務分配到無人機；最后，根據(jù)時序約束對任務隊列中子任務的次序調(diào)換，實現(xiàn)相應策略下的任務隊列優(yōu)化。

2.1確定子任務分配次序

依靠無人機之間的通信機制可以實現(xiàn)無人機子任務執(zhí)行狀態(tài)的發(fā)布，因此只需要保證子任務的遍歷分配順序和任務要求的時序順序保持一致，那么無人機在執(zhí)行子任務時通過向需要協(xié)同飛行的無人機通信發(fā)布自己的任務執(zhí)行狀態(tài)來控制子任務的執(zhí)行順序，保證子任務宏執(zhí)行次序的準確性，從而實現(xiàn)集群任務的時序約束規(guī)劃過程。

根據(jù)子任務之間時序約束以及保存時序約束有向圖的特點，圖論中的廣度優(yōu)先遍歷搜索方法能夠很好地滿足子任務訪問次序要求。采用廣度優(yōu)先遍歷方法遍歷任務的時序約束關系圖，針對每一子任務，選擇在相應策略下最合適的無人機來執(zhí)行子任務。

2.2無人機的選擇

3試驗及結(jié)果

為了簡化模型，假設無人機的飛行高度保持在一定高度不變。根據(jù)圖1所示模型可知，飛行高度決定了無人機的掃描半徑，那么無人機的掃描半徑也保持不變。使用表1的無人機進行任務分配，通過與基于貪心算法的多無人機協(xié)同任務分配算法（CMAG）、短距離優(yōu)先算法（SDF）和短時間優(yōu)先（STF）算法以及遺傳算法（GA），評估MAA算法。

圖4、圖5展示了由三種任務類型子任務組成的復合任務以及由單一類型子任務組成的任務使用不同算法的結(jié)果。從圖中可以看到，短距離優(yōu)先算法和短時間優(yōu)先算法由于不需要考慮時序協(xié)同約束關系，其分配結(jié)果相較于另外三種算法都有更好的性能。

在兩種分配策略下，對多類型子任務組成的任務進行分配的結(jié)果，MAA的算法都優(yōu)于GA算法且接近SDF或者STF，說明MAA取得的局部最優(yōu)結(jié)果接近最優(yōu)解。在對單一類型子任務組成的任務分配時，相比較于MAA通過局部的優(yōu)化，GA算法通過交叉變異過程能夠從更大的范圍找到更好的解，但其所獲取的解不能保證時序約束的準確性。

與CMAG算法相比，由于在子任務分配和無人機選擇兩個階段后進行了一定的任務隊列優(yōu)化，在復合類型或單一類型任務中的某些情況下任務分配效果都有一定的提升，最高提升達20%。

4結(jié)束語

本文提出一種基于改進貪心算法的異構(gòu)多無人機集群協(xié)同飛行任務分配算法。將任務分配與圖論中的廣度優(yōu)先遍歷方法相結(jié)合，采用改進貪心算法優(yōu)化任務分配過程，解決了將有時序約束的任務分配到無人機集群的任務分配問題。試驗結(jié)果表明，與傳統(tǒng)的遺傳算法等相比，MAA在解決多類型任務的任務分配問題上更接近最優(yōu)解。

參考文獻

[1]孫小雷，齊乃明，董程，等.無人機任務分配與航跡規(guī)劃協(xié)同控制方法[J].系統(tǒng)工程與電子技術，2015，37（12）：2772-2776. Sun Xiaolei， Qi Naiming， Dong Cheng， et al. Cooperative control method of UAV task allocation and track planning[J]. Systems Engineering and Electronic Technology， 2015，37 （12）： 2772-2776. （in Chinese）

[2]李華偉.多無人機協(xié)同任務規(guī)劃研究與實現(xiàn)[D].西安：西安電子科技大學，2014. Li Huawei. Research and implementation of multi UAV cooperative mission planning[D]. Xian：Xian University of Electronic Science and Technology， 2014. （in Chinese）

[3]Pachter M，Chandler P R. Challenges of autonomous control[J]. IEEE Control Systems Magazine，1998，18（4）：92-97.

[4]Sakoe H，Chiba S. Dynamic programming algorithm optimization for spoken word recognition[J]. IEEE Transactions on Acoustics，Speech，and Signal Processing，1978，26（1）： 43-49.

[5]Ross G T，Soland R M. A branch and bound algorithm for the generalized assignment problem[J]. Mathematical Programming，1975，8（1）：91-103.

[6]Ye F，Chen J，Tian Y，et al. Cooperative task assignment of a heterogeneous multi-UAV system using an adaptive genetic algorithm[J]. Electronics，2020，9（4）：687.

[7]Li M，Liu C，Li K，et al. Multi-task allocation with an optimized quantum particle swarm method[J]. Applied Soft Computing，2020，96：106603.