基于改進(jìn)蟻群算法的無人機(jī)集群任務(wù)分配和路徑規(guī)劃聯(lián)合優(yōu)化

蘇梅梅，程詠梅，胡勁文，趙春暉，賈彩娟，徐 釗，張劍鋒

（1.西北工業(yè)大學(xué)，西安 710000；2.西安愛生技術(shù)集團(tuán)公司，西安 710065）

1 引 言

隨著無人機(jī)飛行環(huán)境日益復(fù)雜和無人機(jī)性能等要求的提高，無人機(jī)編隊(duì)任務(wù)分配的安全性、資源分配均勻等需求也變得越來越高。之所以要進(jìn)行任務(wù)分配，是因?yàn)槎酂o人機(jī)在執(zhí)行任務(wù)時(shí)，無人機(jī)的油耗等資源受限，無人機(jī)的突發(fā)故障以及無人機(jī)任務(wù)之間的優(yōu)先級邏輯關(guān)系等都會(huì)影響無人機(jī)如何分配任務(wù)和執(zhí)行任務(wù)。根據(jù)各種約束信息下得出任務(wù)規(guī)劃指令，無人機(jī)才能在高保障、高效率、低消耗的需求下完成任務(wù)。目前，常用求解任務(wù)規(guī)劃的算法主要有基于集中式的線性規(guī)劃法、基于分布式市場機(jī)制的方法以及基于啟發(fā)式的算法等。

基于線性規(guī)劃的方法：該類方法主要通過建立滿足需求的線性目標(biāo)函數(shù)，2015年，Malvankar- Mehta[1]在復(fù)雜的有人/無人機(jī)器人任務(wù)分配系統(tǒng)，該團(tuán)隊(duì)針對有人/無人機(jī)器人任務(wù)分配問題，考慮各類風(fēng)險(xiǎn)因素以及人為因素的性能指標(biāo)，利用非線性規(guī)劃算法進(jìn)行求解，完成無人機(jī)任務(wù)分配。2016年，Berger 等[2]針對異構(gòu)飛行器靜態(tài)目標(biāo)搜索過程中的計(jì)算復(fù)雜度高的問題，提出了新的整數(shù)線性規(guī)劃和二次規(guī)劃公式，以降低計(jì)算復(fù)雜度和近似最優(yōu)地解決包含異構(gòu)智能體的離散靜態(tài)搜索路徑規(guī)劃問題，在計(jì)算代價(jià)較小的情形下獲得了包含異構(gòu)飛行器的近似最優(yōu)解。以同樣思維處理異構(gòu)機(jī)器人計(jì)算復(fù)雜度高問題的還有2017年Bays 等[3]，他們解決了異構(gòu)機(jī)器人團(tuán)隊(duì)服務(wù)代理運(yùn)輸過程中的任務(wù)分配問題。該過程是一個(gè)機(jī)器人根據(jù)任務(wù)的優(yōu)先順序，執(zhí)行多個(gè)任務(wù)的過程。該方式可以保證得到解的存在性以及降低計(jì)算復(fù)雜度，然而通常用來解決單一的任務(wù)中，解決方案較單一化，不能處理需要多機(jī)器人協(xié)作才能完成的任務(wù)。另外，隨著任務(wù)和機(jī)器人的增多，計(jì)算復(fù)雜度將呈指數(shù)級增長，這類方法的擴(kuò)展性和效率較弱。

基于市場機(jī)制的方法：該類方法[4]通?；诜植际降目蚣?，是解決多機(jī)器人任務(wù)分配(Multi Robot Task Allocation，MRTA)問題最流行的方法，如一級價(jià)格拍賣、動(dòng)態(tài)角色分配、交易機(jī)器人、默多克、德馬克夫、M+等。由于其良好的可擴(kuò)展性，這些方法特別適用于分布式機(jī)器人領(lǐng)域。在這些方法中，每個(gè)分布式代理都會(huì)計(jì)算一個(gè)完成任務(wù)的費(fèi)用，并廣播該任務(wù)的出價(jià)。拍賣機(jī)器人會(huì)決定最佳出價(jià)，而中標(biāo)者會(huì)嘗試執(zhí)行中標(biāo)的任務(wù)。它們有效地滿足了機(jī)器人的實(shí)際需求團(tuán)隊(duì)，同時(shí)通過捕獲分布式和分布式服務(wù)器各自的優(yōu)勢來產(chǎn)生有效的解決方案。但是，在任務(wù)分配過程中，如果通信成本太高，機(jī)器人的溝通性能會(huì)明顯下降[5]，因此這些方法適用于中小規(guī)模的任務(wù)分配。2018年，Bays 等[6]針對異構(gòu)結(jié)構(gòu)的空間約束的優(yōu)先約束問題，提出了一種帶有調(diào)度約束的分布式任務(wù)分配拍賣法，比使用整數(shù)線性規(guī)劃解決此類問題提高了計(jì)算效率。同樣，2011年，Chen等[7]研究了考慮資源約束的一組異構(gòu)移動(dòng)機(jī)器人的多機(jī)器人任務(wù)分配問題。機(jī)器人按照任務(wù)執(zhí)行所需要的資源來劃分。由于每個(gè)機(jī)器人可能沒有足夠的資源單獨(dú)完成分配的任務(wù)，因此在任務(wù)執(zhí)行中，機(jī)器人必須組成聯(lián)盟，以滿足任務(wù)強(qiáng)加的資源約束。

