未知城市環境下的多機協同目標搜索方法研究

劉大千, 包衛東, 費博雯, 朱曉敏

(國防科技大學系統工程學院, 湖南 長沙 410073)

0 引 言

隨著智能無人技術的快速發展,具有便攜、成本低、機動性強等特點的無人機備受關注,其已被成功應用于智能交通、農業灌溉和戰場偵察等應用領域[1-3]。特別是在智能交通領域,以城市環境為背景的多無人機協同組織與優化成為學者研究的熱點問題之一,在行人監控、車輛跟蹤和道路管理中起著關鍵作用[4]。因此,本文從城市建模角度出發,主要研究多無人機協同目標搜索問題。

目前,多無人機協同目標搜索主要集中于靜態路徑規劃和動態路徑規劃兩個方面,其中動態路徑規劃又可分為分布概率預測和群智能決策兩類方法,并在近些年涌現出了許多優秀的研究成果。在靜態路徑規劃方面,Nielsen等[5]針對搜索區域邊界復雜且區域包含多個障礙物的問題,提出一種凸分解方法,該方法可以有效提高區域覆蓋搜索的效率。謝朋志等[6]將搜索區域進行等面積劃分,并利用人工勢場法計算各無人機的飛行路徑。戴健等[7]將多機協同搜索問題轉化為子區域上的單機搜索問題,實現了對指定區域的快速搜索。Wu等[8]設計了一種基于連續檢測策略的無人機緊急路徑規劃算法,使無人機能夠飛到指定區域并完成對該區域的完全覆蓋。在此基礎上,他們還將無人機協同路徑規劃問題轉化為大規模的0-1優化問題[9],并利用混合智能算法求解該問題,從而提高了搜索任務的執行效率。然而,實際城市環境存在動態變化,上述方法雖然能夠有效解決靜態環境中無人機編隊協同搜索效率低的問題,但難以應對動態環境所帶來的突發情況,具有一定的應用局限性。

在分布概率預測方面,Yu等[10]提出基于概率分布的目標搜索方法。劉重等[11]在此基礎上建立了包含建筑信息的數字信息素地圖(digital pheromone map, DPM),用于對搜索區域環境的感知。肖東等[12]在DPM的基礎上設計了調度信息素,提高了多無人機的協同搜索能力。Tang等[13]提出一種基于矢量信息素的目標搜索方法,通過信息共享對當前時刻的DPM進行實時更新,從而實現了更加高效、準確的目標搜索。黃杰等[14]在目標分布概率圖的基礎上引入標志位,并利用遺傳算法進行優化求解,實驗結果表明該方法在保證多無人機飛行路徑可行的前提下可提升目標搜索的效率。Liu等[15]提出一種基于回訪機制的協同搜索覆蓋算法,通過限定信息素傳播與揮發系數達到較高的搜索效率,然而建立全局概率圖的時效性依賴于城市區域的大小,難以滿足實際應用需求,易造成目標逃離和搜索周期較長等問題。

在群智能決策方面,Yao等[16]針對城市環境下的目標搜索與跟蹤問題進行建模,并利用改進的灰狼算法(improved grey wolf algorithm, IGWA)進行優化求解,從而為無人機編隊規劃出更加準確的飛行路徑。Carabaza等[17]提出一種基于蟻群優化(ant colony optimization, ACO)的無人機編隊搜索方法。與此同時,作者團隊還設計了一個基于最短時間搜索的優化機制,使得ACO能夠快速獲得高質量的水平直線分段無人機飛行軌跡。為了解決未知目標搜索問題,Purbolingga等[18]利用信息素修正ACO算法搜索方式,提高了算法的搜索效率。Zhen等[19]利用人工勢場和ACO相結合的方法,提出一種基于人工勢場和ACO相結合的無人機群協同任務規劃方案,建立了包含4種動目標運動模型的環境概率地圖,并通過改進ACO算法實現了多無人機的實時動態決策,在不確定動態環境中得到了較好的搜索結果。在粒子群優化(particle swarm optimization, PSO)方面,Yang等[20]提出一種擴展PSO方法,利用非完整模型更新機器人群的前進速度和旋轉速度,以實現運動控制。Saadaoui等[21]提出一種基于局部PSO的多無人機協同搜索(multi-unmanned aerial vehicle cooperative search, MUCS)優化方法,并利用貝葉斯理論進行更新,從而提高了MUCS的效率。然而,這些優化方法受搜索環境影響較大,易陷入局部最優解,導致無人機編隊聚集在某一區域搜索,降低多機協同的目標搜索準確率。

