面向多無人平臺區域監視任務的信息素正向激勵柵格方法

陳亞萍, 王楠, 洪華杰, 劉召陽, 閆響達

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

0 引言

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

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

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

本文嘗試對現有控制策略進行改進,以解決環境復雜且多地面無人平臺初始位置鄰近場景下分散巡邏的監視問題。考慮局部因素,為半啟發式控制策略引入柵格法[22]來分配單步目標位置;沿用半啟發式控制策略中對距離的考量,無人平臺的行為仍是趨向全局最大值的網格以分配全局目標位置,綜合考量全局因素和局部因素,同時引入信息素改進目標函數并設置規則解決沖突問題,從而構建出信息素正向激勵柵格法。

1 問題描述

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

1.1 問題建模

多無人平臺在二維環境中持續地移動,每個無人平臺上載有用于觀測環境的傳感器,無人平臺之間信息共享。

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

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

如圖1所示,10×10大小的目標空間中19個黑色占用網格,自由網格中的數字用于表示2.1節的空閑時間或2.2節的信息素值。黑三角形、黑矩形和黑圓形分別表示無人平臺。圖2為兩個無人平臺位置相鄰時規劃層的沖突情況,所分配的目標位置為彼此的當前位置,A、B為兩個平臺。

圖1 網格表示的環境模型

圖2 相鄰無人平臺位置交換示意圖

1.2 假定條件

為簡化計算模型,定義如下約束:

1)忽略無人平臺的質量、形狀、構造、動力學特性以及轉彎產生的影響,將無人平臺視為質點。

2)無人平臺每次只移動一個網格,在連續的時間點之間,每個無人平臺只能從一個網格移動至與其相鄰的網格。

3)每個無人平臺的傳感器觀測范圍等于單個網格的面積,無人平臺處于網格(i,j)時,網格(i,j)便被該無人平臺觀測到且視為被訪問一次,多無人平臺占用同一網格時對該網格的訪問次數視為一次。

4)每個無人平臺的移動方向為上下左右4個方向,無人平臺之間在移動時避開彼此,不發生碰撞行為。

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

1.3 評估標準

評估標準在巡邏問題中起著兩個作用:作為比較不同巡邏策略時性能的衡量標準,或作決策時的參考因素。現有標準主要關注節點兩次訪問之間的時間間隔、成本和收益的權衡以及多機器人系統的特性,以評估其對動態情況的適應性[5]。Machado等[23]提出了許多基于空閑時間的概念,即任何巡邏機器人連續兩次訪問同一節點之間的未訪問時間,并從全局或局部、歷史或實時的角度定義了節點瞬時空閑、瞬時圖空閑和最壞空閑等特定標準。

本文使用全局平均空閑時間并提出沖突占比之和這一新的評估標準,對本文關注的不同控制策略進行比較。

節點在時間步w=t時的空閑時間Idl(t)為

Idl(t)=t-th

(1)

式中:th表示節點最后一次被訪問的時間步。

節點在時間步w=t時的平均空閑時間Idla(t)為

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

(2)

式中:Idla(tp)表示上一時間步的節點平均空閑時間;Freq為節點被訪問次數。

節點在時間步w=t時的最大瞬時空閑時間Idls(t)為

(3)

式中:Idlnum(ti)表示時間步w=ti時節點num的空閑時間;Z為自由網格數量;t1為統計最大瞬間空閑時間的初始時間步。

節點在時間步w=t時的全局平均空閑時間為

(4)

沖突占比之和P為

(5)

式中:Ck表示無人平臺k的沖突占比;nk表示無人平臺k的總沖突次數;W為總迭代次數;Cp表示經歷總迭代次數W的所有無人平臺所發生的沖突次數之和,每次迭代計算一次全局目標位置和單步目標位置。

2 方法和原理

本文信息素正向激勵柵格法是在半啟發式控制策略的基礎上與柵格法相結合,引入信息素和沖突消解規則而產生的。

2.1 半啟發式柵格法

2.1.1 半啟發式控制策略

為每個網格設置空閑時間,該空閑時間表示網格自上次被訪問以來所經過的時間,值越大表示網格沒有被訪問的時間越長,因此持續監控的目標是將最大空閑時間降為最低。對單個無人平臺而言,全局目標位置應是具有最大空閑時間的網格,無人平臺到達全局目標位置后該網格的空閑時間Ap被置為零,在這一路徑中無人平臺所經過網格的空閑時間在被訪問時也被置為零,即

(6)

由于多個無人平臺距離具有最大空閑時間的網格遠近不同,多個無人平臺之間的相對位置會影響對網格的選擇,此時控制策略可以通過為每個網格設置導向值來表示,無人平臺與網格之間的距離以及其余無人平臺與網格之間的距離會影響網格的導向值。為無人平臺k選擇全局目標位置時,計算所有網格的導向值并選擇具有最大導向值的網格,即

