多無人機協同作戰中的任務分配與路徑規劃算法研究

摘要：隨著無人機技術的快速發展，多無人機協同作戰成為無人機系統的重要發展方向。在多無人機協同作戰中，任務分配與路徑規劃是2個關鍵問題，其質量直接影響著整個系統的作戰效能。文章針對多無人機協同作戰中的任務分配與路徑規劃問題展開研究，建立多無人機協同作戰的數學模型，對問題進行形式化描述。文章提出一種基于混合整數規劃的任務分配算法和一種基于改進A*算法的路徑規劃算法。通過仿真實驗對所提出算法的有效性進行了驗證，與其他經典算法進行對比分析。實驗結果表明，文章提出的任務分配與路徑規劃算法能夠有效提高多無人機協同作戰效能。

關鍵詞：多無人機協同作戰；任務分配；路徑規劃；混合整數規劃；改進A*算法

中圖分類號：G305 文獻標志碼：A

0 引言

無人機技術的迅速發展為現代戰爭帶來了革命性變化，多無人機協同作戰更是未來作戰樣式的重要發展方向。在多無人機協同作戰中，任務分配與路徑規劃是2個關鍵問題，其質量直接影響著整個作戰系統的效能。本文針對上述問題，提出了一種基于混合整數規劃與改進A*算法的2個階段求解框架。首先，構建多無人機任務分配的混合整數規劃模型，求解最優的任務分配方案；然后，利用改進的A*算法為每架無人機規劃一條安全、高效的飛行路徑。實驗結果表明，本文所提出的算法在多種場景下都取得了優異的性能，為多無人機協同作戰提供了一種高效可行的解決方案。

1 多無人機協同作戰問題描述

多無人機協同作戰問題研究的是在復雜環境下，如何高效地利用多架無人機完成一系列作戰任務。具體而言，現有一組需要執行的任務和一組可用的無人機，問題就在于滿足諸如無人機性能、任務時間窗口、任務優先級等各種約束條件的前提下，為每個任務合理分配執行無人機，為每架參與作戰的無人機規劃出一條安全高效的飛行路徑，使得整個作戰系統的任務完成效率達到最優。

問題的輸入包括任務集合及其位置、執行時間窗口、優先級等屬性信息，無人機集合及其飛行速度、航程，載荷能力等性能參數，無人機之間的通信拓撲關系以及作戰環境的地圖、氣象、威脅目標分布等信息。輸出則是每個任務的執行無人機分配方案，每架無人機的詳細飛行路線，由一系列航路點構成。

在建模過程中，研究人員建立了多無人機協同作戰問題的混合整數規劃模型。該模型的目標函數是最小化整個任務執行過程中，各架無人機完成所有分配任務的時間最大值，從而使任務執行時間更加均衡［1］。約束條件保證了每個任務只能由一架無人機執行，每架無人機的任務執行時間不超過其可用時間，每個任務必須在規定的時間窗口內完成，無人機的燃料消耗限制以及防止無人機相互碰撞的空間距離約束等。求解這個混合整數規劃模型，就可以得到最優或近似最優的任務分配方案和無人機路徑規劃方案。

2 任務分配算法設計

2.1 基于混合整數規劃的任務分配模型

在上節中，本文建立了多無人機協同作戰問題的混合整數規劃模型。該模型考慮了任務時間窗口、無人機資源約束等因素，是一種典型的任務分配模型。在此基礎上，本文設計了高效的任務分配算法。為進一步提高模型的適用性和求解效率，可以考慮引入以下技巧。

（1）預處理：在求解之前，通過一些預處理技術（如約束傳播、冗余約束刪除等）來簡化模型，縮小變量取值范圍。

（2）線性松弛：將混合整數規劃模型（Mixed Integer Programming，MIP）松弛為線性規劃模型，快速獲得一個下界，用于指導Branch and Bound搜索。

（3）cutting plane：在Branch and Bound搜索過程中，動態生成割平面，減小搜索空間。

（4）啟發式方法：利用問題的特點，設計啟發式算法生成高質量的初始解，加速收斂速度。

（5）分解算法：將大規模問題分解為多個小規模子問題分別求解，再合并結果。

引入這些技巧后，混合整數規劃模型的求解性能可以得到顯著提升。

2.2 任務分配算法流程

基于2.1節的混合整數規劃模型，本文設計了一種兩階段任務分配算法。算法的基本流程如下。

輸入：任務集合T，無人機集合U，無人機性能參數，任務屬性參數。

輸出：任務分配方案X。

第一階段：初始化。

（1）根據無人機性能參數和任務屬性參數，計算無人機執行每個任務所需的代價cij。

（2）根據任務時間窗口和無人機位置，計算最早到達的時間矩陣D。

（3）生成初始任務分配方案X0，可采用最短任務優先、最近無人機優先等簡單規則。

（4）利用啟發式算法（如模擬退火、遺傳算法等）對X0進行改進，得到改進解X1。

第二階段：求解混合整數規劃。

