面向多無人平臺(tái)區(qū)域監(jiān)視任務(wù)的信息素正向激勵(lì)柵格方法

陳亞萍, 王楠, 洪華杰, 劉召陽, 閆響達(dá)

(國防科技大學(xué) 智能科學(xué)學(xué)院, 湖南 長沙 410000)

0 引言

城市作戰(zhàn)是現(xiàn)代戰(zhàn)爭的主要形式之一,也是未來戰(zhàn)爭的重要作戰(zhàn)樣式。城市具有縱橫分布的街巷,高聳、密集而堅(jiān)固的建筑物以及復(fù)雜的地下工程設(shè)施,作戰(zhàn)條件惡劣,因此需要沿街巷或地下工程設(shè)施偵察監(jiān)視。區(qū)域監(jiān)視是對(duì)特定區(qū)域進(jìn)行偵察監(jiān)視以及時(shí)獲取動(dòng)態(tài)環(huán)境信息的一類經(jīng)典問題,例如定期獲取活動(dòng)目標(biāo)的位置信息、地形變化信息或與某些節(jié)點(diǎn)信息交互,其研究對(duì)于城市戰(zhàn)場情報(bào)偵察監(jiān)視具有可觀的軍事意義和應(yīng)用價(jià)值。這類任務(wù)的完成通常需要耗費(fèi)巨大的人力且在特定場合具有一定的危險(xiǎn)性,利用多機(jī)器人系統(tǒng)執(zhí)行該類任務(wù)成為優(yōu)選方案[1]。傳統(tǒng)區(qū)域監(jiān)視通常利用以一定密度布置在區(qū)域中的傳感器網(wǎng)絡(luò)覆蓋整個(gè)任務(wù)空間[2-5],這種靜態(tài)監(jiān)控方法往往存在感應(yīng)范圍固定、有感應(yīng)盲區(qū)、效費(fèi)比等問題。采用多無人平臺(tái)協(xié)同監(jiān)控時(shí),各無人平臺(tái)攜帶傳感器移動(dòng),能動(dòng)態(tài)覆蓋任務(wù)區(qū)域而獲取全局信息,可大大提高效費(fèi)比、提高重點(diǎn)區(qū)域關(guān)注度。

區(qū)域監(jiān)視任務(wù)追求最大訪問頻率以減少兩次訪問之間的時(shí)間差。為最大限度地?cái)U(kuò)大覆蓋范圍,需要不斷訪問地圖中的所有地方,以收集環(huán)境信息,進(jìn)而判斷是否發(fā)生事故或異常情況[6-7]。基于圖的環(huán)境表示是巡邏領(lǐng)域的主要模型,文獻(xiàn)[8-10]使用由節(jié)點(diǎn)和邊組成的無向圖對(duì)環(huán)境建模。當(dāng)一個(gè)環(huán)境中沒有確切的重要位置而整個(gè)區(qū)域都需要巡邏時(shí),可以使用占用網(wǎng)格[11-19]對(duì)環(huán)境建模。其中每個(gè)網(wǎng)格可以是自由的,也可以被機(jī)器人或障礙物占據(jù),決策時(shí)選擇相鄰4個(gè)網(wǎng)格中的一個(gè)作為無人平臺(tái)下一步的目標(biāo)位置。Nigam等[13-15]為每個(gè)網(wǎng)格設(shè)置空閑時(shí)間,表示自上次訪問該網(wǎng)格以來所經(jīng)過的時(shí)間,持續(xù)監(jiān)測的目標(biāo)是將所有網(wǎng)格的最大空閑時(shí)間降至最低,提出了一種考慮全局最值的半啟發(fā)式控制策略并給出了推導(dǎo)過程。文獻(xiàn)[16-17]通過將值增加1個(gè)單位來計(jì)算每個(gè)可訪問網(wǎng)格的空閑時(shí)間,網(wǎng)格被訪問時(shí)的空閑時(shí)間重置為零。文獻(xiàn)[18]尋求局部最小值,利用信息素的剩余量作為空閑時(shí)間的指示器,將智能體的行為定義為信息素梯度的下降,智能體向含有較少信息素的網(wǎng)格移動(dòng),僅考慮智能體附近的4個(gè)相鄰網(wǎng)格。Almeida等[20]通過考慮節(jié)點(diǎn)的空閑度和機(jī)器人當(dāng)前位置與其目標(biāo)節(jié)點(diǎn)之間的距離來增強(qiáng)控制策略。Portugal等[21]對(duì)考慮局部最優(yōu)的自反應(yīng)(CR)方法、啟發(fā)式自反應(yīng)(HCR)方法、考慮全局最優(yōu)的啟發(fā)式尋路自認(rèn)知(HPCC)方法、通用圖的循環(huán)(CGG)算法和多級(jí)子圖巡視(MSP)5種具有代表性的巡邏方法進(jìn)行了評(píng)估。

