分布式多AUV協(xié)同搜索方法

高永琪, 馬威強(qiáng), 張林森, 王 鵬, 趙 苗

(海軍工程大學(xué)兵器工程學(xué)院, 湖北 武漢 430033)

0 引 言

自主式水下航行器(autonomous underwater vehicle, AUV)是一種能在水下自主航行的智能化裝置,具有成本低、隱蔽性強(qiáng)、活動(dòng)受限小等優(yōu)點(diǎn)。當(dāng)前,AUV的航速、續(xù)航力、通信質(zhì)量、導(dǎo)航和控制能力等都在逐步提高,未來能更多地執(zhí)行掃雷、攻擊、情報(bào)搜集、偵察監(jiān)視等軍事任務(wù)。單一AUV作業(yè)往往會(huì)因?yàn)楣收稀⑼獠客{等導(dǎo)致任務(wù)失敗,而多AUV協(xié)同作業(yè)可以通過配合、補(bǔ)位,降低單一AUV失效的影響,從而提高作業(yè)效率。

當(dāng)前,協(xié)同作業(yè)是AUV研究的一個(gè)熱點(diǎn),如協(xié)同定位、協(xié)同搜索、協(xié)同作戰(zhàn)等,亦常以AUV集群為對(duì)象,開展任務(wù)規(guī)劃、編隊(duì)控制、路徑跟蹤、集群穩(wěn)定性等以協(xié)同作業(yè)為目的的研究。

AUV還可以與無人水面艇(unmanned surface vehicle,USV)組成異構(gòu)協(xié)同系統(tǒng)發(fā)揮更大作用,如海底資源探測(cè)。為此,有學(xué)者研究了USV對(duì)AUV路徑的跟蹤算法以及異構(gòu)協(xié)同系統(tǒng)的通信與導(dǎo)航。日本已陸續(xù)在研制與AUV協(xié)同的USV,如日本國(guó)家海洋研究所研制的半潛式USV和日本海洋地球科學(xué)與技術(shù)署的MAINAMI型USV。AUV異構(gòu)協(xié)同也是AUV發(fā)展的一個(gè)重要方向。

搜索是AUV的核心任務(wù)之一,成功搜索到目標(biāo)是執(zhí)行相關(guān)任務(wù)的前提,協(xié)同搜索是國(guó)內(nèi)外多智能體協(xié)同控制領(lǐng)域的一個(gè)研究熱點(diǎn)。

常見的協(xié)同搜索方法有遍歷掃描式搜索、分區(qū)域覆蓋搜索、概率圖引導(dǎo)搜索等。傳統(tǒng)遍歷式掃描容易因目標(biāo)運(yùn)動(dòng)、傳感器失誤等原因造成搜索失敗,常常要求智能體短時(shí)間內(nèi)迂回,而AUV機(jī)動(dòng)性能差,難以滿足要求。

分區(qū)域覆蓋搜索通過合理分配區(qū)域,將多機(jī)覆蓋搜索問題轉(zhuǎn)化為單機(jī)覆蓋搜索問題,文獻(xiàn)[21-23]所述應(yīng)用Voronoi圖對(duì)搜索區(qū)域進(jìn)行分割,該方法被普遍采用,但這種分割復(fù)雜,并且?guī)в胁淮_定性,對(duì)智能體的自主性要求也較高。

概率圖模型可以有效描述任務(wù)環(huán)境信息,反映任務(wù)環(huán)境變化。黃杰等人根據(jù)環(huán)境的先驗(yàn)信息,在原概率圖基礎(chǔ)上引入標(biāo)志位,建立基于雙屬性矩陣的待搜索環(huán)境概率模型,提高環(huán)境和目標(biāo)的信息感知準(zhǔn)確度,但該方法使用集中式協(xié)同結(jié)構(gòu),需要優(yōu)化的決策變量往往是高維的,求解難度大,優(yōu)化時(shí)間長(zhǎng)。彭輝等人提出一種分布式模型預(yù)測(cè)控制的多無人機(jī)協(xié)同搜索模型,采用基于納什最優(yōu)和粒子群優(yōu)化算法進(jìn)行求解,極大地降低求解維度,但無人機(jī)之間需要進(jìn)行多次信息交換才能實(shí)現(xiàn)納什最優(yōu),對(duì)通信有很高要求,實(shí)際中往往無法滿足,具有現(xiàn)實(shí)局限性。張哲璇等人提出一種重訪機(jī)制驅(qū)動(dòng)的協(xié)同搜索規(guī)劃方法,重返可疑區(qū)域,降低由傳感器性能不足造成誤判的影響,但該方法未考慮通信約束,也有現(xiàn)實(shí)局限性。

