無人機群對多目標執(zhí)行多任務(wù)的協(xié)同規(guī)劃方法

衛(wèi)釗丞，劉衛(wèi)東，張小明，樊宇韜

(火箭軍工程大學，陜西 西安 710025)

0 引言

當待執(zhí)行任務(wù)分布廣泛且工作量較大時，單個無人機難以滿足要求，而無人機群通過相互協(xié)同和配合可以更好地完成此類工作。無人機協(xié)同任務(wù)規(guī)劃是提高無人機群工作效率和生存能力的重要手段[1]。

無人機群對多目標執(zhí)行多項任務(wù)的協(xié)同規(guī)劃問題，是當前研究的熱點問題，解決思路是建立多無人機協(xié)同任務(wù)規(guī)劃的數(shù)學模型，使用群智能算法搜索模型最優(yōu)解。文獻[2]提出了自適應(yīng)煙花算法解決多無人機的多約束多任務(wù)規(guī)劃問題，此方法能快速收斂于全局最優(yōu)；文獻[3]提出了帶隊-跟隨編隊方法，用于設(shè)計無人機協(xié)同跟蹤地面目標的制導律；文獻[4]提出了基于離散粒子群算法的多無人機多任務(wù)協(xié)同分配方法，給出了滿足約束條件的任務(wù)分配方法；文獻[5]針對多架異構(gòu)無人機在未知環(huán)境下執(zhí)行搜索打擊任務(wù)，提出了并行帶精英策略非支配排序的遺傳算法求解模型，此方法實時性很強。

目前的研究成果很少考慮任務(wù)執(zhí)行的時間序列問題，本文考慮了任務(wù)規(guī)劃和時序規(guī)劃，提出了保留潛力蜜源人工蜂群算法(retain potential source artificial bee colony algorithm,RPSABC)的無人機群多目標多任務(wù)規(guī)劃問題，旨在提高無人機群任務(wù)規(guī)劃的速度、精度和魯棒性。

1 問題描述與建模

1.1 無人機群協(xié)同任務(wù)規(guī)劃問題描述

將無人機群任務(wù)協(xié)同考慮在戰(zhàn)場環(huán)境下，多架無人機對不同基地的目標執(zhí)行多項任務(wù)，在執(zhí)行任務(wù)時要規(guī)避威脅區(qū)域和禁飛區(qū)域。

將問題具體化，無人機考慮為集偵查、打擊、評估能力于一體的無人機，給定任務(wù)環(huán)境中n架無人機出發(fā)點和m個攻擊目標位置。使用n架無人機對m個目標點執(zhí)行偵查、打擊和評估任務(wù)，3種任務(wù)依次記為C任務(wù)、A任務(wù)和E任務(wù)。某架無人機在某目標位置執(zhí)行1次任務(wù)后會被標記，若此無人機在此區(qū)域再次執(zhí)行任務(wù)存在被打擊的風險，因此規(guī)定同一架無人機在同一目標位置最多執(zhí)行1次任務(wù)。

本文設(shè)定無人機在定值高度層飛行，雷達、防空導彈和防空火炮等威脅簡化為圓模型，如圖1所示。圓模型參數(shù)包括威脅中心、威脅半徑和威脅等級3個參數(shù)。在此需要強調(diào)的是，威脅半徑為雷達、導彈的威脅半徑與無人機外接圓半徑之和，故可以將無人機簡化為一個質(zhì)心。無人機群協(xié)同任務(wù)規(guī)劃和執(zhí)行情況如圖1所示，圖1中Ui為無人機編號，Ti為目標編號。

圖1 無人機群協(xié)同任務(wù)規(guī)劃示意

1.2 協(xié)同任務(wù)規(guī)劃約束條件

對于同一目標點，3類任務(wù)的執(zhí)行順序是偵查、打擊和評估，執(zhí)行順序不允許顛倒，且一個任務(wù)執(zhí)行完畢后才執(zhí)行下一任務(wù)。同一無人機對同一目標點最多執(zhí)行1次任務(wù)，同一目標點必須完成這3類任務(wù)。以上約束條件用公式表達為

(1)

