基于任務拆分的多無人機任務分配多目標優化*

張 曼，王 楨

（解放軍92728 部隊，上海 200436）

0 引言

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

現有對于多無人機任務分配的研究主要集中在多無人機任務分配問題建模和求解方法兩方面。大多數學者［4-9］考慮任務成本最小或效用最大，研究單目標多無人機任務分配優化問題。也有學者兼顧無人機任務成本和收益，研究多無人機分配雙目標優化問題，綜合考慮無人機任務航程和任務完成時間，見文獻［10-13］。

上述研究均假定一項任務可以被單架無人機執行，未考慮多架無人機共同執行某項任務的情形，實際作戰環境下，一個目標被摧毀經常需要多個無人機的資源，需要多架無人機對目標進行攻擊。文獻［14-16］考慮了目標資源需求和無人機資源約束，使多無人機聯盟同時攻擊目標，但只考慮無人機任務時間最短，未考慮無人機任務成本，造成無人機數量較多，我方無人機群代價增加。

本文針對同一構型攻擊無人機群對戰區任務目標攻擊任務分配問題進行研究，考慮無人機資源約束和任務目標點資源需求，在有效任務時間窗的前提下，考慮目標點任務需求可拆分，放寬無人機群同時攻擊約束，以無人機群執行任務成本最小和攻擊目標收益最大為目標，建立基于任務拆分的多無人機任務分配多目標優化模型，并設計多目標禁忌搜索算法獲得Pareto 最優解集，為多無人機協同作戰任務分配網絡優化理論提供參考。

1 模型構建

1.1 問題描述與假設

某個發射/回收站有多架攻擊型無人機，要出發執行戰區的目標攻擊任務，戰區內存在多個任務目標，任務目標的初始位置已知，根據攻擊任務目標的資源需求以及無人機群攜帶的資源量，指派合適的無人機對任務目標進行攻擊。

針對多無人機任務分配問題具體情境，作出如下假設：

1）發射/回收站和可用無人機數量以及具體位置已知；

2）攻擊目標所需資源數量已知；

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

1.2 符號定義與說明

V：V＝｛i|i=0，1，…，n｝，所有節點的集合，0 代表發射/回收站，｛1，2，…，n｝代表n 個任務目標點；

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

Q：無人機攜帶的最大資源數量，同一類型無人機攜帶的資源數量相同；

qi：攻擊任務目標點i 的需要的資源數量，其中i=1，2，…，n；

dij：任意兩個任務目標點i 和j 之間的距離，其中i，j=0，1，…，n；

D：從發射/回收站出發的無人機在每一次執行任務中的最大航程；

d0n：從發射/回收站到任務目標點n 的距離，可通過任務目標點距離數據累加得到；

tki：無人機k 到達任務目標點i 的時間；

tij：無人機從目標點i 飛到目標點j 所用的時間；

yki：無人機k 攻擊目標點i 的資源數量；

uki：無人機k 執行攻擊目標點i 所耗費的時間；

wki：無人機k 在目標點i 的盤旋等待時間，wki；

［ETi，LTi］：攻擊目標點i 的有效時間窗，在此時間窗內，攻擊目標點所得收益不為0；

c0：單架無人機執行任務時航程單位距離成本；

c1：無人機早于目標時間窗到達，盤旋等待的單位時間成本；

vi：任務目標價值；

xijk=1 第k 架無人機攻擊目標i 后攻擊目標j

0 否則 ；

yki：無人機攻擊任務目標點i 消耗的資源數量。

1.3 無人機執行任務收益水平測度

多無人機協同任務分配網絡中，無人機任務收益與目標價值以及無人機開始攻擊目標的時間有關。當無人機k 到達目標點i 的時間ti≤ETi，無人機執行任務收益水平最大，等于任務目標價值；當無人機攻擊目標點的時間ETi＜ti＜LTi，收益隨時間遞增衰減；當無人機攻擊目標點的時間ti≥LTi，此時任務收益水平為0。

式（1）為無人機執行任務收益水平函數。

1.4 基于任務拆分的多無人機任務分配多目標優化模型

引入攻擊目標收益水平函數，建立基于任務拆分的無人機任務分配多目標優化模型。

1.4.1 目標函數

1.4.2 約束條件

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

2 求解算法

研究表明［17-19］，禁忌搜索算法可有效求解多無人機任務分配問題。禁忌搜索算法［20］是GLOVER于1977 年提出，通過引入的存儲結構和相應的禁忌準則以避免迂回搜索，由藐視準則赦免一些被禁忌的優良狀態，以達到全局優化?；诖?，本文結合多無人機任務分配模型特性，設計三階段禁忌搜索算法，采用新的任務目標分配策略，針對本文提出的問題進行求解。算法操作規則如下。

2.1 初始解生成

采用新的任務分配策略，設計三階段法構造初始解。具體步驟如下：

Step 1 采用最近距離插入法，從離發射/回收站最近的任務目標點i 開始，搜索距i 最近的目標點j 作為下一個目標點，如此根據輸入目標點數量生成一組任務目標序列Ii：

Step 2 根據無人機最大資源約束將Step 1 所得Ii轉換成多無人機任務分配序列Kk；

Step 2.1 根據Ii，設無人機已經消耗的資源量expend-Q=0，已攻擊的目標數indextas=0，令i=1，j=i+1 從任務目標序列中第一個任務目標點開始判斷；

