張文博 劉君蘭 李瑜 王海林

摘要：無人機具有體積小、靈活性好、經(jīng)濟效益高、操作簡單等特點，因此，被廣泛應(yīng)用于民生和軍事領(lǐng)域。面對復(fù)雜多任務(wù)需求，單無人機由于受到載荷數(shù)量、儲能、單一功能等因素的限制，在執(zhí)行任務(wù)時具有一定的局限性，多無人機協(xié)同作業(yè)更具優(yōu)勢。任務(wù)規(guī)劃是多無人機協(xié)同作業(yè)的關(guān)鍵技術(shù)之一，主要包括任務(wù)分配、航跡規(guī)劃、數(shù)據(jù)鏈路規(guī)劃、任務(wù)載荷規(guī)劃和應(yīng)急處置規(guī)劃等。對多無人機任務(wù)分配和航跡規(guī)劃方法進行簡單的介紹和對比，重點就任務(wù)分配集中式和分布式方法進行了講解，分析了多無人機任務(wù)規(guī)劃的進一步的研究方向。

關(guān)鍵詞：任務(wù)分配；航跡規(guī)劃；智能優(yōu)化算法；集中式方法；分布式方法

中圖分類號：TP18文獻標志碼：A文章編號：1008-1739（2022）20-52-5

0引言

多無人機任務(wù)規(guī)劃是指根據(jù)無人機需要完成的任務(wù)、無人機的數(shù)量以及無人機的載荷類型，為各無人機分配任務(wù)、規(guī)劃航線、合理調(diào)度，從而達到最大效益。無人機任務(wù)規(guī)劃一般包括航跡規(guī)劃、任務(wù)分配、數(shù)據(jù)鏈路規(guī)劃、任務(wù)載荷規(guī)劃和應(yīng)急處置規(guī)劃等。其中，任務(wù)分配和航跡規(guī)劃是關(guān)鍵技術(shù)。任務(wù)分配的評價指標主要有任務(wù)均衡、飛行距離、消耗成本和毀傷代價等。任務(wù)分配需要遵循的原則是分配給無人機的任務(wù)要和無人機上的載荷相匹配，任務(wù)分配要保證任務(wù)均衡，盡量避免出現(xiàn)大量無人機“空閑”的情況。

1任務(wù)分配模型

多無人機任務(wù)分配典型模型有多旅行商模型、車輛路徑模型和混合整數(shù)線性規(guī)劃模型。這些模型相對簡單，并且研究成熟，能用于表示一些簡單的任務(wù)規(guī)劃問題，任務(wù)分配如圖1所示。

多旅行商模型映射到多無人機任務(wù)分配中，就是讓無人機從各自起點出發(fā)，分別走一段路到達分配的一個或多個目標任務(wù)點，保證最終每個目標任務(wù)點有且僅只有一個無人機經(jīng)過，無人機再返回到自身起點，使得總路徑最短[1]。

車輛路徑模型映射到多無人機任務(wù)分配問題上，無人機相當于配送中心，任務(wù)目標點相當于客戶點。多個配送中心對應(yīng)多個無人機，決定客戶點由哪個配送中心服務(wù)相當于決定任務(wù)由哪個無人機執(zhí)行。規(guī)劃出合理的分配方式以及路徑，使得收益最大化。

混合整數(shù)線性規(guī)劃模型就是指擬合的目標函數(shù)是線性的，所有的約束也是線性的，同時部分求解的決策變量必須是整數(shù)。映射到多無人機任務(wù)分配上，就是要合理分配任務(wù)給每一個無人機，在滿足各約束的情況下，使得任務(wù)效益函數(shù)值最大。常用求解方法有圖解法、匈牙利法和分支定界法等。

2任務(wù)分配方法

多無人機任務(wù)分配方法根據(jù)是否有控制中心分為集中式方法、分布式方法以及二者相結(jié)合的分層次分布式方法。

2.1集中式方法

