顏 驥，李相民,，劉 波

(1.海軍航空工程學(xué)院 兵器科學(xué)與技術(shù)系， 山東 煙臺 264001；

2.中航工業(yè)洛陽電光設(shè)備研究所 光電控制技術(shù)重點實驗室， 河南 洛陽 471023)

應(yīng)用離散粒子群-郭濤算法分配多無人機(jī)協(xié)同任務(wù)*

顏 驥1，李相民1,2，劉 波2

(1.海軍航空工程學(xué)院 兵器科學(xué)與技術(shù)系， 山東 煙臺 264001；

2.中航工業(yè)洛陽電光設(shè)備研究所 光電控制技術(shù)重點實驗室， 河南 洛陽 471023)

針對以往考慮時間窗約束的多無人機(jī)協(xié)同任務(wù)分配問題模型不能反映在有效時間窗內(nèi)，任務(wù)執(zhí)行時間對任務(wù)收益的影響及求解算法效率較低的問題。建立了將任務(wù)收益和任務(wù)執(zhí)行時間直接聯(lián)系起來的任務(wù)分配模型和可行解到粒子整數(shù)編碼方式的映射，設(shè)計了混合離散粒子群-郭濤算法的組合優(yōu)化問題求解策略。借助粒子群算法利用粒子自身信息和種群有用信息指導(dǎo)種群進(jìn)化的本質(zhì)特點，優(yōu)化郭濤算法的適應(yīng)性序列倒置操作；設(shè)計了可變的學(xué)習(xí)選擇概率來選擇個體的學(xué)習(xí)粒子，改進(jìn)了序列倒置算子。仿真實驗驗證了該方法處理復(fù)雜任務(wù)分配問題的有效性。

離散粒子群算法；郭濤算法；任務(wù)分配；有效時間窗；多無人機(jī)

(1.DepartmentofOrdnanceScienceandTechnology,NavalAeronauticalandAstronauticalUniversity,Yantai264001,China；

2.ScienceandTechnologyonElectro-opticControlLaboratory，LuoyangInstituteofElectro-opticalEquipmentofAVIC,Luoyang471023,China)

無人機(jī)(UnmannedAerialVehicle,UAV)因其作戰(zhàn)半徑大、續(xù)航能力強、速度快、高隱身、高機(jī)動、零人員傷亡等優(yōu)勢，將替代有人飛機(jī)在枯燥、惡劣、危險環(huán)境中執(zhí)行如防空壓制、大范圍搜索和摧毀、縱深打擊、電子攻擊、情報偵察監(jiān)視等各種作戰(zhàn)任務(wù)[1]。如此復(fù)雜的作戰(zhàn)任務(wù)，往往需要多架飛機(jī)互相協(xié)作與配合，共同完成。將這些復(fù)雜作戰(zhàn)任務(wù)(mission)分解成一系列UAV能夠理解和直接執(zhí)行的子任務(wù)(task)(后文統(tǒng)稱為任務(wù))，并為每架UAV分配任務(wù)集合，同時確定這些任務(wù)被執(zhí)行的時序是多UAV協(xié)同任務(wù)分配問題的關(guān)鍵。

多UAV多任務(wù)分配是一類非常復(fù)雜的組合優(yōu)化問題(NP-hard)。相關(guān)文獻(xiàn)中針對這類問題建立的模型包括旅行商問題(TravelingSalesmanProblem,TSP)和車輛路徑問題(VehicleRoutingProblem，VRP)以及這些模型的變體[1]。任務(wù)的時間窗約束是多UAV任務(wù)分配中很常見的一類約束，文獻(xiàn)[2]將多UAV的協(xié)同偵察任務(wù)分配問題抽象為帶時間窗的多旅行商(multi-TSPwithtime-windows,MTSPTW)問題，并利用反射禁忌搜索算法對模型求解；文獻(xiàn)[3]建立了多無人機(jī)任務(wù)規(guī)劃的考慮時間窗約束的車輛路徑問題模型(VRPwithtime-windows，VRPTW)，并采用混合整數(shù)線性規(guī)劃方法求解該問題；文獻(xiàn)[4]針對任務(wù)的時間窗約束，建立了多無人作戰(zhàn)飛機(jī)(UnmannedCombatAerialVehide,UCAV)協(xié)同任務(wù)調(diào)度模型，應(yīng)用粒子群優(yōu)化(ParticleSwarmOptimization，PSO)算法求解。顏驥等在上述研究的基礎(chǔ)上，建立了考慮時間窗約束的多UAV任務(wù)分配模型，利用混合離散離子群(DiscreteParticleSwarmOptimization,DPSO)算法和郭濤算法的改進(jìn)方法求解該問題。

