不確定條件下多無人機偵察調度問題*

湛 佳，謝文俊，郭 慶，毛 聲

（空軍工程大學裝備管理與無人機工程學院，西安 710051）

0 引言

多無人機協同偵察將是未來無人機遂行任務的一種重要樣式，其核心問題是多無人機偵察調度問題。由于某些待偵察目標出現的時刻具有不確定性和動態性，導致多無人機偵察調度問題十分復雜。最新的研究成果——不確定理論為無人機偵察動態目標問題研究提供了新的理論工具。該理論是對實際應用中的專家信度進行分析的新興理論，對于先驗知識不足、缺乏大量實驗樣本的問題決策具有重要意義。

文獻[1]將任務分配的代價和收益作為總體目標函數，并基于投標過程對任務進行分配。文獻[2]對作戰時間和飛行距離等指標進行加權，基于攻擊任務的最大價值構建了單目標優化問題模型，并采用多子群蟻群算法求解，但忽略了航程的威脅代價。文獻[3]基于二進制粒子群算法完成任務分配過程。文獻[4]采用整數域改進粒子群優化算法對目標進行分配。人工蜂群（Artificial Bee Colony，ABC）算法其原理是模仿蜂群覓食過程的智能行為，是基于群體的啟發式優化算法[5]。ABC算法與差分進化算法、粒子群優化算法和遺傳算法相比較，進化的依據為適應度函數，具有控制參數少、操作簡單、魯棒性較強和搜索精度較高等特點，求解質量相對較好[6]。但基本ABC算法存在“早熟”的收斂性缺陷，存在開發能力不足，收斂速度較慢等缺點[7]。文獻[8]對傳統人工蜂群算法進行改進，提高了算法的收斂速度和全局搜索能力。文獻[9]將ABC算法與遺傳算子相結合，對可行解進行鄰域搜索，算法的搜索能力得到提高。文獻[10]設計了一種基于粒子群的ABC算法，通過將全局搜索和局部搜索相結合來尋找最優解。文獻[11]針對基本ABC算法容易陷入早熟收斂的缺點，改進了候選食物源的生成方法，增強了ABC算法的全局搜索能力。文獻[12]將多種搜索策略相結合，不同策略的解通過競爭產生新的解，算法的局部搜索能力得到增強。文獻[13]將ABC算法的全局搜索能力和ACO算法的局部搜索能力相結合得到一種ACO-ABC混合算法，以尋求最優解。文獻[14]設定最優鄰域解僅在多次未更新的情況下才能替換當前解，使有潛力的可行解得以保留。

針對動態目標出現時刻的不確定性，本文在傳統人工蜂群算法的基礎上，設計了一種改進的雙重進化人工蜂群算法。該算法以模型的目標函數作為指引，同時針對適應值函數，在全局搜索中對局部最優解進行處理，利用不同局部搜索算子的優點，加快了算法搜索速度，豐富了可行解的多樣性。最后通過仿真實驗表明，該算法能在動態條件下完整偵察到所有目標，取得最大偵察收益，并且其調用的無人機數量以及飛行距離最小，使得總飛行代價最小，實驗驗證了該算法能有效解決多無人機偵察調度問題。

1 多UAV協同偵察數學模型

1.1 問題描述

在戰場環境中，存在n個待偵察目標，用0表示基地，相應的數字表示對應的偵察目標，則組成節點集，用dij表示任意兩節點（i，j）之間的距離。一個具有同質性的無人機偵察分隊K位于基地，每架無人機具有相同的有效偵察載荷量Q。用qi表示每個偵察目標所消耗的偵察載荷量。此外，無人機存在一個續航時間。對于每個待偵察目標i，都存在一個偵察時間窗。在執行任務的每個時間點t，偵察目標分為以下兩類：

1.2 收益值計算

即動態目標j在 ∈[t+1，Li]中所有時刻 出現的信度的和值。

1.3 目標函數

其中，Cp與C0為常數，xijk為｛0，1｝變量，若第 k 架無人機從節點i前往節點j，xijk=1，否則xijk=0，dij為節點i與j之間的距離；目標函數第1項為總偵察收益，第2項為無人機總飛行距離，第3項為無人機固有飛行代價。無人機若能偵察到所有目標，則其總偵察收益最大，若完成偵察任務所調用的無人機數量及其飛行距離最少，那么目標函數的總飛行距離以及固有飛行代價最小，所以優化的總目標在于利用最少數量的無人機和最小化飛行總里程完成偵察任務。