基于啟發(fā)式算法：與上述兩種算法不同，啟發(fā)式算法[8]在處理任務(wù)規(guī)劃問題時(shí)，由于其本身的隨機(jī)性不再是試圖搜索全局空間，而是在計(jì)算時(shí)間和最優(yōu)性能之間達(dá)到某些妥協(xié)，使得同時(shí)兼顧計(jì)算效率和性能之間平衡的一個(gè)次優(yōu)解。2013年，Yuan 等[9]為了解決多機(jī)器人系統(tǒng)的任務(wù)分配問題，提出了一種基于爆炸進(jìn)化的免疫遺傳算法。Manathara 等[10]針對多無人機(jī)作戰(zhàn)的最優(yōu)資源分配問題，針對多種異構(gòu)無人機(jī)設(shè)計(jì)了任務(wù)分配策略，并采用啟發(fā)式算法進(jìn)行求解。Marden等[11]針對多智能體系統(tǒng)中的分布式控制問題，考慮了分配效能函數(shù)設(shè)計(jì)問題，并分析了效能函數(shù)同納什平衡之間的關(guān)系。2013年，該團(tuán)隊(duì)針對多類資源分配問題，采用改進(jìn)的基于狀態(tài)的博弈論方法，進(jìn)一步優(yōu)化了效能函數(shù)，相比傳統(tǒng)的博弈論，提高了資源分配求解速度。2014年，Nagarajan等[12]通過最大限度地提高通信效率和處理成本，提出了一種適用于異構(gòu)多機(jī)器人系統(tǒng)任務(wù)處理的啟發(fā)式搜索任務(wù)分配算法。針對任務(wù)數(shù)量大于系統(tǒng)中機(jī)器人數(shù)量的給定問題，采用對等結(jié)構(gòu)算法找到近似最優(yōu)分配方案。且其研究了多機(jī)器人系統(tǒng)的任務(wù)分配過程，為了解決多機(jī)器人系統(tǒng)的最優(yōu)任務(wù)分配問題，針對動(dòng)態(tài)環(huán)境下多機(jī)器人系統(tǒng)的自主任務(wù)分配問題，采用了一種改進(jìn)的蟻群算法，考慮了任務(wù)約束和機(jī)器人能力。在所有情況下，蟻群算法都比IG 啟發(fā)式算法得到了更好的結(jié)果。2014年，美國珀杜大學(xué)Kim 等[13]針對異構(gòu)無人機(jī)的編隊(duì)區(qū)域搜索和任務(wù)分配問題，提出了一種基于響應(yīng)閾值模型的概率決策機(jī)制的分布式方法，考慮了環(huán)境的不確定性，實(shí)現(xiàn)了快速靈活的無人機(jī)區(qū)域搜索和任務(wù)分配。2019年，Zhao 等[14]利用強(qiáng)化學(xué)習(xí)算法Q-Learning 進(jìn)行快速任務(wù)分配，利用神經(jīng)網(wǎng)絡(luò)近似和經(jīng)驗(yàn)優(yōu)先重放，將在線計(jì)算轉(zhuǎn)移到離線學(xué)習(xí)過程中，具體就是開發(fā)了一個(gè)Q 網(wǎng)絡(luò)編碼分配規(guī)則，有效地將各種不同的任務(wù)分配給無人機(jī)。采取同樣方式的還有2019年Dai 等[15]為了解決環(huán)境探測中的多無人機(jī)協(xié)同搜索問題，通過采用基于拍賣方法、空缺鏈方法、基于策略選擇的Q-Learning 方法來求解多任務(wù)動(dòng)態(tài)勘察與破壞的問題。不同的是，該篇文章考慮的目標(biāo)具有反打擊能力，從而增加了問題的復(fù)雜性。2020年，Brown 等[16]研究了具有任務(wù)間優(yōu)先約束的應(yīng)用中大型機(jī)器人團(tuán)隊(duì)的順序任務(wù)分配和無碰撞路由問題，提出了一個(gè)層次算法來計(jì)算問題的最優(yōu)解。2020年，Gibson 等[17]利用A*算法實(shí)現(xiàn)了實(shí)時(shí)的多智能體路徑規(guī)劃算法。本文通過建立約束下的無人機(jī)模型，每個(gè)無人機(jī)的模型將在每個(gè)時(shí)間步驟中更新，并確定最終的控制。生成的路徑以路徑點(diǎn)序列的形式提供給無人機(jī)。2018年，Zhou 等[18]以固定翼無人機(jī)輔助MCS 系統(tǒng)為研究對象，從能效的角度研究了相應(yīng)的聯(lián)合路徑規(guī)劃和任務(wù)分配問題。將求解的聯(lián)合優(yōu)化問題轉(zhuǎn)化為雙邊兩階段匹配問題，第一階段采用動(dòng)態(tài)規(guī)劃或遺傳算法求解路徑規(guī)劃問題，第二階段采用Gale Shapley算法求解任務(wù)分配問題。然而，2019年，Hafez等[19]研究了無人機(jī)協(xié)同任務(wù)分配和協(xié)同飛行軌跡規(guī)劃問題，提出了一種新的層次模糊控制器和粒編隊(duì)算法。2019年，唐俊林等[20]基于合作型協(xié)同進(jìn)化算法的理念，提出了一種基于競爭型協(xié)同進(jìn)化的多傳感器任務(wù)規(guī)劃算法。首先，建立了防空多傳感器任務(wù)規(guī)劃數(shù)學(xué)模型；其次，基于競爭型協(xié)同算法建立框架，并設(shè)計(jì)了新的編碼方式，提出了交叉、變異以及沖突消解的策略。2020年，史人赫等[21]綜合考慮速度增量和變軌時(shí)間等指標(biāo)，基于雙脈沖霍曼轉(zhuǎn)移構(gòu)建了一種兩層任務(wù)規(guī)劃框架。在此基礎(chǔ)上，提出了一種新型網(wǎng)格編碼差分進(jìn)化方法。該方法引入序列逐次枚舉思想，快速生成滿足一對一任務(wù)約束的任務(wù)指派矩陣，并定制一種面向離散網(wǎng)格編碼的差分變異操作，在保證任務(wù)規(guī)劃方案可行性的前提下實(shí)現(xiàn)設(shè)計(jì)空間的高效探索，從而有效求解在軌服務(wù)任務(wù)規(guī)劃問題。

