基于任務(wù)拆分的多無人機(jī)任務(wù)分配多目標(biāo)優(yōu)化*

張 曼，王 楨

（解放軍92728 部隊(duì)，上海 200436）

0 引言

在現(xiàn)代戰(zhàn)場(chǎng)上，無人機(jī)因其靈活機(jī)動(dòng)、隱蔽性佳等特點(diǎn)而被廣泛用于偵察、攻擊等作戰(zhàn)任務(wù)。隨著現(xiàn)代戰(zhàn)爭(zhēng)模式的發(fā)展，無人機(jī)單機(jī)的機(jī)動(dòng)性、敏捷性已不能滿足復(fù)雜的任務(wù)需求，要求無人機(jī)具備多機(jī)協(xié)同作戰(zhàn)的能力［1］。美國(guó)多所軍事院校、科研單位、軍火公司都曾以全球鷹、捕食者、X-45、X-47為對(duì)象，研究多無人機(jī)協(xié)同任務(wù)分配及協(xié)同控制問題［2］。多無人機(jī)系統(tǒng)是由多架同構(gòu)或異構(gòu)無人機(jī)組成，相比于單架無人機(jī)具有明顯的優(yōu)勢(shì)，多無人機(jī)的任務(wù)規(guī)劃問題是其進(jìn)行高效協(xié)同作戰(zhàn)的關(guān)鍵［3］。如何實(shí)現(xiàn)多個(gè)任務(wù)目標(biāo)的最優(yōu)分配一直是當(dāng)前研究的重點(diǎn)。

現(xiàn)有對(duì)于多無人機(jī)任務(wù)分配的研究主要集中在多無人機(jī)任務(wù)分配問題建模和求解方法兩方面。大多數(shù)學(xué)者［4-9］考慮任務(wù)成本最小或效用最大，研究單目標(biāo)多無人機(jī)任務(wù)分配優(yōu)化問題。也有學(xué)者兼顧無人機(jī)任務(wù)成本和收益，研究多無人機(jī)分配雙目標(biāo)優(yōu)化問題，綜合考慮無人機(jī)任務(wù)航程和任務(wù)完成時(shí)間，見文獻(xiàn)［10-13］。

上述研究均假定一項(xiàng)任務(wù)可以被單架無人機(jī)執(zhí)行，未考慮多架無人機(jī)共同執(zhí)行某項(xiàng)任務(wù)的情形，實(shí)際作戰(zhàn)環(huán)境下，一個(gè)目標(biāo)被摧毀經(jīng)常需要多個(gè)無人機(jī)的資源，需要多架無人機(jī)對(duì)目標(biāo)進(jìn)行攻擊。文獻(xiàn)［14-16］考慮了目標(biāo)資源需求和無人機(jī)資源約束，使多無人機(jī)聯(lián)盟同時(shí)攻擊目標(biāo)，但只考慮無人機(jī)任務(wù)時(shí)間最短，未考慮無人機(jī)任務(wù)成本，造成無人機(jī)數(shù)量較多，我方無人機(jī)群代價(jià)增加。

本文針對(duì)同一構(gòu)型攻擊無人機(jī)群對(duì)戰(zhàn)區(qū)任務(wù)目標(biāo)攻擊任務(wù)分配問題進(jìn)行研究，考慮無人機(jī)資源約束和任務(wù)目標(biāo)點(diǎn)資源需求，在有效任務(wù)時(shí)間窗的前提下，考慮目標(biāo)點(diǎn)任務(wù)需求可拆分，放寬無人機(jī)群同時(shí)攻擊約束，以無人機(jī)群執(zhí)行任務(wù)成本最小和攻擊目標(biāo)收益最大為目標(biāo)，建立基于任務(wù)拆分的多無人機(jī)任務(wù)分配多目標(biāo)優(yōu)化模型，并設(shè)計(jì)多目標(biāo)禁忌搜索算法獲得Pareto 最優(yōu)解集，為多無人機(jī)協(xié)同作戰(zhàn)任務(wù)分配網(wǎng)絡(luò)優(yōu)化理論提供參考。

1 模型構(gòu)建

1.1 問題描述與假設(shè)

