聯合多核FCM和改進GOA的多無人機協同偵查航跡規劃

靳江鋒，劉 旭

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

1 引言

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

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

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

2 偵查目標聚類分析

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

2.1 多核FCM

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

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

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

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

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

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

(1)

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

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

1)μic計算

2)vc計算

3)D(Ti,vc)計算

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

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

2.2 基于多核FCM的偵查目標聚類分析

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

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

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

(2)

(3)

(4)

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

基于多核FCM的目標聚類偽代碼如下：

輸入：目標集；核函數；GOA初始設置

輸出：目標聚類結果

begin

C←Cmin

whileC≤Cmaxdo //GOA操作

t←1

fort≤Tmaxdo

w←1

forw≤Odo //O為GOA種群個數

根據式(2)～式(4)計算蝗蟲個體目標函數值

執行GOA更新操作

end for

更新種群信息

end for

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

end

C←C+1

end

3 多無人機協同偵查航跡規劃

采用改進的多核FCM對偵查目標聚類分析，得到C個目標子類：

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

3.1 代價函數

選取UAV執行任務消耗時間作為代價函數，對于Uj，執行對Sui的偵查任務，Uj按照一定順序先后完成對Sui內Mi個目標的偵查任務，消耗時間為

設定整體任務時間最小為協同規劃目標函數，并采用IDGOA對UAV航跡進行優化求解，從而得到最佳航跡路線。

3.2 IDGOA優化航跡實現

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

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

(5)

圖1 個體編碼示意圖

更新策略從個體編碼定義可以看出，如果仍采用基本GOA進化更新操作，會產生大量無效解，為此提出自適應交換、自適應學習和突變3種更新策略。

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

圖2 自適應交換操作示意圖

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

其中，χi,min、χi,max為χi最小和最大值，圖3為自適應學習操作示意圖。

圖3 自適應學習操作示意圖

圖4為突變操作示意圖。

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

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

基于IDGOA的多無人機協同偵查航跡規劃實現偽代碼如下：

輸入：無人機參數；目標分類；無人機與目標子類對應關系；IDGOA初始設置

輸出：協同偵查航跡

begin

根據個體編碼定義，對蝗蟲種群進行初始化

t←1

whilet≤Tmaxdo

fori≤PGOAdo //PGOA為種群規模

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

end

更新種群信息

fori≤PGOAdo

對Xi(t)所有編碼片段執行自適應學習操作

end

更新種群信息

if(種群進化停滯) do

對種群最優解執行突變操作

end if

更新種群信息

t←t+1

end while

end

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

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

4 仿真實驗

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

表1 無人機參數設置

表2 改進GOA參數設置

4.1 多核FCM性能驗證

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

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

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

表3 評價指標對比

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

圖5 Nursery數據集下收斂曲線

圖6 人工2數據集下收斂曲線

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

4.2 多無人機協同偵查航跡規劃

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

表4 實驗結果

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

圖7 M=14 IDGOA優化航跡Fig.7 The optimized track results for IDGOA with M=14

圖8 M=25 IDGOA優化航跡

5 結論

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