另外，還有一些學(xué)者采用其他方式實(shí)現(xiàn)任務(wù)分配的目的。例如，2019年，于曉強(qiáng)等[22]針對大型空間結(jié)構(gòu)的在軌裝配任務(wù)分配問題，提出了基于擴(kuò)展一致性算法的拍賣算法，在考慮在軌裝配過程中運(yùn)輸、安裝等任務(wù)的時(shí)間先后特性以及某些特定復(fù)雜任務(wù)需要多航天器協(xié)同完成的任務(wù)約束條件下，解決將各項(xiàng)任務(wù)分配給多個(gè)多種類航天器的在軌裝配任務(wù)分配問題。2019年，朱利等[23]為了在最短時(shí)間內(nèi)降低整個(gè)區(qū)域的環(huán)境不確定度，提高多無人機(jī)協(xié)同區(qū)域搜索效率，提出了一種基于Voronoi 圖質(zhì)心的多無人機(jī)協(xié)同區(qū)域搜索算法。針對不斷變化的環(huán)境信息，提出了Discrete Combined Partition and Search（DCPS）策略，該策略將Voronoi 圖質(zhì)心用于引導(dǎo)無人機(jī)運(yùn)動(dòng)，任務(wù)區(qū)域在每一步搜索時(shí)都會(huì)被重新進(jìn)行Voronoi 圖劃分。2021年，杜越洋等[24]針對無人機(jī)載荷選型以及載荷試驗(yàn)過程復(fù)雜、試驗(yàn)周期長、試驗(yàn)成本高的問題，設(shè)計(jì)了一種基于數(shù)據(jù)分發(fā)服務(wù)通信技術(shù)的無人機(jī)任務(wù)載荷綜合仿真平臺(tái)。

上文提到的方法都是先進(jìn)行任務(wù)分配，然后將任務(wù)分配的結(jié)果輸入到路徑規(guī)劃模塊生成所需要的路徑。未考慮任務(wù)分配和路徑規(guī)劃的耦合性。然而這一種處理方式在進(jìn)行任務(wù)分配時(shí)未考慮無人機(jī)本身的運(yùn)動(dòng)學(xué)約束，僅考慮任務(wù)之間的關(guān)系，路徑規(guī)劃的輸入是任務(wù)分配的結(jié)果，降低了問題求解的復(fù)雜度，但在實(shí)際任務(wù)中無法滿足需求。為了應(yīng)對以上困惑，很多學(xué)者將任務(wù)分配與路徑規(guī)劃耦合求解。2015年，Kim 等[25]針對無人機(jī)團(tuán)隊(duì)在不同目標(biāo)移動(dòng)的環(huán)境中執(zhí)行搜索和破壞任務(wù)，在此背景下作者將搜索計(jì)劃和任務(wù)分配在一個(gè)框架下進(jìn)行建模，提出了一種基于響應(yīng)閾值模型的概率決策機(jī)制的分布式方法，搜索計(jì)劃為每架無人機(jī)生成一個(gè)有效的搜索路徑，以方便快速地進(jìn)行目標(biāo)檢測。Deng 等[26]在考慮了UAV 的彈藥數(shù)量約束條件下，通過改變遺傳算法的基因編碼方式，完成了問題的求解。以上文獻(xiàn)均是基于集中式架構(gòu)完成協(xié)同任務(wù)規(guī)劃問題的建模與求解，將規(guī)劃運(yùn)算過程完全在地面站或某個(gè)UAV 上完成。2017年，崔乃剛等[27]以多異構(gòu)無人機(jī)執(zhí)行偵察、打擊以及評估任務(wù)為場景，利用分布式規(guī)劃框架和圖論思想對問題進(jìn)行建模，在考慮了避碰、燃油和任務(wù)次序約束條件下，采取遺傳算法進(jìn)行任務(wù)規(guī)劃問題的求解。然而其規(guī)劃出來的路徑存在交叉現(xiàn)象，會(huì)增加無人機(jī)間的防撞可能性。2019年，Albani 等[28]在多機(jī)器人的工作區(qū)域中利用分層任務(wù)分配與路徑規(guī)劃尋找框架，該框架擴(kuò)展了仿生多機(jī)器人任務(wù)分配（MRTA）框架，使用Floyd-Warshall 算法將任務(wù)分配問題與路徑規(guī)劃問題耦合求解。該框架主要包括三個(gè)步驟，分別是把每個(gè)機(jī)器人通過感知獲得可用的局部知識，以及與其他機(jī)器人交互的任務(wù)分配，利用其他機(jī)器人的知識制定運(yùn)動(dòng)規(guī)劃。

