聯(lián)合多核FCM和改進(jìn)GOA的多無人機協(xié)同偵查航跡規(guī)劃

靳江鋒，劉 旭

(中國飛行試驗研究院， 西安 710089)

1 引言

無人機(unmanned aerial vehicles，UAV)憑借成本低、適應(yīng)性強、零傷亡等特點，在民用和軍用領(lǐng)域發(fā)揮著越來越重要的作用[1]。航跡規(guī)劃作為無人機任務(wù)規(guī)劃的核心部分，目前在有效規(guī)避障礙和威脅的飛行航跡研究方面已經(jīng)相當(dāng)成熟，出現(xiàn)了大量靜態(tài)、動態(tài)、二維與三維規(guī)劃算法[2-4]，但是，針對偵查大規(guī)模目標(biāo)多無人機協(xié)同航跡規(guī)劃的研究還相對較少，特別是，面對大規(guī)模協(xié)同航跡規(guī)劃問題，提升偵查效率、突出偵查針對性和有效性是亟需解決的難題。

多無人機協(xié)同偵查航跡規(guī)劃需要考慮的約束條件多且模型復(fù)雜，求解效率直接決定了協(xié)同偵查效率。序列凸優(yōu)化(sequential convex programming，SCP)方法近年來受到關(guān)注[5]，研究表明，SCP具有更強的高維復(fù)雜求解能力，但是存在運算時間長的缺陷[6]。利用群智能優(yōu)化算法較為突出的運算性能，對協(xié)同偵查模型進(jìn)行快速最優(yōu)化求解是當(dāng)前研究的熱點。文獻(xiàn)[7]將改進(jìn)遺傳算法引入到航跡規(guī)劃求解中，提高了航跡規(guī)劃精度。但面對復(fù)雜高維優(yōu)化問題，智能優(yōu)化算法易陷入局部極值和求解精度不高的缺陷需進(jìn)一步研究，這也是本文研究的重點內(nèi)容之一。此外，文獻(xiàn)[8]采用模糊C均值(Fuzzy C-means，F(xiàn)CM)對目標(biāo)進(jìn)行聚類分析，從而得到每架無人機最佳攻擊序列，提高了攻擊的針對性，但是該方法受聚類算法性能的影響較大。文獻(xiàn)[9]綜合考慮任務(wù)時間約束和攻擊約束，集中一體化求解無人機航跡，一定程度提高了協(xié)同航跡規(guī)劃的有效性，但是該方法數(shù)據(jù)處理維度較高，運算效率較低。文獻(xiàn)[10]將多無人機協(xié)同偵察航跡規(guī)劃等效為多旅行商問題，從而得到了可行飛行航跡，但是該方法更適用于小規(guī)模偵查目標(biāo)應(yīng)用場景。

為此，本文從偵查任務(wù)需求出發(fā)，提出一種聯(lián)合多核FCM和改進(jìn)蝗蟲優(yōu)化算法(grasshopper optimization algorithm，GOA)的多無人機協(xié)同偵查航跡規(guī)劃算法：采用改進(jìn)的多核FCM對多類型偵查目標(biāo)進(jìn)行聚類分析，根據(jù)聚類結(jié)果分別派出匹配度更高的無人機執(zhí)行偵查任務(wù)；綜合研判無人機航跡規(guī)劃約束條件，建立基于時間代價的最優(yōu)航跡規(guī)劃目標(biāo)函數(shù)；采用改進(jìn)的GOA對目標(biāo)函數(shù)進(jìn)行求解，通過重新定義蝗蟲編碼和迭代更新方式，進(jìn)而得到每架無人機偵查序列。該方法更側(cè)重于研究新的多無人機協(xié)同偵查模式，以提供更適用于實際應(yīng)用的多無人機協(xié)同偵查航跡規(guī)劃方案。

2 偵查目標(biāo)聚類分析

以多無人機對目標(biāo)執(zhí)行照相偵察任務(wù)為例，設(shè)有N架具備不同偵查能力的無人機，需要對M個目標(biāo)進(jìn)行偵查，第i個目標(biāo)Ti(Tri,Pri,Imi,Coi)相關(guān)信息已知(Tri為威脅度、Pri為優(yōu)先級、Imi為重要程度、Coi為覆蓋面積)。采用模糊聚類技術(shù)對目標(biāo)進(jìn)行聚類分析，以提高目標(biāo)偵查的針對性和任務(wù)完成的可靠性。

2.1 多核FCM

FCM是目前應(yīng)用最為廣泛的模糊聚類算法之一，但是僅適用于樣本均衡的聚類分析場景[11]。為此，部分學(xué)者利用高維映射函數(shù)Φ(Tk)，將傳統(tǒng)FCM的歐式距離轉(zhuǎn)換為高維空間的線性距離，即：