1 時間窗約束的多UAV任務(wù)分配

假設(shè)二維戰(zhàn)場空間內(nèi)Nu無人機(jī)組成的戰(zhàn)斗編隊執(zhí)行Nt任務(wù)集合，任務(wù)分配算法的目的就是找出任務(wù)到無人機(jī)無沖突的匹配使得某項全局收益最大。若每項任務(wù)不被指派給多于一架的無人機(jī)，則說分配是無沖突的。全局目標(biāo)函數(shù)假設(shè)為所有無人機(jī)局部收益值之和，而單架無人機(jī)的局部收益則是指派給該無人機(jī)的任務(wù)的函數(shù)。

1.1 時間窗約束下的任務(wù)收益函數(shù)

UAV每完成一項任務(wù)就會得到收益，記為vij。收益值的大小體現(xiàn)了任務(wù)的重要程度和飛機(jī)執(zhí)行該任務(wù)的能力，vij=Pij×Vj，其中i為飛機(jī)序號，j為任務(wù)序號，Pij∈[0,1]為UAVi執(zhí)行任務(wù)j的成功概率，與飛機(jī)及其掛載的傳感器、武器性能和目標(biāo)相關(guān)；V1,V2,…,VNt為各項任務(wù)的價值，其與任務(wù)的基準(zhǔn)價值和被執(zhí)行時間相關(guān)。為將時間窗約束合并到收益函數(shù)中，文獻(xiàn)[5]給出了任務(wù)有效時間窗的相關(guān)定義：

2)有效時間窗(uj(t))：任務(wù)的有效時間窗指任務(wù)允許開始的時間段。任務(wù)j的有效時間窗定義為：

(1)

基于上述定義，定義無人機(jī)i執(zhí)行任務(wù)j的收益函數(shù)為

(2)

無人機(jī)i執(zhí)行任務(wù)j的時間τij是無人機(jī)到達(dá)任務(wù)j之前任務(wù)執(zhí)行路徑pi的函數(shù)，而無人機(jī)的任務(wù)執(zhí)行路徑又由其任務(wù)集合xi唯一確定。給定任務(wù)集xi∈{?∪J}Li和任務(wù)執(zhí)行路徑(任務(wù)執(zhí)行時序)pi∈{?∪J}Li，τij可計算為

(3)

其中，J?{1,…,Nt}為任務(wù)下標(biāo)集合；pi(n)表示任務(wù)執(zhí)行路徑上的第n項任務(wù)；dj表示任務(wù)j的持續(xù)時間；Δ(a,b)表示無人機(jī)由任務(wù)位置a移動到任務(wù)位置b所耗費的時間；tloci表示任務(wù)i所處的位置;τi0表示無人機(jī)i開始執(zhí)行任務(wù)的當(dāng)前時間。

1.2 UAV任務(wù)執(zhí)行代價函數(shù)

