應急搜索UAV集群協同任務規劃策略

魯旭濤 智超群 張麗娜 秦英偉 李 靜 王 英

①(中北大學機電工程學院 太原 030051)

②(中北大學信息與通信工程學院 太原 030051)

③(中北大學電氣與控制工程學院 太原 030051)

④(中北大學能源動力工程學院 太原 030051)

1 引言

隨著無人機 (Unmanned Aerial Vehicle， UAV)技術的不斷發展，多UAV協同系統也在不斷進步和完善。相較于單UAV作業，多UAV協同作業容錯性更高，穩定性更強，適合于復雜環境下的作業。隨著多UAV數量的提升，UAV集群的概念應運而生，UAV在應急區域搜索任務或協同作戰任務都有廣泛的應用。

在UAV集群協同區域搜索任務中，相關學者對UAV集群的任務規劃有所研究。文獻[1]針對UAV集群控制復雜度高，設計一種“仿鴻雁自主協同控制方法”。通過鴻雁行為機制，開發了面向UAV平臺的分布式仿生集群系統。文獻[2]將蟻群算法與人工勢場算法結合，避免了3維空間蟻群信息素慣性而導致局部信息忽略的問題，適用于UAV的3維航跡規劃。但UAV航跡實際約束條件較多，航跡規劃一般是多目標動態規劃問題。文獻[3]針對山火火情動態時變特性，通過優化人工蜂群算法，確定UAV山火滅火路徑。但動態時變應用需要及時對滅火路徑進行更新，這對UAV組網的通信模型有較高的需求。

在一些復雜區域搜索難度較高時，對于同樣區域需要進行2～3次覆蓋搜索。則重復性覆蓋搜索過程中，需要對UAV間的空間沖突進行消解。文獻[4]針對復雜地形環境的UAV路徑規劃問題，將“鯨魚算法”加入“灰狼算法”進行優化，通過2維問題的高維處理，將算法目標進行權重劃分，在保證算法收斂速度的同時，提高了整體算法的優解搜索能力。文獻[5]針對灰狼算法收斂速度慢，易陷入局部最優的問題，通過模型離散化處理，使用“A*算法”進行頭狼屬性的初始化，并通過“三次B樣條”方法進行平滑操作，實現UAV航跡規劃。除了空間沖突消解，部分復雜應用中，所需搜索區域內也包含了重點搜索區域和一般搜索區域。

相關學者針對航跡規劃算法也有相關研究。目前對于路徑算法的相關研究均是以最短路徑為單一目標進行尋優，或是在尋優過程中加入各類實際限制條件提升算法尋優的應用性或算法的準確性。文獻[6]采用優化模擬退火算法進行路徑規劃；文獻[7]、文獻[8]和文獻[9]分別對蟻群算法、A*算法和混合粒子群算法進行優化，但算法優化過程均以犧牲算法效率為代價；除了對于算法本身進行優化，同時對于多機協作路徑規劃國內也有一定的研究。文獻[10]、文獻[11]和文獻[12]均在多機協同背景下進行了一種自適應規劃策略；文獻[13]、文獻[14]和文獻[15]則針對實際應用進行了系統針對性優化。

在上述相關研究過程中，多數學者一般以優化算法為目標來達到集群區域搜索的精度、UAV組網的穩定性等參數。或是降低集群控制復雜度，提高網絡拓撲通信能力等。針對多數需要以效率為首要目標的快速搜索策略未有明確的研究。

因此，UAV集群區域搜索任務，應采用以搜索效率為首要目標，結合其他次要目標及約束條件進行數學模型的求解。本文以搜索效率為算法目標，以全覆蓋、搜索精度等為約束條件，通過優化模糊C-均值聚類算法(Optimize Fuzzy C-Means Algorithm，O-FCMA)進行搜索區域模型的劃分，同時結合優化混合粒子群算法(Optimize-Hybrid Particle Swarm Optimization， O-HPSO)在實現高精度、低誤判率條件下，提升區域搜索效率。