本文針對(duì)水下存在通信延時(shí)和協(xié)同過程中單AUV易失效的問題,提出一種通信實(shí)時(shí)性需求低、魯棒性強(qiáng)的協(xié)同搜索算法。通過構(gòu)造人工勢(shì)場(chǎng)避免AUV碰撞與資源浪費(fèi),采用改進(jìn)后的頭腦風(fēng)暴優(yōu)化(brain storm optimization, BSO)算法確保多AUV在協(xié)同搜索時(shí)能在短時(shí)間內(nèi)做出最優(yōu)決策。

1 問題描述

針對(duì)任務(wù)區(qū)域內(nèi)存在的個(gè)靜止目標(biāo),如沉底水雷、海底應(yīng)答器、海底預(yù)置武器等,通過某些手段獲取目標(biāo)先驗(yàn)信息(比如分析區(qū)域水文信息、地形信息判斷這些靜態(tài)目標(biāo)更有可能布放在何處等),但這些信息可能存在一定誤差,因此需要指派個(gè)AUV進(jìn)入任務(wù)區(qū)域,利用攜帶傳感器進(jìn)行具體搜索以獲得目標(biāo)信息。

對(duì)任務(wù)區(qū)域進(jìn)行柵格化,每個(gè)柵格長(zhǎng)寬均為一個(gè)單位長(zhǎng)度,任務(wù)區(qū)域由×個(gè)柵格組成。假設(shè)每個(gè)柵格內(nèi)最多只能有一個(gè)目標(biāo),AUV通過傳感器可確認(rèn)所在柵格有無目標(biāo)。

目前,大部分AUV搭載有先進(jìn)的偵察探測(cè)裝備,如前視聲吶、高分辨率側(cè)掃聲吶及先進(jìn)攝像裝備等。其中部分國(guó)家采用的干涉型合成孔徑聲吶和立體搜索聲吶,具有很高的分辨率,但是這些傳感器仍然可能誤判,具有一定探測(cè)概率和虛警概率。

圖1 AUV運(yùn)動(dòng)方向示意圖Fig.1 Schematic of AUV movement directions

但實(shí)際上,AUV具有機(jī)動(dòng)約束,存在最大偏航角增量和最小偏航角增量。本文為表征機(jī)動(dòng)約束,限制AUV運(yùn)動(dòng)方向?yàn)椤白蠛?、直航、右航?種狀態(tài),偏航角增量分別用“-1、0、1”表示。+1時(shí)刻的偏航角通過取模運(yùn)算獲得,計(jì)算公式如下所示:

(1)

式中: Mod(·)為求余運(yùn)算。

一組偏航角增量可以表征一條搜索路徑,如初始偏航角為0,決策偏航角增量為[1,1,-1,1,0,-1]所表示的搜索路徑如圖2所示。

圖2 搜索路徑示意圖Fig.2 Schematic of search path

2 搜索模型

2.1 目標(biāo)存在概率圖

概率圖中柵格(,)的數(shù)值表征目標(biāo)在該柵格可能存在的概率。先驗(yàn)信息中最有可能出現(xiàn)目標(biāo)的位置為((),()),=1,2,…,。但其周邊也可能存在目標(biāo),因此以((),())作為峰值中心,利用高斯分布函數(shù)表示其附近區(qū)域的初始概率,如下所示:

(2)

式中:表示位置((),())的目標(biāo)存在概率,即高斯分布的峰值;為高斯分布的方差。

當(dāng)AUV航行至柵格(,)時(shí),目標(biāo)尋找概率根據(jù)貝葉斯準(zhǔn)則更新,具體如下。

AUV在第時(shí)刻探測(cè)到目標(biāo),目標(biāo)尋找概率更新如下：

(3)