UAV執(zhí)行任務(wù)過程中，會消耗武器、燃油，還會受到來自敵防御系統(tǒng)的反擊，造成各種資源的損耗，統(tǒng)一稱為UAV執(zhí)行任務(wù)時付出的代價。代價的計算不僅與飛機(jī)和任務(wù)本身相關(guān)，還與飛機(jī)執(zhí)行任務(wù)的路徑有關(guān)，如飛行路徑越長，則燃油消耗越大；在敵方雷達(dá)探測區(qū)域內(nèi)暴露的時間越長，則被敵人發(fā)現(xiàn)和摧毀的可能性就越大[4]。因此，單獨計算無人機(jī)i執(zhí)行任務(wù)j付出的代價cij是不切實際的，只能在給定的任務(wù)執(zhí)行序列下計算無人機(jī)總的任務(wù)執(zhí)行代價。為模型表述上的方便，相關(guān)文獻(xiàn)一般采用啟發(fā)式方法計算cij，具體計算方法可借鑒文獻(xiàn)[6-8]。

1.3 時間窗約束下的問題模型

綜上所述，任務(wù)分配問題可用如下整數(shù)規(guī)劃模型(一般為非線性)描述：

(4)

其中，二值決策變量xij為1則無人機(jī)i被指派給任務(wù)j，否則為0；I?{1,…,Nu}，J?{1,…,Nt}分別為無人機(jī)和任務(wù)的下標(biāo)集。約束1為無人機(jī)載荷約束，Li表示無人機(jī)能完成的任務(wù)數(shù)上限；約束2表示各項任務(wù)僅能被一架無人機(jī)執(zhí)行；約束3表示無人機(jī)的任務(wù)執(zhí)行路徑長度不能超過無人機(jī)的最大航程約束Mpi；約束4表示各項任務(wù)至多能被執(zhí)行一次。

若僅從燃油損耗來計算無人機(jī)i執(zhí)行整個分配任務(wù)的代價Ci，則

(5)

由于任務(wù)的時間窗約束很大程度上決定了任務(wù)的收益，在任務(wù)分配之初，決策者只能通過無人機(jī)的有效載荷、最大航程約束和各任務(wù)的執(zhí)行時間，初步確定參加分配的任務(wù)和執(zhí)行任務(wù)的無人機(jī)。因此，并非所有參與分配的任務(wù)必須被執(zhí)行，而是根據(jù)約束情況來執(zhí)行任務(wù)，使得任務(wù)分配的收益最大化。

2 DPSO和郭濤算法

2.1 DPSO算法

PSO算法[9]中每個粒子對應(yīng)一個可行解，具有位置和速度兩個屬性，分別表示當(dāng)前粒子在解空間的位置和移動速度，并以粒子位置向量對應(yīng)的適應(yīng)度函數(shù)值確定粒子的“優(yōu)劣”程度。每個粒子通過下列公式更新自身狀態(tài)：

(6)

目前PSO的研究大多局限在連續(xù)領(lǐng)域，為求解組合優(yōu)化問題，一般采用3種方式對其進(jìn)行離散化處理，稱為離散粒子群算法(DPSO)，各求解方法采取的策略和優(yōu)缺點見文獻(xiàn)[10]，此處不再贅述。

2.2 郭濤算法

郭濤算法[11]是武漢大學(xué)郭濤提出的一種基于序列倒置(Inver-over)算子的優(yōu)化算法(簡稱GT算法)。GT算法通過對種群內(nèi)每個個體的子序列，按照一定的選擇概率進(jìn)行自適應(yīng)的倒置，以此來提高算法的收斂速度。因郭濤算法兼具一元算子(以較小的概率p執(zhí)行同一父體內(nèi)的隨機(jī)倒序)和二元算子(以較大的概率1-p執(zhí)行不同父體間的導(dǎo)向性倒序)的成分，從而使其成為既有強的選擇壓力又有適應(yīng)性算子的演化算法[12]。

由于GT算法是隨機(jī)選擇種群中的個體進(jìn)行學(xué)習(xí)的，當(dāng)前個體并非每次都能學(xué)到有用經(jīng)驗，其學(xué)習(xí)的盲目性，影響了算法的收斂速度[10]。并且，隨著問題規(guī)模的擴(kuò)大，GT算法解的質(zhì)量下降很快[13]。

3 混合DPSO-GT算法的多UAV任務(wù)分配