綜上所述,現有的研究方法在靜態路徑規劃和動態路徑規劃方面均取得了較好的搜索結果。然而,在實際城市環境中,仍然存在以下問題亟待解決:① 由于無人機視野范圍的限制,易因城市區域過大而導致目標難以發現,致使編隊搜索執行周期較長;② 面對目標運動狀態多樣的問題,特別是在未知城市環境中,現有的協同編隊策略無法滿足搜索區域的均勻覆蓋,易造成目標遺漏問題。針對上述問題,本文提出了面向未知城市環境的MUCS方法。具體而言,面對未知城市環境,無法提前獲知建筑物、障礙物以及地形地貌信息,充分考慮無人機編隊間的信息共享和區域覆蓋能力,建立基于共享代價和覆蓋收益雙重指標的協同搜索模型。在此基礎上,引入編隊安全距離和移動位移約束條件,確保協同模型的實用性和穩定性。為了得到協同模型的優化解,充分發揮群智能算法在優化求解上的收斂速度優勢,改進原有麻雀搜索算法(sparrow search algorithm,SSA)的計算模式。同時,為了發揮無人機的靈活性,本文設定無人機進行變速飛行,以滿足目標的動態變化,從而提高多機協同搜索能力。

本文的創新之處如下:

(1) 提出面向未知城市環境的MUCS,旨在解決目標遺漏和搜索周期較長的問題;

(2) 在模型的構建中,設計基于共享代價和覆蓋收益的雙重指標,確保無人機編隊的協同搜索能力和區域覆蓋能力;

(3) 在模型求解過程中提出改進的SSA,從而提升協同搜索模型的時效性。

1 基本問題描述

1.1 環境模型

本文以城市環境為背景,利用N架無人機組成編隊對未知城市區域Ω進行目標搜索,設定該區域中包含M個運動目標。為了增加目標搜索任務的挑戰性,設置多個建筑物、障礙物等不可達區域,并參照文獻[22]設置3類不同運動狀態的目標供無人機編隊搜索,隨機初始化各個目標的運動類型。

為了便于描述目標搜索過程,本文對搜索區域Ω進行柵格化等分處理,區域Ω的柵格化地圖如圖1所示。

圖1 區域Ω的柵格化地圖Fig.1 Rasterized map of region Ω

該區域的長和寬分別為L和W,單位為m,每個柵格的大小為Δl×Δw。設定每架無人機均等高飛行,且搭載的目標檢測攝像頭均垂直向下。與此同時,為了保證無人機能夠準確識別目標,本文設定各架無人機的飛行高度為Δl,其對應的檢測范圍為“九宮格”,即以無人機在地面的投影為中心,以一個柵格長度為半徑畫圓,與之有交集的柵格即為當前時刻該架無人機的檢測范圍,認定在此范圍內目標能夠被精準發現。

1.2 無人機模型

假設每一時刻同一柵格最多只存在1個目標,每架無人機利用機載攝像頭對區域中的各柵格進行飛行搜索,其行進軌跡由轉彎半徑和速度所共同決定[23],即

UAVi(t)=[xi(t),yi(t),hi(t)]

(1)

式中:xi(t),yi(t)表示第t時刻第i架無人機在區域Ω中的位置坐標;hi(t)表示航行方向。在基于柵格化的路徑規劃過程中,本文將無人機在相鄰時刻的航行方向設置為八鏈碼方向,其表示如圖2所示。具體為:(0) 向前;(1) 向右45°;(2) 向右90°;(3) 向右135°;(4) 向后;(5) 向左135°;(6) 向左90°;(7) 向左45°。無人機模型的具體表達式為

(2)

式中:v為無人機飛行速度;θ為航行角,θ∈[-180°,-135°,-90°,45°,0°,45°,90°,135°]。

圖2 目標與無人機的運動方向標識Fig.2 Moving direction identification of target and unmanned aerial vehicle

需要指出的是,在基于柵格化的路徑規劃過程中,目標僅能在道路上運動,不能穿過建筑物和不可達區域,將目標在相鄰時刻的行進方向表示為如圖2所示。 具體標號為:(0) 向前;(1) 向右90°;(2) 向后;(3) 向左90°。