2 算法模型建立

2.1 區域環境模型建立

對于具體搜索任務主要包括無線通信搜索、光搜索和熱搜索等。其中無線通信搜索包括雷達搜索、定位系統搜索等；光搜索主要包括可見光搜索、紅外光搜索等；熱搜索主要是熱紅外搜索；本文UAV主要采用雷達搜索、可見光搜索、熱紅外搜索等方法，即近距離無具體坐標，僅有區域范圍條件下進行搜索。

UAV集群在進行區域搜索任務過程中，區域環境模型的建立速度影響搜索效率的高低，模型建立的合適參數將影響搜索精度的水平。對于一般應急區域搜索任務，應用環境的建模往往需要一定的計算能力。本方法中搜索區域模型由控制中心進行模型建立。本文對于區域搜索區域采取蜂窩圖化任務區域方法，如圖1所示。

圖1 區域搜索算法環境模型

蜂窩圖六邊形單位長度的設置取決于UAV的搜索能力。蜂窩圖化任務區域能將整體目標分割，降低計算需求，并且提高計算精度。

2.2 區域全覆蓋模型

對于區域搜索任務，需要UAV搜索時將完整區域全部覆蓋，同時區域全覆蓋模型不考慮重點搜索和回訪，及對于任意區域至少被搜索過1次即可。

各個UAV共同搜索覆蓋的實際面積大于或等于所需要進行覆蓋搜索的區域。

全覆蓋模型在計算時一般會產生連續覆蓋。連續時刻UAV搜索過程中鄰近區域會出現重復搜索的現象。即本文方法中全覆蓋模型不考慮重點搜索及回訪情況，任意需要搜索的區域，只要UAV搜索過1次其區域點即可。

2.3 最快搜索目標函數模型

最快搜索目標函數模型，即為最快實現全局搜索。區域內搜索過程中，UAV集群的最快搜索速度即最快搜索區域與搜索到目標的UAV用時的比值。同一集群內的不同UAV在各自的區域內搜索效率不同。對于不同的搜索區域，即使在兩塊區域面積相同的情況下， UAV搜索所要飛行的路徑長度也有差別。

對于UAV集群指定區域任務規劃為

即各個UAV搜索區域小于指定區域，各個UAV搜索區域總和包含指定區域。

對于單個UAV在指定區域內的最快搜索分為全局最快搜索和局部最快搜索。

局部最快搜索

局部最快搜索即在任意時刻盡可能實現當前時刻內的搜索速度最快。即需要當前搜索重復區域最低，搜索未搜索區域最大。

全局最快搜索

全局最快搜索即在最快的時間內將指定需要搜索的區域全部搜索完成。在本文中，將采用全局最快搜索方法，相較于局部最快搜索方法而言，由于區域內被搜索源具有位置不確定性，局部最快搜索方法對于不確定性可能有時快于全局方法。但也有可能比全局方法慢很多，故采用全局最快搜索方法。

2.4 搜索效率模型

設UAV搜索任務區域共劃分為m個區域。搜索效率模型中，平均搜索效率，即所有UAV共同搜索的范圍與時間的比。

UAV行駛一定距離的時間計算式為

2.5 協同UAV高速通信模型

在UAV集群進行協同任務搜索時，需要實現低延時同步信息共享的多UAV高速通信模型。針對本文中的UAV集群路徑規劃過程，采用無線自組網進行UAV間的協同通信。其通信模型結構圖如圖2所示。

由圖2可知，針對每一個UAV將采用自組網方式進行匯聚-路由-終端結構組網的搭建。而UAV集群的高速通信，首先根據文中FCMA進行區域劃分，其各個聚類中心如圖3所示。

圖2 UAV集群組網結構

圖3 UAV區域聚類中心