1.4 約束條件

無人機對單個目標至多完成一次偵察，其約束條件為：

允許無人機在最早可偵察時刻之前到達目標區域，其約束條件為：

無人機必須在可偵察時間窗結束之前開始偵察，其約束條件為：

為了保證時間連續性，其約束條件為：

其中，C為足夠大的常數，基于第k架無人機到達目標點i的時刻aik，以及該目標點所需偵察時間si，即可計算離開時間；

為了保證無人機從基地出發到第1個目標點的時間連續性，其約束條件為：

為了保證無人機返回基地的時間連續性，其約束條件為：

綜上所述，每個決策階段的偵察調度模型如下所示：

2 調度方案求解

2.1 終止條件

一般條件下，若算法完成了設定的迭代次數，則可判定終止。除此之外，也可以通過判斷算法在全局搜索過程中產生的解是否迅速收斂作為算法終止的條件。這種方法可以避免以迭代次數作為終止條件產生的冗余迭代，在動態場景下具有較好的應用效果，缺點是由于迭代次數不夠，可能導致算法在全局搜索過程中未能發揮最佳效能。

2.2 解的編碼方式

用數字表示相應的目標，其中0表示基地。序列首尾數字均為0，表示無人機從基地出發，再返回基地；數字排列的順序代表的是無人機執行任務中偵察目標的順序。將各子序列首尾相接，構成一個完整序列，用此方式來表示一個可行解。各無人機型號不同時，序列中第i個子序列代表第i架無人機的偵察子方案；否則取消這一對應關系，全序列僅表示存在這樣的一個偵察方案，以避免冗余。

以15個目標，3架無人機為例，一種可能的調度方案的表示如圖1所示。

圖1 調度方案示例

為方便文中敘述，用 vk（i）表示第 k架無人機到達的第i個節點，rk表示其對應子序列的節點總數，則該UAV的偵察方案也可用節點集表示，其中初始節點和終止

節點均為基地。

2.3 初始化

1）基地設為v1（1），最低代價設LC為無窮，設置無人機數量上限為#veh，初始化最佳方案序列X=｛v1（1）｝。

4）輸出參數集及其對應的最佳方案集。

2.4 適應值

適應值函數fitD按式（10）計算：

其中，γ為自適應約束系數，在一次局部搜索過程中，γ的值隨搜索過程動態變化，若在較優解中，違反載荷量約束解的數目超過總數的一半，則；否則，其中φ為常數。γ越小，對可行解的限制越小，搜索范圍就越大；γ越大，對可行解的限制越大，搜索范圍就越小。

2.5 選擇和跟隨

在雇傭蜂階段進行之后，跟隨蜂通過概率pi對雇傭蜂找到的蜜源進行選擇，pi根據輪盤賭方法計算，如式（11）所示：

其中，N為解的數量。

2.6 雙重進化過程

在跟隨蜂和雇傭蜂階段，該算法均進行了局部搜索，搜索過程中均采用雙重進化方法[16]。其具體操作過程如下：

1）半隨機式最優插入點算子，如圖2所示。

①隨機選取插入點r1，插入位置記為r2；

②r2遍歷所有可行的插入位置，生成新的可行方案，并計算各可行方案的適應值；

③找到使適應值最小的可行方案，并將r1處的目標插入到該位置。

圖2 半隨機最優式插入點算子

2）半隨機式最優逆轉序列算子，如圖3所示。

①隨機選取子序列的一端記為r1，子序列的另一端記為r2；

②r2遍歷可行子序列的另一端，將r1、r2確定的子序列逆轉，生成新的可行方案，并計算各可行方案的適應值；

③找到使適應值最小的可行方案，并將子序列逆轉。

圖3 半隨機最優逆轉序列算子

這一搜索過程較為快速和高效，計算量較小，在文中將其命名為基于重新構建方案的局部搜索方法。

偵察動態不確定目標的多無人機偵察調度方案求解流程如下頁圖4所示。在目標數據更新之后，優先采用快速局部搜索方法；如果這一方法達到收斂（最優解經過βLimit次迭代未更新），而動態目標仍未出現，則一直采用基于重新構建方案的局部搜索方法，基于待偵察目標集制定當前偵察方案。