綜上所述，啟發(fā)式算法在耗時(shí)和解的最優(yōu)性能之間進(jìn)行綜合考慮，使得同時(shí)兼顧計(jì)算效率和和性能之間平衡的一個(gè)次優(yōu)解。其中，蟻群算法由于其分布式求解的方式，在解決多任務(wù)場景問題中受到廣泛的使用。另外，為了更符合實(shí)際應(yīng)用的需求，將任務(wù)分配與路徑規(guī)劃耦合求解是必不可少的。最重要的是，大部分學(xué)者在無人機(jī)任務(wù)規(guī)劃過程中都考慮了任務(wù)的約束和時(shí)間的約束，在規(guī)劃時(shí)往往會(huì)出現(xiàn)無人機(jī)沒有被分配到任務(wù)，原因是在規(guī)劃的過程當(dāng)中沒有考慮將所擁有無人機(jī)資源進(jìn)行充分利用的約束條件。

本文主要解決復(fù)雜多任務(wù)多編隊(duì)場景中，在考慮任務(wù)優(yōu)先級、航路最短以及耗時(shí)最短等約束，建立任務(wù)分配和路徑規(guī)劃的聯(lián)合優(yōu)化模型，采用改進(jìn)的蟻群算法實(shí)現(xiàn)任務(wù)規(guī)劃。其中，改進(jìn)的蟻群算法主要是為了避免在任務(wù)分配過程當(dāng)中出現(xiàn)路徑交叉、資源分配不均勻的問題。為了解決該問題，本文主要通過引入執(zhí)行任務(wù)的編隊(duì)數(shù)量的約束，且改進(jìn)信息素更新機(jī)制來實(shí)現(xiàn)。

2 問題描述

2.1 任務(wù)分配和路徑規(guī)劃聯(lián)合優(yōu)化模型

任務(wù)分配是運(yùn)籌學(xué)中基本的組合優(yōu)化問題。多無人機(jī)任務(wù)分配是指在給定無人機(jī)種類和數(shù)量前提下，充分考慮戰(zhàn)場環(huán)境、任務(wù)要求和載荷能力約束，研究如何將合適的任務(wù)在合適的時(shí)間分配給合適的無人機(jī)。典型的任務(wù)分配模型有基于旅行商（Travelling Salesman Problem，TSP）模型、混合整數(shù)線性規(guī)劃（Mixed-Integer Linear Programming, MILP）模型、車輛路徑問題（Vehicle Routing Problem, VRP）模型、指派問題模型及運(yùn)輸問題模型。上述模型通常用于單智能體場景中。隨著信息技術(shù)的發(fā)展，無人機(jī)的能力和應(yīng)用領(lǐng)域越來越廣泛。為了完成一項(xiàng)復(fù)雜的任務(wù)，需要多無人機(jī)合作和協(xié)調(diào)。復(fù)雜環(huán)境下的多無人機(jī)系統(tǒng)的協(xié)作與分配是研究熱點(diǎn)問題。

本文旨在解決復(fù)雜環(huán)境中，大型固定翼無人機(jī)投放小型固定翼無人機(jī)群，在經(jīng)過巡航階段后，抵近目標(biāo)區(qū)域，進(jìn)行地毯式搜索偵察、干擾等任務(wù)。在整個(gè)過程中，無人機(jī)編隊(duì)的任務(wù)規(guī)劃包括任務(wù)規(guī)劃和分配、航路規(guī)劃。本文研究的是多無人機(jī)編隊(duì)多類型任務(wù)分配問題以及航跡規(guī)劃問題，由大型無人機(jī)攜帶小型無人機(jī)群飛往任務(wù)執(zhí)行區(qū)，首先通過大飛機(jī)拋撒小型無人機(jī)群，再通過任務(wù)分配指令將小無人機(jī)群分成多個(gè)任務(wù)組進(jìn)行巡航至任務(wù)地點(diǎn)，以不同的任務(wù)隊(duì)形執(zhí)行任務(wù)。每個(gè)無人機(jī)編隊(duì)由一個(gè)無人機(jī)做長機(jī)，多個(gè)無人機(jī)做僚機(jī)來實(shí)現(xiàn)隊(duì)形的控制。任務(wù)分配準(zhǔn)則是整體工作效益最大化、耗時(shí)最小化。下面將對含約束情況下的任務(wù)分配模型建立展開詳細(xì)的介紹。本文的任務(wù)規(guī)劃場景示意圖如圖1 所示。

圖1 多任務(wù)多編隊(duì)任務(wù)規(guī)劃的示意圖Fig.1 Multi-task multi-subgroup task planning

如上述任務(wù)場景所示，假設(shè)有N個(gè)無人機(jī)編隊(duì)組成的固定翼無人機(jī)集群集合U=[U1,U2,…,UN]，K個(gè)任務(wù)的集合M=[M1,M2,…,MK]，每個(gè)固定翼無人機(jī)編隊(duì)均可執(zhí)行任意任務(wù)，每個(gè)任務(wù)需要的編隊(duì)數(shù)量小于等于1，不同的任務(wù)需要無人機(jī)編隊(duì)用不同的隊(duì)形去完成。例如，偵察任務(wù)需要使用“一字隊(duì)形”才能保證偵察范圍的覆蓋率。而突防攻擊任務(wù)需要使用“三角隊(duì)形”才能保證前方無人機(jī)攻擊后方無人機(jī)掩護(hù)的安全性。