式中:為探測(cè)概率，表征柵格中有目標(biāo)且AUV成功探測(cè)到目標(biāo)的概率；為虛警概率，表征柵格中無目標(biāo)但AUV探測(cè)到目標(biāo)的概率。

AUV在第時(shí)刻未探測(cè)到目標(biāo),目標(biāo)尋找概率,更新如下所示:

(4)

AUV在搜索過程中,用傳感器探測(cè)柵格中是否有目標(biāo),并及時(shí)更新目標(biāo)存在概率圖,當(dāng)柵格內(nèi)概率大于閾值時(shí),認(rèn)為該柵格存在目標(biāo),并將該柵格的概率置零,以避免吸引AUV再次前往搜索。

2.2 環(huán)境不確定度圖

環(huán)境不確定度()∈[0,1]表示AUV對(duì)柵格(,)中環(huán)境信息的掌握情況,其中()=1表示AUV對(duì)環(huán)境信息完全不確定,()=0表示AUV對(duì)環(huán)境信息完全確定。初始不確定度根據(jù)目標(biāo)存在概率確定,計(jì)算公式如下:

=1-(-ln()-(1-)ln(1-))

(5)

隨著AUV對(duì)柵格的不斷探測(cè),其對(duì)柵格環(huán)境的掌握愈發(fā)清晰,環(huán)境不確定度不斷變小,具體更新如下:

(6)

式中:∈[0,1]為環(huán)境不確定度遞減因子。

2.3 協(xié)調(diào)信息素圖

多艘AUV在同一時(shí)刻搜索同一柵格,一方面是對(duì)資源的浪費(fèi),降低了搜索效率;另一方面容易碰撞,破壞了系統(tǒng)結(jié)構(gòu)。本文通過協(xié)調(diào)信息素圖構(gòu)造人工勢(shì)場(chǎng),合理協(xié)調(diào)AUV集群,避免多艘AUV同時(shí)搜索同一柵格。

(7)

柵格的協(xié)調(diào)信息素越多,說明AUV越有可能與其他AUV發(fā)生沖突,前往該柵格會(huì)給協(xié)同過程帶來更大隱患。

3 協(xié)同搜索方法

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

多AUV協(xié)同搜索的目的是盡量掌握整個(gè)任務(wù)區(qū)域信息,盡可能發(fā)現(xiàn)更多目標(biāo)。因此，綜合考慮目標(biāo)存在概率收益、環(huán)境掌握程度收益和協(xié)同代價(jià)制定目標(biāo)函數(shù)。

(1) 目標(biāo)存在概率收益。目標(biāo)存在概率收益是指按照當(dāng)前目標(biāo)存在概率圖,AUV依照搜索路徑航行,所經(jīng)過柵格的目標(biāo)存在概率之和,表征AUV沿著最有可能發(fā)現(xiàn)目標(biāo)的路徑航行。

(8)

式中:是指第個(gè)AUV按照預(yù)測(cè)的搜索路徑航行所經(jīng)過柵格的集合。

(2) 環(huán)境掌握程度收益。環(huán)境掌握程度收益是指按照當(dāng)前環(huán)境不確定圖,AUV按照搜索路徑航行,所經(jīng)過柵格的環(huán)境不確定度之和,表征AUV沿著環(huán)境不確定度最大的路徑航行,盡快降低環(huán)境不確定度,提高對(duì)環(huán)境的掌握程度。

(9)

目標(biāo)存在概率收益與環(huán)境掌握程度收益度量標(biāo)準(zhǔn)不一,實(shí)際計(jì)入目標(biāo)函數(shù)時(shí),需要進(jìn)行歸一化處理。

(10)

基于上述子目標(biāo)函數(shù),目標(biāo)函數(shù)計(jì)算公式如下:

(11)

式中:,,是子目標(biāo)函數(shù)影響系數(shù);為一個(gè)充分大的正數(shù)。

3.2 分布式協(xié)同搜索過程

本文采用滾動(dòng)優(yōu)化策略實(shí)時(shí)產(chǎn)生最優(yōu)搜索路徑,在滾動(dòng)時(shí)域內(nèi)預(yù)測(cè)步,但只執(zhí)行最優(yōu)決策的第一步;采用分布式結(jié)構(gòu),將整個(gè)AUV系統(tǒng)的全局優(yōu)化問題轉(zhuǎn)化為各AUV子系統(tǒng)的局部?jī)?yōu)化問題,減小優(yōu)化規(guī)模、縮短優(yōu)化時(shí)間。

