多無(wú)人機(jī)任務(wù)與航跡規(guī)劃方法綜述

張文博 劉君蘭 李瑜 王海林

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

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

中圖分類號(hào)：TP18文獻(xiàn)標(biāo)志碼：A文章編號(hào)：1008-1739（2022）20-52-5

0引言

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

1任務(wù)分配模型

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

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

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

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

2任務(wù)分配方法

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

2.1集中式方法

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

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

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

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

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

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

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