現(xiàn)有方法大多僅考慮全局信息或局部信息,并且為使多個(gè)無人平臺(tái)容易分散開地巡邏,通常將多個(gè)機(jī)器人的初始位置分散布置,忽略了實(shí)際應(yīng)用中由于執(zhí)行任務(wù)的需要、工作效率、任務(wù)銜接或環(huán)境復(fù)雜等因素導(dǎo)致多個(gè)無人平臺(tái)的位置彼此鄰近的情況,尤其是在有障礙環(huán)境中多無人平臺(tái)位置鄰近時(shí)不易分散開以至于發(fā)生規(guī)劃層面的沖突,包括分配到同一目標(biāo)位置或相鄰兩個(gè)無人平臺(tái)交換當(dāng)前位置。

本文嘗試對(duì)現(xiàn)有控制策略進(jìn)行改進(jìn),以解決環(huán)境復(fù)雜且多地面無人平臺(tái)初始位置鄰近場景下分散巡邏的監(jiān)視問題。考慮局部因素,為半啟發(fā)式控制策略引入柵格法[22]來分配單步目標(biāo)位置;沿用半啟發(fā)式控制策略中對(duì)距離的考量,無人平臺(tái)的行為仍是趨向全局最大值的網(wǎng)格以分配全局目標(biāo)位置,綜合考量全局因素和局部因素,同時(shí)引入信息素改進(jìn)目標(biāo)函數(shù)并設(shè)置規(guī)則解決沖突問題,從而構(gòu)建出信息素正向激勵(lì)柵格法。

1 問題描述

由于城市作戰(zhàn)的環(huán)境包含窄巷、各種形狀的路口、建筑物等特征或者執(zhí)行任務(wù)的需要,多無人平臺(tái)在巡邏過程中可能難以避免地出現(xiàn)位置相近的情況。為及時(shí)獲取變化的戰(zhàn)場信息,應(yīng)盡可能使無人平臺(tái)分散巡邏并避免有網(wǎng)格長時(shí)間沒有被訪問到,以提高資源利用率和對(duì)目標(biāo)空間的訪問效率。為此,有必要研究多無人平臺(tái)在環(huán)境復(fù)雜且位置相近時(shí)的分散巡邏策略。

1.1 問題建模

多無人平臺(tái)在二維環(huán)境中持續(xù)地移動(dòng),每個(gè)無人平臺(tái)上載有用于觀測環(huán)境的傳感器,無人平臺(tái)之間信息共享。

1)目標(biāo)空間。目標(biāo)空間為劃分成g×g個(gè)網(wǎng)格的正方形區(qū)域,每個(gè)網(wǎng)格以其中心處的坐標(biāo)(i,j)為位置坐標(biāo),每個(gè)網(wǎng)格的邊長為單位值1。目標(biāo)空間中的網(wǎng)格分為被障礙物占據(jù)的占用網(wǎng)格和未被占據(jù)的自由網(wǎng)格。

2)n個(gè)無人平臺(tái)。假設(shè)無人平臺(tái)只能處在網(wǎng)格的中心處或在從一個(gè)網(wǎng)格中心移向另一個(gè)網(wǎng)格中心的路上,將時(shí)間離散化為時(shí)間點(diǎn),在任一時(shí)間點(diǎn)無人平臺(tái)k(k=1,2,…,n)位于其相應(yīng)的位置上。由于在無人平臺(tái)到達(dá)全局目標(biāo)位置前,其余無人平臺(tái)可能已經(jīng)訪問該位置,每個(gè)無人平臺(tái)每到達(dá)一個(gè)網(wǎng)格,便為其重新分配全局目標(biāo)位置和單步目標(biāo)位置。

如圖1所示,10×10大小的目標(biāo)空間中19個(gè)黑色占用網(wǎng)格,自由網(wǎng)格中的數(shù)字用于表示2.1節(jié)的空閑時(shí)間或2.2節(jié)的信息素值。黑三角形、黑矩形和黑圓形分別表示無人平臺(tái)。圖2為兩個(gè)無人平臺(tái)位置相鄰時(shí)規(guī)劃層的沖突情況,所分配的目標(biāo)位置為彼此的當(dāng)前位置,A、B為兩個(gè)平臺(tái)。

圖1 網(wǎng)格表示的環(huán)境模型