多UAV多任務(wù)分配是復(fù)雜的組合優(yōu)化問題，受DPSO算法和GT算法思想的啟發(fā)，采用混合DPSO-GT算法求解該問題。

3.1 基本思路與粒子編碼方式

混合算法的基本思路是：在DPSO算法中引入序列倒置算子，該算子在學(xué)習(xí)時不是隨機(jī)選擇學(xué)習(xí)對象，而是按照一定規(guī)律，從具有全局極值的粒子、具有局部極值的粒子子群以及種群中隨機(jī)選擇的粒子；保留GT算法中粒子自身的變異操作(隨機(jī)倒序)，保證種群的多樣性；改進(jìn)GT算法的序列倒置算子，提高算法的收斂速度和精度；單次子序列倒置操作后立即對粒子評價，若新粒子優(yōu)于舊粒子，更新舊粒子。

采用正整數(shù)向量編碼的方式。對每個可能的解，編碼應(yīng)能表示Nt個任務(wù)在Nu架無人機(jī)之間的分配。設(shè)3架無人機(jī)執(zhí)行6項任務(wù)某個可能的解可用路徑序列[14]表示為：

5-0-4-3-6-0-2-1

這表示無人機(jī)1執(zhí)行任務(wù)5，無人機(jī)2依次執(zhí)行任務(wù)4，3和6，無人機(jī)3則依次執(zhí)行任務(wù)2和1。若路徑序列中存在相鄰的兩個0，如

5-2-1-0-0-4-3-6

則表示有一架無人機(jī)(無人機(jī)2)未被分配任務(wù)。

因此，多無人機(jī)多任務(wù)分配問題解的編碼可用Nt+Nu-1維的向量表示。向量每一維對應(yīng)的正整數(shù)表示任務(wù)或任務(wù)分割節(jié)點，該正整數(shù)在向量中所處的維數(shù)則表示其在任務(wù)路徑序列中的位置。不至于引起后文倒置算子的混淆，用大于Nt的整數(shù)表示任務(wù)分割節(jié)點0。如上例3架無人機(jī)6項任務(wù)的任務(wù)路徑序列

5-0-4-3-6-0-2-1

可用編碼表示為：

5-7-4-3-6-8-2-1

3.2 序列倒置算子的改進(jìn)

假設(shè)當(dāng)前粒子s為5-7-4-3-6-8-2-1，圖1為基本序列倒置操作的單次迭代過程：

圖1 基本序列倒置操作單次迭代過程Fig.1 Single iteration of basic inver-over operator

由圖1可知，第一次倒置操作為當(dāng)前解引入了新的邊(3,2)，第二次倒置操作在引入新邊(7,2)的同時卻將上次倒置引入的新邊(3,2)從解中移除。

事實上，基于當(dāng)前種群中各個體所包含的有用信息來指導(dǎo)倒序是郭濤算法成功的關(guān)鍵[12]，為盡量保留這些有用的信息，即倒置操作引入的新邊，采用帶方向的循環(huán)序列倒置[13,15]方法，將粒子的編碼看成一個有方向的虛擬圓環(huán)，編碼中所有的倒置操作均發(fā)生在從c的下一位基因到基因c′的有向子序列中，如圖2所示。

圖2 帶方向的循環(huán)序列倒置操作單次迭代過程Fig.2 Single iteration of inver-over operator considering the direction of the tour

3.3 混合DPSO-GT算法參數(shù)設(shè)置

根據(jù)3.1節(jié)的思路，設(shè)計的混合算法引入3個學(xué)習(xí)選擇概率參數(shù)和1個局部最優(yōu)子群比參數(shù)：p1,p2,p3和rs。局部最優(yōu)子群[10]指由種群中適應(yīng)度較高的部分粒子組成的子群，若種群粒子規(guī)模M=100，rs=0.2，則局部最優(yōu)子群由適應(yīng)度較高的前20個粒子組成。

圖3 粒子學(xué)習(xí)來源及選擇概率區(qū)分Fig.3 Learning resource of particles and selection probability differentiating