與傳統(tǒng)任務(wù)分配建模不同，本文的固定翼無人機(jī)編隊(duì)在選擇執(zhí)行任務(wù)時(shí)，會(huì)同時(shí)兼顧任務(wù)的優(yōu)先級順序和距離約束進(jìn)行選擇。具體是指，每個(gè)固定翼無人機(jī)編隊(duì)在選擇任務(wù)區(qū)域時(shí)根據(jù)自己的隊(duì)形優(yōu)先選擇與自己相對應(yīng)的任務(wù)區(qū)域，因而每個(gè)編隊(duì)都有自己對應(yīng)的優(yōu)先級準(zhǔn)則，當(dāng)排在優(yōu)先級最前面的任務(wù)完成時(shí)，再去變換隊(duì)形完成下一個(gè)優(yōu)先級的任務(wù)。要求當(dāng)任務(wù)分配結(jié)束后，必須保證所有任務(wù)均被執(zhí)行。因此，對于編隊(duì)U1來講，其執(zhí)行任務(wù)的優(yōu)先級是M1,M2,…,MK，對編隊(duì)U2來講， 其執(zhí)行任務(wù)的優(yōu)先級是M2,M3, …,M K,M1，對于編隊(duì)Un來講，其執(zhí)行任務(wù)的優(yōu)先級是MK,…,M2,M1。另外，通過設(shè)計(jì)任務(wù)評價(jià)矩陣來判斷該無人機(jī)是否已經(jīng)執(zhí)行任務(wù)，如果無人機(jī)已經(jīng)執(zhí)行任務(wù)，則該無人機(jī)的任務(wù)評價(jià)矩陣為零。本文的目標(biāo)是將K個(gè)任務(wù)分配給N個(gè)無人機(jī)編隊(duì)，使得在能耗和時(shí)間消耗最少的情況下總體收益最大。綜上所述，本文設(shè)計(jì)如下的任務(wù)和路徑規(guī)劃模型。

假設(shè)：（1）UAV 的燃油限制約束可以等價(jià)于UAV 的最長飛行時(shí)間；（2）無人機(jī)可以正常通信，不受通信干擾，甚至通信中斷；（3）UAV 在任務(wù)期間不會(huì)被破壞。

其中，J函數(shù)為本文的優(yōu)化指標(biāo)；為本文的任務(wù)分配和路徑規(guī)劃的綜合代價(jià)；1L 代表時(shí)間的約束；2L 代表任務(wù)分配到無人機(jī)的值；3L 代表一個(gè)任務(wù)僅需要一個(gè)編隊(duì)來完成。通常，任務(wù)規(guī)劃是在上述約束條件下進(jìn)行任務(wù)分配。

不同于傳統(tǒng)的建模方式，本文為了充分利用所有的編隊(duì)資源，使得任務(wù)完成的時(shí)間消耗最少，并兼顧執(zhí)行任務(wù)的優(yōu)先級別和路徑最優(yōu)的原則。設(shè)置了約束條件L4和L5，pUAVi代表i號編隊(duì)的位置，Mpj代表j號任務(wù)的位置。L4代表每個(gè)無人機(jī)編隊(duì)在選擇任務(wù)時(shí)仍要考慮就近原則，即假設(shè)對于任務(wù)M1來講，編隊(duì)U1和編隊(duì)U2均搜索到任務(wù)M1，按照任務(wù)優(yōu)先級，此時(shí)應(yīng)該編隊(duì)U1去執(zhí)行M1，然而此時(shí)編隊(duì)U2距離M1更近，且若編隊(duì)U1去執(zhí)行M1可能會(huì)與其他編隊(duì)的路徑出現(xiàn)交叉，會(huì)增大編隊(duì)之間的碰撞的可能性。因此，本文將會(huì)安排編隊(duì)U2去執(zhí)行M1，編隊(duì)U1去執(zhí)行其他任務(wù)。L5條件是指執(zhí)行任務(wù)的編隊(duì)數(shù)量和所擁有的編隊(duì)總數(shù)量相等，該約束避免了出現(xiàn)無人機(jī)沒有被分配到任務(wù)的情況。

2.2 無人機(jī)集群編隊(duì)ID 設(shè)計(jì)

在進(jìn)行無人機(jī)多編隊(duì)任務(wù)分配和路徑規(guī)劃之前，本文首先將散亂的無人機(jī)群通過調(diào)用ID 的方式實(shí)現(xiàn)各編隊(duì)的集結(jié)。ID 表示包括編隊(duì)編號和各編隊(duì)各無人機(jī)的編號。然而，在編程過程中考慮到變量名的第一個(gè)字符不能是數(shù)字，所以本文將采用UAV+ID 作為這架飛機(jī)的名字。

（1）方法1：十進(jìn)制數(shù)表示法

由于本文的無人機(jī)數(shù)量為30 架，因此本文通過三位十進(jìn)制數(shù)來設(shè)計(jì)ID 編號，如圖2 所示，其中，百分位的十進(jìn)制數(shù)代表無人機(jī)編隊(duì)的編號，十分位和個(gè)位的十進(jìn)制數(shù)的組合代表編隊(duì)中各無人機(jī)的編號。因此，利用十進(jìn)制數(shù)設(shè)計(jì)的無人機(jī)ID 的格式為UAV101，UAV315 等。其分別代表1 號編隊(duì)中的1 號無人機(jī)，3 號編隊(duì)中的15 號無人機(jī)。

圖2 基于十進(jìn)制編隊(duì)ID 的設(shè)計(jì)Fig.2 Design of formation ID based on decimal

（2）方法2：二進(jìn)制數(shù)表示法

另外一種設(shè)計(jì)無人機(jī)ID 的方式是采用二進(jìn)制的方式。與方法1 類似，編隊(duì)ID 的設(shè)計(jì)包含編隊(duì)編號和編隊(duì)中各無人機(jī)的編號，總共包含8位，前四位是指無人機(jī)編隊(duì)的編號，后四位是指編隊(duì)中各無人機(jī)的編號。如圖3 所示，例如，00010010 和00100011 則分別代表1 號編隊(duì)中的2號無人機(jī)和2 號編隊(duì)中的3 號無人機(jī)。