2 多機協同目標搜索建模

協同搜索目標要求無人機編隊在盡可能少的時間內找出區域Ω中的所有目標,本文假設當目標處于無人機視覺的觀察范圍內時,即認定無人機已經能夠捕獲目標[24]。針對單無人機搜索性能差、執行周期較長的問題,提出一種多無人機協同優化模型,以提高多無人機的協同搜索能力,MUCS的整體架構如圖3所示。圖3中,藍色長方體為建筑物,白色矩形框為不可達區域。

圖3 MUCS的整體架構Fig.3 Overall architecture of the MUCS

具體協同搜索過程如下:① 設計目標函數。本文旨在解決目標遺漏和搜索周期較長問題,因此將編隊信息共享代價和區域覆蓋收益定義為目標函數,以提高無人機編隊搜索能力;② 編隊約束。在編隊飛行過程中,安全飛行距離和最大運動位移是兩個最重要的約束條件,決定著協同模型的實用性和穩定性;③ 優化模型求解。基于上述目標函數和約束條件,建立協同編隊優化模型,并在求解過程中,設計改進的SSA進行優化解算,提高模型的時效性。

2.1 目標函數

綜合考慮無人機信息共享能力和編隊區域覆蓋能力,本文將信息共享代價和區域覆蓋收益作為目標函數,將代價和收益定義為兩個雙曲正切函數,計算無人機編隊的最優搜索解,這兩種函數的具體描述如下。

(1) 信息共享代價

為了保證實時共享搜索信息,無人機編隊應盡可能地向區域中央進行收縮,以滿足信息傳輸距離的要求。設單無人機的信息共享代價函數為

(3)

式中:f1為雙曲正切函數,用于將無人機與區域中心的距離進行歸一化操作(距離范圍為[0,1]的值),其函數的圖像如圖4(a)所示;d表示無人機與指定區域中心的距離;dmax表示最大通信距離;Δd表示緩沖距離,其取值范圍為[0,1]。因此,無人機編隊的信息共享代價函數為

(4)

式中:di表示第i架無人機與區域中心的距離。

(2) 區域覆蓋收益

為了確保發現城市區域中的所有目標,無人機應盡可能地向區域邊緣進行擴張,以使多無人機能夠均勻分布在城市區域的各個角落,從而提高編隊搜索的成功率。設單無人機的區域覆蓋收益函數為

(5)

式中:f2同樣為雙曲正切函數,其函數的圖像如圖4(b)所示;d′表示無人機與指定區域邊緣的距離,dmin表示最小安全距離。因此,無人機編隊的區域覆蓋收益函數為

(6)

從圖4可以看出,信息共享代價與區域覆蓋收益之間的取值恰好相反。信息共享是將編隊之間的距離最小化,而區域覆蓋是將編隊之間的距離最大化。本文設計的目標函數旨在保證收益與代價之間達到平衡,既能夠保證編隊的通信能力,同時還能夠保證無人機均勻分布在城市區域中,因此多無人機協同優化模型的目標函數為

F=4F1+F2

(7)

圖4 雙曲正切函數的示例Fig.4 Examples of hyperbolic tangent functions

圖5 無人機編隊的收益與代價示例Fig.5 Example of revenue and cost of unmanned aerial vehicle formation

為了進一步說明信息共享代價與區域覆蓋收益之間的關系,圖5展示了多無人機編隊協同搜索的收益與代價。圖5中,綠色框表示覆蓋收益區域,分布在城市區域的四周;紫色框表示信息共享代價區域,分布在城市區域中心;藍色框便是城市建筑物。在式(7)中,由于在區域覆蓋收益函數F2中已經計算了4個邊界點區域的區域覆蓋收益,為了保證通信良好條件下,無人機搜索路徑在城市區域中均勻分布并達到良好的搜索效率,將目標函數中F1的權重設置為4,平衡信息共享代價和區域覆蓋收益。無人機根據自身位移向收益或代價區域移動,達到向中心收縮或向邊界點擴張的平衡,從而完成目標搜索任務。

2.2 約束條件

(1) 安全距離約束

在無人機編隊搜索過程中,為了避免發生碰撞,對無人機之間的距離進行要求是十分必要的[25-26]。為了簡化對無人機編隊的安全距離統計的描述,將編隊中的無人機進行數字標號,并按升序依次計算兩架無人機之間的距離,具體計算公式如下:

(8)

式中:dmin為常數,表示最小安全距離。

(2) 最大運動位移約束

在實際的搜索應用中,無人機的速度應受到限制,以避免在遇到突發情況時發生無人機因慣性導致無法及時避障的情況,進而造成機身受損。由于在實驗中設定的目標運動軌跡未知,無人機需要進行變速運動,因此本文對最大運動位移進行限制,具體表達式為

(9)

式中:smax為最大運動位移。

2.3 模型求解

在多機協同搜索過程中,本文建立基于共享代價和覆蓋收益雙重指標的優化模型,具體表達式為

(10)

為了滿足優化模型求解的時效性,引入群智能算法進行迭代優化,群智能算法已被證明適用于許多實際問題,因此,本文選用最新的SSA對式(10)進行求解。SSA是一種非常有效的智能優化算法,它根據麻雀覓食并逃避其他捕食者的行為而提出,且具有尋優能力強、收斂速度快等優點[27-28]。麻雀是群居動物,其捕食(優化)過程主要包含3個步驟:① 發現者搜索食物;② 跟隨者爭奪食物;③ 邊緣個體發現其他獵食者并發出警報。

為了使SSA適用于本文提出的優化模型,對SSA中的3個步驟進行改進,具體數學描述如下。

(1) 發現者:選擇50%初始函數F最大的個體作為發現者,其位置更新方式為

(11)

式中:t為當前迭代數;I為一個1×dim的單位矩陣,dim為求解維度;Q為服從正態分布的隨機數;Si,j是第i個麻雀在第j維空間中的位置。

(2) 追隨者:將剩余的另50%個體作為追隨者,其位置更新方式為

(12)

(3) 警戒者:在麻雀搜索食物的同時,它們中的部分會負責警戒,當其他獵食者靠近時,它們會放棄當前的食物,移動到一個新的位置。從種群中隨機選擇N/4個個體進行警戒,其位置更新公式如下:

(13)

2.4 算法流程

本文利用群智能算法對建立的協同模型進行優化求解,從而獲得無人機編隊的最優搜索位置,MUCS的主要流程如圖6所示。

圖6 協同目標搜索流程Fig.6 Process of collaborative target search

MUCS的主要步驟可描述如下:

步驟 1設置無人機初始飛行參數和SSA的初始參數。初始飛行參數包括初始位置、速度范圍以及初始航向角等參數。此外,SSA參數包括迭代次數t、維度dim以及候選樣本數量n等參數。

步驟 2計算各無人機的備選路徑點。結合各無人機的實時位置與八鏈碼方向關系,確定下一時刻的候選位置坐標,輸入SSA。

步驟 3在SSA中,首先利用式(7)計算各無人機的目標函數(適應性函數),并按降序排列,從而選出當前時刻無人機編隊中的發現者、追隨者以及警戒者。

步驟 4分別利用式(11)～式(13)更新發現者、追隨者以及警戒者的位置,判斷是否滿足迭代優化條件。若滿足條件,則執行步驟5;反之,則繼續執行此步驟。

步驟 5將輸出結果與建筑物坐標進行對比,若二者存在重合或包含關系,則證明不滿足搜索要求;反之,則輸出當前時刻無人機編隊的最優搜索位置。

3 實驗結果與分析

在MUCS中,無人機飛行參數、目標的初始參數和SSA的參數是十分重要的組成部分,因此本節首先對這些參數進行說明。為了說明MUCS的先進性,本節設計了其與現有方法的對比實驗,從定性和定量角度分析說明了所提協同優化模型的有效性。

3.1 實驗參數設置

城市區域Ω的實際面積大小為3 050 m×3 050 m,本文利用柵格進行等比例劃分,形成61×61個柵格,即柵格的Δl和Δw均為50 m。在該城市區域中,為了增加目標搜索任務的復雜性,共設置了42個建筑物,每個建筑物占用9個柵格(實際面積為22 500 m2),其中還包含了密集建筑群,以更好地模擬城市環境,并利用12架無人機組成編隊,對區域Ω進行目標搜索,目標數量設置為9個運動目標,無人機間的最大通信距離dmax為25個柵格,最小安全距離dmin為0.5個柵格,無人機和目標的初始運動狀態設置分別如表1和表2所示。此外,SSA的主要初始參數設置如表3所示。