集中式任務(wù)分配方法由一個地面站或者中心無人機為每個無人機生成任務(wù)序列，通過通信鏈路將規(guī)劃結(jié)果傳遞到各無人機上，基于地面站控制的多無人機任務(wù)分配如圖2所示。集中式方法由控制中心完成規(guī)劃，能對全局問題進行求解和優(yōu)化，理論上可獲得全局最優(yōu)的任務(wù)分配方案[2]，但集中式方法計算量大、實時性差、動態(tài)規(guī)劃能力弱、對通信網(wǎng)絡(luò)要求高。

集中式方法主要分為最優(yōu)化方法和啟發(fā)式方法。

①最優(yōu)化方法是將任務(wù)分配問題看作一個組合優(yōu)化問題，主要包括窮舉法、混合整數(shù)線性法和圖論法等。窮舉法簡單易實現(xiàn)、魯棒性強，但計算速度慢，適用于小規(guī)模任務(wù)分配。混合整數(shù)線性法根據(jù)任務(wù)約束條件來構(gòu)建線性目標函數(shù)求極值，該方法精確度高、計算速度快。然而，混合整數(shù)線性法對于復(fù)雜高維環(huán)境，不一定能求出有效解。圖論法將無人機與任務(wù)的關(guān)系映射到圖中，通過圖來設(shè)計合理的分配方案，適用于小規(guī)模多無人機多任務(wù)分配問題。

②啟發(fā)式方法就是在一定時間范圍內(nèi)，在解空間中尋找滿足各約束條件的局部最優(yōu)解，主要有列表算法、聚類算法和智能類算法。列表算法給每一個任務(wù)構(gòu)建一個優(yōu)先級函數(shù)，確定任務(wù)執(zhí)行的順序，分配給每個無人機，適用于有明確優(yōu)先級的任務(wù)分配情況。Levchuk等[3]利用多維動態(tài)列表規(guī)劃方法完成了作戰(zhàn)任務(wù)中的平臺資源分配。聚類算法的目的是使得聚類后類內(nèi)的節(jié)點盡量接近，類之間的節(jié)點盡量遠離，通過將任務(wù)進行聚類，從而形成與無人機數(shù)量相等的任務(wù)簇，能有效規(guī)劃出合理的分配方案。Zhao等[4]利用K-means聚類算法實現(xiàn)了多機任務(wù)分配。

智能類算法大多通過模仿自然界中生物群體的行為，來尋求最優(yōu)解，典型算法有遺傳算法、粒子群算法和蟻群算法等。

遺傳算法是基于生物遺傳進化過程的算法，通過交叉、變異和遺傳等步驟進一步優(yōu)化解。該算法不受問題限制，適用性強。遺傳算法相較于其他啟發(fā)式算法，有較好的應(yīng)用前景和實用性[5]。王超等[6]利用多車場車輛路徑規(guī)劃模型，建立了多無人機多任務(wù)規(guī)劃模型，利用改進的遺傳算法對所建立的模型進行分析求解，獲得無人機的任務(wù)執(zhí)行的先后順序以及安全的航跡。吳蔚楠等[7]提出改進分布式遺傳算法來適應(yīng)異構(gòu)無人機。

蟻群算法是一種模仿螞蟻覓食行為的算法，利用正反饋尋求最優(yōu)解。蟻群算法收斂慢、易陷入局部最優(yōu)解，針對這些缺陷，研究者對蟻群算法進行改進，如保留每次迭代中的最優(yōu)值，動態(tài)調(diào)整節(jié)點的選擇概率，兼顧全局搜索和局部搜索等[8]。蘇梅梅等[9]利用啟發(fā)式蟻群算法求解多任務(wù)分配問題，充分考慮了任務(wù)分配與路徑規(guī)劃的耦合性，有效地解決了多編隊多任務(wù)分配和路徑規(guī)劃問題中部分無人機編隊“空閑”問題。