(7)

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

δk按下式計算:

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

(8)

式中:(px,py)為無人平臺k當前位置的坐標;(i,j)為網格的坐標。

min(δn)按下式計算:

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

(9)

式中:(p1x,p1y),…,(pnx,pny)為除無人平臺k以外其余無人平臺的當前位置坐標。

將上述方法應用于本文的有障礙環境,令占用網格的導向值Vi,j為極小的常數:

Vij=-10 000

(10)

但僅改變有障礙網格的值Vi,j并不能使無人平臺完全避開占用網格。這是因為Vi,j用于計算無人平臺的全局目標位置,將Vi,j賦極小值只能保證不會將該網格選作無人平臺的全局目標位置,無人平臺在朝著全局目標位置移動的過程中仍然可能經過該占用網格,因此有必要尋求一種避障方法。

2.1.2 柵格法

為避開占用網格,無人平臺需要從相鄰網格中選擇合適的網格作為單步目標位置。文獻[22]所提柵格搜索算法步驟如下:

步驟1確定起始位置、全局目標位置和占用網格。

步驟2搜索無人平臺的相鄰網格并選出自由網格。

步驟3利用評價函數h來計算自由網格(i,j)與全局目標位置(i′,j′)之間的距離:

(11)

步驟4選取與全局目標位置之間的距離最小的自由網格,并將其作為無人平臺的單步目標位置。

試驗時發現直接應用柵格法時,無人平臺會“穿過”占用網格,這是不被允許的。因此對柵格法進行如下改進:如果選出的最優自由網格剛剛被訪問過,則選擇次優的自由網格,即與全局目標位置之間的距離第二小的自由網格。圖3所示為加入柵格法前后的效果,線段表示無人平臺的大致移動軌跡。

圖3 加入柵格法前后的對比圖

利用半啟發式控制策略結合柵格法構建半啟發式柵格法(SGM),并在無人平臺每走至一個網格時重新計算全局目標位置。算法流程如下:

步驟1初始化目標空間大小g、無人平臺數量、速度和初始位置、占用網格位置以及網格空閑時間。

步驟2執行如下循環:

①計算各個無人平臺的當前位置與各自由網格之間的距離;

②對單個無人平臺而言,計算其余無人平臺的當前位置與各自由網格之間距離的最小值;

③為占用網格的導向值賦值-10 000;

④每個無人平臺根據式(7)計算其對應的各個自由網格的導向值,并選擇具有最大導向值的自由網格作為其全局目標位置;

⑤對每個無人平臺使用柵格法,執行2.1.2節中的步驟;

⑥當無人平臺到達單步目標位置后,根據式(6)將對應網格的空閑時間清零。

為避免將同一個全局目標位置分配給不同的無人平臺,在計算無人平臺對應網格的導向值時,選出次最大導向值的網格,出現重復分配的情況時將次最大導向值的網格作為新的全局目標位置。

2.2 信息素正向激勵柵格法設計

2.2.1 信息素

自然界中具有探索價值的地方往往沉積較多的信息素,信息素的正反饋使得螞蟻傾向于沿著信息素多的路線行進,隨著探索區域價值的變化,信息素的沉積量也會改變。受此啟發,對目標空間網格分解后為每個網格預設相應的信息素,假定所有自由網格的初始信息素相同。將無人平臺對網格的訪問結果視為信息素的衰減,被無人平臺訪問過的網格其信息素會減小一定值,未被訪問的網格其信息素增加一定值。只要有一個自由網格一直沒有被無人平臺監測過,則該網格的信息素值就大于其他網格的信息素值。因此無人平臺趨向于朝著信息素值大的網格行進。

坐標為(i,j)的網格當前信息素表示為

(12)

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

(13)

2.2.2 沖突消解規則

柵格法雖然解決了將占用網格分配給無人平臺的問題,但多個無人平臺的位置彼此鄰近時,不同無人平臺可能分配到同一個自由網格,并在之后保持規劃軌跡重合,影響資源利用率和巡視效率。為此,本文研究多無人平臺執行持續監控任務中的運動協調問題,沖突消解的主要目標是減少目標位置在分配過程中的沖突,使無人平臺盡量分散開地探測環境。對單個無人平臺如何到達分配的目標位置,在向著目標位置移動過程中如何避障這些不作研究。圖4所示為沖突消解原理圖。

圖4 沖突消解原理圖

為解決沖突問題,依照以下規則選擇單步目標位置:

當兩個無人平臺相鄰時,每個無人平臺選擇回頭,單步目標位置為前一步到達的網格:

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