協(xié)同搜索問題實(shí)際上是一個(gè)非線性優(yōu)化問題,可以通過智能優(yōu)化算法進(jìn)行優(yōu)化。本文采取基于全局最優(yōu)和差分變異的頭腦風(fēng)暴優(yōu)化(global-best difference-mutation brain storm optimization, GDBSO)算法優(yōu)化目標(biāo)函數(shù),利用其收斂速度快、優(yōu)化效率高、可靠性較強(qiáng)的優(yōu)點(diǎn),快速得到收益最大、代價(jià)最小的最優(yōu)決策,GDBSO算法主要包括以下幾個(gè)操作步驟。

聚類操作:種群中的個(gè)個(gè)體通過k-means聚類方法分成類,并定義每一類的最優(yōu)個(gè)體為該類的類中心。

取代操作:聚類后,以取代概率產(chǎn)生隨機(jī)個(gè)體取代某一個(gè)類的類中心,防止算法過早地收斂,并有助于算法跳出局部最優(yōu)。

選擇操作:通過4種方法選擇待變異個(gè)體。

按照輪盤賭概率選中一個(gè)類,選擇該類的類中心為待變異個(gè)體;

按照輪盤賭概率選中一個(gè)類,選擇該類中隨機(jī)一個(gè)個(gè)體為待變異個(gè)體;

隨機(jī)選中兩個(gè)類,融合兩個(gè)類的類中心成為待變異個(gè)體;

隨機(jī)選中兩個(gè)類,在兩個(gè)類中各隨機(jī)選出一個(gè)個(gè)體,融合成為待變異個(gè)體。

追隨操作:以追隨概率使得選擇出來的個(gè)體追隨全局最優(yōu)個(gè)體。

變異操作:以差分概率對(duì)待變異個(gè)體進(jìn)行差分變異,否則產(chǎn)生隨機(jī)新個(gè)體作為變異個(gè)體。

分布式多AUV協(xié)同搜索決策算法步驟如下。

根據(jù)先驗(yàn)信息初始化搜索圖。

產(chǎn)生第個(gè)AUV的初始種群,種群為個(gè)個(gè)體,每個(gè)個(gè)體有個(gè)自變量,每個(gè)自變量的取值范圍為-1、0、1。

利用GDBSO算法對(duì)步驟2中的種群進(jìn)行優(yōu)化,對(duì)每一個(gè)選擇、追隨、變異操作產(chǎn)生的個(gè)體進(jìn)行四舍五入取整,若取整后新個(gè)體的自變量不符合條件則重新進(jìn)行選擇、追隨、變異操作。

將當(dāng)前最優(yōu)決策、當(dāng)前探測(cè)情況發(fā)送至其他AUV,執(zhí)行最優(yōu)決策第一步。

判斷是否達(dá)到最大搜索步長(zhǎng),是則結(jié)束,否則轉(zhuǎn)入步驟6。

接收上一決策時(shí)刻其他AUV共享的信息,更新搜索圖,轉(zhuǎn)入步驟2。

AUV之間交互的信息包括最優(yōu)決策與探測(cè)情況,最優(yōu)決策更新環(huán)境不確定度和協(xié)調(diào)信息素,探測(cè)情況更新目標(biāo)存在概率。時(shí)刻探測(cè)當(dāng)前柵格,接收到其他AUV在(-1)時(shí)刻發(fā)出的信息,融合后更新自身搜索圖,以此作出決策,并發(fā)送最優(yōu)決策與探測(cè)情況。AUV決策的實(shí)際依據(jù)為上一步的信息,由此允許通信有一定延時(shí)。

AUV根據(jù)當(dāng)前時(shí)刻各自的搜索圖進(jìn)行優(yōu)化決策,其中協(xié)調(diào)信息素來源于上一時(shí)刻接受的其他AUV的最優(yōu)決策,使得AUV避開可能與其他AUV沖突的柵格。

4 仿真研究