如圖3所示，概率p1用于決定當(dāng)前粒子是從自身挑選一個基因進(jìn)行隨機(jī)倒置操作還是從其他粒子中挑選基因進(jìn)行導(dǎo)向性倒序操作；p2和p3則用于區(qū)分當(dāng)前粒子向種群中其他粒子學(xué)習(xí)時，粒子的來源。類似PSO算法中的可變慣性權(quán)重w，概率值p1和p3隨迭代的進(jìn)行逐步減小，如圖3中箭頭所示，其值按式(7)變化

(7)

其中，g為當(dāng)前運行的代數(shù)，Ng為算法設(shè)定的運行代數(shù)。在算法運行初期，p1和p3較大，類似文獻(xiàn)[10]的方法，粒子隨機(jī)倒置操作和向種群中全局最優(yōu)以外的其他粒子學(xué)習(xí)的導(dǎo)向性倒置操作較多，有利于算法跳出局部極小點，便于全局搜索；而到了算法運行后期，則算法類似文獻(xiàn)[12]的快速倒序算法，粒子向種群中其他粒子學(xué)習(xí)的概率和向全局最優(yōu)值學(xué)習(xí)的概率相近，在保持種群多樣性的同時，利用當(dāng)前最優(yōu)解指導(dǎo)倒序，加快算法收斂。概率值p2不變，設(shè)定為0.5。

3.4 適應(yīng)度函數(shù)

算法的適應(yīng)度函數(shù)即為式(4)，通過對粒子的編碼可實現(xiàn)約束2和約束4，對于無人機(jī)任務(wù)能力約束和最大航程約束，采用如下方法：

當(dāng)分配方案(粒子)中某架無人機(jī)的任務(wù)數(shù)超出其能完成最大任務(wù)數(shù)時，算法不再計算方案中后續(xù)任務(wù)給該架無人機(jī)帶來的收益和付出的代價。

當(dāng)分配方案中某架無人機(jī)的任務(wù)數(shù)在其能完成最大任務(wù)數(shù)之內(nèi)時，判斷無人機(jī)的當(dāng)前航程是否超出其最大航程，若是，則將任務(wù)列表中的當(dāng)前及其后續(xù)任務(wù)去除。

3.5 混合DPSO-GT算法描述

混合算法可描述如下：

步驟1 設(shè)置種群大小M、運行總迭代數(shù)Ng、學(xué)習(xí)選擇概率p1～p3、局部最優(yōu)子群比rs。

步驟2 根據(jù)種群大小，按3.1節(jié)的編碼方式隨機(jī)產(chǎn)生粒子并計算其適應(yīng)度值。求每個粒子的Pi，并求出種群的Pg。

步驟3 按式(7)計算p1和p3，根據(jù)rs值確定局部最優(yōu)子群M′。

步驟4 對種群中的每個粒子S，隨機(jī)選擇一個基因c。

步驟6 判斷S的基因c和c′是否相鄰。若相鄰，判斷是否種群中所有粒子都已完成學(xué)習(xí)，如學(xué)習(xí)未完成，轉(zhuǎn)入步驟4；若已完成，轉(zhuǎn)入步驟9。若兩基因不相鄰，則轉(zhuǎn)入步驟7。

步驟7 按3.2節(jié)提供的方法進(jìn)行子序列倒置。單次倒序操作后，按照式(4)、式(5)，立即計算該粒子的適應(yīng)度值，若該值大于序列倒置前適應(yīng)度值，則更新當(dāng)前粒子；否則，不更新當(dāng)前粒子。若更新后該粒子的適應(yīng)度值大于其Pi值，則更新該粒子及其Pi值，否則不更新。同樣，若Pi值大于Pg值，則更新相應(yīng)的Pg值及其對應(yīng)的粒子。

步驟8 令c=c′，轉(zhuǎn)入步驟5。

算法的具體流程如圖4所示。

圖4 混合DPSO-GT算法流程框圖Fig.4 Flow chart of mixed DPSO-GT algorithm

4 仿真算例

4.1 任務(wù)想定

