一種基于蟻群算法的無人機協同任務規劃優化算法

黃偉民+王亞剛

摘 要：隨著無人機在軍事領域的廣泛應用，越來越多的無人機將應用在未來戰場，因此無人機協同規劃變得越來越重要。建立了多無人機協同任務分配模型，并研究了模型求解的有效算法。在蟻群算法的基礎上提出針對密度較大目標區域的多無人機協同任務規劃的優化方法，優化蟻群算法的搜索條件，降低了蟻群算法的時間和空間復雜度。

關鍵詞：無人機；協同規劃；蟻群算法；目標群密度

DOIDOI：10.11907/rjdk.171261

中圖分類號：TP319

文獻標識碼：A 文章編號：1672-7800（2017）007-0131-03

0 引言

多基地多無人機協同偵查模型可以描述為：利用多種不同性能的無人機對多個空間分散的目標進行偵查，這些無人飛機分散在多個地理位置不同的基地上，需要快速制定無人偵查飛機的偵查任務計劃以滿足偵查要求和實際約束條件。在無人機迅速發展的同時，雷達技術也快速發展，因此一旦有偵察無人機進入防御方某一目標群配屬雷達探測范圍，防御方目標群的配屬雷達均開機對空警戒和搜索目標，并會采取相應對策，包括發射導彈對無人機進行摧毀等，因此偵察無人機滯留防御方雷達探測范圍內時間越長，被其摧毀的可能性就越大[1-2]。本文以偵察、監視任務為中心，以協同探測多基地目標為背景，在蟻群算法規劃路線的基礎上進一步優化線路，以此盡可能縮短無人機任務飛行時間和被雷達探測到的時間。

2 無人機偵察目標群聚類

為了最大程度上利用各無人機基地資源，首先要對目標群進行聚類。常用的聚類方法有K-means聚類算法、層次聚類算法、SOM聚類算法和FCM聚類算法[3]。本文采用層次分析法對目標群進行聚類， 通過聚類，可以規劃出各無人機基地派出的無人機的探測目標群，在無人機數量和飛行參數限制條件下，這樣做能最大限度地提高效率。

層次分析法的算法流程如圖1所示。

3 基于改進蟻群算法的目標群路線規劃

對目標群聚類后，要對每個類里的線路進行規劃[4，6-7]，首先采用蟻群算法規劃路線。在無人機協同任務規劃中，蟻群算法能夠很好地規劃目標群之間的最優路徑，但是沒有考慮到目標群密度條件，針對密度較小的目標群，蟻群算法給出的是最優解，但是對于密度較大的目標群模型，蟻群算法給出的路徑并不是最優解，很多在無人機探測半徑之內的目標可以一次飛過，不需要飛到每個點的上空探測，盡可能在兩偵查目標之間航行，能夠偵查到載荷搜索范圍內的目標。鑒于此，提出對蟻群算法的改進算法。首先對三目標距離模型進行建模，設無人機的探測半徑為Kr，如圖2所示。x為目標1到目標3的距離，y為目標2到目標3的距離，a為1，2目標之間的距離，則可得其模型如圖2所示。

Step3：當m只蟻都完成了后續節點選擇后，完成一次循環，各路徑上信息素根據下式進行局部信息素更新：

其中，Δτkij 表示第k只螞蟻留在路徑（i，j）上的信息素，表示本次循環中路徑（i，j）信息素的增量；ρ為信息素軌跡的衰減系數，通常設置ρ<1來避免路徑上信息素的無限累計。

Step4：重復Step2和Step3，直到到達目標點。更新全局信息素Q，清空k的禁忌表tabuk。

Step5：計算螞蟻所有路徑的總長度，將新的路徑與已知的最優路徑相比較。若新路徑更優，則替換已知的最優路徑，存儲當前最優路徑的各個節點。

Step6：迭代次數Nstep加1，若Nstep>Maxstep，則停止尋找，輸出最優路徑，否則轉到Step2繼續尋找。

蟻群算法的時間和空間復雜度為[5]：

式中，n為所求問題規模，Nc 為算法的迭代次數，m為所求問題中的樣本數量[11]。

改進后的蟻群算法時間和空間復雜度為：

4 實驗結果分析

為驗證算法的可行性和有效性，用Matlab對算法進行程序仿真[8-9]。圖3為多無人機基地和目標群落之間的地理位置關系；圖4為各目標群落內目標間距離關系圖。對此情景下的多無人機協同任務進行規劃。

使用MATLAB編寫層次聚類算法[3]求出各目標群的聚類圖，如圖5所示。

實驗參數為信息啟發式因子α =1；期望啟發式因子β=5；信息素殘留因子ρ =0.5；蟻群的波數為20；每波螞蟻的數量為30。

用MATLAB對蟻群算法[5]進行仿真求出偵查路徑和航程，如表1所示；使用改進后的蟻群算法計算出偵查路徑和航程，具體如表2所示。由表1、表2可得出，優化后的路線減少了飛行的節點數，從而減少了轉彎次數，降低了能耗和路徑長度，飛行距離減少了36.7%。

5 結語

本文主要研究解決了多無人機協同規劃問題，采用層次聚類對目標群進行行分類，把分類目標群分配給各無人機基地。將目標群密度因素引入到蟻群算法中，極大降低了蟻群算法的時間和空間復雜度，加快了算法的收斂速度。用Matlab進行仿真實驗，仿真結果表明，改進的蟻群算法能夠更好地解決多無人機規劃的實際問題，且隨著目標群的密度變大和無人機探測半徑的增加，其優化效果越明顯。

參考文獻：

[1] BAUSO D，GIARRE L，PESENTI R.Multiple UAV cooperative path planning via neuro-dynamic programming[C].Proceedings of the IEEE Conference on Decision and Control，2004：1087-1092.

[2] AIAA.Cooperative task assignment and path planning of multiple UAVs[C].2007 Conference and Exhibit，California，2007.

[3] WANG X Z，XIAO J B.Applied research of adshpso algorithm in multi-uav cooperative mission planning[J].Applied Mechanics& Materials，2013（375）：1106-1109.

[4] 鄧啟波.多無人機協同任務規劃技術研究[D].北京：北京理工大學，2014.

[5] 郭海洋.基于蜂群算法的無人機群協同飛行策略研究[D].哈爾濱：哈爾濱工程大學，2012.

[6] 韓攀.多無人機協同任務規劃技術[D].南京：南京航空航天大學，2013.

[7] 程聰.無人機協同作戰任務分配與攻擊效能評估技術[D].南京：南京航空航天大學，2013.

[8] 王國強，羅賀，胡笑旋.無人機編隊協同任務規劃仿真系統研究[J].系統仿真學報，2014（8）：1856-1862.

[9] 吳靜.多無人機協同航跡規劃及效能評估方法研究[D].南昌：南昌航空大學，2012.

[10] 朱艷萍.多無人機協同攻擊策略研究[D].南昌：南京航空航天大學，2012.endprint