首先,為驗(yàn)證本文提出的協(xié)同搜索算法的有效性,將GDBSO與BSO分別應(yīng)用于決策過程,對(duì)比搜索結(jié)果。其次,改變預(yù)測(cè)步長(zhǎng)、子目標(biāo)函數(shù)影響系數(shù)等參數(shù),分析其對(duì)搜索過程的影響。最后,分析搜索過程中某AUV失效對(duì)整個(gè)AUV集群搜索效能的影響。

為減少偶然性對(duì)仿真結(jié)果的影響,各組仿真均獨(dú)立運(yùn)行50次。計(jì)算機(jī)仿真平臺(tái)為Matlab 2016a,處理器為Intel(R) Core(TM)i5-6200U CPU@2.30 GHz,RAM4GB,操作系統(tǒng)為windows10-64位。

分布式協(xié)同搜索模型參數(shù)如表1所示。

表1 分布式協(xié)同搜索模型參數(shù)

任務(wù)區(qū)域?yàn)?0 km×20 km大小的海域,均勻劃分為20×20的柵格。根據(jù)先驗(yàn)信息,初始目標(biāo)存在概率分布如圖3所示。

圖3 初始目標(biāo)存在概率分布圖Fig.3 Probability distribution diagram of initial target existence

4.1 不同算法比較

使用兩艘AUV搜索50步,每步?jīng)Q策預(yù)測(cè)=8步,AUV的出發(fā)航向均為0。將子目標(biāo)函數(shù)影響系數(shù)設(shè)置為=0.4、=0.4、=0.2,GDBSO算法與BSO算法的參數(shù)設(shè)置參考文獻(xiàn)[31],其中,種群數(shù)量=30,最大迭代次數(shù)=30。

基于GDBSO和BSO決策的分布式多AUV協(xié)同搜索路徑如圖4所示。

圖4 基于不同決策的協(xié)同搜索路徑示意圖Fig.4 Schematics diagram of collaborative search paths based on different decision-making

圖4中,黑色三角形為AUV出發(fā)位置,黑色菱形為實(shí)際目標(biāo)位置,與先驗(yàn)信息中最有可能的位置存在一定差異,紅色區(qū)域?yàn)榻絽^(qū)域。

GDBSO和BSO均有能力在50步內(nèi)成功尋得所有目標(biāo),并且避開禁航區(qū)與避免AUV同時(shí)搜索同一柵格,可見本文提出的分布式協(xié)同搜索方法具有可行性。

GDBSO和BSO各獨(dú)立仿真50次,統(tǒng)計(jì)結(jié)果如表2所示。

表2 不同算法搜索效果比較

GDBSO與BSO相比,尋得目標(biāo)數(shù)量更多、每步?jīng)Q策時(shí)間更短,可見GDBSO在決策方面更有優(yōu)勢(shì)。

4.2 參數(shù)影響分析

設(shè)定預(yù)測(cè)周期=8,取不同的子目標(biāo)函數(shù)影響系數(shù)進(jìn)行仿真,各組均獨(dú)立仿真50次,結(jié)果如表3所示。

表3 子目標(biāo)函數(shù)影響系數(shù)的影響

結(jié)果表明,搜索結(jié)果與子目標(biāo)函數(shù)影響系數(shù)的取值息息相關(guān)。目標(biāo)存在概率收益權(quán)重不斷增大,環(huán)境掌握程度收益權(quán)重不斷減小,尋得目標(biāo)數(shù)量逐漸增大后減小,可見這兩個(gè)權(quán)重處于某種平衡時(shí)能使算法有更好的搜索效果。當(dāng)=04、=04、=0.2時(shí),尋得目標(biāo)數(shù)最多為8.80,說明目標(biāo)存在概率收益權(quán)重等于環(huán)境掌握程度收益權(quán)重時(shí),目標(biāo)函數(shù)引導(dǎo)AUV決策的效果為佳。

設(shè)定子目標(biāo)函數(shù)影響系數(shù)為=04、=04、=02,取不同預(yù)測(cè)周期,各組均獨(dú)立仿真50次,結(jié)果如圖5所示。

圖5 不同預(yù)測(cè)周期的影響Fig.5 Impact of different forecast periods