各個UAV在自身所需覆蓋區域內均有一個聚類中心，則通過FCMA算法進一步對已有的聚類中心進行優化，得到的結果如圖4所示。其中，紅色實心點即為每個UAV的區域聚類中心，而黑色節點即為所有紅色實心點的聚類中心，依照黑色節點坐標所屬區域，則將區域內的UAV設為通信路由節點，其余設為終端節點。進一步通過各個路由節點取聚類得到整體UAV集群的匯聚節點，其結果圖如圖5所示。其中，紅色實心點所屬區域內的UAV做終端節點，黑色實心點所屬區域內的UAV做路由節點，藍色實心點所屬區域的UAV做匯聚節點。通過此種方法通信實現UAV集群的無線自組網高速通信。

圖4 UAV集群路由節點尋優圖

圖5 UAV集群無線組網節點尋優圖

3 區域搜索任務算法設計

3.1 多UAV搜索區域劃分方法

區域搜索任務劃分主要通過對節點集內各個節點的隸屬度函數，進行指定類別的區域劃分，在本次應用中，通過已知路由-終端UAV組的數量確定區域劃分數量，進一步得到整體區域內合理有效的任務分配。區域任務劃分流程圖如圖6所示。

圖6 O-FCMA流程圖

節點與聚類中心的關系式為

即節點所屬類的最大距離小于UAV搜索的最遠距離。

聚類中心收斂過程為：

不僅是《圣經》還是《佛經》還是諺語，都給紅月賦予了災難的形象。《罪與罰》中沒有大量的敘述，僅用了個“紅月”就將小說境界全然升華，讓所有人都明白阿斯科爾尼科夫的命運，小說以最簡練的情景，用幾個字傳達出了一個貫穿整個小說的線索——阿斯科爾尼科夫正一步步走向災難。

(1)本文主要在原有隸屬度函數基礎上，加入當前節點與其最近節點的歐氏距離作為影響因素，從而使得節點的分類方法具有同類性。優化后的隸屬度函數計算式為

其中，dimin表示距離當前節點最近節點的歐氏距離，σ代表加入最近距離影響因子對隸屬度函數的權重。對于最近節點的篩選方法，不采用當前節點與其他全部節點計算歐氏距離的方法，而是對于區域內全部節點進行X軸、Y軸和Z軸的順序排列，分別計算X軸、Y軸和Z軸距離當前節點最近節點的歐氏距離，最小值取為最近節點與當前節點的歐氏距離。

(2)按照當前類別重新進行當前類別內聚類中心的計算，計算式為

根據區域內各個節點的隸屬度及其坐標值則可以得到最優當前區域內聚類中心節點坐標。

(3)計算當前條件下的目標函數值。目標函數值計算式如式(16)

當目標函數收斂達到一定精度時，即可判斷當前聚類算法滿足終止條件。

3.2 搜索區域蜂窩圖路徑節點規劃

UAV區域搜索原理如圖7，設1和2分別為UAV在固定時刻的最小單位搜索區域，則1時刻和2時刻時，UAV處于的位置即1和2的圓心。

圖7 蜂窩覆蓋原理圖

圖8 蜂窩-節點覆蓋圖

圖中覆蓋6邊形的圓形即為UAV搜索范圍，六邊形構成的蜂窩圖間即為UAV實際運動覆蓋的范圍。而圓形和六邊形的共同中心即為UAV所需要經過的坐標點。

3.3 搜索區域路徑規劃策略

UAV區域搜索路徑規劃模型即在實現傳統路徑規劃問題的基礎上，自適應確定區域搜索過程的路徑轉折節點。

設整體區域內共有n個節點需要UAV應急搜索，則搜索過程的總體距離為

式中，D1表示UAV路徑當前搜索節點與下一搜索點之間的距離和。

式中，Di表示當前節點是各個UAV搜索過程的路徑總和。

單一UAV在搜索指定區域的時間計算式為

式中，v表示UAV行駛速度。

在完成建立對于時間間隔約束的路徑規劃問題的數學模型后，O-HPSO的具體尋優過程流程圖如圖9。

圖9 O-HPSO流程圖

優化預選擇機制的HPSO適應度函數式為