假設(shè)經(jīng)前期作戰(zhàn)，我方由3架具備偵察、監(jiān)視能力的無人機(jī)組成的編隊，欲實施對敵10個目標(biāo)的偵察、監(jiān)視任務(wù)。本節(jié)仿真分析運用混合算法，完成3架無人機(jī)對上述10個目標(biāo)進(jìn)行任務(wù)分配的效果。

仿真場景中，3架無人機(jī)的初始位置，10個任務(wù)的期望開始時間和位置坐標(biāo)在橫坐標(biāo)為(-2km，2.5km)，縱坐標(biāo)為(-1.5km,5.5km)的二維平面內(nèi)隨機(jī)生成；設(shè)偵察監(jiān)視任務(wù)的持續(xù)時間均為10s；采用式(1)～(5)的無人機(jī)任務(wù)分配模型。

表1和表2中的數(shù)據(jù)為某次仿真實驗中的無人機(jī)信息和目標(biāo)信息。假設(shè)目標(biāo)和無人機(jī)在二維平面內(nèi)運動，便于說明問題，假設(shè)任意兩目標(biāo)位置距離遠(yuǎn)大于無人機(jī)最小轉(zhuǎn)彎半徑，無人機(jī)在不同位置間的航行距離為該兩點間的Euclidean距離。

表1 無人機(jī)信息表

表2 目標(biāo)信息表

4.2 任務(wù)分配結(jié)果

基于4.1節(jié)中的想定，設(shè)各架無人機(jī)最大任務(wù)數(shù)為4，使用混合DPSO-GT算法得到任務(wù)分配結(jié)果如圖5、圖6所示。圖5表示各無人機(jī)的任務(wù)分配和任務(wù)執(zhí)行路徑(任務(wù)執(zhí)行順序)，圖6表示各無人機(jī)的任務(wù)計劃表，即任務(wù)的執(zhí)行時間，圖6中粗實線表示任務(wù)實際執(zhí)行時間，細(xì)虛線表示任務(wù)期望執(zhí)行時間。

圖5 時間窗約束下的無人機(jī)任務(wù)路徑Fig.5 UAV paths with time windows

圖6 無人機(jī)計劃時刻表Fig.6 UAV schedules

由圖6可知，運用本算法生成的無人機(jī)任務(wù)計劃表，任務(wù)1比預(yù)計時間推遲7秒執(zhí)行，任務(wù)7因各架無人機(jī)距其較遠(yuǎn)，無法在其有效時間內(nèi)到達(dá)而無法執(zhí)行，其他任務(wù)都按計劃執(zhí)行，取得了很好的規(guī)劃結(jié)果。設(shè)各架無人機(jī)最大任務(wù)數(shù)為2，則規(guī)劃結(jié)果如圖7所示。

圖7 最大任務(wù)數(shù)約束下的無人機(jī)任務(wù)路徑Fig.7 UAV paths with maximum workload constrains

設(shè)各架無人機(jī)最大任務(wù)數(shù)為4，單架無人機(jī)最大航程不超過6km，則規(guī)劃結(jié)果如圖8所示。

圖8 最大航程約束下的無人機(jī)任務(wù)路徑Fig.8 UAV paths with maximum range constrains

4.3 與其他方法的比較

為驗證混合DPSO-GT算法(后文簡稱之為MIDPSO算法)的有效性，將該方法和文獻(xiàn)[4]的DPSO算法、文獻(xiàn)[12]的快速倒序算子(FasterInversionOperator,FIO)、文獻(xiàn)[10]的反序DPSO(Inver-overDPSO,IDPSO)算法對上述想定條件下進(jìn)行100次蒙特卡洛仿真結(jié)果比對，其中種群規(guī)模為40，迭代次數(shù)為100，其他參數(shù)設(shè)置見3.3節(jié)及相關(guān)文獻(xiàn)。

表3為DPSO算法，IDPSO算法，F(xiàn)IO和MIDPSO算法的運行結(jié)果。