某個(gè)發(fā)射/回收站有多架攻擊型無人機(jī)，要出發(fā)執(zhí)行戰(zhàn)區(qū)的目標(biāo)攻擊任務(wù)，戰(zhàn)區(qū)內(nèi)存在多個(gè)任務(wù)目標(biāo)，任務(wù)目標(biāo)的初始位置已知，根據(jù)攻擊任務(wù)目標(biāo)的資源需求以及無人機(jī)群攜帶的資源量，指派合適的無人機(jī)對(duì)任務(wù)目標(biāo)進(jìn)行攻擊。

針對(duì)多無人機(jī)任務(wù)分配問題具體情境，作出如下假設(shè)：

1）發(fā)射/回收站和可用無人機(jī)數(shù)量以及具體位置已知；

2）攻擊目標(biāo)所需資源數(shù)量已知；

3）假定無人機(jī)以固定的高度和速度巡航，不考慮無人機(jī)的飛行高度和俯仰角等限制，模型簡(jiǎn)化在二維平面。

1.2 符號(hào)定義與說明

V：V＝｛i|i=0，1，…，n｝，所有節(jié)點(diǎn)的集合，0 代表發(fā)射/回收站，｛1，2，…，n｝代表n 個(gè)任務(wù)目標(biāo)點(diǎn)；

K：表示可用無人機(jī)數(shù)目的集合，K＝｛k|k=1，2，…，m｝；

Q：無人機(jī)攜帶的最大資源數(shù)量，同一類型無人機(jī)攜帶的資源數(shù)量相同；

qi：攻擊任務(wù)目標(biāo)點(diǎn)i 的需要的資源數(shù)量，其中i=1，2，…，n；

dij：任意兩個(gè)任務(wù)目標(biāo)點(diǎn)i 和j 之間的距離，其中i，j=0，1，…，n；

D：從發(fā)射/回收站出發(fā)的無人機(jī)在每一次執(zhí)行任務(wù)中的最大航程；

d0n：從發(fā)射/回收站到任務(wù)目標(biāo)點(diǎn)n 的距離，可通過任務(wù)目標(biāo)點(diǎn)距離數(shù)據(jù)累加得到；

tki：無人機(jī)k 到達(dá)任務(wù)目標(biāo)點(diǎn)i 的時(shí)間；

tij：無人機(jī)從目標(biāo)點(diǎn)i 飛到目標(biāo)點(diǎn)j 所用的時(shí)間；

yki：無人機(jī)k 攻擊目標(biāo)點(diǎn)i 的資源數(shù)量；

uki：無人機(jī)k 執(zhí)行攻擊目標(biāo)點(diǎn)i 所耗費(fèi)的時(shí)間；

wki：無人機(jī)k 在目標(biāo)點(diǎn)i 的盤旋等待時(shí)間，wki；

［ETi，LTi］：攻擊目標(biāo)點(diǎn)i 的有效時(shí)間窗，在此時(shí)間窗內(nèi)，攻擊目標(biāo)點(diǎn)所得收益不為0；

c0：?jiǎn)渭軣o人機(jī)執(zhí)行任務(wù)時(shí)航程單位距離成本；

c1：無人機(jī)早于目標(biāo)時(shí)間窗到達(dá)，盤旋等待的單位時(shí)間成本；

vi：任務(wù)目標(biāo)價(jià)值；

xijk=1 第k 架無人機(jī)攻擊目標(biāo)i 后攻擊目標(biāo)j

0 否則 ；

yki：無人機(jī)攻擊任務(wù)目標(biāo)點(diǎn)i 消耗的資源數(shù)量。

1.3 無人機(jī)執(zhí)行任務(wù)收益水平測(cè)度

多無人機(jī)協(xié)同任務(wù)分配網(wǎng)絡(luò)中，無人機(jī)任務(wù)收益與目標(biāo)價(jià)值以及無人機(jī)開始攻擊目標(biāo)的時(shí)間有關(guān)。當(dāng)無人機(jī)k 到達(dá)目標(biāo)點(diǎn)i 的時(shí)間ti≤ETi，無人機(jī)執(zhí)行任務(wù)收益水平最大，等于任務(wù)目標(biāo)價(jià)值；當(dāng)無人機(jī)攻擊目標(biāo)點(diǎn)的時(shí)間ETi＜ti＜LTi，收益隨時(shí)間遞增衰減；當(dāng)無人機(jī)攻擊目標(biāo)點(diǎn)的時(shí)間ti≥LTi，此時(shí)任務(wù)收益水平為0。