3 實驗結果及分析

3.1 應用場景想定

本文將UAV對某海域島礁的偵察監視設定為任務背景，假設基地位于島礁集群的中點（經度114.60°，緯度9.47°）。各個目標以及目標與基地兩兩之間的距離通過歐式空間距離確定；具體結果利用高斯坐標轉換進行計算，采用是西安1980參考橢球和三度帶投影。本文假定，原50個島礁中，有5個島礁附近會有非法船只出現，作為動態不確定目標，其基本設置如下頁表1所示。

表1中出現時刻所服從的不確定分布是依據已知信息和戰場經驗估計而來，具體內容為其出現時刻服從的不確定分布；持續時間為對方艦船在爭議海域停留的時間。設定飛行速度為144 km/h，飛行單位距離所耗時間為確定值，要求對多無人機進行動態調度，使得無人機使用數量最少，總飛行代價最低，同時盡可能完成所有目標的偵察。

3.2 仿真試驗

圖4 算法流程圖

表1 動態不確定目標信息

在UAV執行任務過程中，針對本文設計任務的計算量和搜索深度，在不同的時間緊迫度情況下，結合HB-ABC與RC-ABC的局部搜索策略進行動態多UAV目標的偵察調度求解。實驗中，最大循環次數設置為1 000，β的值設定為3，Limit的值設定為20。由于實驗中動態目標出現的具體時刻不同，會影響偵察調度方案的指定。故選擇其中一種執行的情況，利用STK軟件展示如圖5所示。從圖中可以看出，無人機對所有目標均進行了偵察，其總偵察收益達到最大。

圖5 偵察調度方案

為測試將RC-ABC算法和HB-ABC算法局部搜索策略相結合的有效性，分別單獨用這兩種ABC算法進行跟蹤，并與RC-HB-ABC算法比較最終跟蹤結果，其中RC-HB-ABC算法中與終止條件相關的參數β取3，且動態目標的權重遠大于已知目標。

實驗設計兩種不同的動態度進行測試，分別為10%，30%；即分別有總數量中10%，30%的目標是決策者在無人機開始偵察時僅擁有專家的不確定知識，而它們并未出現。隨機選取C101、C106、R101、R106、RC101、RC106 進行改動和實驗，實驗中，隨機選取原測試數據集中的點作為動態目標點，出現時刻在[0，Li]中生成。對每組動態測試數據，通過30次的運行選取最佳結果，結果如表2與表3所示。

表2 10%動態度下不同ABC算法結果比較

表3 30%動態度下不同ABC算法結果比較

由表2與表3可知，從優化距離的角度來看，將兩種策略相結合取得的效果最佳。RC-ABC算法與HB-ABC算法依據測試集動態度的不同，優化結果有差異；但整體上來看RC-HB-ABC算法在動態度測試問題中優化結果相對較好。

為對結果進行具體評估，在10%動態度下，將3種跟蹤策略解決R103測試集的收斂曲線展示如圖6所示。由圖6可知，HB-ABC算法跟蹤策略收斂速度較快，但由于搜索深度不夠，解的質量相對不是很理想，但在動態目標出現的緊迫度較高時能得到最好質量的解；RC-ABC算法的局部搜索策略能夠進行較為深度的搜索，但搜索時間較長，在緊迫度較低的情況下能夠得到最好質量的解；RC-HB-ABC算法的搜索策略結合了兩種搜索策略的優點，一方面判斷使用哪一種具體策略的過程中計算量較小，因此，在時間緊迫度高的情況下收斂速度與HB-ABC的局部搜索策略幾乎相同；另一方面在搜索時間較長的情況下，由于是順次進行兩種搜索策略，在某些情況下還能求得比RC-ABC質量更好的解。實驗結果驗證了所提出算法的有效性以及解決多無人機調度問題的可行性。

圖6 收斂曲線圖

4 結論

本文在構建動態環境下多無人機調度問題模型的基礎上，設計了一種改進的雙重進化人工蜂群算法求解該模型。通過仿真實驗，證明該算法能在動態條件下完全偵察到所有目標，取得最大偵察收益，并且完成偵察任務所調用的無人機數量以及飛行距離最短，使飛行代價最小。最后將該算法與RC-ABC以及HB-ABC算法進行比較，實驗結果表明該算法能顯著提高收斂速度和全局尋優能力。