約束條件下的多無人機協同任務分配方法

盛景泰，杜亞男

1. 中國電子科技集團公司第五十一研究所，上海 201800

2. 中國電子科技集團公司第三十八研究所，安徽 合肥 230088

3. 哈爾濱工程大學 信息與通信工程學院，黑龍江 哈爾濱 150001

無人機是一種有動力、可控制、能夠執行多種類型任務的無人駕駛飛行器。現代局部戰爭中，隨著戰場環境和作戰任務的日趨復雜，無人機的協同作戰將是未來空中作戰的一種重要形式[1]。美國軍方最早開始無人機集群相關研究的布局。在2005 年，美國國防部發布文件對無人機群系統提出了更高的要求，期望無人機在自主控制方面可以實現“全自主集群”。自2014 年起，美國國防部戰略能力辦公室、美國海軍、國防高級研究計劃局( Defense Advanced Research Projects Agency, DARPA)先后啟動“無人機蜂群”項目、“低成本無人機技術蜂群”和“小精靈”項目。2016 年，英國、俄羅斯先后開啟了無人機研究項目。隨后，中國軍方也開始密切關注并大力推動無人機集群相關技術的進展[2]。

無人機技術已經在多個行業上得到廣泛應用。在軍事應用上，在偵察監測、火力打擊、電子對抗、聯合打擊等方面發揮了重要的作用。在民事應用上，在搶災救援、拍照取景、城市航跡規劃也扮演著重要的角色。

在現有的多無人機任務分配研究中有多種任務分配方式[3]。根據多無人機作戰任務的關聯性，可以分為協同任務分配[4]和獨立任務分配；根據無人機作戰所處的環境，又分為靜態任務分配[5-6]和動態任務分配[7]；根據無人機執行任務分配的控制方式，又可以分為集中式控制、分布式控制和分層分布式控制。

集中式控制任務分配方法就是無人機之間的通信、信號傳輸統一由一個控制中心進行[8]。以集中式控制任務分配方法為基礎的常用模型有車輛路徑問題模型[9]、混合整數線性規劃模型[10]等。梁國偉等[11]通過混合整數線性規劃模型的分析，提出了一種基于相似度的遺傳退火算法解決無人機集群的任務分配優化問題。趙民全[12]采用多旅行商問題建立無人機群協同任務規劃模型，并采用改進的遺傳算法進行修正求解。楊毅[13]針對無人機進行偵察的任務，設計了一種多旅行商問題和每個旅行商任務均衡的集中控制偵察策略，為了簡化問題，使用K-means 算法對偵察區域進行劃分。

分布式控制[14]是指無人機集群不只由一個控制中心來控制無人機，還可以通過無人機之間進行通信、信號傳輸，這樣靈活性會更強，但是對無人機的要求會更高，需要無人機具有自主控制能力。分布式控制方法主要有合同網方法[15]、拍賣方法[16-17]等。王然然等[18]針對無人機集群的任務分配和路徑規劃問題，以合同網拍賣算法為基礎，構架無人機群拍賣架構和拍賣收益函數，并結合退火算法調整任務順序。

上述文獻均在多無人機任務分配問題上作出了一定的貢獻，然而很少在多約束條件下解決多個目標聯合優化多無人機協同任務分配問題。為了解決上述問題，本文建立了多目標聯合優化的多無人機協同作戰任務分配模型，綜合考慮了幾個復雜的約束條件，擴展已有方法的應用局限；并設計了量子食肉植物算法來優化目標函數，以克服食肉植物算法算法易陷入局部收斂以及收斂性能較差的弊端，突破了現有多無人機任務分配方法的性能局限。

1 多無人機任務分配模型

為了滿足復雜戰場環境的作戰需求，本文建立了攻擊效益、損耗代價和時間代價聯合為目標函數的多無人機協同作戰任務分配模型，綜合考慮了任務約束、航程約束和攻擊約束條件。

多無人機任務分配模型中，將需要執行的任務定義為多架無人機協同攻擊地面目標。設有N架無人機需要執行T個敵方目標任務，則無人機與敵方目標任務之間的任務分配矩陣為

式中：n=1,2,···,N；t=1,2,···,T；xn,t=1表示第n架無人機對第t個敵方地面目標執行攻擊任務；xn,t=0表示第n架無人機不執行第t個敵方地面目標的攻擊任務。