圖2 相鄰無人平臺(tái)位置交換示意圖

1.2 假定條件

為簡化計(jì)算模型,定義如下約束:

1)忽略無人平臺(tái)的質(zhì)量、形狀、構(gòu)造、動(dòng)力學(xué)特性以及轉(zhuǎn)彎產(chǎn)生的影響,將無人平臺(tái)視為質(zhì)點(diǎn)。

2)無人平臺(tái)每次只移動(dòng)一個(gè)網(wǎng)格,在連續(xù)的時(shí)間點(diǎn)之間,每個(gè)無人平臺(tái)只能從一個(gè)網(wǎng)格移動(dòng)至與其相鄰的網(wǎng)格。

3)每個(gè)無人平臺(tái)的傳感器觀測范圍等于單個(gè)網(wǎng)格的面積,無人平臺(tái)處于網(wǎng)格(i,j)時(shí),網(wǎng)格(i,j)便被該無人平臺(tái)觀測到且視為被訪問一次,多無人平臺(tái)占用同一網(wǎng)格時(shí)對(duì)該網(wǎng)格的訪問次數(shù)視為一次。

4)每個(gè)無人平臺(tái)的移動(dòng)方向?yàn)樯舷伦笥?個(gè)方向,無人平臺(tái)之間在移動(dòng)時(shí)避開彼此,不發(fā)生碰撞行為。

5)約定兩個(gè)無人平臺(tái)相鄰包括如下情形:兩個(gè)無人平臺(tái)之間的曼哈頓距離小于等于2。

1.3 評(píng)估標(biāo)準(zhǔn)

評(píng)估標(biāo)準(zhǔn)在巡邏問題中起著兩個(gè)作用:作為比較不同巡邏策略時(shí)性能的衡量標(biāo)準(zhǔn),或作決策時(shí)的參考因素。現(xiàn)有標(biāo)準(zhǔn)主要關(guān)注節(jié)點(diǎn)兩次訪問之間的時(shí)間間隔、成本和收益的權(quán)衡以及多機(jī)器人系統(tǒng)的特性,以評(píng)估其對(duì)動(dòng)態(tài)情況的適應(yīng)性[5]。Machado等[23]提出了許多基于空閑時(shí)間的概念,即任何巡邏機(jī)器人連續(xù)兩次訪問同一節(jié)點(diǎn)之間的未訪問時(shí)間,并從全局或局部、歷史或?qū)崟r(shí)的角度定義了節(jié)點(diǎn)瞬時(shí)空閑、瞬時(shí)圖空閑和最壞空閑等特定標(biāo)準(zhǔn)。

本文使用全局平均空閑時(shí)間并提出沖突占比之和這一新的評(píng)估標(biāo)準(zhǔn),對(duì)本文關(guān)注的不同控制策略進(jìn)行比較。

節(jié)點(diǎn)在時(shí)間步w=t時(shí)的空閑時(shí)間Idl(t)為

Idl(t)=t-th

(1)

式中:th表示節(jié)點(diǎn)最后一次被訪問的時(shí)間步。

節(jié)點(diǎn)在時(shí)間步w=t時(shí)的平均空閑時(shí)間Idla(t)為

Idla(t)=(Idla(tp)·Freq+Idl(t))/(Freq+1)

(2)

式中:Idla(tp)表示上一時(shí)間步的節(jié)點(diǎn)平均空閑時(shí)間;Freq為節(jié)點(diǎn)被訪問次數(shù)。

節(jié)點(diǎn)在時(shí)間步w=t時(shí)的最大瞬時(shí)空閑時(shí)間Idls(t)為

(3)

式中:Idlnum(ti)表示時(shí)間步w=ti時(shí)節(jié)點(diǎn)num的空閑時(shí)間;Z為自由網(wǎng)格數(shù)量;t1為統(tǒng)計(jì)最大瞬間空閑時(shí)間的初始時(shí)間步。

節(jié)點(diǎn)在時(shí)間步w=t時(shí)的全局平均空閑時(shí)間為

(4)

沖突占比之和P為

(5)

式中:Ck表示無人平臺(tái)k的沖突占比;nk表示無人平臺(tái)k的總沖突次數(shù);W為總迭代次數(shù);Cp表示經(jīng)歷總迭代次數(shù)W的所有無人平臺(tái)所發(fā)生的沖突次數(shù)之和,每次迭代計(jì)算一次全局目標(biāo)位置和單步目標(biāo)位置。

2 方法和原理