圖3 基于二進(jìn)制編隊(duì)ID 的設(shè)計(jì)Fig.3 Design of formation ID based on binary

通過對比分析，為了更加清晰易懂地識別編隊(duì)編號，本文選用方法1 來設(shè)計(jì)各無人機(jī)的ID編號。由于本文在集中式框架下進(jìn)行編隊(duì)，在分配任務(wù)時(shí)，將各編隊(duì)視為整體。

3 基于改進(jìn)的蟻群算法的任務(wù)分配和路徑規(guī)劃

與傳統(tǒng)的蟻群算法不同的是，本文將任務(wù)分配和路徑規(guī)劃耦合討論。由2.1 節(jié)建模分析可知，多無人機(jī)多任務(wù)規(guī)劃問題是一個(gè)典型的組合優(yōu)化問題，且在文獻(xiàn)[29-30]中已經(jīng)證明了該問題是一個(gè)NP-hard 問題，因此其求解難度很大。正如研究現(xiàn)狀分析可知，為了降低求解難度，通常任務(wù)分配與路徑規(guī)劃可分為兩個(gè)子問題來求解，路徑規(guī)劃的輸入是任務(wù)分配的任務(wù)序列，弱化其兩者之間的耦合性。然而，這種處理方式往往不考慮模型自身的運(yùn)動(dòng)學(xué)約束、任務(wù)之間的相互影響，以及任務(wù)分配取決于路徑長度，只有根據(jù)分配策略才能獲得準(zhǔn)確的路徑長度等因素。因此，任務(wù)分配與路徑規(guī)劃問題必須耦合[31]分析才滿足實(shí)際要求。

另外，為了考慮任務(wù)優(yōu)先級順序和充分利用無人機(jī)編隊(duì)資源的約束，本文設(shè)計(jì)新的信息素更新機(jī)制。傳統(tǒng)的蟻群算法信息素更新機(jī)制，對于螞蟻來講，每個(gè)任務(wù)對應(yīng)的Q 是在同樣的條件下進(jìn)行更新的。即在同樣的信息素濃度增強(qiáng)系數(shù)的影響下，螞蟻搜索任務(wù)時(shí)不會(huì)考慮任務(wù)的優(yōu)先級順序。然而，這種更新機(jī)制在本文的任務(wù)背景下會(huì)導(dǎo)致無人機(jī)編隊(duì)在執(zhí)行任務(wù)時(shí)有可能存在隊(duì)形不斷切換的問題，增加了問題的復(fù)雜性。

為了解決上述問題，本文在使用蟻群算法求解多任務(wù)分配問題時(shí)，將本文所期望的整體收益函數(shù)模塊加入到概率更新公式中，使得蟻群在搜索的過程中有著更多的啟發(fā)信息。更有針對性地找到滿足本文需求的目標(biāo)，改善了傳統(tǒng)蟻群算法的隨機(jī)性和解的最優(yōu)性。為了使得無人機(jī)編隊(duì)在搜索尋找任務(wù)時(shí)能夠兼顧任務(wù)的優(yōu)先級約束，保證無人機(jī)在任務(wù)分配過程中，能夠充分利用資源，使得總體工作時(shí)間盡可能較少，本文通過把任務(wù)優(yōu)先級因素考慮到信息素更新機(jī)制中。具體是指，通過對無人機(jī)編隊(duì)和任務(wù)進(jìn)行編號，相應(yīng)的編隊(duì)對應(yīng)的與其隊(duì)形相符合的任務(wù)。螞蟻在搜索任務(wù)時(shí)，如果無人機(jī)編隊(duì)編號與任務(wù)編號對應(yīng)，則其留下的信息素濃度將會(huì)更多，反之，當(dāng)無人機(jī)編隊(duì)搜索到的任務(wù)編號不對應(yīng)時(shí)，其留下的信息素濃度會(huì)較少。信息素增強(qiáng)度系數(shù)Q的設(shè)置如下。

同時(shí)，本文在進(jìn)行任務(wù)分配的同時(shí)，兼顧路徑規(guī)劃的實(shí)際情況。首先，將任務(wù)隨機(jī)分配給某個(gè)節(jié)點(diǎn)處。然后根據(jù)當(dāng)前螞蟻編號，臨界點(diǎn)矩陣采取不同的分配策略的螞蟻編號的臨界點(diǎn)。其中螞蟻在公式(2)信息素增強(qiáng)因子啟示下，散布信息素濃度，更新信息素濃度。螞蟻根據(jù)信息素規(guī)則，每個(gè)任務(wù)分配好無人機(jī)編隊(duì)后，本文同時(shí)進(jìn)行路徑規(guī)劃的求解，在任務(wù)分配過程中，無人機(jī)獲得無人機(jī)任務(wù)序列后，路徑規(guī)劃過程為每個(gè)無人機(jī)生成可飛行安全的路徑，以最小化/最大化預(yù)定義的目標(biāo)函數(shù)，如尋求最短的飛行路徑。

其中，τij(t)為t時(shí)刻節(jié)點(diǎn)i與節(jié)點(diǎn)j之間的信息素濃度；ρ為信息揮發(fā)因子；α為信息啟發(fā)因子；β為期望啟發(fā)式因子；H(dij,Cost(U i,Mj))為固定翼無人機(jī)編隊(duì)任務(wù)分配和路徑規(guī)劃的綜合代價(jià)；Cost(U i,Mj)為蟻群根據(jù)任務(wù)執(zhí)行難易程度選擇任務(wù)i的代價(jià)；dij為無人機(jī)編隊(duì)與任務(wù)之間的距離。本文所提算法的流程圖如圖4 所示。