表1 無人機初始狀態

表2 目標初始狀態

表3 SSA初始參數

3.2 對比仿真實驗

為了驗證MUCS的有效性,本節主要將其與較為流行的兩類群優化算法,即文獻[12]的DPM和文獻[27]的SSA進行仿真實驗對比,主要評定指標包含搜索時間周期、發現目標數以及區域覆蓋率[29-31]。兩個方法的具體細節描述為:DPM為典型的數字信息素優化算法,加入調度信息素,并在分布式模型預測控制框架下對其進行優化求解,從而完成目標搜索任務。SSA則為最新群智能算法的代表,在優化求解中模仿麻雀的捕食策略,從而提高目標搜索的準確率。

MUCS、SSA與DPM這3種方法在不同搜索周期下的無人機編隊飛行路徑如圖7所示,其中彩色點為各無人機的搜索飛行軌跡點,藍色長方體表示城市中的密集建筑物,白色框為城市規劃區域。從圖7可以看出,3種方法均能夠較好地完成目標搜索任務,無人機編隊分布在城市區域的各個角落,但無法比較3種方法的編隊性能。因此,為了能夠清晰展示無人機編隊的搜索路徑,本節的飛行路徑圖均為二維平面圖,3種方法在不同搜索周期下的飛行路徑及目標運動路徑分別如圖8～圖16所示。需要指出的是,無人機能夠在高空飛過城市規劃區域(白色框),但目標無法進入此區域,僅能在道路上運動,而無人機和目標均不能穿行密集建筑物。

圖7 3種方法在400個周期下的3D飛行路徑Fig.7 3D flight paths of three methods under 400 search cycles

圖8 MUCS在3個不同搜索周期下的無人機運動軌跡Fig.8 Unmanned aerial vehicle motion trajectories of MUCS under three different search cycles

圖9 MUCS在3個不同搜索周期下的目標運動軌跡Fig.9 Target motion trajectories of MUCS under three different search cycles

圖10 MUCS在3個不同搜索周期下的機間距離Fig.10 Distances between unmanned aerial vehicles of MUCS under three different search cycles

圖11 SSA在3個不同搜索周期下的無人機運動軌跡Fig.11 Unmanned aerial vehicle motion trajectories of SSA under three different search cycles

圖12 SSA在3個不同搜索周期下的目標運動軌跡Fig.12 Target motion trajectories of SSA under three different search cycles

圖13 SSA在3個不同搜索周期下的機間距離Fig.13 Distances between unmanned aerial vehicles of SSA under three different search cycles

圖14 DPM在3個不同搜索周期下的無人機運動軌跡Fig.14 Unmanned aerial vehicle motion trajectories of DPM under three different search cycles

圖15 DPM在3個不同搜索周期下的目標運動軌跡Fig.15 Target motion trajectories of DPM under three different search cycles

圖16 DPM在3個不同搜索周期下的機間距離Fig.16 Distances between unmanned aerial vehicles of DPM under three different search cycles

從圖8、圖11和圖14的無人機運動軌跡可以看出,群智能算法的迭代優化更加合理,執行目標函數更為理想,在整個市區中無人機編隊分布得更加均勻。無人機和目標的初始運動狀態如表1和表2所示。MUCS和SSA在城市環境中呈現出“區域式”的分布,更加體現了區域覆蓋式搜索的群智能性,具體表現為搜索區域覆蓋更加均勻、密集,且無人機之間很少有重復的搜索路徑。雖然在較短周期內無人機的覆蓋范圍更小,但隨著搜索的不斷深入,群智能性逐漸體現,這對于運動目標搜索而言是十分有利的,能夠較好地完成目標搜索任務。DPM利用信息素的釋放和稀釋進行全局圖更新,能夠保證無人機編隊均勻分布在城市的各個角落,具有較高的區域覆蓋率,對于靜態目標的搜索而言是十分有利的,因此其全局搜索能力更強,區域覆蓋率更大。然而,本文主要面向動態目標搜索任務,由于目標位置發生實時變化,若僅要求區域全覆蓋是無法滿足搜索要求的,因為目標可能在下一時刻出現在無人機已搜索過的區域中,造成目標遺漏現象。