x為無人機的編碼；當?shù)趇個無人機在第j個目標點執(zhí)行任務(wù)時xi,j=1，否則xij=0；k用于區(qū)分執(zhí)行任務(wù)類型，k=1,2,3分別代表執(zhí)行偵查、打擊和評估任務(wù)；t1j,k、t2j,k、t3j,k分別表示無人機對第j個目標點執(zhí)行第k類任務(wù)的開始時間、結(jié)束時間和等待時間；tj,k為對第j個目標點執(zhí)行第k類任務(wù)所需時間。本文假設(shè)對同一目標點執(zhí)行3類任務(wù)的時間相同。

1.3 目標函數(shù)建立

設(shè)定無人機飛行速度不變，記為v。無人機群的最后一項任務(wù)執(zhí)行完畢后，整個無人機群的任務(wù)才算執(zhí)行完畢，因此執(zhí)行任務(wù)耗時最長的無人機代表了此無人機群的耗時。基于以上考慮，將目標函數(shù)設(shè)置為

(2)

S=(S1,S2,…,Sn)，Si代表無人機Ui執(zhí)行所有任務(wù)的總航程。

由于目標函數(shù)中提到了航程問題，點與點之間的航跡規(guī)劃問題必須交代清楚，本文使用文獻[6]中給出的航跡規(guī)劃方法。

2 優(yōu)化模型求解

2.1 保留潛力蜜源人工蜂群算法

人工蜂群算法原理已經(jīng)成熟，可以參考文獻[7-8]，這里不再贅述。針對算法自身缺陷和無人機對多目標執(zhí)行多樣任務(wù)優(yōu)化問題，做以下說明和改進：

a.蜜源編碼方式。由于每個目標點需要執(zhí)行3項任務(wù)，則對于m個目標點需設(shè)置3m維的蜜源編碼，從編碼第1位開始，每3位代表1個目標點任務(wù)，也就是說第1、2、3位分別表示對第1個目標點執(zhí)行偵查、打擊和評估任務(wù)，第4、5、6位表示對第2個目標點執(zhí)行任務(wù)，以此類推。記1個任務(wù)分配序列為(x1,x2,…,x3m)，則表示相應(yīng)位置的任務(wù)由編碼為xj的無人機執(zhí)行。

b.改進蜜源初始化。蜜源初始化是生成1個NB×3m的矩陣，由于編碼只能取整數(shù)，則傳統(tǒng)人工算法的初始化方法不再適用。為了解決這一問題，改進蜜源初始化方法為

xj=rand(0,n)

(3)

rand(0,n)表示0～n的隨機整數(shù)。蜜源初始化時，要求同一無人編號在同一目標3個任務(wù)中最多出現(xiàn)1次。

c.改進觀察蜂對雇傭蜂的選擇概率。在傳統(tǒng)算法中，觀察蜂依據(jù)雇傭蜂蜜源適應(yīng)度值確定跟隨概率，該方法利于算法收斂，但是卻容易陷入局部最優(yōu)?？烧J為連續(xù)被優(yōu)化的蜜源附近更具有搜索潛力，更具有搜索價值，基于這一考慮，設(shè)置變量D1(i)、D2(i)用于記錄蜜源連續(xù)更新次數(shù)。當蜜源i更新時，令D1(i)=0，D2(i)=D2(i)+1；當蜜源i保持不變時，令D2(i)=0，D1(i)=D1(i)+1。D1(i)、D2(i)最大值均設(shè)定為Limit，Limit表示局部搜索最大次數(shù)。

經(jīng)過多次搜索未更新的蜜源，說明其鄰域搜索意義不大，已經(jīng)陷入了局部最優(yōu)。而多次更新的蜜源鄰域搜索活力較大，對算法尋優(yōu)指導意義更大，因此應(yīng)將觀察蜂更大概率地分配到此區(qū)域。記G(i)為蜜源i的評估分值，每個蜜源基礎(chǔ)分為50，各蜜源得分計算方法為

G(i)=

(4)

fit(i)表示第i只蜜蜂的適應(yīng)度值，本文中f(i)=Fi表示第i只蜜蜂的目標函數(shù)，且有

(5)

依據(jù)各蜜源得分，確定觀察蜂的動態(tài)選擇概率為

(6)