（1）以X1為初始解構建MIP。

（2）設置求解器參數（如時間限制、Gap限制等），調用求解器求解MIP。

（3）若在時間限制內得到最優解X*，則輸出X*；否則輸出當前最優可行解。

后處理：

（1）對任務分配方案X*進行可視化呈現。

（2）統計任務完成率、平均任務延遲等性能指標。

算法的偽代碼如下：

以上算法在初始化階段引入啟發式方法，生成高質量可行解，加快MIP的求解速度；在求解階段，利用MIP求解器得到最優解或近似最優解；后處理階段，對結果進行可視化呈現和性能評估。

3 路徑規劃算法設計

3.1 改進的A*算法

本文在標準A*算法的基礎上，引入自適應啟發函數、多啟發函數融合、搜索空間動態調整、雙向搜索和局部路徑優化等策略，以進一步提高算法在復雜環境下的搜索效率和路徑質量［2］。

3.2 無人機路徑規劃模型

為了使用改進的A*算法進行無人機路徑規劃，需要將問題轉化為圖搜索問題。首先，將無人機的飛行環境離散化為一個三維網格地圖，每個網格代表一個可能的航路點。無人機在相鄰網格之間飛行，構成了一條飛行路徑。現定義以下符號：

（1）s：起點，無人機的初始位置。

（2）g：目標點，無人機的目標位置。

（3）N（n）：節點n的相鄰節點集合。

（4）c（n，n′）：無人機從節點n飛行到節點n′的代價。

（5）h（n）：從節點n到目標點的估計代價，即啟發函數值。

（6）f（n）=g（n）+h（n）：節點n的估價函數值，g（n）為從起點到n的實際代價。

（7）d（n）：節點n的飛行高度。

（8）t（n）：節點n所處的威脅區域等級。

無人機路徑規劃問題可建模為加權有向圖上的最短路徑搜索問題，現做出以下定義：

（1）頂點：每個網格對應一個頂點，起點s和目標點g也是2個特殊頂點。

（2）邊：若2個網格相鄰，則它們對應的頂點之間存在一條有向邊。

（3）邊權：無人機在2個相鄰網格之間飛行的代價，與飛行距離、高度變化量、威脅區域等級等因素有關。

在該模型下，無人機路徑規劃問題轉化為在加權有向圖中，尋找一條從起點s到目標點g的最小代價路徑。

3.3 路徑規劃算法流程

基于3.1節的改進A*算法和3.2節的無人機路徑規劃模型，本文設計了一種無人機路徑規劃算法。算法的基本流程如下。

輸入：三維網格地圖Map，起點s，目標點g，無人機性能參數。

輸出：一條從s到g的飛行路徑Path。

算法流程：

（1）初始化：將起點s加入開放列表OpenList，計算f（s）。

（2）迭代搜索：while OpenList不為空：從OpenList中取出f值最小的節點n。if n是目標點g：返回路徑Path。將n加入閉合列表ClosedList。for each n′∈N（n）：if n′在ClosedList中：continue計算g（n′）、h（n′）、f（n′）。if n′不在OpenList中：將n′加入OpenList，將n記為n′的父節點［3］。else if g（n′）<n′的原g值：更新n′的g值和f值，將n記為n′的父節點。

（3）路徑提取：if找到目標點g：從g開始，沿著父節點指針逆向追蹤，得到一條從s到g的路徑Path。對Path進行局部優化，得到最終路徑。else：報告搜索失敗。

其中，f（n）的計算公式為：

f（n）=g（n）+w1×h1（n）+w2×h2（n）+w3×h3（n）+...

其中，h1（n）、h2（n）、h3（n）...為多個啟發函數，分別估計節點n到目標點的距離、飛行高度差、威脅區域等級等；w1、w2、w3...為對應的權重系數，可根據無人機性能和任務需求動態調整。

算法的偽代碼如下：

4 仿真實驗與結果分析

4.1 實驗環境與參數設置

實驗在一臺配置為Intel Core i7處理器、16 GB內存的計算機上進行。仿真平臺基于C++語言開發，可以靈活配置無人機數量、任務類型、地圖環境等參數。

實驗中，本文考慮了以下幾種場景。

（1）小規模場景：10架無人機，20個任務，100×100的網格地圖。

（2）中規模場景：30架無人機，50個任務，200×200的網格地圖。

（3）大規模場景：50架無人機，100個任務，500×500的網格地圖。

無人機的飛行速度、航程、通信范圍等參數根據實際情況設置。任務的位置、優先級、時間窗口等屬性隨機生成。地圖中包含不同高度的地形和若干威脅區域。

算法參數方面，混合整數規劃模型采用Gurobi求解器，時間限制設為300 s。A*算法的啟發函數權重通過網格搜索調優得到［4］。每個場景下隨機生成30組測試數據，取平均值作為算法的性能指標。

4.2 任務分配算法實驗結果

本文測試了基于混合整數規劃的任務分配算法在不同場景下的求解性能，與基于市場機制的分配算法、基于遺傳算法的分配算法進行了對比。實驗結果表明：

