基于蟻群算法的無人機偵察任務分配

馬培博，鐘 麟

(中國電子科技集團公司第五十四研究所，河北 石家莊 050081)

0 引言

在現階段的對抗場景中，空中力量的強弱往往對結果起到了關鍵性作用[1]。其中無人機在訓練過程中不需要飛行員參與空中訓練，大大節省費用的同時也避免了人員傷亡；并且無人機的地勤保障要求較低，無需大規模的起降場地，因而機動性較強[2-3]。鑒于無人機具備上述優勢，在戰場偵察任務中起到了至關重要的作用，且未來戰場中利用無人機執行偵察任務將是必然的發展趨勢[4]。

偵察任務分配本質是一個指派問題，根據目標的特點指派符合要求的偵察無人機。在當前多數研究中，將該問題抽象成旅行商問題或車輛路徑問題等，然后利用智能算法進行求解[5-6]。而在實際應用中，上述模型缺乏一定的約束條件，將有可能產生無效的分配方案。如不同的目標所需的機載設備不同，若不考慮負載匹配將可能給無人機分配一個無法進行偵察的目標；不同的無人機其性能也不盡相同，若將距離較遠的目標分配給剩余航程較短的無人機將會造成無人機半路返航甚至墜毀。

本文在聚焦實際偵察任務特點的基礎上，充分考慮所需的約束條件，建立了無人機任務分配模型。針對所建立模型和任務分配問題的特點，選用蟻群算法作為模型的求解算法，設計了無人機偵察任務分配算法，并通過仿真實驗驗證了該算法的有效性和實用性。

1 偵察任務分配問題模型設計

本文針對的應用背景為靜態任務分配，即待解決問題的場景為靜止狀態，無人機和偵察目標的數量、位置屬性等均已確定且在一定時間內保持不變[7]。通過本文算法將場景中存在的無人機與偵察目標進行匹配，得到偵察任務分配方案。在進行分配時，按照最小代價準則、放棄分配準則和最大分配率準則進行分配，得到無人機偵察任務分配問題的數學模型如下：

(1)

式(1)是將目標分配方案的整體代價值f最小作為優化目標函數，根據放棄分配準則和最大分配率準則設定了約束條件。目標函數中DCost為該方案中無人機執行任務所需的飛行航程，根據場景模型中無人機和目標的位置，可以計算出各無人機與目標間的距離。無人機i到目標j的距離即為分配方案(i,j)的航程代價:

DCost(i,j)=D(Ui,Tj)=‖Ui,Tj‖,

(2)

式中，i1、i2分別為無人機位置的橫縱坐標，j1、j2分別為目標位置的橫縱坐標。

目標函數中TCost為該分配方案所需的耗時，給無人機分配偵察目標時，需要飛行到達目標所在位置，因而會付出相應的時間代價，即各無人機的飛行時間。

(3)

式中，D(i,j)表示無人機i到目標j的距離，speed(i)為無人機i的飛行速度。由于航程和時間的量綱不同，因此加入調整因子α、β來調整二者的權重。

λ為方案違反約束條件時加入的懲罰因子，本文設定的約束條件包括航程約束、載荷約束和時間約束。在場景模型中對每個無人機均設定了最大航程，在比較分配方案時需要判斷完成偵察任務所需的飛行距離是否超過了該平臺的最大航程。若超出了最大航程，則需要在該分配方案的代價值中加入航程約束的懲罰因子DSin。

(4)

式中，DCost(i)為平臺i完成所有偵察任務所需的飛行距離，maxDis(i)為平臺i的最大航程。

同理，在場景設定中，對每個無人機也設定了最大飛行時間。為避免分配方案中出現無人機耗時過大的情況，在比較分配方案時需要判斷完成偵察任務所需的時間是否超過了該無人機的最大飛行時間。式(5)為無人機最大飛行時間的計算公式。當分配方案的總耗時大于無人機的最大飛行時間時，則需要在該分配方案的代價值中加入時間約束的懲罰因子TSin。

(5)

(6)

無人機可攜帶的偵察裝置種類多樣，可以搭載電子偵察設備進行通信偵察，攜帶航空照相機進行拍攝，也可以搭載可見光、紅外等光電偵察設備，部分無人機也裝有實時情報處理和傳輸設備，這就決定了不同的無人機可匹配的偵察目標不同[8]。因此，對分配方案需要判斷是否滿足載荷要求，將場景中設定的無人機載荷與匹配的目標所需的載荷類型進行對比，若二者存在匹配的載荷，表示該分配方案滿足載荷要求，否則將對該方案加入載荷約束的懲罰因子LSin。

(7)

式中，TNeed為目標所需的載荷種類集合，PLoad為無人機攜帶的載荷種類集合。只有當PLoad中存在TNeed中的元素時，才能保證該匹配關系能夠滿足載荷要求。

2 算法設計

2.1 蟻群算法原理

蟻群算法是一種啟發式智能算法，屬于集中式算法。該算法是由學者根據自然中蟻群覓食規律提出的一種仿生算法[9]。蟻群算法中每個螞蟻個體通過計算各路徑的轉移概率后選擇轉移方向，并根據總路徑長度釋放相關的信息素。該算法最早應用于旅行商問題，也可以用于解決指派問題、路由問題等。