式（1）為無人機(jī)執(zhí)行任務(wù)收益水平函數(shù)。

1.4 基于任務(wù)拆分的多無人機(jī)任務(wù)分配多目標(biāo)優(yōu)化模型

引入攻擊目標(biāo)收益水平函數(shù)，建立基于任務(wù)拆分的無人機(jī)任務(wù)分配多目標(biāo)優(yōu)化模型。

1.4.1 目標(biāo)函數(shù)

1.4.2 約束條件

式（2）和式（3）為目標(biāo)函數(shù)，表示最小化任務(wù)總成本和最大化攻擊任務(wù)目標(biāo)總收益；式（4）和式（5）表示每個(gè)任務(wù)目標(biāo)點(diǎn)至少被分配給1 架無人機(jī)；式（6）和式（7）表示攻擊任務(wù)目標(biāo)點(diǎn)的資源需求約束；式（8）和式（9）表示無人機(jī)攜帶任務(wù)資源能力約束和最大航程約束；式（10）表示無人機(jī)到達(dá)下一個(gè)任務(wù)目標(biāo)點(diǎn)的時(shí)間；式（11）和式（12）表示無人機(jī)從發(fā)送/回收站出發(fā)，最終回到發(fā)射/回收站。

2 求解算法

研究表明［17-19］，禁忌搜索算法可有效求解多無人機(jī)任務(wù)分配問題。禁忌搜索算法［20］是GLOVER于1977 年提出，通過引入的存儲(chǔ)結(jié)構(gòu)和相應(yīng)的禁忌準(zhǔn)則以避免迂回搜索，由藐視準(zhǔn)則赦免一些被禁忌的優(yōu)良狀態(tài)，以達(dá)到全局優(yōu)化。基于此，本文結(jié)合多無人機(jī)任務(wù)分配模型特性，設(shè)計(jì)三階段禁忌搜索算法，采用新的任務(wù)目標(biāo)分配策略，針對(duì)本文提出的問題進(jìn)行求解。算法操作規(guī)則如下。

2.1 初始解生成

采用新的任務(wù)分配策略，設(shè)計(jì)三階段法構(gòu)造初始解。具體步驟如下：

Step 1 采用最近距離插入法，從離發(fā)射/回收站最近的任務(wù)目標(biāo)點(diǎn)i 開始，搜索距i 最近的目標(biāo)點(diǎn)j 作為下一個(gè)目標(biāo)點(diǎn)，如此根據(jù)輸入目標(biāo)點(diǎn)數(shù)量生成一組任務(wù)目標(biāo)序列Ii：

Step 2 根據(jù)無人機(jī)最大資源約束將Step 1 所得Ii轉(zhuǎn)換成多無人機(jī)任務(wù)分配序列Kk；

Step 2.1 根據(jù)Ii，設(shè)無人機(jī)已經(jīng)消耗的資源量expend-Q=0，已攻擊的目標(biāo)數(shù)indextas=0，令i=1，j=i+1 從任務(wù)目標(biāo)序列中第一個(gè)任務(wù)目標(biāo)點(diǎn)開始判斷；

Step 2.2 依次讀取所得任務(wù)目標(biāo)序列中攻擊第i 個(gè)至第j 個(gè)點(diǎn)的資源需求量，更新無人機(jī)已消耗的任務(wù)資源expend-Q，已攻擊的任務(wù)目標(biāo)數(shù)indextas；

Step 2.3 判斷任務(wù)目標(biāo)序列中第i 個(gè)目標(biāo)點(diǎn)至第j 個(gè)目標(biāo)點(diǎn)所需的資源量，即無人機(jī)已經(jīng)消耗的資源量expend-Q 是否超出最大資源約束Q，若否，進(jìn)入Step 2.4，若是，則進(jìn)入Step 3；

Step 2.4 令j=j+1，繼續(xù)任務(wù)目標(biāo)序列選擇下一個(gè)目標(biāo)點(diǎn)，判斷j 是否超過i 的總個(gè)數(shù)，若是進(jìn)入步驟Step 4；若否，返回Step 2.2；