本文信息素正向激勵(lì)柵格法是在半啟發(fā)式控制策略的基礎(chǔ)上與柵格法相結(jié)合,引入信息素和沖突消解規(guī)則而產(chǎn)生的。

2.1 半啟發(fā)式柵格法

2.1.1 半啟發(fā)式控制策略

為每個(gè)網(wǎng)格設(shè)置空閑時(shí)間,該空閑時(shí)間表示網(wǎng)格自上次被訪問以來所經(jīng)過的時(shí)間,值越大表示網(wǎng)格沒有被訪問的時(shí)間越長,因此持續(xù)監(jiān)控的目標(biāo)是將最大空閑時(shí)間降為最低。對(duì)單個(gè)無人平臺(tái)而言,全局目標(biāo)位置應(yīng)是具有最大空閑時(shí)間的網(wǎng)格,無人平臺(tái)到達(dá)全局目標(biāo)位置后該網(wǎng)格的空閑時(shí)間Ap被置為零,在這一路徑中無人平臺(tái)所經(jīng)過網(wǎng)格的空閑時(shí)間在被訪問時(shí)也被置為零,即

(6)

由于多個(gè)無人平臺(tái)距離具有最大空閑時(shí)間的網(wǎng)格遠(yuǎn)近不同,多個(gè)無人平臺(tái)之間的相對(duì)位置會(huì)影響對(duì)網(wǎng)格的選擇,此時(shí)控制策略可以通過為每個(gè)網(wǎng)格設(shè)置導(dǎo)向值來表示,無人平臺(tái)與網(wǎng)格之間的距離以及其余無人平臺(tái)與網(wǎng)格之間的距離會(huì)影響網(wǎng)格的導(dǎo)向值。為無人平臺(tái)k選擇全局目標(biāo)位置時(shí),計(jì)算所有網(wǎng)格的導(dǎo)向值并選擇具有最大導(dǎo)向值的網(wǎng)格,即

(7)

式中:Vi,j表示網(wǎng)格(i,j)的導(dǎo)向值;Ai,j為網(wǎng)格(i,j)的空閑時(shí)間;ω0和ω1為加權(quán)參數(shù),ω0=-1/v,ω1=-1/v,v為無人平臺(tái)的速度;δk為無人平臺(tái)k與網(wǎng)格(i,j)之間的距離;δn為其余無人平臺(tái)與網(wǎng)格(i,j)之間的距離。

δk按下式計(jì)算:

δk=|px-i|+|py-j|

(8)

式中:(px,py)為無人平臺(tái)k當(dāng)前位置的坐標(biāo);(i,j)為網(wǎng)格的坐標(biāo)。

min(δn)按下式計(jì)算:

min(δn)=min(|p1x-i|+|p1y-j|,…,|pnx-i|+|pny-j|)

(9)

式中:(p1x,p1y),…,(pnx,pny)為除無人平臺(tái)k以外其余無人平臺(tái)的當(dāng)前位置坐標(biāo)。

將上述方法應(yīng)用于本文的有障礙環(huán)境,令占用網(wǎng)格的導(dǎo)向值Vi,j為極小的常數(shù):

Vij=-10 000

(10)

但僅改變有障礙網(wǎng)格的值Vi,j并不能使無人平臺(tái)完全避開占用網(wǎng)格。這是因?yàn)閂i,j用于計(jì)算無人平臺(tái)的全局目標(biāo)位置,將Vi,j賦極小值只能保證不會(huì)將該網(wǎng)格選作無人平臺(tái)的全局目標(biāo)位置,無人平臺(tái)在朝著全局目標(biāo)位置移動(dòng)的過程中仍然可能經(jīng)過該占用網(wǎng)格,因此有必要尋求一種避障方法。

2.1.2 柵格法

為避開占用網(wǎng)格,無人平臺(tái)需要從相鄰網(wǎng)格中選擇合適的網(wǎng)格作為單步目標(biāo)位置。文獻(xiàn)[22]所提柵格搜索算法步驟如下:

步驟1確定起始位置、全局目標(biāo)位置和占用網(wǎng)格。

步驟2搜索無人平臺(tái)的相鄰網(wǎng)格并選出自由網(wǎng)格。

步驟3利用評(píng)價(jià)函數(shù)h來計(jì)算自由網(wǎng)格(i,j)與全局目標(biāo)位置(i′,j′)之間的距離:

(11)

步驟4選取與全局目標(biāo)位置之間的距離最小的自由網(wǎng)格,并將其作為無人平臺(tái)的單步目標(biāo)位置。