在自然界中，科學家發現螞蟻在行走過程中可以在地面上沉積一種化學物質，并且該物質可以被其他螞蟻個體識別，稱之為信息素[10-11]。螞蟻個體在完成一次完整的巡游后，會通過釋放信息素來標記出完整的路徑，并且釋放信息素的濃度與該路徑長度成反比，當其經過的路徑越短，釋放的信息素越大；反之，則釋放的信息素越小[12]。當后續螞蟻個體經過未知路徑時，可以根據之前螞蟻留下的信息素進行選擇，優先挑選信息素較大的路徑，并且后續經過的螞蟻個體也將釋放新的信息素[13]。經此以往，便形成一個正反饋機制，最優路徑上的信息素濃度會越來越大，而其他路徑上的信息素會隨時間的推移而減少，最終可以挑選出最優路徑[14]。

2.2 算法實現步驟

將蟻群算法應用于本文的UAV偵察任務分配模型中時，具體的步驟及實現過程如下。

(1) 算法初始化

對蟻群算法中涉及的參數進行初始化設置，參數可分為算法參數和場景參數。算法參數主要包括蟻群規模m、問題規模n，最大迭代次數iter_max、信息素/啟發函數重要程度因子α、β和信息素矩陣(τij)m×n等。并將禁忌表tabuk(k=1,2,…，m)設置為空集，代表當前螞蟻沒有已選擇的目標；用集合allowk={C-tabuk}表示螞蟻下一步可以選擇的目標集合，C為問題中所有的目標點。場景參數中主要包括無人機/目標的位置、無人機飛行速度、目標所需載荷、無人機載荷和無人機最大航程。根據場景設定，對上述參數進行設置。

(2) 生成蟻群

(8)

如螞蟻個體可表示為：

(9)

其所代表的分配方案中，每個無人機均分得了一個目標，其中1號目標分給2號無人機，4號目標分配給3號無人機，以此類推。

(3) 計算分配方案代價值

生成蟻群后，對每只螞蟻個體代表的分配方案計算代價值，用方案代價值來表示每只螞蟻的巡游路徑長度。分配方案的總代價值包括無人機的航程代價、執行任務所需的時間代價以及違反約束條件時引入的懲罰因子[16]。

(4) 更新蟻群信息素

(10)

其次根據信息素增量矩陣來更新蟻群的信息素矩陣，計算公式如式(11)，其中τij(t+n)為更新后的信息素取值，ρ為揮發因子，τij(t)為更新前的信息素取值。

τij(t+n)=(1-ρ)×τij(t)+Δτij。

(11)

根據上述步驟進行iter_max次循環后，選出代價值最小的分配方案作為本次迭代的最優分配方案，并將該分配方案及最小迭代次數曲線進行展示。

3 仿真實驗與結果分析

3.1 仿真實驗設計

本文設計的仿真實驗場景為8個無人機和8個待偵察目標，在50 km×50 km的范圍內進行偵察。表 1和表 2分別為實驗中蟻群算法參數取值和場景參數設定。無人機載荷分別用1～4代表了4種不同類型的載荷，當無人機載荷設定為[1 2 3 4]時，表示該無人機可以匹配現有場景中的所有目標；當無人機載荷的取值為其中一種或幾種時，表示該無人機只能滿足某種特定類型目標對載荷的需求。將場景中航程約束懲罰因子S1、時間約束懲罰因子S2和載荷約束懲罰因子S3的取值設定為相同值，均為100。

表1 蟻群算法參數取值

表2 場景參數取值

進行實驗時，先根據上表設定的參數取值獲取分配方案。其次，進行兩次對比實驗，一是改變某些無人機的載荷后，觀察載荷約束是否起到作用；二是改變某些無人機的最大航程后，分析航程約束是否起到作用。

3.2 仿真實驗結果及分析

根據上述場景設定及實驗流程，在Matlab 2012環境中，耗時1.2 s得到偵察任務分配方案及最小代價迭代曲線分別如圖 1和圖 2所示。

圖1 偵察任務分配方案Fig.1 Reconnaissance task assignment plan

圖2 最小代價迭代曲線Fig.2 Minimum cost iteration curve

圖 1中每個無人機根據自身屬性參數選定了一個最適合自身的目標進行匹配，所有無人機與目標均進行了分配。圖 2表示該場景收斂曲線，代表每次迭代中計算得到的最小代價值，從最終的分配方案代價值可以看出，該分配方案未違反約束條件，因此，當前獲取的偵察任務分配方案為局部最優分配方案。

3.3 載荷約束驗證實驗及分析

在上述實驗的基礎上，改變某些無人機的載荷，使其只能匹配某個目標，并增大載荷約束懲罰因子S3取值，使違反載荷約束的分配方案能夠被算法過濾，改變后的場景參數取值如表 3所示。

表3 載荷約束驗證實驗參數取值

根據表 3中載荷的變化，將8號無人機改為攜帶一種載荷，且只能滿足8號目標的需求。從圖 5可以看出，改變了原來的分配方案，使8號無人機與8號目標進行了匹配，表明載荷約束起到了作用。并且圖 6中迭代次數進一步增大，表明約束條件增多時需要更多的迭代次數來找到局部最優分配方案。

圖3 改變載荷后任務分配方案Fig.3 Task allocation after changing load

圖4 改變載荷后最小代價迭代曲線Fig.4 Minimum cost iteration curve after changing load

4 結論

根據一對一場景及載荷約束驗證場景實驗結果分析得出，基于蟻群算法加入約束的無人機偵察任務分配模型能夠滿足場景需求，能夠在約束條件作用下獲取局部最優分配方案，更好地貼合實際應用場景。同時通過分析算法實驗的耗時，證明該算法敏捷高效，具備可行性和有效性。