以攻擊效益、損耗代價、時間代價聯合為目標函數的多無人機協同作戰任務分配模型中，采用慣性權重方法將多個目標聯合為單個目標，多無人機協同任務分配模型為

式中：F(X)為多無人機任務分配模型中需要優化的最大值聯合目標函數；F1(X)為攻擊效益，該函數值用于獲取多無人機協同任務分配方案中無人機攻擊敵方目標取得的總效益，任務分配方案的好壞關系著總效益的高低；F2(X)為損耗代價，該函數值用于獲取多無人機協同任務分配方案中無人機攻擊敵方目標時付出的傷亡代價；F3(X)為時間代價，該函數值用于多無人機協同任務分配方案中無人機攻擊敵方目標所付出的最大時間代價； α1、 α2和 α3分別為攻擊效益目標函數、損耗代價目標函數和時間代價目標函數的權值因子。

式中Un,t為第n架無人機攻擊第t個敵方目標獲得的攻擊效益。

式中：Dn為第n架無人機在執行完畢自身的所有任務后的總飛行距離；vn為第n架無人機的飛行速度，這里假設無人機執行任務的時間忽略不計。

式中：d0,j1為無人機基地位置與第j1個敵方目標位置之間的距離；為第j1個敵方目標位置與第j2個敵方目標位置之間的距離；為第jm-1個敵方目標位置與第jm個敵方目標位置之間的距離。j1滿足xn,j1=1，且與無人機基地位置距離最近，j2滿足xn,j2=1，且與第j1個敵方目標位置距離最近，以此類推，jm滿足xn,jm=1，且與第jm-1個敵方目標位置距離最近。

在多無人機任務分配模型中，還需要滿足約束條件，分別為任務約束、攻擊約束、航程約束和目標價值毀傷約束。其中，任務約束為

式中：t=1,2,···,T，任務約束表示每個敵方目標不能被2 架以上無人機攻擊。航程約束為

式中：n=1,2,···,N，為第n架 無人機的航程。攻擊約束為

式中An為第n架無人機的最大執行任務數。則目標價值毀傷約束為

多無人機任務分配模型需要在滿足上述4 個約束條件的情況下獲取1 個最優的任務分配方案，而解決有約束優化問題相對于無約束優化問題要更復雜，為了簡化問題求解的難度，本文使用懲罰項方法，將上述4 個約束條件轉化成懲罰項分別代入到目標函數中，任務分配方案不滿足任一約束條件時都會受到“懲罰”，即目標函數值變劣。使用懲罰項方法后，可以將本文的有約束優化問題轉化為無約束優化問題，成功降低了問題求解難度。則有約束優化問題轉化為無約束優化問題后的多無人機任務分配模型為

式中：max(·)為最大值函數， |·|為絕對值函數， β1、β2和 β3分別為攻擊效益目標函數、損耗代價目標函數和時間代價目標函數的權值因子， χ1、 χ2、χ3和 χ4分別為任務約束懲罰項、攻擊約束懲罰項、航程約束懲罰項和目標價值毀傷約束懲罰項的權值因子。其中，攻擊約束懲罰項代入到攻擊效益目標函數中得到式(2)，任務約束懲罰項代入到損耗代價目標函數中得到式(3)，航程約束懲罰項和目標價值毀傷約束懲罰項代入到時間代價目標函數中得到式(4)。

由式(1）~（4)可知，多無人機任務分配矩陣不滿足任務約束懲罰項時攻擊效益目標函數值會受到影響，不滿足攻擊約束懲罰項時損耗代價目標函數會受到影響，不滿足航程約束懲罰項或目標價值毀傷約束懲罰項時時間代價目標函數會受到影響。而任一個目標函數受到影響都會使本文所建模型的目標函數值降低，模型目標函數值越低，說明該任務分配方案的性能越差。因此，多無人機任務分配矩陣要盡量滿足上述4 種約束懲罰項。懲罰項方法起到了所建模型即使是無約束優化問題而任務分配矩陣也要滿足了上述4 種約束條件的效果，簡化了問題的求解難度。

2 基于量子食肉植物算法的多無人機任務分配