Step 3 將目標(biāo)點(diǎn)j 的資源需求量進(jìn)行拆分，更新expend-Q=k，輸出任務(wù)目標(biāo)序列第i 個(gè)對(duì)應(yīng)目標(biāo)點(diǎn)的序號(hào)到第j 個(gè)對(duì)應(yīng)目標(biāo)點(diǎn)的序號(hào)，更新expend-Q（j+1）=expend-Q（i）+ expend-Q（j）-k，賦值i=j+1，j=j+2，返回Step 2.2；

Step 4 判斷輸出序列個(gè)數(shù)是否大于可用無人機(jī)總數(shù)，若是，返回Step 1 重新生成任務(wù)目標(biāo)初始序列，若否，根據(jù)路徑優(yōu)化各無人機(jī)攻擊任務(wù)序列，最后輸出多無人機(jī)任務(wù)分配初始解。

2.2 初始解評(píng)價(jià)

計(jì)算初始解的任務(wù)總成本f1及總收益f2，G 為一個(gè)較大的數(shù)，若不滿足無人機(jī)資源約束或航程約束，f1=f1+G；若不滿足目標(biāo)有效時(shí)間窗約束，f2=f2-G。

2.3 生成候選集

候選集生成取決于鄰域操作方法，常通過reverse、insert、swap 變換產(chǎn)生。對(duì)目標(biāo)序列Ii 隨機(jī)采用上述操作方法生成鄰域結(jié)構(gòu)，再將其轉(zhuǎn)化成無人機(jī)任務(wù)分配序列，生成候選集。

2.4 候選解評(píng)價(jià)

計(jì)算候選解的各目標(biāo)函數(shù)值，并對(duì)不滿足約束的解進(jìn)行相應(yīng)的懲罰。

2.5 禁忌規(guī)則

選擇固定值15 作為禁忌長(zhǎng)度，構(gòu)造n×3 的矩陣作為禁忌表，將鄰域操作的禁忌對(duì)象存放在禁忌表中，其中，n 表示禁忌長(zhǎng)度，第1 列代表對(duì)應(yīng)的變異類型，第2、3 列表示相應(yīng)鄰域操作變化的任務(wù)目標(biāo)點(diǎn)。

2.6 更新局部非劣解、全局非劣解、禁忌表

比較各候選解的f1、f2，篩選候選非劣解集；比較候選非劣解和全局非劣解，得到新的候選非劣解集。判斷候選非劣解是否滿足藐視準(zhǔn)則，更新當(dāng)前解和禁忌表。

2.7 終止準(zhǔn)則

達(dá)到事先指定最大循環(huán)迭代次數(shù)或者在事先給定的某一步數(shù)之內(nèi)當(dāng)前最好解未改進(jìn)，則停止搜索，輸出全局非劣解集，結(jié)束算法。

多目標(biāo)無人機(jī)任務(wù)分配禁忌搜索算法具體流程如圖2 所示。

圖2 禁忌搜索算法流程圖Fig.2 Flowchart of tabu search algorithm

3 仿真驗(yàn)證

3.1 任務(wù)場(chǎng)景

設(shè)計(jì)采用攻擊無人機(jī)執(zhí)行任務(wù)，已知任務(wù)區(qū)域內(nèi)有25 個(gè)任務(wù)目標(biāo)，每個(gè)任務(wù)目標(biāo)點(diǎn)詳細(xì)數(shù)據(jù)如下頁(yè)表1 所示，無人機(jī)發(fā)射/回收站坐標(biāo)為（35，35），無人機(jī)發(fā)射/回收中心擁有的無人機(jī)總數(shù)為10，無人機(jī)最大任務(wù)能力（即攜帶攻擊資源數(shù)量）為8，最大航程約束為100，單位距離能耗成本為10，單位時(shí)間等待成本為5，任務(wù)目標(biāo)初始價(jià)值均為1。

表1 任務(wù)目標(biāo)點(diǎn)信息Table 1 Task target point information

3.2 結(jié)果分析

基于以上任務(wù)場(chǎng)景，利用禁忌搜索算法對(duì)是否考慮任務(wù)拆分的任務(wù)分配方案進(jìn)行求解，算法參數(shù)設(shè)置如下：最大迭代次數(shù)Max_Iter=500，鄰域解數(shù)量為300，禁忌長(zhǎng)度為15。Pareto 解集分布如圖3 所示。

圖3 多無人機(jī)任務(wù)分配Pareto 解集分布對(duì)比圖Fig.3 Distribution comparison diagram of Pareto solution set for multi-UAV task assignment

