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

顏 驥，李相民,，劉 波

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

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

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

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

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

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

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

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

(1.DepartmentofOrdnanceScienceandTechnology,NavalAeronauticalandAstronauticalUniversity,Yantai264001,China；

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

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

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

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

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

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

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

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

(1)

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

(2)

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

(3)

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

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

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

1.3 時(shí)間窗約束下的問(wèn)題模型

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

(4)

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

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

(5)

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

2 DPSO和郭濤算法

2.1 DPSO算法

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

(6)

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

2.2 郭濤算法

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

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

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

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

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

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

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

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

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

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

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

因此，多無(wú)人機(jī)多任務(wù)分配問(wèn)題解的編碼可用Nt+Nu-1維的向量表示。向量每一維對(duì)應(yīng)的正整數(shù)表示任務(wù)或任務(wù)分割節(jié)點(diǎn)，該正整數(shù)在向量中所處的維數(shù)則表示其在任務(wù)路徑序列中的位置。不至于引起后文倒置算子的混淆，用大于Nt的整數(shù)表示任務(wù)分割節(jié)點(diǎn)0。如上例3架無(wú)人機(jī)6項(xiàng)任務(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為基本序列倒置操作的單次迭代過(guò)程：

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

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

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

圖2 帶方向的循環(huán)序列倒置操作單次迭代過(guò)程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è)計(jì)的混合算法引入3個(gè)學(xué)習(xí)選擇概率參數(shù)和1個(gè)局部最優(yōu)子群比參數(shù)：p1,p2,p3和rs。局部最優(yōu)子群[10]指由種群中適應(yīng)度較高的部分粒子組成的子群，若種群粒子規(guī)模M=100，rs=0.2，則局部最優(yōu)子群由適應(yīng)度較高的前20個(gè)粒子組成。

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

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

(7)

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

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

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

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

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

3.5 混合DPSO-GT算法描述

混合算法可描述如下：

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

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

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

步驟4 對(duì)種群中的每個(gè)粒子S，隨機(jī)選擇一個(gè)基因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)，立即計(jì)算該粒子的適應(yīng)度值，若該值大于序列倒置前適應(yīng)度值，則更新當(dāng)前粒子；否則，不更新當(dāng)前粒子。若更新后該粒子的適應(yīng)度值大于其Pi值，則更新該粒子及其Pi值，否則不更新。同樣，若Pi值大于Pg值，則更新相應(yīng)的Pg值及其對(duì)應(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)視能力的無(wú)人機(jī)組成的編隊(duì)，欲實(shí)施對(duì)敵10個(gè)目標(biāo)的偵察、監(jiān)視任務(wù)。本節(jié)仿真分析運(yùn)用混合算法，完成3架無(wú)人機(jī)對(duì)上述10個(gè)目標(biāo)進(jìn)行任務(wù)分配的效果。

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

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

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

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

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

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

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

圖6 無(wú)人機(jī)計(jì)劃時(shí)刻表Fig.6 UAV schedules

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

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

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

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

4.3 與其他方法的比較

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

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

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

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

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

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

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

5 結(jié)論

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

References)

[1] 沈林成，牛軼峰，朱華勇.多無(wú)人機(jī)自主協(xié)同控制理論與方法[M].北京：國(guó)防工業(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)度問(wèn)題研究[J]. 系統(tǒng)仿真學(xué)報(bào), 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] 邸斌，周銳，丁全心. 多無(wú)人機(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)多無(wú)人機(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].模式識(shí)別與人工智能, 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ì)算機(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ì)算機(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é)基金資助項(xiàng)目(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