式中主要對粒子實時更新位置與速度做出描述。通過對實際算法尋優過程中的相關常數進行控制，提高尋優結果精度。

O-HPSO中的預選擇機制條件式為

式(23)為O-HPSO中的預選擇機制條件，預選擇機制核心條件即為子代與父代適應度值的優劣比較，同時出現子代適應度值小于父代適應度值的情況下，由于在算法過程中部分個體未能及時顯示優等特性而在當下迭代過程中適應度值較差，則可以通過隨機重新生成一定數量的全新粒子個體，保證整個種群內的個體類型多樣性。

4 實驗及分析

本文在一塊500 m×400 m的不規則平面區域進行仿真實驗。通過本方法將實現搜索任務區域劃分，同時對于各個區域內進行UAV的路徑規劃，完成多UAV條件下最快的區域搜索任務。總體流程圖如圖10所示。

圖10 本方法總體流程圖

4.1 算法參數設置

總體算法中的相關參數設置如表1所示。

表1 總體方法中常數參數數值及說明

4.2 實驗測試

本文實驗分為有源搜索測試、無源搜索測試兩部分，均在500 m×400 m范圍內進行。本文在上述相關參數設置下，使用配置為Intel Core i5-4200U，16 GB運行內存的計算機上，Windows10系統環境下，利用Matlab2017b進行實驗。

4.2.1 有源區域任務搜索測試

有源搜索，即在有固定目標的情況下，UAV集群尋找該搜索源位置的過程。已知被搜索源的具體位置為圖7中的標記點，坐標為(98.45，222.5) m，則UAV集群按照本文所述方法，16架UAV執行區域搜索任務時，搜索路徑規劃圖如圖11所示。

由圖11可得，每種方法中16架無人機最大距離差值為模擬退火算法-K聚類算法的76 m，最小差值為本文算法的48 m。有源任務采用5種算法的對比結果如圖12和表2所示。

圖11 有源搜索本文算法UAV集群路徑圖

圖12 有源搜索5種算法UAV路徑對比圖

由表2可知，在上述有源集群UAV任務搜索的條件下，5種不同方法均滿足ξ，即搜索區域劃分均勻標準。同時本文算法ξ值最小，采用O-FCMA進行任務區域劃分最均勻，實現UAV集群整體搜索效率最大化。

表2 有源搜索對比試驗結果

4.2.2 無源區域任務搜索測試

無源搜索，即常規巡檢，無固定搜索目標，UAV集群需要將所需搜索區域全部覆蓋。本方法得到最終UAV集群路徑規劃如圖13所示。共計16個UAV，5種算法所得到的各個UAV搜索行駛的路徑長度如圖14所示。

圖13 無源搜索本文算法UAV集群路徑圖

圖14 無源搜索5種算法UAV路徑對比圖

可知，在搜索目標過程中，由于不同UAV路徑出現重復區域搜索，不同UAV飛行路徑長度不同。但16架UAV最大距離差值為62 m，占最快搜索UAV總飛行長度的19%。搜索效率為96%。即UAV在指定區域內進行搜索任務時，搜索時間越短，相對搜索效率越高，不同UAV之間飛行差值越小。對比結果如表3。

表3 無源搜索對比試驗結果

4.3 實驗結果分析

由以上結果可得，本文所提方法較其他方法而言，在完成全覆蓋區域條件上，搜索效率最優，且最大與最小飛行距離差最小。

5 結束語

本文通過以多UAV區域任務搜索為背景，首先將所需搜索任務區域進行蜂窩圖處理，將完整區域進行單位六邊形分割，然后將蜂窩圖等效至UAV所必須經過的坐標點。在已知坐標點條件下，采用O-FCMA將任務區域劃分給各個UAV，通過O-HPSO在UAV指定區域內規劃最佳路徑。較其他算法而言，在保證全覆蓋條件下，無源搜索降低了16%～31%的UAV決策時間，提升了3%～7%的搜索效率；有源搜索降低了7%～21%的UAV集群決策時間，提升了7%～13%的搜索效率。