ΦT(Tk)Φ(Tk)-ΦT(Tk)Φ(vi)-Φ(Tk)ΦT(vi)+ΦT(vi)Φ(vi)

當(dāng)ΦT(Tk)Φ(vi)滿足Mercer條件[12]時，不需要知道Φ(Tk)具體形式就可以實現(xiàn)聚類分析，此時稱ΦT(Tk)Φ(vi)為核函數(shù)，而且任何半正定的函數(shù)都可以作為核函數(shù)。

為提升對大規(guī)模且孤立點較多、維度較高數(shù)據(jù)的聚類性能，設(shè)計多核FCM，即采用Q個Φj(Tk)對Tk進(jìn)行高維映射：

Θ(Tk)=η1Φ1(Tk)+…+ηjΦj(Tk)+…+ηQΦQ(Tk)

其中，ηj為權(quán)重系數(shù)，且η1+…+ηQ=1。為便于范數(shù)計算，引入多核矩陣AQ×Q：

(1)

將式(1)代入J(U,V)有：

下面給出μic、vc和D(Ti,vc)計算推導(dǎo)過程：

1)μic計算

2)vc計算

3)D(Ti,vc)計算

(A(Ti)-vc)T(A(Ti)-vc)=

其中，κk(Ti,Ti)為核函數(shù)。從μic、vc和D(Ti,vc)的推導(dǎo)過程可以看出，給定Q個滿足Mercer條件的核函數(shù)就可以實現(xiàn)多核FCM聚類分析。

2.2 基于多核FCM的偵查目標(biāo)聚類分析

多核FCM引入了多個高維映射函數(shù)，提高了復(fù)雜數(shù)據(jù)聚類分析能力，但是仍然存在缺陷：容易陷入局部極值；對初始聚類中心敏感；聚類個數(shù)C需要事先已知。為此將GOA[13]引入到多核FCM迭代聚類過程，即將聚類中心V={v1,…,vC}等效為蝗蟲個體編碼，J(U,V)等效為GOA目標(biāo)函數(shù)，通過GOA不斷迭代進(jìn)化，最終實現(xiàn)聚類分析，可有效克服容易陷入局部極值和對初始聚類中心敏感的缺陷。此時，在每次GOA迭代過程中，vc為某個確定的向量，省略了vc計算過程，故D(Ti,vc)可以簡化為：

D(Ti,vc)=‖A(Ti)-vc‖2=

(A(Ti)-vc)T(A(Ti)-vc)=

(2)

(3)

(4)

為解決C需事先已知的問題，設(shè)置C在[Cmin,Cmax]范圍內(nèi)依次變化，分別執(zhí)行GOA操作，選取使得J(U,V)取值最小時對應(yīng)的聚類個數(shù)為最佳Cbest。

基于多核FCM的目標(biāo)聚類偽代碼如下：

輸入：目標(biāo)集；核函數(shù)；GOA初始設(shè)置

輸出：目標(biāo)聚類結(jié)果

begin

C←Cmin

whileC≤Cmaxdo //GOA操作

t←1

fort≤Tmaxdo

w←1

forw≤Odo //O為GOA種群個數(shù)

根據(jù)式(2)～式(4)計算蝗蟲個體目標(biāo)函數(shù)值

執(zhí)行GOA更新操作

end for

更新種群信息

end for

比對J(U,V)取值，保留最小值及對應(yīng)的聚類個數(shù)

end

C←C+1

end

3 多無人機協(xié)同偵查航跡規(guī)劃

采用改進(jìn)的多核FCM對偵查目標(biāo)聚類分析，得到C個目標(biāo)子類：

根據(jù)子類目標(biāo)屬性，合理派出N架無人機執(zhí)行協(xié)同偵查任務(wù)。為方便問題描述且不失一般性，取N=C，并設(shè)定每個Sui只對應(yīng)一架無人機Uj(1≤j≤C)。為盡可能降低偵查時間、減少無人機損傷和提高偵查成功率，采用改進(jìn)的離散蝗蟲優(yōu)化算法(Improved Discrete GOA,IDGOA)對Uj航跡點進(jìn)行規(guī)劃。

3.1 代價函數(shù)

選取UAV執(zhí)行任務(wù)消耗時間作為代價函數(shù)，對于Uj，執(zhí)行對Sui的偵查任務(wù)，Uj按照一定順序先后完成對Sui內(nèi)Mi個目標(biāo)的偵查任務(wù)，消耗時間為

