劉大千, 包衛(wèi)東, 費博雯, 朱曉敏

(國防科技大學(xué)系統(tǒng)工程學(xué)院, 湖南 長沙 410073)

0 引 言

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

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

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

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

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

本文的創(chuàng)新之處如下:

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

(2) 在模型的構(gòu)建中,設(shè)計基于共享代價和覆蓋收益的雙重指標(biāo),確保無人機編隊的協(xié)同搜索能力和區(qū)域覆蓋能力;

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

1 基本問題描述

1.1 環(huán)境模型

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

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

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

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

1.2 無人機模型

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

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

(1)

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

(2)

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

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

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

2 多機協(xié)同目標(biāo)搜索建模

協(xié)同搜索目標(biāo)要求無人機編隊在盡可能少的時間內(nèi)找出區(qū)域Ω中的所有目標(biāo),本文假設(shè)當(dāng)目標(biāo)處于無人機視覺的觀察范圍內(nèi)時,即認(rèn)定無人機已經(jīng)能夠捕獲目標(biāo)[24]。針對單無人機搜索性能差、執(zhí)行周期較長的問題,提出一種多無人機協(xié)同優(yōu)化模型,以提高多無人機的協(xié)同搜索能力,MUCS的整體架構(gòu)如圖3所示。圖3中,藍(lán)色長方體為建筑物,白色矩形框為不可達(dá)區(qū)域。

圖3 MUCS的整體架構(gòu)Fig.3 Overall architecture of the MUCS

具體協(xié)同搜索過程如下:① 設(shè)計目標(biāo)函數(shù)。本文旨在解決目標(biāo)遺漏和搜索周期較長問題,因此將編隊信息共享代價和區(qū)域覆蓋收益定義為目標(biāo)函數(shù),以提高無人機編隊搜索能力;② 編隊約束。在編隊飛行過程中,安全飛行距離和最大運動位移是兩個最重要的約束條件,決定著協(xié)同模型的實用性和穩(wěn)定性;③ 優(yōu)化模型求解?；谏鲜瞿繕?biāo)函數(shù)和約束條件,建立協(xié)同編隊優(yōu)化模型,并在求解過程中,設(shè)計改進的SSA進行優(yōu)化解算,提高模型的時效性。

2.1 目標(biāo)函數(shù)

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

(1) 信息共享代價

為了保證實時共享搜索信息,無人機編隊?wèi)?yīng)盡可能地向區(qū)域中央進行收縮,以滿足信息傳輸距離的要求。設(shè)單無人機的信息共享代價函數(shù)為

(3)

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

(4)

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

(2) 區(qū)域覆蓋收益

為了確保發(fā)現(xiàn)城市區(qū)域中的所有目標(biāo),無人機應(yīng)盡可能地向區(qū)域邊緣進行擴張,以使多無人機能夠均勻分布在城市區(qū)域的各個角落,從而提高編隊搜索的成功率。設(shè)單無人機的區(qū)域覆蓋收益函數(shù)為

(5)

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

(6)

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

F=4F1+F2

(7)

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

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

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

2.2 約束條件

(1) 安全距離約束

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

(8)

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

(2) 最大運動位移約束

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

(9)

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

2.3 模型求解

在多機協(xié)同搜索過程中,本文建立基于共享代價和覆蓋收益雙重指標(biāo)的優(yōu)化模型,具體表達(dá)式為

(10)

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

為了使SSA適用于本文提出的優(yōu)化模型,對SSA中的3個步驟進行改進,具體數(shù)學(xué)描述如下。

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

(11)

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

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

(12)

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

(13)

2.4 算法流程

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

圖6 協(xié)同目標(biāo)搜索流程Fig.6 Process of collaborative target search

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

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

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

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

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

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

3 實驗結(jié)果與分析

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

3.1 實驗參數(shù)設(shè)置

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

表1 無人機初始狀態(tài)

表2 目標(biāo)初始狀態(tài)

表3 SSA初始參數(shù)

3.2 對比仿真實驗

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

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

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

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

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

表4 3種方法在400個周期下的發(fā)現(xiàn)目標(biāo)位置

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

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

表5 3種方法的定量對比

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

3.3 主要參數(shù)分析

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

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

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

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

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

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

表6 MUCS在不同周期下的搜索結(jié)果

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

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

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

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

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

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

4 結(jié)束語

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

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