食肉植物算法(carnivorous plant algorithm,CPA)[19]是Meng 等[20]以食肉植物在惡劣環境中如何適應生存為靈感設計出一種新的元啟發式算法，并通過多組仿真證明該算法的優越性。本文使用量子演進機制對食肉植物算法加以改進，設計出一種帶有量子編碼和量子演化機制的的量子食肉植物算法(quantum carnivorous plant algorithm,QCPA)。

2.1 QCPA 原理

2.1.1 初始化量子種群

QCPA 中初始化種群時，與CPA 不同，初始的是各個個體的量子位置，再對個體量子位置進行測量得到個體位置。QCPA 中種群規模大小為G，其中，食肉植物種群規模為g，獵物種群規模為=G-g，最大迭代次數為K，則QCPA 中第k次迭代第i個生物個體的量子位置為

式中：i=1,2,···,G，0 ≤≤1，l=1,2,···,L，L為待求解變量的最大維數。則QCPA 種群初代第i個生物個體的量子位置為

2.1.2 量子位置的測量規則

種群中每個生物同樣都有對應的適應度值。CPA 中，通過解空間中生物的位置來計算適應度值，而QCPA 中種群初始解空間的是量子位置，因此需要對量子位置進行測量得到生物的位置再計算適應度值。設第k次迭代第i個生物的量子位置為則其第l維量子位置的測量規則為

2.1.3 分類和分組

在每次迭代中計算出所有生物的適應度值后，會通過所有生物的適應度值對種群進行排序，對于最大值優化問題，需要按照適應度值對種群空間進行降序排列。排序后的解空間中，適應度值較優的前g個生物為食肉植物，則其余的生物為獵物。具體來說，對于排序后的：i=1,2,···,g時，用來表示食肉植物；i=g+1,g+2,···,G時，用來表示獵物。

分類后的種群空間被分成食肉植物種群和獵物種群2 部分。這時需要對獵物種群進行分組，在分組過程中，適應度值最優的獵物被分到適應度值最優的食肉植物組，類似地，適應度值第2、第3 的獵物被分到第2、第3 個食肉植物，按照上述方式所有食肉植物都分到一個獵物后，如果還有剩余獵物，將繼續按照上述方式分組，直到不再剩余獵物為止。

2.1.4 生長過程

QCPA 種群的所有生物都會通過生長過程更新自身的量子位置。食肉植物和獵物在生長過程中，量子位置更新公式是不同的，這有助于維護多種群中解空間的多樣性。第i個食肉植物在生長過程中第l維量子旋轉角更新公式為

第i個獵物在生長過程中量子旋轉角更新公式為

食肉植物和獵物通過生長過程得到量子旋轉角后，通過量子旋轉門公式可以計算出食肉植物和獵物的量子位置，具體如下：

式中：i=1,2,···,G；l=1,2,···,L。

2.1.5 繁殖過程

QCPA 中食肉植物從獵物上吸收養分，并利用這些養分進行繁殖。就繁殖而言，只允許最優適應度值的食肉植物進行繁殖，且繁殖g-1次。繁殖過程的量子旋轉角更新公式為

式中：i=2,3,···,g；l=1,2,···,L；為第i個食肉植物通過生長過程更新后的第l維量子旋轉角；為再生系數；為[0,1]之間的隨機數；為繁殖因子，具體為

式中：i=2,3,···,g；l=1,2,···,L；?i為取自集合{2,3,···,g}的隨機數，且滿足?i≠i，第k次迭代第i個生物的位置可以得到該生物的適應度值為。

繁殖過程產生的量子旋轉角后，使用量子旋轉門更新食肉植物的量子位置，具體如下：

式中：i=2,3,···,g；l=1,2,···,L。

2.1.6 重組過程

重組過程將生長過程產生的食肉植物和獵物以及繁殖過程產生的食肉植物的量子位置進行測量得到生物個體的相應位置，計算出其各自的適應度值，并與上一代的種群結合，形成一個新的種群，并按照適應度值對這個新種群進行降序排序，選擇前G個生物繼續進行上述過程，直到最大迭代次數K為止。

2.2 基于QCPA 的多無人機任務分配