設(shè)定整體任務(wù)時間最小為協(xié)同規(guī)劃目標(biāo)函數(shù)，并采用IDGOA對UAV航跡進(jìn)行優(yōu)化求解，從而得到最佳航跡路線。

3.2 IDGOA優(yōu)化航跡實現(xiàn)

GOA作為最近被提出的新型智能優(yōu)化算法，在連續(xù)優(yōu)化領(lǐng)域展現(xiàn)出突出的尋優(yōu)性能[14]。為使GOA能夠應(yīng)用于航跡規(guī)劃問題，提出改進(jìn)離散GOA(IDGOA)：重新定義多段式蝗蟲個體編碼，設(shè)計多種進(jìn)化更新策略。

個體編碼對于蝗蟲個體Xi(t)，定義其編碼為

(5)

圖1 個體編碼示意圖

更新策略從個體編碼定義可以看出，如果仍采用基本GOA進(jìn)化更新操作，會產(chǎn)生大量無效解，為此提出自適應(yīng)交換、自適應(yīng)學(xué)習(xí)和突變3種更新策略。

其中，ηi，max、ηi，min為ηi最大和最小值，Tmax為最大迭代次數(shù)。圖2為自適應(yīng)交換操作示意圖。

圖2 自適應(yīng)交換操作示意圖

1<χi,min≤χi≤χi,max≤α

其中，χi,min、χi,max為χi最小和最大值，圖3為自適應(yīng)學(xué)習(xí)操作示意圖。

圖3 自適應(yīng)學(xué)習(xí)操作示意圖

圖4為突變操作示意圖。

圖4 突變操作示意圖Fig.4 The schematic diagram of mutation operation

從上述3種進(jìn)化策略可以看出，隨著迭代次數(shù)不斷增加，蝗蟲個體參與“自適應(yīng)操作”的編碼不斷減少，而從優(yōu)秀個體得到的信息不斷增加，并且采用突變操作，有效擴展算法的收斂空間，提升收斂效率。給出IDGOA個體編碼和更新策略后，將時間代價函數(shù)定義為IDGOA目標(biāo)函數(shù)，通過迭代更新，得到每架無人機航跡點信息，最終得到協(xié)同偵查航跡路線。

基于IDGOA的多無人機協(xié)同偵查航跡規(guī)劃實現(xiàn)偽代碼如下：

輸入：無人機參數(shù)；目標(biāo)分類；無人機與目標(biāo)子類對應(yīng)關(guān)系；IDGOA初始設(shè)置

輸出：協(xié)同偵查航跡

begin

根據(jù)個體編碼定義，對蝗蟲種群進(jìn)行初始化

t←1

whilet≤Tmaxdo

fori≤PGOAdo //PGOA為種群規(guī)模

對Xi(t)所有編碼片段執(zhí)行自適應(yīng)交換操作

end

更新種群信息

fori≤PGOAdo

對Xi(t)所有編碼片段執(zhí)行自適應(yīng)學(xué)習(xí)操作

end

更新種群信息

if(種群進(jìn)化停滯) do

對種群最優(yōu)解執(zhí)行突變操作

end if

更新種群信息

t←t+1

end while

end

計算復(fù)雜度根據(jù)IDGOA實現(xiàn)流程，設(shè)種群初始化計算復(fù)雜度為O(PGOAM)，每次迭代最大計算復(fù)雜度為O((2PGOA+1)M)，可得IDGOA計算復(fù)雜度為

Tmax×O((2PGOA+1)M)+O(PGOAM)≈TmaxO(2PGOAM)

4 仿真實驗

仿真實驗分為兩個部分：多核FCM性能驗證實驗和多無人機協(xié)同偵查航跡規(guī)劃實驗。表1表示了無人機參數(shù)設(shè)置，其中，V為無人機速度、R偵查半徑、(x,y)為空間坐標(biāo)位置。表2表示了改進(jìn)GOA參數(shù)設(shè)置，其中，Q為種群規(guī)模、λ為控制系數(shù)。

表1 無人機參數(shù)設(shè)置

表2 改進(jìn)GOA參數(shù)設(shè)置

4.1 多核FCM性能驗證

采用經(jīng)典的Nursery數(shù)據(jù)集、Adult數(shù)據(jù)集以及人造數(shù)據(jù)集對多核FCM聚類性能進(jìn)行驗證，并選取基本FCM、核主元熵FCM[15]進(jìn)行對比實驗，假定人造數(shù)據(jù)集聚類個數(shù)對3種算法是未知的。每種算法獨立運行30次，對于人造數(shù)據(jù)集，定義聚類評價指標(biāo)EC：