表4為其他3種算法獲得與MIDPSO算法同等求解質(zhì)量時，種群大小、迭代次數(shù)、平均運行時間的100次蒙特卡洛仿真統(tǒng)計值。

表3 4種算法同等運行條件下的求解質(zhì)量

表4 4種算法同等求解質(zhì)量下的運行條件

由表3、表4結(jié)果可知，在同等運行條件下，和同等的求解質(zhì)量要求下，MIDPSO算法相比其他算法，在時效性和求解質(zhì)量方面都具有顯著優(yōu)勢。

仿真發(fā)現(xiàn)，MIDPSO算法的運行效率受學(xué)習(xí)選擇概率參數(shù)p1～p3的影響較大，3.3節(jié)對3個參數(shù)的設(shè)置是經(jīng)過多次蒙特卡洛仿真實驗得出的結(jié)果，限于篇幅，不做進(jìn)一步說明。

5 結(jié)論

討論了時間窗約束下的多UAV協(xié)同多任務(wù)分配問題。時間窗的約束，任務(wù)必須在指定的時間范圍內(nèi)完成，建立了時間窗約束下的任務(wù)分配模型；設(shè)計了簡潔的任務(wù)分配編碼方式；提出的混合DPSO-GT算法綜合了離散粒子群算法和郭濤算法的優(yōu)勢，同時又較好地克服它們的缺點。以多無人機(jī)編隊執(zhí)行對敵監(jiān)視偵察任務(wù)為例，說明了該算法的有效性。考慮無人機(jī)航路可飛性約束以及任務(wù)的時序性約束將是課題進(jìn)一步討論的內(nèi)容。

References)

[1] 沈林成，牛軼峰，朱華勇.多無人機(jī)自主協(xié)同控制理論與方法[M].北京：國防工業(yè)出版社,2013:1-20.

SHENLincheng,NIUYifeng,ZHUHuayong.TheoriesandmethodsofautonomouscooperativecontrolformultipleUAVs[M].Beijing:NationalDefenseIndustryPress, 2013: 1-20. (inChinese)

[2]RyanJL,BaileyTG,MooreJT,etal.Reactivetabusearchinunmannedaerialreconnaissancesimulations[C]//ProceedingsofWinterSimulationConference, 1998,1: 873-879. [3]WeinsteinAL,SchumacherC.UAVschedulingviathevehicleroutingproblemwithtimewindows(Preprint)[R].AFRL-VA-WP-TP-2007-306, 2007.

[4] 霍霄華，沈林成. 多UCAV協(xié)同控制中的任務(wù)調(diào)度問題研究[J]. 系統(tǒng)仿真學(xué)報, 2007, 19(16): 3623-3626.

HUOXiaohua,SHENLincheng.Taskschedulinginmulti-UCAVcooperativecontrol[J].JournalofSystemSimulation, 2007, 19(16): 3623-3626. (inChinese)

[5]PondaS,ReddingJ,ChoiHL,etal.Decentralizedplanningforcomplexmissionswithdynamiccommunicationconstraints[C]//Proceedingsof2010AmericanControlConference,Baltimore,MD:AACC, 2010:3998-4003.

[6] 杜繼永，張鳳鳴，楊驥，等. 多UCAV協(xié)同任務(wù)分配模型及粒子群算法求解[J]. 控制與決策, 2012, 27(11): 1751-1755.DUJiyong,ZHANGFengming,YANGJi,etal.CooperativetaskassignmentformultipleUCAVusingparticleswarmoptimization[J].ControlandDecision, 2012, 27(11): 1751-1755. (inChinese)

[7] 邸斌，周銳，丁全心. 多無人機(jī)分布式協(xié)同異構(gòu)任務(wù)分配[J]. 控制與決策, 2013, 28(2): 274-278.

DIBin,ZHOURui,DINGQuanxin.Distributedcoordinatedheterogeneoustaskallocationforunmannedaerialvehicles[J].ControlandDecision, 2013, 28(2): 274-278. (inChinese)