仿真結(jié)果表明，任務(wù)不拆分情況下，雙目標(biāo)Pareto 解集中任務(wù)總成本最低為6 294.74，總收益最大為0.860 6；當(dāng)考慮任務(wù)拆分時(shí)，雙目標(biāo)Pareto 解集中任務(wù)總成本最低為6 266.68，總收益最大為0.895 4。因此，基于目標(biāo)任務(wù)拆分的分配方案，無人機(jī)執(zhí)行任務(wù)成本及效益更優(yōu)。此外，隨著無人機(jī)執(zhí)行任務(wù)的成本增加，任務(wù)收益逐漸增加，收益水平的提高往往以增加任務(wù)成本為代價(jià)。

為分析目標(biāo)任務(wù)拆分時(shí)，任務(wù)成本和收益間的影響，對(duì)總成本最低和收益最大的單目標(biāo)最優(yōu)實(shí)驗(yàn)結(jié)果進(jìn)行下一步分析。相應(yīng)的多無人機(jī)任務(wù)分配結(jié)果如表2 所示。

表2 多無人機(jī)任務(wù)分配結(jié)果Table 2 Task assignment results of multi-UAV

從各指標(biāo)最優(yōu)的方案可以看出：

1）成本最低分配方案與任務(wù)收益最大分配方案相比，任務(wù)需求拆分較少，僅拆分了目標(biāo)點(diǎn)14、15、2，收益最大方案任務(wù)需求拆分較多，拆分了目標(biāo)點(diǎn)16、1、15、9、2。

2）相比總成本最優(yōu)分配方案，收益最優(yōu)分配方案無人機(jī)航程成本有所增加，說明多個(gè)目標(biāo)點(diǎn)任務(wù)拆分導(dǎo)致航程增加；時(shí)間窗等待成本增加則是為了滿足目標(biāo)任務(wù)時(shí)間窗約束，以提高無人機(jī)任務(wù)收益。

4 結(jié)論

在多無人機(jī)任務(wù)分配優(yōu)化過程中，基于任務(wù)拆分，采用多無人機(jī)對(duì)同一目標(biāo)進(jìn)行攻擊，有效提高任務(wù)收益。本文考慮任務(wù)目標(biāo)資源需求及任務(wù)有效時(shí)間窗，以無人機(jī)執(zhí)行任務(wù)總成本最小、攻擊目標(biāo)收益最大為優(yōu)化目標(biāo)，建立多目標(biāo)優(yōu)化模型；針對(duì)模型特點(diǎn)，采用三階段禁忌搜索算法進(jìn)行求解，尋求最優(yōu)任務(wù)分配方案。得出以下結(jié)論：

1）在多無人機(jī)任務(wù)分配優(yōu)化網(wǎng)絡(luò)中，目標(biāo)任務(wù)需求拆分可有效提高無人機(jī)執(zhí)行任務(wù)效率，無人機(jī)任務(wù)成本及任務(wù)收益均可得到優(yōu)化。

2）作戰(zhàn)過程中，決策者往往需要同時(shí)考慮多個(gè)作戰(zhàn)目標(biāo)，但這些目標(biāo)往往具有沖突性，無法同時(shí)達(dá)到最優(yōu)。因此，需要決策者依據(jù)自身戰(zhàn)略以及戰(zhàn)場(chǎng)環(huán)境變化，合理分配無人機(jī)作戰(zhàn)資源。

3）決策者在制定決策時(shí)應(yīng)考慮實(shí)際情況，對(duì)于難度大、攻擊資源需求量高的目標(biāo)點(diǎn)可優(yōu)先考慮目標(biāo)任務(wù)拆分；對(duì)于任務(wù)資源需求小的任務(wù)目標(biāo)，則僅考慮單無人機(jī)攻擊，避免過度拆分，增加無人機(jī)航程成本。

在作戰(zhàn)過程中，無人機(jī)任務(wù)分配網(wǎng)絡(luò)規(guī)劃更為復(fù)雜，未來將研究無人機(jī)動(dòng)態(tài)任務(wù)分配優(yōu)化問題；在實(shí)際應(yīng)用時(shí)，戰(zhàn)場(chǎng)信息數(shù)據(jù)更加龐大，算法性能有待進(jìn)一步優(yōu)化。