圖4 改進(jìn)的蟻群算法的流程圖Fi g.4 Flow chart of improved ACO

本文所提算法的運(yùn)算復(fù)雜度分析如下：假設(shè)每個(gè)編隊(duì)需要執(zhí)行n個(gè)任務(wù)，采用改進(jìn)的蟻群算法的求解運(yùn)算時(shí)間復(fù)雜度為O(n4)；空間復(fù)雜度O(n2)。根據(jù)編程過程當(dāng)中循環(huán)迭代機(jī)制，其中n是任務(wù)數(shù)量，m是螞蟻數(shù)量，T是迭代次數(shù)，m通常取n的2/3，記m=2n/3；T通常取n的倍數(shù)，記T=k·n，則時(shí)間復(fù)雜度2n(n–1)nTnk/3，當(dāng)n趨于無窮大時(shí)，k會(huì)遠(yuǎn)小于n，故時(shí)間復(fù)雜度為O(n4)?？臻g復(fù)雜度n·n+n·m，當(dāng)n趨于無窮大時(shí)，空間復(fù)雜度約等于n2，故空間復(fù)雜度為O(n2)。

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

本文在MATLAB2019b 平臺(tái)進(jìn)行仿真驗(yàn)證，將進(jìn)行多組仿真實(shí)驗(yàn)驗(yàn)證本文算法。本文將通過性能指標(biāo)來分析算法的有效性。為了充分驗(yàn)證本文所提出算法的正確性，設(shè)置了三種情形，分別是編隊(duì)個(gè)數(shù)小于任務(wù)個(gè)數(shù)、編隊(duì)個(gè)數(shù)等于任務(wù)個(gè)數(shù)以及編隊(duì)個(gè)數(shù)大于任務(wù)個(gè)數(shù)。并分別采用傳統(tǒng)的蟻群算法和本文提出的改進(jìn)的蟻群算法進(jìn)行對比，充分展示本文保證資源充分利用以及距離約束條件下的任務(wù)規(guī)劃結(jié)果。

4.1 性能指標(biāo)

為了評價(jià)本文算法的有效性，本文設(shè)置以下性能指標(biāo)。

（1）任務(wù)完成數(shù)量等于K；

（2）執(zhí)行任務(wù)的無人機(jī)編隊(duì)量等于N；

（3）每個(gè)編隊(duì)路徑的重合度為0；

（4）資源分配不均勻度（無人機(jī)閑置個(gè)數(shù)）為Y。

4.2 仿真任務(wù)場景設(shè)置

在實(shí)驗(yàn)的過程中，蟻群的數(shù)量很重要，因?yàn)橄伻簲?shù)量過大，會(huì)導(dǎo)致搜索過的路徑上信息素變化趨于平均，這樣就不好找出好的路徑了；蟻群數(shù)量過小時(shí)，易使未被搜索到的路徑信息素減小到0，這樣可能會(huì)出現(xiàn)早熟，沒找到全局最優(yōu)解。通常，在時(shí)間等資源條件緊迫的情況下，螞蟻數(shù)設(shè)定為城市數(shù)的1.5 倍較穩(wěn)妥。本文主要設(shè)置了三種任務(wù)，分別是抵近偵察、協(xié)同干擾和電子對抗。

為了進(jìn)一步說明本文所提算法的有效性，將分別討論無人機(jī)編隊(duì)個(gè)數(shù)和任務(wù)個(gè)數(shù)相等和不等的情形下進(jìn)行仿真驗(yàn)證。在仿真環(huán)境中本文設(shè)置了最多五個(gè)無人機(jī)編隊(duì)和最多五個(gè)任務(wù)，并根據(jù)優(yōu)先級順序依次注明無人機(jī)編隊(duì)標(biāo)識和任務(wù)標(biāo)識，分別是{U1,U2,U3,U4,U5}和{M1,M2,M3,M4,M5}。通過多次測試，參數(shù)A=200、B=50效果最為滿意，根據(jù)本文的三種任務(wù)場景的難易程度，本文設(shè)置Cost(U i,Mj)矩陣如下：

4.3 多任務(wù)多編隊(duì)任務(wù)規(guī)劃仿真驗(yàn)證與分析

本文的子群集結(jié)仿真結(jié)果如圖5 所示，藍(lán)色的“■”代表無人機(jī)的起始位置，紅色的“▲”代表無人機(jī)的目標(biāo)位置。紅色的軌跡代表Leader 的飛行軌跡，其余黑色軌跡代表Follower 的飛行 軌跡。在不碰撞的前提下，30 架任意初始位置的無人機(jī)通過對ID 的調(diào)用，使用集結(jié)控制算法，經(jīng)過400s 后，實(shí)現(xiàn)了三個(gè)子群的分群。每個(gè)子群集結(jié)成各自所指定的隊(duì)形，分別為一字形、三角形以及圓周隊(duì)形。

圖5 基于ID 的無人機(jī)編隊(duì)集結(jié)仿真圖Fig.5 UAV subgroup aggregation based ID