d.改進蜜源評價方法。傳統(tǒng)算法中，依據(jù)蜜源適應(yīng)度值大小決定是否接受蜜源，這種選擇方式過早地將有潛力的蜜源淘汰掉，使算法前期收斂較快，算法后期收斂較慢。為了解決這一問題，本文提出了蜜源選擇的Metropolis準則[9]，蜜蜂由當前蜜源轉(zhuǎn)向新蜜源的轉(zhuǎn)移概率為

(7)

P(o→n)為由當前蜜源o向新蜜源n轉(zhuǎn)移的概率，下降函數(shù)T(t)=T(t-1)·σ，σ為退火系數(shù)，取σ=0.8。

分析式(7)可知，當新蜜源適應(yīng)度小于原蜜源時，仍有一定的轉(zhuǎn)移概率，有利于保留具有潛力的蜜源；在算法初期，退火溫度T(t)較高，適應(yīng)度差的蜜源轉(zhuǎn)移概率較大，保留有潛力蜜源的概率也大，有利于算法跳出局部最優(yōu)；算法后期退火溫度逐漸減小，算法更加“關(guān)注”優(yōu)質(zhì)蜜源，更多蜜蜂在優(yōu)質(zhì)蜜源鄰域內(nèi)細致搜索，提高尋優(yōu)精度。

2.2 保留潛力蜜源人工蜂群算法流程

根據(jù)上節(jié)對人工蜂群算法機理的改進，使用保留潛力蜜源人工蜂群算法尋優(yōu)的步驟為：

a.初始化算法參數(shù)。種群規(guī)模NB、局部搜索最大次數(shù)Limit、最大迭代次數(shù)MaxCycle、概率值P1，設(shè)置trial(i)=0,iter=0。

b.進行種群初始化，依據(jù)適應(yīng)度值將蜜蜂分為雇傭蜂和觀察蜂。

c.雇傭蜂進行鄰域搜索，依據(jù)Metropolis準則判斷是否接受新蜜源，使用搖擺舞將蜜源信息傳遞給觀察蜂。

d.觀察蜂根據(jù)動態(tài)選擇概率選擇雇傭蜂，而后與雇傭蜂一起進行鄰域搜索，依據(jù)Metropolis準則判斷是否接受新蜜源，若蜜源更新則trial(i)=0，若不更新則trial(i)=trial(i)+1。

e.判斷trial(i)>Limit是否成立，若成立則第i只蜜蜂轉(zhuǎn)化為偵查蜂進行隨機搜索，若不成立則轉(zhuǎn)至下一步。

f.輸出全局最優(yōu)蜜源，iter=iter+1，判斷iter>MaxCycle是否成立，若成立則算法結(jié)束，否則轉(zhuǎn)至步驟c。

2.3 時序規(guī)劃方法

使用改進人工蜂群算法尋優(yōu)得到目標函數(shù)意義下的最優(yōu)解，其解的形式為3m維的行向量，以此為基礎(chǔ)進行時序規(guī)劃。提取每個無人機經(jīng)過的目標點，由于每個無人機執(zhí)行任務(wù)的目標點是有限的，因此使用排列法就可以將所有順序窮盡地列舉出來，然后計算每種順序的目標函數(shù)，目標函數(shù)最小時對應(yīng)的任務(wù)順序即為任務(wù)的執(zhí)行時序。所有無人機在同一時刻開始，由出發(fā)點逐個飛向目標點，直至所有任務(wù)執(zhí)行完畢。

3 仿真驗證

為了驗證保留潛力蜜源人工蜂群算法在無人機群協(xié)同任務(wù)規(guī)劃中的可行性和有效性，使用MATLAD R2014a軟件進行仿真驗證。目標點分布在1 000 km×1 000 km環(huán)境范圍內(nèi)，共設(shè)置10個目標點，分別記為T1～T10，位置坐標分別為(50,300)(310,300)(210,700)(620,610)(250,500)(620,350)(450,470)(600,150)(820,350)(420,750)。任務(wù)執(zhí)行范圍內(nèi)存在8個威脅，威脅參數(shù)設(shè)置如表1所示。使用5架無人機組成的無人機群執(zhí)行任務(wù)，無人機參數(shù)如表2所示。