（1）混合整數規劃算法能夠在較短時間內得到全局最優解或近似最優解，優于另外2種算法。求解時間隨著問題規模的增大而增長。

（2）市場機制算法具有分布式特性，計算速度快，但解的質量難以保證。

（3）遺傳算法的解質量較高，但在大規模問題上的收斂速度較慢。

在小規模場景下，3種算法的性能差異不明顯。但在中大規模場景下，混合整數規劃算法的優勢逐漸體現。例如：在50架無人機、100個任務的場景下，混合整數規劃算法的任務完成率比另外2種算法高出10%以上，而平均求解時間僅為180 s左右。

4.3 路徑規劃算法實驗結果

實驗測試了改進A*算法在不同地圖環境下的路徑規劃性能，與標準A*算法、人工勢場法、RRT算法進行了對比。實驗結果表明：

（1）改進A*算法能夠快速規劃出一條無碰撞、低威脅的飛行路徑。在同等條件下，其搜索效率比標準A*算法提高了50%以上。

（2）人工勢場法容易陷入局部最優，無法有效處理復雜地形。

（3）RRT算法能夠找到一條可行路徑，但路徑質量不高且不具備最優性。

對于不同復雜度的地圖，改進A*算法都能在1 s內得到一條高質量飛行路徑。即使在500×500的大規模地圖上，其平均規劃時間也在5 s以內。相比之下，標準A*算法常常需要幾十秒甚至更長時間。

多啟發函數融合策略和動態搜索空間調整策略是提升算法性能的關鍵。前者綜合考慮了無人機的飛行特性和環境信息，后者避免了不必要的搜索擴展。實驗表明，這2個策略使算法的收斂速度提高了1倍以上。此外，本文還測試了改進A*算法應對動態威脅的能力。通過實時更新地圖信息并重新規劃路徑，無人機能夠及時躲避突發威脅，保證飛行安全。

4.4 與其他算法的對比分析

本文提出的任務分配與路徑規劃算法，在多個場景下展現了優異的性能。與基于市場機制和遺傳算法的任務分配方法相比，本文算法在解的質量和求解效率方面都有明顯優勢，尤其在大規模問題上。在路徑規劃方面，改進的A*算法在搜索效率、路徑質量等指標上也優于標準A*算法、人工勢場法和RRT算法［5］。本文算法之所以表現出色，主要在于其充分利用了問題的特點，引入了多種優化策略，如任務分配中的線性松弛和割平面技術，路徑規劃中的多啟發函數融合等。兩階段協同優化框架考慮了任務分配與路徑規劃的耦合關系，進一步提升了算法整體性能。

5 結語

本文針對多無人機協同作戰中的任務分配與路徑規劃問題，提出了一種基于混合整數規劃和改進A*算法的兩階段優化求解方法。通過建立精確的數學模型，引入多種優化策略，考慮任務分配與路徑規劃的耦合關系，本文算法能夠高效地解決多無人機協同作戰問題，為無人機的實際應用提供了新的思路和方法。在未來的工作中，筆者將進一步完善算法，提高其適應復雜動態環境的能力，拓展其應用場景，如考慮無人機的異構性、引入在線學習機制等，以期為無人機技術和軍事應用的發展作出更大貢獻。

參考文獻

［1］楊廣超，周傳睿，邢文革.海戰場無人機集群與反艦導彈協同作戰樣式與反制策略研究［J］.戰術導彈技術，2024（1）：141-149.

［2］劉芳名，王凱.美軍有人戰機與無人機協同作戰研究［J］.艦船電子工程，2023（12）：14-18.

［3］侯典寧，孟凡凱，朱煉.直升機與無人機協同作戰研究［J］.艦船電子工程，2023（10）：6-8.

［4］毛雪玥，彭盛龍.基于協同作戰的無人機航路重規劃算法研究［J］.艦船電子工程，2023（6）：27-31，93.

［5］趙琳，呂科，郭靖，等.基于深度強化學習的無人機集群協同作戰決策方法［J］.計算機應用，2023（11）：3641-3646.

Research on task allocation and path planning algorithms in Multi-UAV cooperative combat

Abstract： With the rapid development of UAV technology， multi-UAV cooperative operation has become an important development direction of UAV system. In multi-UAV cooperative operations， mission assignment and path planning are two key issues， and their quality directly affects the operational effectiveness of the whole system. This paper studies the task allocation and path planning in multi-UAV collaborative operation. The mathematical model of multi-UAV cooperative operation is established， and the problem is formally described. We propose a task assignment algorithm based on mixed integer programming and a path planning algorithm based on an improved A* algorithm. The effectiveness of the proposed algorithm is verified by simulation experiments and compared with other classical algorithms. The experimental results show that the task assignment and path planning algorithm can improve the effectiveness of multi-UAV cooperation.

Key words： multi-UAV collaboration; task assignment; path planning; mixed integer planning; improved A* algorithm