從圖9、圖12和圖15的目標運動軌跡可以看出,MUCS和SSA能夠快速捕獲目標,致使目標的運動軌跡更少,而DMP的運動目標在較長時間周期下才能發現,導致目標的運動軌跡更長,這進一步說明了群智能算法的區域搜索能力。表4顯示了3種方法在400個搜索周期下的發現目標位置坐標,其單位為柵格。其中,“-”表示未發現此目標,表4清晰記錄了3種方法搜索到的目標位置,MUCS能捕獲所有目標,而SSA則能夠發現8個目標,遺漏了3號目標T3。DMP僅發現了7個目標,未能捕獲2號目標和8號目標。

另一方面,圖10、圖13和圖16的機間距離記錄了3種方法在搜索過程中的無人機間的最大距離和最小距離,其中MUCS和SSA能夠較好地利用群優化算法限制機間距離,從而更好地避免了無人機路徑存在無人機之間距離大于dmax情況的發生。然而,DMP假設全局通信,并沒有對機間距離進行限制,因此該方法的機間距離較大,最大可達到82個柵格,這種情況再一次證明了基于群智能算法的協同編隊的有效性。

表4 3種方法在400個周期下的發現目標位置

與群智能算法SSA相比,本文提出的MUCS的搜索性能更好,區域覆蓋率更高,搜索路徑規劃更為合理。從圖8和圖11中的無人機運動軌跡比較可以看出,MUCS能夠更好地發揮編隊優勢,各無人機之間連通性更強,而SSA在400個周期后仍存在大面積未探測區域,搜索效果不理想。這種現象說明了本文利用改進的群智能算法進行模型求解的優勢,具有較強的尋優能力。使用該方法時,無論是在區域的邊界還是在城市中心,均有搜索無人機的出現,且運動位移較大。

為了能夠更加清晰地對比3種方法的性能,分別從搜索周期、發現目標數以及路徑覆蓋率3方面進行定量分析,對比結果如表5所示。需要指出的是,為了體現實驗的公平性,本文對3種方法分別進行了10次獨立運行,并取平均結果作為最終的數據統計結果。

表5 3種方法的定量對比

在表5中,當搜索周期同為100時,3種方法的區域覆蓋率相當,均保持在20%左右。但DPM的搜索結果更優,能夠發現4個目標,這說明采用數字信息素圖進行目標搜索在較短的周期內是十分有效的。而當搜索周期達到200時,3種方法的發現目標數均為6個,而MUCS的區域覆蓋率為42.57%,SSA的覆蓋率為41.53%,DPM最低,僅為39.36%,這也進一步體現了群智能算法的目標搜索能力。在增加100個搜索周期的情況下,發現目標數增加了4個,相比之下,信息素圖方法僅增加了2個,且區域覆蓋率最低。隨著搜索任務的不斷深入,從發現目標數方面的對比不難看出,MUCS在400 s時即可找出全部9個目標,且區域覆蓋率達到73.58%。而SSA在400 s時能夠找出8個目標,DPM在400 s時僅能發現7個目標,且區域覆蓋率僅能夠達到61.09%。因此,無論是在相同周期下的發現目標數,還是在區域覆蓋率上,MUCS均具有一定的優勢,這進一步證明了本文所提改進群智能搜索策略的有效性。

3.3 主要參數分析

在組織無人機編隊進行目標搜索的過程中,無人機數量和機載攝像頭的探測范圍為目標搜索任務中的重要一環,直接決定著搜索任務的成敗。因此,本文分別對這兩個參數進行實驗分析,說明所提協同優化方法的有效性。

(1) 無人機數量對搜索結果的影響

在本節實驗中,設定目標的數量及運動狀態不變,目標數量固定為9個,運動狀態如表2所示。為了說明對目標搜索結果的影響,在無人機初始狀態方面,本文仍采用均勻分布在四周的策略進行實驗,即設定無人機數量分別為4、8、12、16架。為了得到更加可靠的對比結果,將每組實驗分別運行10次,并取10次實驗的平均值作為最終的統計結果,MUCS在400個周期下的搜索結果如圖17所示。

圖17 MUCS在400個周期下的搜索結果Fig.17 Search results of MUCS in 400 cycles