表1 各威脅參數(shù)

表2 各無人機參數(shù)

保留潛力蜜源人工蜂群算法的參數(shù)設(shè)置為：種群規(guī)模NB=60、局部搜索最大次數(shù)Limit=10、最大迭代次數(shù)MaxCycle=300。

為了形成對比，分別使用本文保留潛力蜜源人工蜂群算法、逆向算子人工蜂群算法(improved artificial bee colony algorithm based on reverse operator,ROABC)[10]、基本人工蜂群算法(artificial bee colony algorithm,ABC)進行無人機群協(xié)同任務(wù)規(guī)劃，各算法進行20次仿真。算法迭代過程中，目標函數(shù)最優(yōu)值變化曲線如圖2所示。

圖2 不同算法的目標函數(shù)最優(yōu)值變化曲線

由圖2可以看出:在算法迭代前20次，3種算法收斂速度相差不大，而后ABC算法收斂速度緩慢，算法陷入局部極值，尋優(yōu)結(jié)果較差；在算法迭代至80次時，ROABC算法收斂速度變緩，RPSABC算法繼續(xù)快速收斂；從收斂結(jié)果看，RPSABC搜索結(jié)果最優(yōu)，其次為ROABC算法、ABC算法。

記所有無人機起飛時刻為0時刻，使用改進人工蜂群算法規(guī)劃的任務(wù)最優(yōu)分配時刻表如圖3所示。

圖3 各無人機任務(wù)執(zhí)行時刻表

以無人機U5為例，按時序執(zhí)行任務(wù)的航跡如圖4所示。

圖4 U5執(zhí)行任務(wù)航跡

由圖3可知:每個目標點都執(zhí)行了3類任務(wù)，意味著任務(wù)完成；且同一目標點不同任務(wù)在時間上分散，滿足同一目標點不能同時執(zhí)行不同任務(wù)的約束；同一無人機在同一目標點最多執(zhí)行了1次任務(wù)，保證了無人機的安全。由圖4可知，時序安排非常合理，沒有出現(xiàn)“南轅北轍”的現(xiàn)象。

為了進一步比較RPSABC算法、ROABC算法和ABC算法在無人機群協(xié)同任務(wù)規(guī)劃中的性能，統(tǒng)計20次仿真的平均收斂迭代次數(shù)、目標函數(shù)收斂值均值和目標函數(shù)收斂值標準差，結(jié)果如表3所示。

表3 不同算法尋優(yōu)參數(shù)

結(jié)合表3與圖2可知：RPSABC算法在迭代158次時收斂，目標函數(shù)值不再下降，比ROABC算法的收斂速度提高了31.9%，比ABC算法的收斂速度提高了40.4%；RPSABC算法任務(wù)規(guī)劃的目標函數(shù)值最優(yōu)，比ROABC算法減小了5.2%，比ABC算法減小了19.0%；而且RPSABC算法的收斂值標準差最小，說明此算法的穩(wěn)定性和魯棒性最好。這是因為在改進人工蜂群算法中，觀察蜂選擇雇傭蜂的動態(tài)選擇策略既考慮了適應(yīng)度高的蜜源，也考慮了具有搜索潛力的蜜源，利于算法尋優(yōu)；將Metropolis準則應(yīng)用于蜜源評價，算法前期搜索優(yōu)質(zhì)蜜源和潛力蜜源，算法后期更加關(guān)注優(yōu)質(zhì)蜜源，保證了算法前期跳出局部最優(yōu)，后期細致搜索，最終使改進算法收斂速度快，收斂精度高。

4 結(jié)束語

本文研究了無人機群對多基地多目標執(zhí)行多項任務(wù)的規(guī)劃問題，建立了無人機群協(xié)調(diào)任務(wù)規(guī)劃的環(huán)境模型和數(shù)學模型，使用動態(tài)選擇規(guī)則、優(yōu)質(zhì)蜜源引導、Metropolis準則等改進了人工蜂群算法，將改進人工蜂群算法應(yīng)用于多無人機協(xié)同任務(wù)規(guī)劃問題。仿真結(jié)果表明，改進算法在收斂速度和收斂精度上均優(yōu)于逆向算子人工蜂群算法、基本人工蜂群算法。