試驗(yàn)時(shí)發(fā)現(xiàn)直接應(yīng)用柵格法時(shí),無人平臺(tái)會(huì)“穿過”占用網(wǎng)格,這是不被允許的。因此對(duì)柵格法進(jìn)行如下改進(jìn):如果選出的最優(yōu)自由網(wǎng)格剛剛被訪問過,則選擇次優(yōu)的自由網(wǎng)格,即與全局目標(biāo)位置之間的距離第二小的自由網(wǎng)格。圖3所示為加入柵格法前后的效果,線段表示無人平臺(tái)的大致移動(dòng)軌跡。

圖3 加入柵格法前后的對(duì)比圖

利用半啟發(fā)式控制策略結(jié)合柵格法構(gòu)建半啟發(fā)式柵格法(SGM),并在無人平臺(tái)每走至一個(gè)網(wǎng)格時(shí)重新計(jì)算全局目標(biāo)位置。算法流程如下:

步驟1初始化目標(biāo)空間大小g、無人平臺(tái)數(shù)量、速度和初始位置、占用網(wǎng)格位置以及網(wǎng)格空閑時(shí)間。

步驟2執(zhí)行如下循環(huán):

①計(jì)算各個(gè)無人平臺(tái)的當(dāng)前位置與各自由網(wǎng)格之間的距離;

②對(duì)單個(gè)無人平臺(tái)而言,計(jì)算其余無人平臺(tái)的當(dāng)前位置與各自由網(wǎng)格之間距離的最小值;

③為占用網(wǎng)格的導(dǎo)向值賦值-10 000;

④每個(gè)無人平臺(tái)根據(jù)式(7)計(jì)算其對(duì)應(yīng)的各個(gè)自由網(wǎng)格的導(dǎo)向值,并選擇具有最大導(dǎo)向值的自由網(wǎng)格作為其全局目標(biāo)位置;

⑤對(duì)每個(gè)無人平臺(tái)使用柵格法,執(zhí)行2.1.2節(jié)中的步驟;

⑥當(dāng)無人平臺(tái)到達(dá)單步目標(biāo)位置后,根據(jù)式(6)將對(duì)應(yīng)網(wǎng)格的空閑時(shí)間清零。

為避免將同一個(gè)全局目標(biāo)位置分配給不同的無人平臺(tái),在計(jì)算無人平臺(tái)對(duì)應(yīng)網(wǎng)格的導(dǎo)向值時(shí),選出次最大導(dǎo)向值的網(wǎng)格,出現(xiàn)重復(fù)分配的情況時(shí)將次最大導(dǎo)向值的網(wǎng)格作為新的全局目標(biāo)位置。

2.2 信息素正向激勵(lì)柵格法設(shè)計(jì)

2.2.1 信息素

自然界中具有探索價(jià)值的地方往往沉積較多的信息素,信息素的正反饋使得螞蟻傾向于沿著信息素多的路線行進(jìn),隨著探索區(qū)域價(jià)值的變化,信息素的沉積量也會(huì)改變。受此啟發(fā),對(duì)目標(biāo)空間網(wǎng)格分解后為每個(gè)網(wǎng)格預(yù)設(shè)相應(yīng)的信息素,假定所有自由網(wǎng)格的初始信息素相同。將無人平臺(tái)對(duì)網(wǎng)格的訪問結(jié)果視為信息素的衰減,被無人平臺(tái)訪問過的網(wǎng)格其信息素會(huì)減小一定值,未被訪問的網(wǎng)格其信息素增加一定值。只要有一個(gè)自由網(wǎng)格一直沒有被無人平臺(tái)監(jiān)測過,則該網(wǎng)格的信息素值就大于其他網(wǎng)格的信息素值。因此無人平臺(tái)趨向于朝著信息素值大的網(wǎng)格行進(jìn)。

坐標(biāo)為(i,j)的網(wǎng)格當(dāng)前信息素表示為

(12)

式中:α為與距離、網(wǎng)格重要度有關(guān)的衰減系數(shù),α∈(0, 1);β為沉積系數(shù),β>1;Celli,j的單位為與時(shí)間有關(guān)的量綱,本文中取s。選擇最大導(dǎo)向值的網(wǎng)格作為無人平臺(tái)的全局目標(biāo)位置:

(13)

2.2.2 沖突消解規(guī)則