情形1：編隊(duì)個(gè)數(shù)小于任務(wù)個(gè)數(shù)(N

根據(jù)圖6(a)可知，當(dāng)編隊(duì)個(gè)數(shù)小于任務(wù)個(gè)數(shù)時(shí)，利用蟻群算法求解任務(wù)規(guī)劃問題時(shí)，存在兩個(gè)無人機(jī)編隊(duì)路徑交叉的現(xiàn)象。通過本文所提出的啟發(fā)式蟻群算法，當(dāng)編隊(duì)個(gè)數(shù)小于任務(wù)個(gè)數(shù)時(shí)，充分利用了每個(gè)無人機(jī)編隊(duì)資源，并且在兼顧距離約束和編隊(duì)執(zhí)行任務(wù)的優(yōu)先順序約束的條件下，滿足本文任務(wù)分配和路徑規(guī)劃的性能指標(biāo)，分配結(jié)果如圖6(b)所示。表1 對比說明了本文所提算法路徑重合度優(yōu)于傳統(tǒng)的蟻群算法，即防撞性能更優(yōu)。

圖6 傳統(tǒng)的和改進(jìn)的蟻群任務(wù)分配與路徑規(guī)劃仿真圖(N < K)Fig.6 Traditional and improved ACO task assignment and path planning(N < K)

表1 多任務(wù)多編隊(duì)任務(wù)分配和路徑 規(guī)劃指標(biāo)（情形1）Table 1 Index of multi-task, multi-subgroup task allocation and path planning (case 1)

情形2：編隊(duì)個(gè)數(shù)等于任務(wù)個(gè)數(shù)(N=K)

根據(jù)圖7(a)可知，當(dāng)編隊(duì)個(gè)數(shù)等于任務(wù)個(gè)數(shù)時(shí)，利用蟻群算法求解任務(wù)規(guī)劃問題時(shí)，同樣存在兩個(gè)無人機(jī)編隊(duì)“空閑”的現(xiàn)象。通過本文所提出的啟發(fā)式蟻群算法，當(dāng)編隊(duì)個(gè)數(shù)等于任務(wù)個(gè)數(shù)時(shí)，充分利用每個(gè)無人機(jī)編隊(duì)資源，并且在兼顧距離約束和編隊(duì)執(zhí)行任務(wù)的優(yōu)先順序約束的條件下，滿足本文任務(wù)分配和路徑規(guī)劃的性能指標(biāo)，分配結(jié)果如圖7(b)所示。表2 說明本文所提算法在該場景中資源分配更加均勻，不存在無人機(jī)空閑的情形。

圖7 傳統(tǒng)的和改進(jìn)的蟻群任務(wù)分配與路徑規(guī)劃仿真圖(N = K)Fig.7 Traditional and improved ACO task assignment and path planning(N = K)

表2 多任務(wù)多編隊(duì)任務(wù)分配和路徑 規(guī)劃指標(biāo)（情形2）Table 2 Index of multi-task, multi-subgroup task allocation and path planning (case 2)

情況3：編隊(duì)個(gè)數(shù)大于任務(wù)個(gè)數(shù)(N>K)

根據(jù)圖8(a)可知，當(dāng)編隊(duì)個(gè)數(shù)大于任務(wù)個(gè)數(shù)時(shí)，利用蟻群算法求解任務(wù)規(guī)劃問題時(shí)，同樣存在三個(gè)無人機(jī)編隊(duì)“空閑”的現(xiàn)象。經(jīng)過本文所提出的啟發(fā)式蟻群算法，當(dāng)編隊(duì)個(gè)數(shù)大于任務(wù)個(gè)數(shù)時(shí)，由于每個(gè)任務(wù)僅需要一個(gè)編隊(duì)執(zhí)行，所以仍然存在兩個(gè)編隊(duì)閑置，但與傳統(tǒng)的蟻群算法相比，本文所提算法充分利用了每個(gè)無人機(jī)編隊(duì)資源，并且在兼顧距離約束和編隊(duì)執(zhí)行任務(wù)的優(yōu)先順序約束的條件下，滿足本文任務(wù)分配和路徑規(guī)劃的性能指標(biāo)，分配結(jié)果如圖8(b)所示。同時(shí)，表3 表明在該場景中本文所提算法的分配均勻度優(yōu)于傳統(tǒng)的蟻群算法。

表3 多任務(wù)多編隊(duì)任務(wù)分配和路徑規(guī)劃指標(biāo)（情形3） Table 3 Index of multi-task, multi-subgroup task allocation and path planning (case 3)

圖8 傳統(tǒng)的和改進(jìn)的蟻群任務(wù)分配與路徑規(guī)劃仿真圖(N > K)Fig.8 Traditional and improved ACO task assignment and path planning(N > K)

5 結(jié) 論

本文主要解決了多任務(wù)多編隊(duì)的任務(wù)分配和路徑規(guī)劃問題。通過對現(xiàn)有的任務(wù)分配算法進(jìn)行調(diào)研發(fā)現(xiàn)，蟻群算法是解決多編隊(duì)多任務(wù)分配和路徑規(guī)劃有效的解決算法，在保證較優(yōu)解的同時(shí)計(jì)算效率也可滿足需求。同時(shí)，指出了任務(wù)分配和路徑規(guī)劃過程中沒能充分利用資源，使得出現(xiàn)無人機(jī)“空閑”的問題，以及路徑交叉問題。針對上述問題，本文通過分析多任務(wù)多編隊(duì)的任務(wù)分配和路徑規(guī)劃的實(shí)際需求，在考慮距離、時(shí)間以及任務(wù)優(yōu)先級等約束基礎(chǔ)上，建立了任務(wù)分配和路徑規(guī)劃耦合的優(yōu)化模型，且提出了啟發(fā)式的蟻群算法。最后，通過仿真驗(yàn)證本文算法與傳統(tǒng)蟻群算法的效果對比，證明了本文算法的有效性。