從圖17可以看出,區域覆蓋面積隨無人機數量的不斷增加而變大。當N=16時,MUCS在400個搜索周期下的區域覆蓋率達到78.93%,且能夠找到區域中的所有目標,這表明多無人機協同目標搜索的群體智能性。同時,當N=8時,MUCS在400個搜索周期下能夠找出8個目標。特別地,該方法在400個搜索周期下能夠找出全部的9個目標,這說明了本文所提協同優化模型的有效性。

為了更加清晰地說明無人機數量對搜索結果的影響,表6統計了MUCS在不同周期下的發現目標數和區域覆蓋率。表6中,在N=4的情況下,MUCS在400個搜索周期下的區域覆蓋率可達到49.84%,占城市區域的50%,發現目標數為4;當N=8時,MUCS在400個周期下的區域覆蓋率為67.31%,發現目標數為8;而當N=12時,MUCS僅在400個周期下區域覆蓋率即可達到73.58%,即可發現所有目標,這說明無人機數量對目標搜索結果有著重要的影響。無人機數量越多,目標搜索的時間周期越短,區域覆蓋率越高。

表6 MUCS在不同周期下的搜索結果

(2) 無人機探測范圍對搜索結果的影響

無人機探測范圍是無人機協同目標搜索的前提,是發現目標的重要保障。本節同樣選取9個運動目標、12架無人機組成編隊進行實驗,它們的具體狀態描述如表1和表2所示。為了深入分析無人機探測范圍對搜索結果的影響,本節設定不同的探測范圍:① 探測半徑r為1個柵格,即只有當無人機與目標位置重合時,才視為發現目標;② 設定探測半徑為2個網格,即各架無人機探測范圍為9個柵格;③ 設定探測半徑為3個網格,即各架無人機探測范圍為25個柵格。為了得到更準確的結果,同樣將每組實驗分別運行10次,并取10次實驗的平均值作為最終的統計結果,本節僅統計在200個搜索周期下的搜索結果,如圖18所示。

圖18 不同探測半徑下的搜索結果Fig.18 Search results under different detection radius

從圖18可以看出,隨著探測半徑的增大,發現目標數也在不斷增加,最大為9個,但區域覆蓋面積卻隨著半徑的增大而略有減小。這是因為當探測半徑較大時,目標則會被快速發現,待區域中的所有目標均被找到后,編隊中的無人機將停留在原地或在小范圍內重復飛行,因此區域覆蓋率略有下降。在此基礎上,表7列出了3個探測半徑下的不同周期的搜索結果。

表7 MUCS在不同探測半徑下的搜索結果

在表7中,當搜索周期t為50時,3種探測半徑的區域覆蓋率相當,但發現目標數卻相差較大。當探測半徑為3時,MUCS能夠發現8個運動目標;當探測半徑為2時,MUCS在100個周期下能夠找到9個目標,且區域覆蓋率僅為21.28%,與探測半徑為3的搜索結果相當。需要指出的是,MUCS在半徑為2時僅在100個周期內已經能夠找出全部目標,故而本節并未列出400～600個搜索周期下進行的實驗。因此,通過上述定性和定量分析能夠得到以下結論:當搜索周期較小時,探測半徑越大,發現目標數越多;當搜索周期較大時,探測半徑將不再具有優勢,甚至在區域覆蓋率上略有降低。

4 結束語

本文針對未知城市環境下多機協同目標搜索問題展開研究,提出了基于群智能優化的搜索模型,構建了基于信息共享代價和區域覆蓋收益雙重指標的協同目標搜索函數。同時,為了增加城市環境的復雜度,本文在城市區域中設定了許多密集建筑物,并設計了3類不同運動狀態的目標,使其均勻分布在該區域,從而保證了目標的多樣性。在模型求解過程中,為了滿足目標搜索的時效性,提出改進的麻雀搜索算法進行優化求解,保證每架無人機均能夠得到最優路徑可行解。實驗結果表明,與當前流行的搜索方法相比,本文提出的MUCS在相同搜索周期的約束下,在區域覆蓋率和發現目標數方面均具備較大優勢,在保證目標搜索成功率的同時,增強了對未知城市環境的區域覆蓋能力。

目前,多無人機協同編隊所面臨的另一個難點問題是通信鏈路不穩定問題。在未來的工作中,將從模型的性能出發,重點考慮如何解決無人機之間的局部通信鏈路和搜索環境動態變化等問題,使得設計的協同模型仍能夠在復雜城市環境中完成目標搜索任務。