應急搜索UAV集群協(xié)同任務規(guī)劃策略

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

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

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

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

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

1 引言

隨著無人機 (Unmanned Aerial Vehicle， UAV)技術的不斷發(fā)展，多UAV協(xié)同系統(tǒng)也在不斷進步和完善。相較于單UAV作業(yè)，多UAV協(xié)同作業(yè)容錯性更高，穩(wěn)定性更強，適合于復雜環(huán)境下的作業(yè)。隨著多UAV數(shù)量的提升，UAV集群的概念應運而生，UAV在應急區(qū)域搜索任務或協(xié)同作戰(zhàn)任務都有廣泛的應用。

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

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

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

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

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

2 算法模型建立

2.1 區(qū)域環(huán)境模型建立

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

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

圖1 區(qū)域搜索算法環(huán)境模型

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

2.2 區(qū)域全覆蓋模型

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

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

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

2.3 最快搜索目標函數(shù)模型

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

對于UAV集群指定區(qū)域任務規(guī)劃為

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

對于單個UAV在指定區(qū)域內(nèi)的最快搜索分為全局最快搜索和局部最快搜索。

局部最快搜索

局部最快搜索即在任意時刻盡可能實現(xiàn)當前時刻內(nèi)的搜索速度最快。即需要當前搜索重復區(qū)域最低，搜索未搜索區(qū)域最大。

全局最快搜索

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

2.4 搜索效率模型

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

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

2.5 協(xié)同UAV高速通信模型

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

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

圖2 UAV集群組網(wǎng)結(jié)構

圖3 UAV區(qū)域聚類中心

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

圖4 UAV集群路由節(jié)點尋優(yōu)圖

圖5 UAV集群無線組網(wǎng)節(jié)點尋優(yōu)圖

3 區(qū)域搜索任務算法設計

3.1 多UAV搜索區(qū)域劃分方法

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

圖6 O-FCMA流程圖

節(jié)點與聚類中心的關系式為

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

聚類中心收斂過程為：

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

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

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

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

根據(jù)區(qū)域內(nèi)各個節(jié)點的隸屬度及其坐標值則可以得到最優(yōu)當前區(qū)域內(nèi)聚類中心節(jié)點坐標。

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

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

3.2 搜索區(qū)域蜂窩圖路徑節(jié)點規(guī)劃

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

圖7 蜂窩覆蓋原理圖

圖8 蜂窩-節(jié)點覆蓋圖

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

3.3 搜索區(qū)域路徑規(guī)劃策略

UAV區(qū)域搜索路徑規(guī)劃模型即在實現(xiàn)傳統(tǒng)路徑規(guī)劃問題的基礎上，自適應確定區(qū)域搜索過程的路徑轉(zhuǎn)折節(jié)點。

設整體區(qū)域內(nèi)共有n個節(jié)點需要UAV應急搜索，則搜索過程的總體距離為

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

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

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

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

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

圖9 O-HPSO流程圖

優(yōu)化預選擇機制的HPSO適應度函數(shù)式為

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

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

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

4 實驗及分析

本文在一塊500 m×400 m的不規(guī)則平面區(qū)域進行仿真實驗。通過本方法將實現(xiàn)搜索任務區(qū)域劃分，同時對于各個區(qū)域內(nèi)進行UAV的路徑規(guī)劃，完成多UAV條件下最快的區(qū)域搜索任務?？傮w流程圖如圖10所示。

圖10 本方法總體流程圖

4.1 算法參數(shù)設置

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

表1 總體方法中常數(shù)參數(shù)數(shù)值及說明

4.2 實驗測試

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

4.2.1 有源區(qū)域任務搜索測試

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

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

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

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

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

表2 有源搜索對比試驗結(jié)果

4.2.2 無源區(qū)域任務搜索測試

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

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

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

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

表3 無源搜索對比試驗結(jié)果

4.3 實驗結(jié)果分析

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

5 結(jié)束語

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