(14)

式中:U(u,t)為確定無人平臺單步目標位置u的效用函數;Idl(t)min表示無人平臺當前位置的相鄰自由網格中的最小空閑時間。

當無人平臺沒有與其他無人平臺相鄰時,若其相鄰自由網格數量大于1則禁止回頭,單步目標位置為除前一步到達的網格之外的距離全局目標位置最近的網格:

U(u,t)=hmin

(15)

式中:hmin表示無人平臺的相鄰自由網格中與全局目標位置之間的最小距離。

自循環是指無人平臺的規劃軌跡構成閉合矩形,如圖5所示。

圖5 自循環判斷示意圖

圖5中,無人平臺當前位置為p1,自循環可能發生在p1p2p3p4、p1p4p′3p′2、p1p′4p″2p′2和p1p′4p″3p2中的其中一個矩形,根據無人平臺最近3次分配的單步目標位置為矩形的3個頂點,判斷無人平臺處于自循環。當無人平臺發生自循環時,若除該4個網格之外的網格中存在與無人平臺前進方向一致的網格,則單步目標位置為該網格,否則選擇除該4個網格之外的任一可到達網格:

發生自循環p1p2p3p4時,p1的兩個相鄰網格p2、p4為自循環矩形中的點,選擇另外兩個相鄰網格p′2、p′4中信息素大的網格作為單步目標位置:

(16)

無人平臺當前位置為p2且發生自循環p1p2p3p4時,若相鄰自由網格為3個,則選擇另外一個相鄰自由網格p″3為單步目標位置:

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

(17)

式中:Nf為相鄰自由網格集合。

若無人平臺當前位置的相鄰自由網格均在自循環矩形中,則選擇自循環矩形中的任一可到達網格,直到可以分配自循環矩形以外的相鄰自由網格為止。以無人平臺當前位置在p3且自循環為p1p2p3p4為例:

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

(18)

2.2.3 信息素正向激勵柵格法

將信息素和上述規則引入半啟發式柵格法,形成信息素正向激勵柵格法(PPIGM),對應的多無人平臺持續監控控制流程如圖6所示。

圖6 持續監控流程示意圖

同一個無人平臺可能計算出多個全局目標位置,多個無人平臺的全局目標位置也可能相同,因此采用如下次優分配過程:

同一個無人平臺存在多個全局目標位置時,選擇距離該無人平臺最近的一個全局目標位置;不同無人平臺計算得到同一個全局目標位置時,為距離該全局目標位置遠的無人平臺分配次優目標位置,次優目標位置為該無人平臺計算得到的次大導向值網格。

加入信息素的SGM與次優分配過程完成了無人平臺全局目標位置的分配,利用沖突消解優化無人平臺單步目標位置的選擇。

3 試驗結果及分析

3.1 試驗模型和參數選取

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

圖7 不同障礙物數量的情景1

圖8 不同障礙物數量的情景2

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

3.2 與現有控制策略對比

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

3.2.1 情景1

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

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

圖10為OBS=19、OBS=13和OBS=6共3種條件下不同算法全局平均空閑時間隨迭代次數的變化。由圖10可見:障礙物數量較多時PPIGM的全局平均空閑時間明顯小于SGM,特別當OBS=19時SGM沒有收斂,這是因為在后期無人平臺陷入局部區域而無法走出,也是沖突占比之和低的原因;整體而言CR和HPCC的最終全局平均空閑時間較大,PPIGM、EVAP和CLInG的最終全局平均空閑時間較小,表現較好。

圖10 情景1不同算法的全局平均空閑時間對比圖

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

3.2.2 情景2

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

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

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

圖12 情景2不同算法的全局平均空閑時間對比圖

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

3.3 小結

1) PPIGM在沖突消解上的表現優于現有控制策略且在全局平均空閑時間上的表現較優,這是因為PPIGM根據全局目標位置分配單步目標位置,綜合考慮了沖突消解和空閑時間的因素,而根據無人平臺在沖突時的反應規則,難以避免地要犧牲掉部分空閑時間;

2) PPIGM全局平均空閑時間的分布整體趨近正態分布,且相較于現有控制策略分布較為集中,這是因為現有控制策略均只考慮全局目標位置或只考慮單步目標位置,導致數據分布偏態較重也較為分散。

4 結論

本文對復雜環境中多無人平臺初始位置鄰近情況下的持續監控方法進行研究,在半啟發式控制策略和柵格法的基礎上通過引入信息素改進了目標函數,并制定沖突消解規則,從而構建出信息素正向激勵柵格法。得出以下主要結論:

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

2) PPIGM對障礙物數量變化的適應性較好,在沖突消解和全局平均空閑時間上的綜合表現較為優越。

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