未知城市環(huán)境下的多機(jī)協(xié)同目標(biāo)搜索方法研究

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

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

0 引 言

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

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

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

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

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

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

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

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

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

1 基本問題描述

1.1 環(huán)境模型

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

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

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

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

1.2 無人機(jī)模型

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

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

(1)

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

(2)

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

圖2 目標(biāo)與無人機(jī)的運(yùn)動(dòng)方向標(biāo)識(shí)Fig.2 Moving direction identification of target and unmanned aerial vehicle

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

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

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

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

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

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

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

(1) 信息共享代價(jià)

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

(3)

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

(4)

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

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

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

(5)

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

(6)

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

F=4F1+F2

(7)

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

圖5 無人機(jī)編隊(duì)的收益與代價(jià)示例Fig.5 Example of revenue and cost of unmanned aerial vehicle formation

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

2.2 約束條件

(1) 安全距離約束

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

(8)

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

(2) 最大運(yùn)動(dòng)位移約束

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

(9)

式中:smax為最大運(yùn)動(dòng)位移。

2.3 模型求解

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

(10)

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

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

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

(11)

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

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

(12)

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

(13)

2.4 算法流程

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

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

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

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

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

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

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

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

3 實(shí)驗(yàn)結(jié)果與分析

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

3.1 實(shí)驗(yàn)參數(shù)設(shè)置

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

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

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

表3 SSA初始參數(shù)

3.2 對(duì)比仿真實(shí)驗(yàn)

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

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

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

圖8 MUCS在3個(gè)不同搜索周期下的無人機(jī)運(yùn)動(dòng)軌跡Fig.8 Unmanned aerial vehicle motion trajectories of MUCS under three different search cycles

圖9 MUCS在3個(gè)不同搜索周期下的目標(biāo)運(yùn)動(dòng)軌跡Fig.9 Target motion trajectories of MUCS under three different search cycles

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

圖11 SSA在3個(gè)不同搜索周期下的無人機(jī)運(yùn)動(dòng)軌跡Fig.11 Unmanned aerial vehicle motion trajectories of SSA under three different search cycles

圖12 SSA在3個(gè)不同搜索周期下的目標(biāo)運(yùn)動(dòng)軌跡Fig.12 Target motion trajectories of SSA under three different search cycles

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

圖14 DPM在3個(gè)不同搜索周期下的無人機(jī)運(yùn)動(dòng)軌跡Fig.14 Unmanned aerial vehicle motion trajectories of DPM under three different search cycles

圖15 DPM在3個(gè)不同搜索周期下的目標(biāo)運(yùn)動(dòng)軌跡Fig.15 Target motion trajectories of DPM under three different search cycles

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

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

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

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

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

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

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

表5 3種方法的定量對(duì)比

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

3.3 主要參數(shù)分析

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

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

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

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

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

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

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

(2) 無人機(jī)探測(cè)范圍對(duì)搜索結(jié)果的影響

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

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

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

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

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

4 結(jié)束語(yǔ)

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

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