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

陳宇恒 陳進朝 陳雪聰

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

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

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

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

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

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

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

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

1系統(tǒng)模型

1.2任務(wù)模型

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

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

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

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

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

1.3時序協(xié)同約束

1.3.1協(xié)同約束定義

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

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

2.1確定子任務(wù)分配次序

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

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

2.2無人機的選擇

3試驗及結(jié)果

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

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

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

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

4結(jié)束語

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

參考文獻

[1]孫小雷，齊乃明，董程，等.無人機任務(wù)分配與航跡規(guī)劃協(xié)同控制方法[J].系統(tǒng)工程與電子技術(shù)，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é)同任務(wù)規(guī)劃研究與實現(xiàn)[D].西安：西安電子科技大學(xué)，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.