勾青超,李慶奎
(北京信息科技大學(xué) 自動(dòng)化學(xué)院,北京 100192)
多無人機(jī)協(xié)同[1]在軍事領(lǐng)域和民用領(lǐng)域都具有廣泛的應(yīng)用前景。任務(wù)規(guī)劃是多無人機(jī)協(xié)同任務(wù)的關(guān)鍵技術(shù),是實(shí)現(xiàn)多無人機(jī)協(xié)同完成任務(wù)的指揮系統(tǒng),主要包括任務(wù)分配和航跡規(guī)劃。任務(wù)分配是在考慮多種約束下,對(duì)同類型的無人機(jī)或者是異構(gòu)無人機(jī)進(jìn)行任務(wù)指派,是實(shí)現(xiàn)協(xié)同任務(wù)的核心。
多無人機(jī)任務(wù)分配已經(jīng)成為目前的研究熱點(diǎn),國內(nèi)外學(xué)者開展了相關(guān)的研究工作。文獻(xiàn)[2]用遺傳算法求解異構(gòu)無人機(jī)的多機(jī)協(xié)同任務(wù)分配問題;文獻(xiàn)[3]介紹了合同網(wǎng)方法的提出及發(fā)展;文獻(xiàn)[4]對(duì)一致性包算法(CBBA)進(jìn)行了擴(kuò)展,提出了基于改進(jìn)沖突消解原則的一致性聯(lián)盟算法(CBCA),以實(shí)現(xiàn)異構(gòu)多智能體協(xié)同無沖突任務(wù)分配。智能算法對(duì)于求解任務(wù)分配具有先天的優(yōu)勢(shì),主要包括基于蟻群算法的任務(wù)分配[5]、基于粒子群算法的任務(wù)分配[6-10]、基于遺傳算法的任務(wù)分配[11]等。
目前,任務(wù)分配的算法模型多是基于多目標(biāo)單任務(wù)進(jìn)行的。而實(shí)際上在真實(shí)環(huán)境中無人機(jī)需要通過協(xié)同同時(shí)執(zhí)行多個(gè)任務(wù)。為研究多目標(biāo)多任務(wù)的任務(wù)分配問題,本文將鴿群算法進(jìn)行改進(jìn),并將其離散化,應(yīng)用改進(jìn)后的算法對(duì)多無人機(jī)的協(xié)同任務(wù)分配問題進(jìn)行了求解。鴿群算法[12]具有全局優(yōu)化的特點(diǎn),對(duì)于多約束多目標(biāo)問題具有較大的求解優(yōu)勢(shì)。
假定多無人機(jī)在執(zhí)行廣域搜索攻擊任務(wù)中,任務(wù)區(qū)域已被其他無人機(jī)或者偵察平臺(tái)搜索到Nt個(gè)疑似目標(biāo),需要任務(wù)區(qū)域內(nèi)的多無人機(jī)對(duì)疑似目標(biāo)依次進(jìn)行偵察、攻擊。令發(fā)現(xiàn)的目標(biāo)集合為T={T1,T2,…,TNt},任務(wù)區(qū)域的無人機(jī)有Nv個(gè),其集合為V={V1,V2,…,VNv}。對(duì)每個(gè)目標(biāo)需要執(zhí)行的任務(wù)集合為M={M1,M2,…,MNm}。無人機(jī)的任務(wù)集合為K={K1,K2,…,KNc},Nc為無人機(jī)需要執(zhí)行的任務(wù)總數(shù)量,Nc=Nv×Nm。作戰(zhàn)示意圖如圖1所示。
在示例中,三架無人機(jī)UAV1、UAV2、UAV3執(zhí)行對(duì)target1-target6的攻擊任務(wù),目的是在滿足約束條件的前提下,找到最優(yōu)的任務(wù)分配方法。示例中的求解結(jié)果為UAV1攻擊target1與target2、UAV2攻擊target3與target4、UAV3攻擊target5與target6的路徑代價(jià)最小,即為最優(yōu)的方案。
在任務(wù)分配問題中存在以下約束:
1)任務(wù)時(shí)序約束。多無人機(jī)對(duì)同一目標(biāo)進(jìn)行偵察和攻擊任務(wù)時(shí)具有時(shí)序約束。對(duì)該目標(biāo)的攻擊任務(wù)必須在對(duì)該目標(biāo)的偵察任務(wù)完成之后,即:
TM1 (1) 2)多機(jī)協(xié)同約束。任務(wù)集合中的任何一個(gè)任務(wù)只能被完成一次,即所有無人機(jī)對(duì)同一個(gè)目標(biāo)只能依次進(jìn)行一次偵察和攻擊任務(wù),即: (2) 3)彈藥數(shù)量約束。設(shè)對(duì)多無人機(jī)進(jìn)行任務(wù)分配時(shí),無人機(jī)1當(dāng)前剩余未使用彈藥數(shù)量為M,則無人機(jī) 1執(zhí)行攻擊任務(wù)的次數(shù)必須小于或者等于M。即: (3) 4)任務(wù)時(shí)間約束。定義同一個(gè)目標(biāo)的不同任務(wù)執(zhí)行時(shí)存在時(shí)間間隔,即前一個(gè)任務(wù)完成后需經(jīng)過一個(gè)最小時(shí)間間隔之后才允許執(zhí)行下一個(gè)任務(wù),而且時(shí)間間隔不允許超出最大時(shí)間間隔,即 tM(nt)+Δtmin≤tM(nt+1)≤tM(nt)+Δtmax (4) 該類問題通常選取航程或者航行時(shí)間作為方案決策的重要標(biāo)準(zhǔn)。本文選取所有目標(biāo)被完成后無人機(jī)航行總距離以及時(shí)間作為衡量指標(biāo),認(rèn)為總航程最短的任務(wù)分配方案最優(yōu)。假設(shè)Di為第i架無人機(jī)與目標(biāo)的區(qū)間信息,j為被執(zhí)行任務(wù)的目標(biāo),即第i架無人機(jī)對(duì)所有目標(biāo)的航程代價(jià)為 (5) 最優(yōu)方案為 (6) 鴿群算法是根據(jù)鴿子所特有的導(dǎo)航能力而提出的。將鴿子歸巢行為看作依靠磁場(chǎng)與地標(biāo)的兩階段尋徑。在離巢較遠(yuǎn)距離依賴地磁場(chǎng)確定歸巢大致方向,在靠近鴿巢時(shí),根據(jù)附近熟悉的地標(biāo)建筑鎖定鴿巢位置?;绝澣核惴ㄈ缦隆?/p> 2.1.1 第一階段:依靠磁場(chǎng)尋徑 鴿群在多維搜索空間中,鴿子的位置和速度在每一次迭代中都會(huì)得到更新,更新過程如下: V(t)=V(t-1)×e-Rt+d×(Xgbest-X(t-1)) (7) X(t)=X(t-1)+V(t) (8) 式中:R為磁場(chǎng)因子,R∈{0,1};d為取值范圍在(0,1)的隨機(jī)數(shù);Nc為目前迭代次數(shù);經(jīng)過Nc-1次迭代循環(huán)后,通過比較所有鴿子的位置得到全局最優(yōu)位置Xgbest。當(dāng)該循環(huán)次數(shù)達(dá)到所要求的迭代次數(shù)后,即停止磁場(chǎng)因子階段的迭代,進(jìn)入地標(biāo)算子中繼續(xù)工作。 2.1.2 第二階段:依靠地標(biāo)尋徑 更新地標(biāo)函數(shù)為 (9) X(t)=X(t-1)+d×(X(t)-X(t-1)) (10) 式中f(X(t))為當(dāng)前鴿子的適度值函數(shù),即設(shè)定的目標(biāo)函數(shù)。 舍棄函數(shù)為 (11) 在依靠地標(biāo)尋徑的過程中,每一次迭代后鴿子的數(shù)量都會(huì)減少一半。那些遠(yuǎn)離目的地的鴿子對(duì)地標(biāo)不熟悉,它們將不再有分辨路徑的能力,因而被舍去。Xc是剩余鴿子的中心位置,將被當(dāng)作地標(biāo),即作為飛行的參考方向。 基本鴿群算法流程如圖2所示。 2.2.1 鴿群算法離散化 鴿群算法是針對(duì)連續(xù)函數(shù)提出的智能算法。本文在對(duì)任務(wù)分配問題進(jìn)行求解時(shí),首先對(duì)鴿群算法進(jìn)行離散化處理。具體方式是將鴿群的速度和位置坐標(biāo)離散化,通常用0或1來表示(離散二進(jìn)制),或者自定義整數(shù)數(shù)組來表示。 針對(duì)多無人機(jī)多目標(biāo)任務(wù)的分配問題,本文將目標(biāo)的序列與無人機(jī)的序列進(jìn)行編碼。考慮到多機(jī)協(xié)同約束,即每個(gè)目標(biāo)任務(wù)均只需要一架無人機(jī)完成,所以可擬定確定的目標(biāo)序列,通過隨機(jī)排列無人機(jī)編碼序列,來形成不同的任務(wù)分配方案,分配結(jié)果實(shí)例如圖3所示。 圖3描述的是5個(gè)無人機(jī)針對(duì)8個(gè)目標(biāo)執(zhí)行兩種任務(wù)的一種隨機(jī)編碼序列,圖中數(shù)字即代表第幾個(gè)無人機(jī)去執(zhí)行對(duì)應(yīng)行目標(biāo)的對(duì)應(yīng)列類型任務(wù)。 2.2.2 鴿群算法的改進(jìn) 任務(wù)分配問題難以擬合成一個(gè)連續(xù)函數(shù),而基本鴿群算法針對(duì)離散問題難以處理,本文對(duì)鴿群算法進(jìn)行改進(jìn),改進(jìn)后的模型如下。 1)第一階段,迭代次數(shù)l≤N1時(shí): X=e-R×l×X(l-1)+d×(Xgbest-X(l-1)) (12) 式中Xgbest為當(dāng)前全局最優(yōu)解。 2)第二階段,迭代次數(shù)N1≤l≤(N1+N2)時(shí): X=e-R×l×X(l-1)+rand(Xc-X(l-1)) (13) (14) 標(biāo)準(zhǔn)鴿群算法通過每次剩余鴿群中的中心位置向目標(biāo)靠近來尋優(yōu),容易過早收斂。在進(jìn)行尋優(yōu)搜索時(shí),前期希望算法擁有較強(qiáng)的全局搜索能力,局部搜索能力影響小,后期更希望算法能夠進(jìn)行精確的局部搜索,因此希望局部更新對(duì)算法的影響更大。因此本文對(duì)式中磁場(chǎng)因子R進(jìn)行了重新設(shè)計(jì),使其在迭代過程中呈現(xiàn)非線性衰減的趨勢(shì),避免過早收斂: (15) 式中: (16) 2.2.3 約束處理 為了更好地處理約束,同時(shí)為了規(guī)避在生成任務(wù)分配方案時(shí)出現(xiàn)生成不可能方案(如負(fù)數(shù)或者超出無人機(jī)數(shù)量的數(shù)值)的情況,本文對(duì)任務(wù)分配方案序列進(jìn)行了處理,將單列無人機(jī)編碼數(shù)組轉(zhuǎn)化為目標(biāo)與無人機(jī)對(duì)應(yīng)關(guān)系的連接矩陣,行數(shù)等于目標(biāo)數(shù)目,列數(shù)等于無人機(jī)數(shù)目,用0或1表示,方案的對(duì)應(yīng)關(guān)系轉(zhuǎn)化示例如圖4所示。 對(duì)于連接矩陣L,其取值僅有{0,1},因此,可以生成二進(jìn)制的速度矩陣,利用“與或”邏輯關(guān)系,完成迭代中的迭代結(jié)果離散化。在連接矩陣中,對(duì)以下約束進(jìn)行處理: 1)多機(jī)協(xié)同約束。在連接矩陣中對(duì)應(yīng)每行和為1,即: ∑(A(i),2)=1 (17) 2)彈藥約束。當(dāng)任務(wù)類型為攻擊約束時(shí)(定義任務(wù)類型變量nt,當(dāng)nt=2時(shí)): ∑(A(i),1)≤2 (18) 3)任務(wù)時(shí)序約束。通過定義任務(wù)類型變量nt,取值{1,2},分別對(duì)應(yīng)目標(biāo)的偵察與攻擊任務(wù)。程序通過擴(kuò)展矩陣維數(shù)來解決目標(biāo)的多任務(wù)類型,并依次對(duì)任務(wù)類型進(jìn)行迭代。 4)任務(wù)間隔約束。定義時(shí)間序列組,分別記錄目標(biāo)任務(wù)的完成時(shí)刻Tt與無人機(jī)完成任務(wù)時(shí)刻Tu(前者需要通過后者數(shù)值來計(jì)算),判斷同一目標(biāo)的不同任務(wù)類型完成時(shí)間是否滿足約束條件。 ① 若任務(wù)間隔時(shí)間Δt小于最小間隔時(shí)間Δtmin,則認(rèn)為無人機(jī)通過盤旋來延長飛行時(shí)間,即此段距離認(rèn)為是: D=v×Δtmin (19) ② 若任務(wù)間隔時(shí)間Δt大于最大間隔時(shí)間Δtmax,則通過罰函數(shù)進(jìn)行處罰,定義罰函數(shù)因子PT: F=D+M×PT (20) 式中M是較大值,當(dāng)滿足約束時(shí),PT=0;當(dāng)不滿足約束時(shí),PT=1。 2.2.4 適應(yīng)度函數(shù) 適應(yīng)度函數(shù)的選取直接影響到算法的收斂速度以及能否找到最優(yōu)解。本文通過計(jì)算鴿群中各粒子的適應(yīng)度函數(shù)來判斷個(gè)體適應(yīng)程度。即通過計(jì)算多無人機(jī)完成多目標(biāo)任務(wù)的總航程,來判斷個(gè)體的優(yōu)秀程度,選取航程最短的作為最優(yōu)方案: 1)對(duì)于單任務(wù)類型問題,不需要考慮復(fù)雜的多任務(wù)條件約束,不利用外部信息,僅以適應(yīng)度函數(shù)為依據(jù),利用鴿群中每個(gè)粒子的適應(yīng)度來進(jìn)行搜索,最優(yōu)適應(yīng)度即為任務(wù)分配結(jié)果中粒子的總航程累加結(jié)果。 2)對(duì)于多任務(wù)類型問題,需要考慮到任務(wù)間隔約束。最優(yōu)適應(yīng)度需要比較多種任務(wù)階段適應(yīng)度值的累加結(jié)果得出,并對(duì)不滿足約束的某段航程進(jìn)行處理,即延長或者懲罰。 程序運(yùn)行流程框架如圖5所示。 其中constraints_solve函數(shù)對(duì)迭代后得到的速度矩陣進(jìn)行處理,處理多機(jī)協(xié)同約束和彈藥約束。其思路是: 第一步:對(duì)多于目標(biāo)任務(wù)數(shù)量的坐標(biāo)進(jìn)行隨機(jī)去除(初步滿足多機(jī)協(xié)同約束,總無人機(jī)執(zhí)行任務(wù)數(shù)等于目標(biāo)需要執(zhí)行任務(wù)數(shù))。 第二步:進(jìn)一步處理多機(jī)協(xié)同約束,將和不為1的行中多余的點(diǎn)進(jìn)行轉(zhuǎn)移。首先要搜索行和大于1的行,利用random_choose函數(shù)隨機(jī)選取多余的點(diǎn)(增加了種群多樣性),然后搜索同列中可轉(zhuǎn)移的位置(行和為0的位置),在搜索結(jié)果中隨機(jī)選取轉(zhuǎn)移位置進(jìn)行轉(zhuǎn)移,轉(zhuǎn)移只改變行數(shù),不改變列數(shù)。 第三步:處理彈藥約束。首先搜索列和大于2的列,隨機(jī)選取多余的點(diǎn),然后隨機(jī)選取其他列可轉(zhuǎn)移的位置進(jìn)行轉(zhuǎn)移,轉(zhuǎn)移只改變列數(shù),不改變行數(shù)。 calFitness函數(shù)通過累加各無人機(jī)完成任務(wù)的路程獲得個(gè)體適應(yīng)度值。對(duì)于彈藥數(shù)量大于1的模型,存在單無人機(jī)對(duì)多個(gè)目標(biāo)進(jìn)行攻擊的情況,在此情況下計(jì)算適應(yīng)度時(shí),需要選擇該無人機(jī)攻擊的先后順序,即需要通過比較不同情況的適應(yīng)度高低,選擇較低的方案。 仿真環(huán)境為CPU2.50GHz四核,內(nèi)存8 GB,Matlab R2018b。假設(shè)目標(biāo)數(shù)量8個(gè);執(zhí)行任務(wù)的無人機(jī)數(shù)量為5架;彈藥約束為2發(fā);迭代粒子數(shù)為100;迭代次數(shù)N1=350,N2=150;最小時(shí)間間隔Δtmin=0.25 s,最大時(shí)間間隔Δtmax=1 s。 針對(duì)多目標(biāo)執(zhí)行攻擊任務(wù),隨機(jī)生成目標(biāo)及無人機(jī)位置,相同位置下,將離散鴿群算法與遍歷算法及基于Sigmoid函數(shù)慣性權(quán)重自適應(yīng)調(diào)整的粒子群優(yōu)化算法[13-14]對(duì)比。在目標(biāo)數(shù)量較少的情況下,3種算法的分配結(jié)果一致。遍歷算法的運(yùn)行時(shí)間為27.30 s,粒子群算法的運(yùn)行時(shí)間為7.13 s,離散鴿群算法的運(yùn)行時(shí)間為6.87 s。任務(wù)分配結(jié)果如圖6所示。 目標(biāo)數(shù)量增加到16個(gè),執(zhí)行任務(wù)的無人機(jī)數(shù)量增加到10架,其他條件無變化時(shí),采用粒子群算法與離散鴿群算法的任務(wù)分配結(jié)果如圖7所示。 在目標(biāo)較多的情況下,粒子群算法求解的總路程最小距離為80.75 km,運(yùn)行時(shí)間為13.74 s;離散鴿群算法求解的總路程最小距離為75.01 km,運(yùn)行時(shí)間為11.58 s。可以看出,隨著目標(biāo)數(shù)量增多,離散鴿群算法在尋優(yōu)能力及收斂速度方面有了一定程度的提高。 針對(duì)多目標(biāo)多任務(wù)的情況,初始最優(yōu)分配與離散鴿群算法分配結(jié)果如圖8所示。 多目標(biāo)多任務(wù)的最優(yōu)分配方案如圖9所示。 在多目標(biāo)多任務(wù)的情況下,初始最優(yōu)分配方案的總路程最小距離為352.58 km,運(yùn)行時(shí)間為47.56 s;離散鴿群算法求解的總路程最小距離為162.97 km米,運(yùn)行時(shí)間為23.34 s。從圖8及圖9可以看出,針對(duì)復(fù)雜度很高的多目標(biāo)多任務(wù)問題模型,離散鴿群算法可以快速求出一個(gè)較優(yōu)解。不同任務(wù)類型的無人機(jī)方案分配序列大致相同,這符合實(shí)際情況的判斷(不考慮最小時(shí)間約束和彈藥約束差異的情況下,同一個(gè)目標(biāo)的兩個(gè)任務(wù)必然由同一個(gè)無人機(jī)執(zhí)行完成)。 本文在對(duì)復(fù)雜約束條件進(jìn)行預(yù)處理的基礎(chǔ)上,使用改進(jìn)后的離散鴿群算法對(duì)無人機(jī)的任務(wù)分配問題進(jìn)行求解。仿真結(jié)果表明,改進(jìn)后的離散鴿群算法具有較優(yōu)越的全局尋優(yōu)能力,在收斂速度方面要優(yōu)于粒子群算法,大大優(yōu)于遍歷算法,同時(shí)在處理多目標(biāo)任務(wù)的高復(fù)雜度問題上也有非常好的表現(xiàn)。 但是對(duì)于多約束問題,隨著約束的增加,利用隨機(jī)結(jié)果修正迭代的鴿群算法效率會(huì)大大降低,大量隨機(jī)結(jié)果不符合約束成為無效解,極不利于算法的快速收斂,此時(shí)需要對(duì)每次迭代的數(shù)據(jù)進(jìn)行預(yù)處理,但是多約束問題的約束解耦也存在較大難度,在實(shí)際問題中的應(yīng)用還有待進(jìn)一步研究。1.3 目標(biāo)函數(shù)
2 數(shù)學(xué)模型
2.1 基本鴿群算法
2.2 鴿群算法的離散化與改進(jìn)
3 離散鴿群算法流程
4 仿真分析
5 結(jié)束語