柵格法雖然解決了將占用網(wǎng)格分配給無人平臺(tái)的問題,但多個(gè)無人平臺(tái)的位置彼此鄰近時(shí),不同無人平臺(tái)可能分配到同一個(gè)自由網(wǎng)格,并在之后保持規(guī)劃軌跡重合,影響資源利用率和巡視效率。為此,本文研究多無人平臺(tái)執(zhí)行持續(xù)監(jiān)控任務(wù)中的運(yùn)動(dòng)協(xié)調(diào)問題,沖突消解的主要目標(biāo)是減少目標(biāo)位置在分配過程中的沖突,使無人平臺(tái)盡量分散開地探測環(huán)境。對(duì)單個(gè)無人平臺(tái)如何到達(dá)分配的目標(biāo)位置,在向著目標(biāo)位置移動(dòng)過程中如何避障這些不作研究。圖4所示為沖突消解原理圖。

圖4 沖突消解原理圖

為解決沖突問題,依照以下規(guī)則選擇單步目標(biāo)位置:

當(dāng)兩個(gè)無人平臺(tái)相鄰時(shí),每個(gè)無人平臺(tái)選擇回頭,單步目標(biāo)位置為前一步到達(dá)的網(wǎng)格:

U(u,t)=Idl(t)min

(14)

式中:U(u,t)為確定無人平臺(tái)單步目標(biāo)位置u的效用函數(shù);Idl(t)min表示無人平臺(tái)當(dāng)前位置的相鄰自由網(wǎng)格中的最小空閑時(shí)間。

當(dāng)無人平臺(tái)沒有與其他無人平臺(tái)相鄰時(shí),若其相鄰自由網(wǎng)格數(shù)量大于1則禁止回頭,單步目標(biāo)位置為除前一步到達(dá)的網(wǎng)格之外的距離全局目標(biāo)位置最近的網(wǎng)格:

U(u,t)=hmin

(15)

式中:hmin表示無人平臺(tái)的相鄰自由網(wǎng)格中與全局目標(biāo)位置之間的最小距離。

自循環(huán)是指無人平臺(tái)的規(guī)劃軌跡構(gòu)成閉合矩形,如圖5所示。

圖5 自循環(huán)判斷示意圖

圖5中,無人平臺(tái)當(dāng)前位置為p1,自循環(huán)可能發(fā)生在p1p2p3p4、p1p4p′3p′2、p1p′4p″2p′2和p1p′4p″3p2中的其中一個(gè)矩形,根據(jù)無人平臺(tái)最近3次分配的單步目標(biāo)位置為矩形的3個(gè)頂點(diǎn),判斷無人平臺(tái)處于自循環(huán)。當(dāng)無人平臺(tái)發(fā)生自循環(huán)時(shí),若除該4個(gè)網(wǎng)格之外的網(wǎng)格中存在與無人平臺(tái)前進(jìn)方向一致的網(wǎng)格,則單步目標(biāo)位置為該網(wǎng)格,否則選擇除該4個(gè)網(wǎng)格之外的任一可到達(dá)網(wǎng)格:

發(fā)生自循環(huán)p1p2p3p4時(shí),p1的兩個(gè)相鄰網(wǎng)格p2、p4為自循環(huán)矩形中的點(diǎn),選擇另外兩個(gè)相鄰網(wǎng)格p′2、p′4中信息素大的網(wǎng)格作為單步目標(biāo)位置:

(16)

無人平臺(tái)當(dāng)前位置為p2且發(fā)生自循環(huán)p1p2p3p4時(shí),若相鄰自由網(wǎng)格為3個(gè),則選擇另外一個(gè)相鄰自由網(wǎng)格p″3為單步目標(biāo)位置:

u=p″3,Nf={p1,p3,p″3}

(17)

式中:Nf為相鄰自由網(wǎng)格集合。

若無人平臺(tái)當(dāng)前位置的相鄰自由網(wǎng)格均在自循環(huán)矩形中,則選擇自循環(huán)矩形中的任一可到達(dá)網(wǎng)格,直到可以分配自循環(huán)矩形以外的相鄰自由網(wǎng)格為止。以無人平臺(tái)當(dāng)前位置在p3且自循環(huán)為p1p2p3p4為例:

u=p2∨p4,Nf={p2,p4}

(18)

2.2.3 信息素正向激勵(lì)柵格法

將信息素和上述規(guī)則引入半啟發(fā)式柵格法,形成信息素正向激勵(lì)柵格法(PPIGM),對(duì)應(yīng)的多無人平臺(tái)持續(xù)監(jiān)控控制流程如圖6所示。

圖6 持續(xù)監(jiān)控流程示意圖

同一個(gè)無人平臺(tái)可能計(jì)算出多個(gè)全局目標(biāo)位置,多個(gè)無人平臺(tái)的全局目標(biāo)位置也可能相同,因此采用如下次優(yōu)分配過程:

同一個(gè)無人平臺(tái)存在多個(gè)全局目標(biāo)位置時(shí),選擇距離該無人平臺(tái)最近的一個(gè)全局目標(biāo)位置;不同無人平臺(tái)計(jì)算得到同一個(gè)全局目標(biāo)位置時(shí),為距離該全局目標(biāo)位置遠(yuǎn)的無人平臺(tái)分配次優(yōu)目標(biāo)位置,次優(yōu)目標(biāo)位置為該無人平臺(tái)計(jì)算得到的次大導(dǎo)向值網(wǎng)格。

加入信息素的SGM與次優(yōu)分配過程完成了無人平臺(tái)全局目標(biāo)位置的分配,利用沖突消解優(yōu)化無人平臺(tái)單步目標(biāo)位置的選擇。

3 試驗(yàn)結(jié)果及分析

3.1 試驗(yàn)?zāi)Ｐ秃蛥?shù)選取

如圖7所示,仿真環(huán)境為10×10的二維網(wǎng)格空間,每個(gè)網(wǎng)格的邊長為單位值1,黑色網(wǎng)格表示占用網(wǎng)格,障礙物數(shù)量分別為OBS=19、OBS=13和OBS=6,自由網(wǎng)格數(shù)量分別為Z=81、Z=87和Z=94。自由網(wǎng)格的數(shù)量不同表示通道的彎曲復(fù)雜程度不同,以對(duì)比通道變化對(duì)算法性能的影響。情景1中無人平臺(tái)的初始位置分別為(8, 4),(6, 3),(7, 2);情景2(見圖8)中無人平臺(tái)的初始位置分別為(1, 1),(6, 3),(4, 2)。式(7)中Ai,j初始值為0,網(wǎng)格(i,j)被訪問前Ai,j每單位時(shí)間步增1,一旦被訪問Ai,j則置為0。式(12)中α=0.9,β=1.1,ω0=-1,ω1=-1。

圖7 不同障礙物數(shù)量的情景1

圖8 不同障礙物數(shù)量的情景2

圖9展示了兩種情景Z=81時(shí)的軌跡圖。由圖9 可見,無人平臺(tái)的初始位置不同,規(guī)劃軌跡也不相同。下面分別在兩種情景下開展試驗(yàn),將PPIGM與SGM、文獻(xiàn)[21]中的CR、HCR、HPCC(Dijkstra算法改用A*算法)以及文獻(xiàn)[18]中的EVAP、CLInG進(jìn)行對(duì)比試驗(yàn),其中HCR在本文環(huán)境模型下退化為CR,因此實(shí)際上是與SGM、CR、HPCC、EVAP、CLInG進(jìn)行對(duì)比。

3.2 與現(xiàn)有控制策略對(duì)比

分別從沖突占比之和與全局平均空閑時(shí)間兩方面對(duì)比不同算法的性能。

3.2.1 情景1

表1為OBS=19、OBS=13和OBS=6共3種 條件下不同算法迭代次數(shù)W=1 000的沖突占比之和。由表1可見:試驗(yàn)中CR和HPCC一直出現(xiàn)兩個(gè)無人平臺(tái)沖突的情況,其次為EVAP和CLInG,表現(xiàn)較優(yōu)的為SGM(沖突占比之和為20%左右),PPIGM的沖突占比之和為0.1%,表現(xiàn)最優(yōu);在障礙物數(shù)量變化時(shí)PPIGM的表現(xiàn)適應(yīng)性好,沖突占比之和始終保持為0.1%;SGM也隨障礙物數(shù)量的增加沖突占比之和減小;EVAP和CLInG雖然在OBS=19時(shí)沖突占比之和有所下降,但整體而言仍保持較高的沖突占比之和,造成這一波動(dòng)的原因在于EVAP和CLInG包含隨機(jī)機(jī)制。

表1 情景1 OBS取不同值時(shí)的沖突占比之和

圖10為OBS=19、OBS=13和OBS=6共3種條件下不同算法全局平均空閑時(shí)間隨迭代次數(shù)的變化。由圖10可見:障礙物數(shù)量較多時(shí)PPIGM的全局平均空閑時(shí)間明顯小于SGM,特別當(dāng)OBS=19時(shí)SGM沒有收斂,這是因?yàn)樵诤笃跓o人平臺(tái)陷入局部區(qū)域而無法走出,也是沖突占比之和低的原因;整體而言CR和HPCC的最終全局平均空閑時(shí)間較大,PPIGM、EVAP和CLInG的最終全局平均空閑時(shí)間較小,表現(xiàn)較好。

圖10 情景1不同算法的全局平均空閑時(shí)間對(duì)比圖