EC反映了不同類之間的離散度，EC取值越小，表明聚類效果越好。表3給出了不同數(shù)據(jù)集下各評價指標(biāo)對比結(jié)果，其中EC,i/EC,j表示FCM、核主元熵FCMEC取值與本文提出多核FCMEC取值的比值。

從表3可以看出：對于數(shù)據(jù)規(guī)模較小的Nursery數(shù)據(jù)集，多核FCM與核主元熵FCM都展現(xiàn)出了很好的聚類性能，聚類正確率都在90%以上，而FCM聚類正確率只有56.6%。對于較大規(guī)模Adult數(shù)據(jù)集，多核FCM聚類效果明顯優(yōu)于核主元熵FCM，聚類正確率提高了約21.1%。對于聚類個數(shù)事先未知的人工數(shù)據(jù)集，核主元熵FCM與FCM幾乎不能實現(xiàn)有效聚類分析，聚類評價指標(biāo)遠(yuǎn)遠(yuǎn)大于多核FCM，而多核FCM都得到了正確聚類個數(shù)，并且具有較小的聚類評價指標(biāo)。由于多核FCM采用多重迭代確定最佳聚類個數(shù)，導(dǎo)致算法運算時間較長，可以采用線下并行計算的方式來提高運行效率。

表3 評價指標(biāo)對比

為了驗證GOA算法收斂性能，選取WOA[16]、SCA[17]等新型智能優(yōu)化算法對多核FCM迭代過程進(jìn)行優(yōu)化。圖5、圖6是在Nursery數(shù)據(jù)集和人工2數(shù)據(jù)集下J(U,V)收斂曲線。

圖5 Nursery數(shù)據(jù)集下收斂曲線

圖6 人工2數(shù)據(jù)集下收斂曲線

從圖5、圖6可以看出：GOA具有較快的收斂速度和收斂精度，表明該算法具有較為突出的全局尋優(yōu)能力。

4.2 多無人機協(xié)同偵查航跡規(guī)劃

對多無人機協(xié)同偵查算例進(jìn)行仿真(無人機、目標(biāo)具體物理參數(shù)參考文獻(xiàn)[2])。分別設(shè)置M=14、M=25，采用多核FCM對目標(biāo)進(jìn)行聚類分析，根據(jù)聚類個數(shù)派出無人機執(zhí)行協(xié)同偵查任務(wù)，利用IDGOA給出航跡信息。IDGOA優(yōu)化航跡規(guī)劃階段實質(zhì)為多旅行商問題，為此采用文獻(xiàn)[18]的改進(jìn)分組遺傳算法、文獻(xiàn)[19-20]的新混合遺傳算法進(jìn)行對比實驗。表4給出了實驗結(jié)果，圖7、圖8給出了不同M值的IDGOA優(yōu)化航跡結(jié)果。

表4 實驗結(jié)果

從表4可以看出：當(dāng)M=14時，除文獻(xiàn)[16]給出的U3偵查序列不同于其他2種算法外，其余具有相同的規(guī)劃結(jié)果，這表明，對于小規(guī)模規(guī)劃問題，3種算法幾乎具有同樣的規(guī)劃能力。當(dāng)M=25，3種算法僅僅對于U4給出了同樣的偵查序列，而對于U1、U2、U3，IDGOA得到的整體任務(wù)時間明顯優(yōu)于其他2種算法，整體執(zhí)行任務(wù)時間降低了約8.9%～10.7%，這表明，對于同樣的航跡規(guī)劃問題，IDGOA具有更加突出的全局尋優(yōu)能力，收斂精度更高，這是因為自適應(yīng)交換、自適應(yīng)學(xué)習(xí)和突變3種更新策略的引入，進(jìn)一步擴展了算法收斂空間，使得算法能夠有效避免局部最優(yōu)，進(jìn)而得到更好地收斂結(jié)果。

圖7 M=14 IDGOA優(yōu)化航跡Fig.7 The optimized track results for IDGOA with M=14

圖8 M=25 IDGOA優(yōu)化航跡

5 結(jié)論

針對多無人機協(xié)同偵察航跡規(guī)劃問題，提出了一種聯(lián)合多核FCM和GOA的多無人機協(xié)同偵查航跡規(guī)劃算法。該算法將多核FCM引入到航跡規(guī)劃中，通過對目標(biāo)進(jìn)行聚類分析，讓具有更多相似屬性的目標(biāo)聚為一類，為多無人機協(xié)同決策提供了依據(jù)。而且，多核FCM穩(wěn)定高效的聚類能力以及IDGOA復(fù)雜問題突出的優(yōu)化性能，使得算法具有更好的航跡規(guī)劃效率和更低的代價，仿真實驗也分別證實了所提方法的有效性和優(yōu)越性。