由圖5(a)可見,預(yù)測(cè)周期過長(zhǎng)或過短都使得搜索效果變差,當(dāng)預(yù)測(cè)周期=8時(shí),搜索效果最佳。預(yù)測(cè)周期過短,AUV沒有充分利用搜索圖信息,不能作出對(duì)未來更有利的決策。預(yù)測(cè)周期變長(zhǎng),優(yōu)化規(guī)模變大,算法求解難度增大,更容易陷入局部最優(yōu),導(dǎo)致搜索效果差強(qiáng)人意。由圖5(b)可見,預(yù)測(cè)周期越長(zhǎng),每步?jīng)Q策時(shí)間越長(zhǎng),但預(yù)測(cè)周期取6～10時(shí)均小于1 s,滿足協(xié)同搜索實(shí)時(shí)性要求。綜上所述,建議設(shè)定預(yù)測(cè)周期=8,既有較好搜索效果,又滿足較短決策時(shí)間。

4.3 AUV數(shù)量變化

為分析AUV數(shù)量對(duì)搜索效果的影響,分別指派2～7艘AUV執(zhí)行協(xié)同搜索任務(wù),每組仿真均獨(dú)立運(yùn)行50次,統(tǒng)計(jì)尋得目標(biāo)數(shù)量如圖6所示。

圖6 AUV數(shù)量變化的影響Fig.6 Impact of number changes of AUVs

當(dāng)AUV數(shù)量少于5艘時(shí),尋得目標(biāo)數(shù)量隨AUV數(shù)量增大而增大,大于5艘后,尋得目標(biāo)數(shù)量基本不變。在任務(wù)區(qū)域與搜索步長(zhǎng)不變的條件下,AUV數(shù)量達(dá)到一定值后,數(shù)量增長(zhǎng)對(duì)搜索效果基本無幫助。AUV數(shù)量為6艘時(shí)的搜索示意圖如圖7所示,在搜索后期,出現(xiàn)柵格被反復(fù)搜索的情況,造成資源浪費(fèi)。因此要根據(jù)實(shí)際情況,指派合適數(shù)量的AUV,提高搜索效率,同時(shí)避免資源浪費(fèi)。

圖7 6艘AUV搜索結(jié)果示意圖Fig.7 Schematic diagram of search result for six AUVs

由于海洋水下環(huán)境復(fù)雜,AUV編隊(duì)在執(zhí)行任務(wù)過程中容易發(fā)生部分AUV失效,為此,指派4艘AUV組成AUV集群執(zhí)行協(xié)同搜索任務(wù),各AUV搜索50步,假設(shè)在20步時(shí)有1艘AUV失效。獨(dú)立運(yùn)行仿真50次,結(jié)果如圖8所示。

圖8 單AUV失效時(shí)搜索結(jié)果示意圖Fig.8 Schematic diagram of search results in case of single AUV failure

由圖6可知,單AUV未失效時(shí)4艘AUV尋得目標(biāo)數(shù)量占實(shí)際總目標(biāo)數(shù)量的95.4%,而由圖8所示,單AUV在途中失效時(shí)該比例為94.8%,僅比未失效低0.6%?？梢?協(xié)同搜索方法魯棒性較好,AUV集群并未因個(gè)別AUV失效而導(dǎo)致整體搜索效果大幅度下降。

5 結(jié) 論

本文針對(duì)水下協(xié)同搜索中通信延時(shí)、單AUV作業(yè)過程中失效的問題,提出一種具有較強(qiáng)實(shí)時(shí)性和魯棒性的分布式協(xié)同搜索方法,用于對(duì)任務(wù)海域的靜態(tài)目標(biāo)完成協(xié)同搜索。該方法利用上一步搜索圖信息進(jìn)行決策,減弱通信實(shí)時(shí)性需求,通過協(xié)調(diào)信息素避免AUV碰撞與資源浪費(fèi),使用GDBSO優(yōu)化目標(biāo)函數(shù),確保AUV短時(shí)間內(nèi)獲得最優(yōu)決策。仿真結(jié)果表明，單個(gè)AUV在協(xié)同搜索過程中失效對(duì)整體搜索效果影響很小,驗(yàn)證了方法的魯棒性。但本文研究的搜索目標(biāo)是靜態(tài)的,實(shí)際任務(wù)中還有動(dòng)態(tài)目標(biāo),協(xié)同搜索靜態(tài)和動(dòng)態(tài)目標(biāo)是下一步研究方向。