一種基于蟻群算法的無人機(jī)協(xié)同任務(wù)規(guī)劃優(yōu)化算法

黃偉民+王亞剛

摘 要：隨著無人機(jī)在軍事領(lǐng)域的廣泛應(yīng)用，越來越多的無人機(jī)將應(yīng)用在未來戰(zhàn)場，因此無人機(jī)協(xié)同規(guī)劃變得越來越重要。建立了多無人機(jī)協(xié)同任務(wù)分配模型，并研究了模型求解的有效算法。在蟻群算法的基礎(chǔ)上提出針對密度較大目標(biāo)區(qū)域的多無人機(jī)協(xié)同任務(wù)規(guī)劃的優(yōu)化方法，優(yōu)化蟻群算法的搜索條件，降低了蟻群算法的時(shí)間和空間復(fù)雜度。

關(guān)鍵詞：無人機(jī)；協(xié)同規(guī)劃；蟻群算法；目標(biāo)群密度

DOIDOI：10.11907/rjdk.171261

中圖分類號：TP319

文獻(xiàn)標(biāo)識碼：A 文章編號：1672-7800（2017）007-0131-03

0 引言

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

2 無人機(jī)偵察目標(biāo)群聚類

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

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

3 基于改進(jìn)蟻群算法的目標(biāo)群路線規(guī)劃

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

Step3：當(dāng)m只蟻都完成了后續(xù)節(jié)點(diǎn)選擇后，完成一次循環(huán)，各路徑上信息素根據(jù)下式進(jìn)行局部信息素更新：

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

Step4：重復(fù)Step2和Step3，直到到達(dá)目標(biāo)點(diǎn)。更新全局信息素Q，清空k的禁忌表tabuk。

Step5：計(jì)算螞蟻所有路徑的總長度，將新的路徑與已知的最優(yōu)路徑相比較。若新路徑更優(yōu)，則替換已知的最優(yōu)路徑，存儲(chǔ)當(dāng)前最優(yōu)路徑的各個(gè)節(jié)點(diǎn)。

Step6：迭代次數(shù)Nstep加1，若Nstep>Maxstep，則停止尋找，輸出最優(yōu)路徑，否則轉(zhuǎn)到Step2繼續(xù)尋找。

蟻群算法的時(shí)間和空間復(fù)雜度為[5]：

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

改進(jìn)后的蟻群算法時(shí)間和空間復(fù)雜度為：

4 實(shí)驗(yàn)結(jié)果分析

為驗(yàn)證算法的可行性和有效性，用Matlab對算法進(jìn)行程序仿真[8-9]。圖3為多無人機(jī)基地和目標(biāo)群落之間的地理位置關(guān)系；圖4為各目標(biāo)群落內(nèi)目標(biāo)間距離關(guān)系圖。對此情景下的多無人機(jī)協(xié)同任務(wù)進(jìn)行規(guī)劃。

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

實(shí)驗(yàn)參數(shù)為信息啟發(fā)式因子α =1；期望啟發(fā)式因子β=5；信息素殘留因子ρ =0.5；蟻群的波數(shù)為20；每波螞蟻的數(shù)量為30。

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

5 結(jié)語

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

參考文獻(xiàn)：

[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] 鄧啟波.多無人機(jī)協(xié)同任務(wù)規(guī)劃技術(shù)研究[D].北京：北京理工大學(xué)，2014.

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

[6] 韓攀.多無人機(jī)協(xié)同任務(wù)規(guī)劃技術(shù)[D].南京：南京航空航天大學(xué)，2013.

[7] 程聰.無人機(jī)協(xié)同作戰(zhàn)任務(wù)分配與攻擊效能評估技術(shù)[D].南京：南京航空航天大學(xué)，2013.

[8] 王國強(qiáng)，羅賀，胡笑旋.無人機(jī)編隊(duì)協(xié)同任務(wù)規(guī)劃仿真系統(tǒng)研究[J].系統(tǒng)仿真學(xué)報(bào)，2014（8）：1856-1862.

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

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