使用所設計的QCPA 可有效解決多無人機任務分配時所遇到的一些問題。在求解多無人機任務分配問題時，QCPA 種群中的每個生物位置都對應著一個多無人機任務分配方案。因為分配模型中有N架無人機和T個敵方地面目標，則QCPA 種群中所有生物的位置維度為L=N×T。具體對應方式為：將對應任務分配方案中第1 行的將對應任務分配方案中第2 行的以此類推，將對應任務分配方案中的最后一行其對應的任務分配矩陣為，將其代入到適應度計算公式中會得到多無人機任務分配模型的目標函數值。因此，對于多約束任務分配問題，可以得到第k次迭代第i個生物的適應度函數為

基于QCPA 的多無人機任務分配算法的整體步驟如下：

1）設置種群規模G、最大迭代次數K、食肉植物種群規模g、無人機數量N、敵方地面目標數量T、吸引系數 σ和再生系數 σˉ等。

2）初始化種群空間，獲得種群所有生物的量子位置，對所有生物的量子位置進行測量得到位置。

3）將所有生物的位置對應為任務分配方案代入多無人機任務分配模型中，根據適應度函數計算每個生物的適應度值。

4）按照適應度函數值對種群進行降序排列。對種群進行分類和分組，分成食肉植物和獵物共2 類。

5）使用生長過程更新食肉植物和獵物的量子位置，使用繁殖過程更新食肉植物的量子位置。對所有生物的量子位置進行測量得到相應的位置。

6）根據適應度函數計算每個生物的適應度值，使用重組過程獲取新種群，并選擇前G個生物用于下一次迭代更新。

7）判斷是否達到最大迭代次數K，若是則終止迭代，將最優食肉植物的位置qˉK1對應為多無人機最優任務分配方案輸出；否則繼續執行步驟4）。

3 實驗結果與分析

為了證明本文設計的量子食肉植物算法（quantum carnivorous plant algorithm, QCPA）優越性，選擇了離散粒子群算法(discrete particle swarm optimization, DPSO)[21]、北方蒼鷹算法(northern goshawk optimization, NGO)[22]、 離散鴿群算法(discrete pigeon-inspired optimization, DPIO)[23]和量子磷蝦算法(quantum krill herd algorithm, QKHA)[24]作為對比算法。算法的參數設置如表1 所示。

表1 QCPA 與對比算法的參數設置

在6 種不同的作戰規模中進行仿真分析，規模越大，需要處理的數據量就越大，仿真難度也會增加，這時就會考驗算法的尋優能力。6 種作戰規模如表2 所示，無人機的信息如表3 所示，敵方目標信息如表4 所示。

表2 多無人機作戰規模設置

表3 無人機信息

表4 敵方目標位置信息

在多無人機作戰任務分配模型中，設攻擊效益的權值因子 β1=1、損耗代價的權值因子β2=-1、時間代價的權值因子β3=-0.008、任務約束懲罰項的權值因子 χ1=1.12、 χ2=1.04、 χ3=0.95、 χ4=1.38，無人機基地位置為(2 500,0)。無人機的殺傷概率如表5 所示，與無人機有關，無人機性能越好，殺傷概率越大。生存概率如表6 所示，與敵方地面目標有關，地面目標防御能力越強，無人機執行相應任務時的生存概率就越小。敵方地面目標的價值如表7 所示。

表5 無人機的殺傷概率

表6 生存概率

表7 敵方目標價值

在6 種作戰規模中，終止迭代次數為200 次，種群規模為400，進行20 次獨立重復實驗，仿真結果為20 次實驗的平均值。QCPA 與4 個對比算法的目標函數值仿真如圖1 所示，目標函數值的計算公式如多無人機任務分配模型式(5)所示。由圖1 可知，隨著作戰規模的增大，QCPA 的目標函數值逐漸增加，原因是任務數量的增多，獲取的任務總價值也會相應地增多。而其他對比算法，尤其是DPIO，在作戰規模增大時，目標函數值前3 個作戰規模在緩慢增加，到第4 個作戰規模開始大幅度減少，這是因為隨著作戰規模的增大，優化任務分配方案的難度也會增加，而且受到多個約束懲罰項的影響，目標函數值也會降低，造成了其他對比算法在作戰規模增大時，目標函數反而降低的現象。總體來說，QCPA 的目標函數值最優，DPSO 其次，QKHA、NGO、DPIO的目標函數值較劣。

圖1 QCPA 與對比算法的目標函數值