Step 2.2 依次讀取所得任務目標序列中攻擊第i 個至第j 個點的資源需求量，更新無人機已消耗的任務資源expend-Q，已攻擊的任務目標數indextas；

Step 2.3 判斷任務目標序列中第i 個目標點至第j 個目標點所需的資源量，即無人機已經消耗的資源量expend-Q 是否超出最大資源約束Q，若否，進入Step 2.4，若是，則進入Step 3；

Step 2.4 令j=j+1，繼續任務目標序列選擇下一個目標點，判斷j 是否超過i 的總個數，若是進入步驟Step 4；若否，返回Step 2.2；

Step 3 將目標點j 的資源需求量進行拆分，更新expend-Q=k，輸出任務目標序列第i 個對應目標點的序號到第j 個對應目標點的序號，更新expend-Q（j+1）=expend-Q（i）+ expend-Q（j）-k，賦值i=j+1，j=j+2，返回Step 2.2；

Step 4 判斷輸出序列個數是否大于可用無人機總數，若是，返回Step 1 重新生成任務目標初始序列，若否，根據路徑優化各無人機攻擊任務序列，最后輸出多無人機任務分配初始解。

2.2 初始解評價

計算初始解的任務總成本f1及總收益f2，G 為一個較大的數，若不滿足無人機資源約束或航程約束，f1=f1+G；若不滿足目標有效時間窗約束，f2=f2-G。

2.3 生成候選集

候選集生成取決于鄰域操作方法，常通過reverse、insert、swap 變換產生。對目標序列Ii 隨機采用上述操作方法生成鄰域結構，再將其轉化成無人機任務分配序列，生成候選集。

2.4 候選解評價

計算候選解的各目標函數值，并對不滿足約束的解進行相應的懲罰。

2.5 禁忌規則

選擇固定值15 作為禁忌長度，構造n×3 的矩陣作為禁忌表，將鄰域操作的禁忌對象存放在禁忌表中，其中，n 表示禁忌長度，第1 列代表對應的變異類型，第2、3 列表示相應鄰域操作變化的任務目標點。

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

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

2.7 終止準則

達到事先指定最大循環迭代次數或者在事先給定的某一步數之內當前最好解未改進，則停止搜索，輸出全局非劣解集，結束算法。

多目標無人機任務分配禁忌搜索算法具體流程如圖2 所示。

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

3 仿真驗證

3.1 任務場景

設計采用攻擊無人機執行任務，已知任務區域內有25 個任務目標，每個任務目標點詳細數據如下頁表1 所示，無人機發射/回收站坐標為（35，35），無人機發射/回收中心擁有的無人機總數為10，無人機最大任務能力（即攜帶攻擊資源數量）為8，最大航程約束為100，單位距離能耗成本為10，單位時間等待成本為5，任務目標初始價值均為1。

表1 任務目標點信息Table 1 Task target point information

3.2 結果分析

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

圖3 多無人機任務分配Pareto 解集分布對比圖Fig.3 Distribution comparison diagram of Pareto solution set for multi-UAV task assignment

仿真結果表明，任務不拆分情況下，雙目標Pareto 解集中任務總成本最低為6 294.74，總收益最大為0.860 6；當考慮任務拆分時，雙目標Pareto 解集中任務總成本最低為6 266.68，總收益最大為0.895 4。因此，基于目標任務拆分的分配方案，無人機執行任務成本及效益更優。此外，隨著無人機執行任務的成本增加，任務收益逐漸增加，收益水平的提高往往以增加任務成本為代價。

為分析目標任務拆分時，任務成本和收益間的影響，對總成本最低和收益最大的單目標最優實驗結果進行下一步分析。相應的多無人機任務分配結果如表2 所示。

表2 多無人機任務分配結果Table 2 Task assignment results of multi-UAV

從各指標最優的方案可以看出：

1）成本最低分配方案與任務收益最大分配方案相比，任務需求拆分較少，僅拆分了目標點14、15、2，收益最大方案任務需求拆分較多，拆分了目標點16、1、15、9、2。

2）相比總成本最優分配方案，收益最優分配方案無人機航程成本有所增加，說明多個目標點任務拆分導致航程增加；時間窗等待成本增加則是為了滿足目標任務時間窗約束，以提高無人機任務收益。

4 結論

在多無人機任務分配優化過程中，基于任務拆分，采用多無人機對同一目標進行攻擊，有效提高任務收益。本文考慮任務目標資源需求及任務有效時間窗，以無人機執行任務總成本最小、攻擊目標收益最大為優化目標，建立多目標優化模型；針對模型特點，采用三階段禁忌搜索算法進行求解，尋求最優任務分配方案。得出以下結論：

1）在多無人機任務分配優化網絡中，目標任務需求拆分可有效提高無人機執行任務效率，無人機任務成本及任務收益均可得到優化。

2）作戰過程中，決策者往往需要同時考慮多個作戰目標，但這些目標往往具有沖突性，無法同時達到最優。因此，需要決策者依據自身戰略以及戰場環境變化，合理分配無人機作戰資源。

3）決策者在制定決策時應考慮實際情況，對于難度大、攻擊資源需求量高的目標點可優先考慮目標任務拆分；對于任務資源需求小的任務目標，則僅考慮單無人機攻擊，避免過度拆分，增加無人機航程成本。

在作戰過程中，無人機任務分配網絡規劃更為復雜，未來將研究無人機動態任務分配優化問題；在實際應用時，戰場信息數據更加龐大，算法性能有待進一步優化。