[8] 王婷，符小衛(wèi)，高曉光. 基于改進(jìn)遺傳算法的異構(gòu)多無人機(jī)任務(wù)分配[J]. 火力與指揮控制, 2013, 38(5): 37-41.WANGTing,FUXiaowei,GAOXiaoguang.Cooperativetaskassignmentforimprovedgeneticalgorithm[J].FireControl&CommandControl, 2013, 38(5): 37-41. (inChinese)

[9]KennedyJ,EberhartrC.Particleswarmoptimization[C]//ProceedingsofIEEEInternationalConferenceonNeuralNetwork,USA:IEEE, 1995: 1942-1948．

[10] 鄭東亮，薛云燦，楊啟文，等. 基于Inver-Over算子的改進(jìn)離散粒子群優(yōu)化算法[J].模式識別與人工智能, 2010, 23(1): 97-102.

ZHENGDongliang,XUEYuncan,YANGQiwen,etal.ModifieddiscreteparticleswarmoptimizationalgorithmbasedonInver-Overoperator[J].PatternRecognitionandArtificialIntelligence, 2010,23(1): 97-102. (inChinese)

[11]TaoG，MichalewiczZ．Inver-overoperatorfortheTSP[C]//Proceedingsofthe5thInternationalConferenceonParallelProblemSolvingfromNature, 1998: 803-812．

[12] 閉應(yīng)洲，丁立新，楊小雄. 快速倒序算子的研究[J]. 計算機(jī)工程與應(yīng)用, 2009, 45(4): 45-47.

BIYingzhou,DINGLixin,YANGXiaoxiong.Onfasterinversionoperator[J].ComputerEngineeringandApplications, 2009, 45(4):45-47. (inChinese)

[13]WangYT,SunJ,LiJQ,etal.AmodifiedInver-Overoperatorforthetravelingsalesmanproblem[C]//Proceedingsof7thInternationalConferenceonIntelligentComputing,2012:17-23.

[14]PengY，ZhuHY.ResearchonvehicleroutingproblemwithstochasticdemandandPSO-DPalgorithmwithInver-Overoperator[J].SystemsEngineering-Theory&Practice, 2008, 28(10): 76-81.

[15] 安晶，徐森. 一種結(jié)合粒子群優(yōu)化理論改進(jìn)的郭濤算法及其應(yīng)用[J]. 計算機(jī)應(yīng)用與軟件, 2014, 31(2): 296-299, 320.ANJin,XUSeng.APSOtheoryintegratedimprovedGUOTAOalgorithmanditsapplication[J].ComputerApplicationsandSoftware, 2014, 31(2): 296-299, 320. (inChinese)

Cooperative task allocation of multi-UAVs with mixed DPSO-GT algorithm

YAN Ji1, LI Xiangmin1,2, LIU Bo2

Ageneralmathematicsmodelforcooperativetaskallocationofmulti-UAVswithtimewindowsconstrainswasproposedwhichincorporatingtaskgainsandexecutiontimedirectly,andsimplifingthemodelformulationandalgorithmdesigning.Bydefiningasuitableparticlestructure,analgorithmbasedontheprinciplesofdiscreteparticleswarmoptimizationandGuoTaoalgorithmwasdesigned.TheInver-overOperatorwasdirectedbytheswarm,thelocalandglobaloptimal.Variablelearningselectionprobabilityisintroducedintothealgorithmtoselectthelearningparticles,andtheInver-Overoperatorwasmodified.Simulationverifiestheproposedtaskplanningmethodologyforcomplexmissions.

discreteparticleswarmoptimizationalgorithm;GuoTaoalgorithm;taskallocation;timewindowsofvalidity;multi-UAVs

2014-10-27

航空科學(xué)基金資助項目(20135184008)

顏驥(1984—)，男，湖南湘陰人，博士研究生，E-mail：53072472@qq.com;李相民(通信作者)，男，教授，博士，博士生導(dǎo)師，E-mail：xiangmin_li@163.com

10.11887/j.cn.201504027

http://journal.nudt.edu.cn

TP

A