QCPA 與4 個對比算法的攻擊效益如圖2，攻擊效益的計算公式如式(2)。由圖2 可知，在6 種作戰規模中，QCPA 的攻擊效益都明顯優于其他對比算法。QCPA 與4 個對比算法的損耗代價如圖3 所示，損耗代價的計算公式如式(3)。由圖3可知，在6 種作戰規模中，QCPA 的損耗代價都優于其他對比算法，而且隨著作戰規模的增大，QCPA 的損耗代價增長率明顯小于其他算法，這說明，QCPA 在作戰規模增大時，損耗代價對QCPA 輸出最優任務分配方案的目標函數值影響最小。QCPA 與4 個對比算法的時間代價如圖4所示，時間代價的計算公式如式(4)。由圖4 可知，QCPA 的時間代價同樣優于其他4 種算法。

圖2 QCPA 與對比算法的攻擊效益

圖3 QCPA 與對比算法的損耗代價

圖4 QCPA 與對比算法的時間代價

為了進一步證明QCPA 在解決多無人機任務分配問題的優越性，設無人機數量為N=8，敵方目標數量為T=20，進行20 次獨立重復實驗，QCPA 與4 個對比算法的目標函數值對比如表8所示。其中，目標函數值是各個算法到達最大迭代次數時輸出的最優任務分配方案的目標函數值，任務分配方案越好，目標函數值越大；平均值是進行20 次獨立重復實驗的目標函數值取平均數得到的；最大值是20 次獨立重復實驗中算法最好的結果；標準差越小表明算法輸出任務分配方案的目標函數值越穩定。由表8 可以看出，QCPA 在平均值、最大值、標準差上都要優于其他算法。

表8 目標函數值對比

通過上述實驗的仿真結果可知，在解決多無人機作戰任務分配問題上，QCPA 和DPSO 相比于其他算法的收斂性能更加優越，因此選擇QCPA 與DPSO 進一步對比任務分配方案的性能，設無人機數量為N=8，敵方目標數量為T=20，迭代次數為200，種群規模為400，QCPA與DPSO 的最優任務分配方案如表9 所示。由表9可知，QCPA 的最優任務分配方案基本滿足了任務約束、攻擊約束、航程約束以及目標價值毀傷約束，且最優目標函數值明顯優于DPSO 的最優目標函數值。而DPSO 沒有滿足任務約束等約束，因為有多架無人機重復執行的任務，并且敵方目標編號為8、14、18 和19 時沒有無人機執行。

表9 QCPA 與DPSO 的最優任務分配方案

再次增大作戰規模，若無人機數量為N=12，敵方目標數量為T=30，終止迭代次數為200，種群規模為400，QCPA 與DPSO 的最優任務分配方案如表10。由表10 可知，QCPA 同樣滿足了任務約束、攻擊約束、航程約束以及目標價值毀傷約束，且最優目標函數值明顯優于DPSO 的最優目標函數值。而DPSO 仍然沒有滿足任務約束等約束，并且敵方目標編號為6、8、10、12、17、25 和27 時沒有無人機執行。

表10 QCPA 與DPSO 的最優任務分配方案

4 結論

1）本文研究了一種考慮多約束條件下的多無人機作戰任務分配問題，針對該問題建立了多無人機任務分配模型，將有約束的多無人機任務分配優化問題轉化為無約束的多無人機任務分配問題，降低了運算量和問題求解的難度，提高了性能和擴展了應用范圍。2）在計算最優任務分配方案上，設計了QCPA，克服了現有算法易陷入局部收斂以及受到約束懲罰項的影響導致目標函數值過劣的弊端。在6 種作戰規模中，QCPA 與對比算法在目標函數值、攻擊效益、損耗代價、時間代價和任務分配方案性能上均展現出了優越性。

本文在多約束條件下的多無人機作戰任務分配問題的下一步研究將從2 方面開展：一是解決多無人機動態任務分配問題，實際的戰場環境瞬息萬變，動態任務分配可以滿足在動態變化的環境中得到有效的任務分配方案，使任務分配問題更加貼切真實戰場環境；二是設計更復雜的多目標優化問題，實際戰場環境錯綜復雜，會受到更多因素影響，設計更多合適的目標函數，并采用多目標優化算法求出Pareto 前端解。