圖11給出了PPIGM與現(xiàn)有5種算法在全局平均空閑時(shí)間上的分布隨障礙物數(shù)量的變化情況。由圖11可見:PPIGM的全局平均空閑時(shí)間比較接近正態(tài)分布,現(xiàn)有算法的分布特性基本上呈偏態(tài)分布;SGM在OBS=19時(shí)的分布最為分散;CR和HPCC的分布情況次于PPIGM、EVAP和CLInG,這些表現(xiàn)與圖10吻合;PPIGM的箱體寬度小于EVAP和CLInG,表明PPIGM的分布更為集中。

3.2.2 情景2

表2為OBS=19、OBS=13和OBS=6共3種條件下不同算法總迭代次數(shù)W=1 000的沖突占比之和。由表2可見,各算法表現(xiàn)與情景1大致相同,PPIGM的沖突占比之和較為穩(wěn)定地保持在很小的水平。值得注意的是,EVAP隨障礙物數(shù)量的增加沖突占比之和增大,CLInG雖然在OBS=19時(shí)沖突占比之和略微下降,但整體而言仍保持較高的沖突占比之和。

表2 情景2 OBS取不同值時(shí)沖突占比之和

圖12展示了OBS=19、OBS=13和OBS=6共3種條件下不同算法的全局平均空閑時(shí)間隨迭代次數(shù)的變化。由圖12可見:各算法的表現(xiàn)與情景1大致相同。障礙物數(shù)量較少時(shí)PPIGM的全局平均空閑時(shí)間有較大峰,但在后期能夠降下來,證明PPIGM能夠跳出局部區(qū)域,為克服SGM陷入局部區(qū)域的缺陷提供了可能;整體而言,CR和HPCC的最終全局平均空閑時(shí)間較大,PPIGM、EVAP和CLInG的最終全局平均空閑時(shí)間較小,表現(xiàn)較好。

圖12 情景2不同算法的全局平均空閑時(shí)間對(duì)比圖

圖13給出了不同算法在全局平均空閑時(shí)間上的分布隨障礙物數(shù)量變化情況,從中可見各算法的表現(xiàn)與情景1大致相同。

3.3 小結(jié)

1) PPIGM在沖突消解上的表現(xiàn)優(yōu)于現(xiàn)有控制策略且在全局平均空閑時(shí)間上的表現(xiàn)較優(yōu),這是因?yàn)镻PIGM根據(jù)全局目標(biāo)位置分配單步目標(biāo)位置,綜合考慮了沖突消解和空閑時(shí)間的因素,而根據(jù)無人平臺(tái)在沖突時(shí)的反應(yīng)規(guī)則,難以避免地要犧牲掉部分空閑時(shí)間;

2) PPIGM全局平均空閑時(shí)間的分布整體趨近正態(tài)分布,且相較于現(xiàn)有控制策略分布較為集中,這是因?yàn)楝F(xiàn)有控制策略均只考慮全局目標(biāo)位置或只考慮單步目標(biāo)位置,導(dǎo)致數(shù)據(jù)分布偏態(tài)較重也較為分散。

4 結(jié)論

本文對(duì)復(fù)雜環(huán)境中多無人平臺(tái)初始位置鄰近情況下的持續(xù)監(jiān)控方法進(jìn)行研究,在半啟發(fā)式控制策略和柵格法的基礎(chǔ)上通過引入信息素改進(jìn)了目標(biāo)函數(shù),并制定沖突消解規(guī)則,從而構(gòu)建出信息素正向激勵(lì)柵格法。得出以下主要結(jié)論:

1) PPIGM能夠很好地解決多無人平臺(tái)在復(fù)雜環(huán)境且位置鄰近時(shí)的沖突問題,全局平均空閑時(shí)間與現(xiàn)有方法相比也較好。

2) PPIGM對(duì)障礙物數(shù)量變化的適應(yīng)性較好,在沖突消解和全局平均空閑時(shí)間上的綜合表現(xiàn)較為優(yōu)越。

本文研究結(jié)果對(duì)后續(xù)研究工作和應(yīng)用均具有極強(qiáng)的指導(dǎo)意義和參考價(jià)值。受限于當(dāng)前條件,本次試驗(yàn)是在特定參數(shù)(n=3,α=0.9,β=1.1,ω0=-1,ω1=-1)下進(jìn)行的,參數(shù)變化對(duì)PPIGM的性能影響有待研究;此外PPIGM中包含隨機(jī)機(jī)制,大量試驗(yàn)樣本情況下PPIGM的性能表現(xiàn)也值得關(guān)注。