基于距離信息的追逃策略: 信念狀態連續隨機博弈

陳靈敏 馮 宇 李永強

近年來,追逃問題在飛行器、移動機器人等領域一直廣受關注,如無人機圍捕搜查[1]、機器人協同對抗[2]、搜索救援[3]等.在典型追逃問題中追捕方試圖快速捕獲或逼近逃逸方,而逃逸方則試圖遠離追捕方以避免被捕獲.自二十世紀六十年代提出一對一追逃問題以來[4],學術界對其進行了充分探索[5-8],并逐步演變為當下的多對一[9-11]、多對多[12-14]對抗問題的研究.

追逃問題可視為智能體間的對抗與合作問題,因此博弈論[15-17]被廣泛用于此類問題的求解[18-20].文獻[21]在追逃雙方具有無限視野下建立了線性二次型微分博弈模型,將多追捕者與多逃逸者問題轉化為多組兩人零和微分博弈.文獻[22]基于非零和博弈框架,研究了針對三種不同類型追捕者的追逃問題,并分析了可捕獲性、納什均衡以及捕獲時間.文獻[23]在確保每個時刻都至少有一個追捕者具有全局視野的情況下,提出了基于微分模型的追捕策略.不同于無限視野的結果,文獻[24]在有限視野下設計了追捕群體快速逼近逃逸者的分布式算法,并根據初始分布及速度比推導了捕獲條件.文獻[25]采用圖論方式研究了有限感知的追捕問題,為每個智能體求解了分布式最優策略.

上述研究均基于模型求解追逃策略,然而現實中由于不確定因素的存在,構建準確的模型極為困難,而強化學習可通過無模型的方式尋求最優策略,因此其與追逃問題的結合也成為當下研究熱點[6-7,26].針對某一方使用固定策略的追捕問題,文獻[8]利用視野圖像引入逃逸者位置的信念狀態,并基于Soft actor-critic 算法獲取最優追捕策略.文獻[27]基于深度Q網絡,并借助人工勢場法對獎勵函數進行改造以獲取逃逸策略.而對于追逃雙方通過對抗學習進行智能追捕的問題,文獻[28]在無限視野下,提出了Q(λ) -learning 算法以求解追逃策略.文獻[29]則在有限視野下基于深度確定性策略梯度,提出了兩種網絡拓撲結構來快速求解策略,降低了多智能體算法的復雜度.文獻[30]對深度確定性策略梯度公式進行向量化拓展,提出了一種多智能體協同目標預測網絡,保證了追捕群體對目標軌跡預測的有效性.

上述絕大多數追逃問題求解均基于定位信息,但在特定環境下此類信息無法獲取.如水下航行器在固定海域中執行巡航與入侵驅逐任務時,由于無線電信號在海水中迅速衰減,此時航行器無法借助無線電導航系統對入侵者實現水下遠距離、大范圍的定位[31-32],在此情況下,借助輕便且低頻的測距傳感器實現追捕的研究是極為重要的.文獻[33]研究了單個追捕者基于距離構造幾何圖形以估計逃逸者的追逃問題,并提出了在三維環境下使用兩個追捕者估計逃逸者位置的方法.在固定信標的幫助下,文獻[34]基于三角定位進行逃逸者位置估計,并提出了對測量距離進行去噪處理的方法以獲得精準定位.文獻[35]借助凸優化方法,提出一種基于測量距離的梯度算法實現對逃逸者的定位.文獻[36]針對固定規則下的單移動機器人目標跟蹤問題,提出了一種利用測量距離與距離變化率求解追捕策略的方法.此外,文獻[37]基于距離變化率提出了自適應切換算法,證明了該算法穩定性與收斂性,并在距離變化率不可用時將其擴展為使用觀測器補償的算法,通過移動機器人圍捕實驗驗證了其有效性.

綜上所述,基于距離的追逃問題已有較多研究成果,但部分結果仍基于模型求解[32,35-37],或只針對固定策略的逃逸者[36],亦或是需要借助額外設備如信標等[34].因此在無模型情況下針對智能逃逸者,僅利用距離信息來實現追捕的問題仍有待于進一步探索.本文將基于距離信息的N對 1 圍捕問題與隨機博弈相結合,研究最優追逃策略.在此問題中,追捕群體僅領導者可測量與逃逸者間的相對距離,其他跟隨者通過領導者的共享獲取此信息,而逃逸者則擁有無限視野.為求解追捕策略,將環境分割引入信念區域狀態以估計逃逸者位置.同時根據相對距離,對信念區域狀態進行修正.領導者借助信念引入想象逃逸者,建立了信念區域狀態下的連續隨機追博弈,并使用不動點定理證明此博弈平穩納什均衡策略的存在性.為求解逃逸策略,由于逃逸者具有全局信息優勢,在追捕群體最優策略的基礎上,建立基于混合狀態的MDP 與相應最優的貝爾曼方程.最后給出了基于強化學習的追逃策略求解算法.

本文結構安排如下: 第1 節對追逃問題作出具體描述;第2 節證明基于信念區域狀態的追博弈存在平穩納什均衡策略,并構建逃逸者的混合狀態MDP 與最優貝爾曼方程;第3 節給出求解追逃問題平穩策略的算法;第4 節通過數值仿真與對比,驗證本文方法的有效性;第5 節是全文總結.

符號說明.Rm表示m維歐幾里得空間;ei表示第i個元素為 1,其余為 0 的列向量;‖·‖ 表示歐幾里得范數;? (A) 表示在集合A上概率測度的集合.

1 問題描述

本文研究N對1 追逃問題,將N個追捕者表示為Pi,i=1,···,N,其中P1是領導者,其余為跟隨者,逃逸者表示為E.令第i個追捕者和逃逸者在k階段的位置分別為Pi(k) 和E(k).具體描述如下:

1) 環境: 如圖1 所示,二維地圖環境由不規則邊界和障礙物組成.追逃雙方均可獲知環境信息,且追捕群體和逃逸者都被禁止觸碰邊界與障礙物.

圖1 追逃問題環境Fig.1 Environment of pursuit-evasion problem

2) 信息: 追捕群體僅領導者配備測距傳感器,用于測量其與逃逸者間的相對距離d(P1,E)=‖P1-E‖,追捕群體間可共享此信息與各自的位置;而逃逸者具有全局視野,可獲得追捕群體的定位信息.為方便起見,假設即使被障礙物遮擋,領導者仍可測量相對距離.

3)捕獲條件:k階段任意一個追捕者與逃逸者間的相對距離小于設定值?,即d(Pi(k),E(k))=‖Pi(k)-E(k)‖

4) 速度與方向約束: 使用vPi(k) 表示第i個追捕者在階段k的速度,vPi(k)∈VP:={=1,···,M1}.類似地,逃逸者速度為vE(k)∈VE:={=1,···,M2}.追逃雙方運動速度具有以下約束: a) 不同追捕者每階段可選擇不同速度;b) 追捕群體和逃逸者在每階段中的速度是常數;c)此外,追捕者與逃逸者移動方向的選擇被限定為D1和D2個,即

5) 目標: 追捕群體目標為盡快捕捉到逃逸者,而逃逸者目標為避免被追捕群體抓獲.

注 1.論述4) 中的約束b) 限定了雙方在每階段中使用勻速運動進行追逃.當需考慮變速運動的情況時,可通過在動作集中引入額外的加速度來實現,這只會擴大雙方的動作集,對本文結論并無本質影響.上述追逃問題被定義在二維環境中,但通過改變相應動作與狀態,可直接將本文結果擴展到三維.

2 非完全信息追逃問題

本節針對此追逃問題,給出基于信念區域狀態的連續隨機博弈框架與馬爾科夫決策過程.其中第2.1 節通過對環境進行區域分割以估計逃逸者的位置,并令跟隨者采取包圍行動;第2.2 節建立連續隨機博弈框架求解追捕策略,并證明了此博弈平穩納什均衡策略的存在性;第2.3 節建立基于混合狀態的馬爾科夫決策過程與相應最優貝爾曼方程求解逃逸策略.

2.1 信念區域狀態和重心距離

由于追捕群體無法對逃逸者作出定位,因此對地圖進行分割以估計逃逸者位置.如圖2(a) 所示,在地圖中沿橫向和縱向作平行線,將其分割成L個區域.令逃逸者所處的區域作為狀態,則狀態集合S:={s1,···,sL,si=ei,i=1,···,L},其中si表示第i個區域.但僅通過測距仍無法獲知其具體狀態,因此引入信念區域狀態.

圖2 (a) L 個區域;(b) 追捕群體的劃分Fig.2 (a) L regions;(b) Division of pursuit group

定義 1.信念區域狀態集合B=?(S) 表示在區域狀態集合B上的概率分布集合,則k時刻下信念區域狀態Bk ∈B表示追捕群體對逃逸者所處區域的概率估計.

追捕群體使用信念區域狀態估計逃逸者位置,然而跟隨者未配備測距傳感器,無法測量自身與逃逸者間的距離,因此它們在追捕過程中使用包圍的方式來協助領導者達到捕獲的目的.為實現包圍,將追捕群體劃分為多個三角形,每個跟隨者Pi與其最近的兩個跟隨者及領導者構成兩個三角形,即Pi和P1是兩個三角形的公共點.如圖2(b),跟隨者P4與P2、P3以及領導者P1形成三角形△P4P1P2和△P4P1P3.整個追捕群體可構成f個三角形,其中f的取值如下

根據追捕群體位置可計算出所有三角形的重心Gi,i=1,···,f.需要注意的是,如果某一跟隨者Pi與任意一個鄰居以及領導者P1共線,則相應的三角形重心變為線段重心.

定義第i個重心與領導者間的距離為重心距離,即 ‖Gi(k)-P1(k)‖,i=1,···,f.顯然每個跟隨者均存在兩個與自身相關的重心距離.可知當三角形重心越接近上述以領導者位置P1(k) 為圓心,相對距離d(P1(k),E(k)) 為半徑的圓,跟隨者包圍效果越好.因此每階段任意跟隨者Pi都試圖最小化相應的兩個重心距離與d(P1(k),E(k)) 的差值.令此差值為?i,顯然其與跟隨者的移動方向和速度相關.

此外,為避免追逃雙方觸碰邊界及障礙物,引入如圖3 中所示的黃色警戒區域.地圖邊界的警戒區域是沿邊界向內延伸相應智能體的一步最大距離,即;而障礙物的警戒區域則是向外延伸相應一步最大距離.由于追逃雙方知道環境信息和自身位置,因此警戒區域的信息是公開的.第2.2 節將通過對警戒區域內智能體獎勵的設置,來規避其碰撞邊界及障礙物的風險.

圖3 警戒區域Fig.3 Warning area

圖4 第 m 個區域Fig.4 The m -th area

2.2 基于信念區域狀態的追博弈

由于雙方獲知的位置信息不對稱,因此追捕群體借助信念區域狀態引入一個想象逃逸者,由此建立連續隨機追博弈來求解追捕策略.

其次,k階段基于信念區域狀態Bk和想象逃逸者的概率動作,可計算出區域狀態轉移概率 Pr(sn|sm,).即在概率動作下,追捕群體認為想象逃逸者從狀態sm(第m個區域)到sn(第n個區域)的概率為

信念區域狀態更新機制.

基于區域狀態轉移概率 P r(sn|sm,) 與測量距離d(P1(k),Eˉ(k)),可進行信念區域狀態的更新,其分為修正與估計兩個過程.具體來說,追捕群體根據測量距離對信念區域狀態進行后驗修正,再使用P r(sn|sm,)估計下一階段的信念區域狀態.為給出信念區域狀態修正機理,做出如下定義.

定義 2.假設逃逸者均勻分布在區域m中,k階段的預測距離表示追捕群體和逃逸者分別做出純動作后,逃逸者與領導者間的期望距離.

基于預測距離與相對距離兩者間的差異來修正信念區域狀態.如圖5 所示,令領導者與想象逃逸者在k階段做出動作前的位置分別為和(x,y),因此預測距離為

圖5 預測距離Fig.5 Prediction distance

令k階段的信念區域狀態為Bk=b,則k階段逃逸者位于m區域的先驗概率為

令k階段追捕群體的純動作為aP,想象逃逸者的概率動作為,做出此動作后領導者與想象逃逸者之間的距離為dk=d(P1(k),(k)).基于此,可獲取信念區域狀態的后驗概率,即

引理 1.k階段信念區域狀態的后驗概率為

證明.根據信念區域狀態后驗概率的定義,可得

第三個等式由貝葉斯公式得出,其中Pr(sm,dk|b,aP,) 表示在信念區域狀態b下,追捕群體與逃逸者分別做出動作aP,后,逃逸者位于m區域以及其與領導者間的距離為dk的概率;使用條件概率公式可得第四個等式;根據式 (4),可知逃逸者位于m區域的先驗概率值僅與b有關,因此Pr(sm|b,aP,)=Pr(sm|b)=b(sm),所以第五個等式成立.

對于 P r(dk|sm,b,aP,),其值與預測距離和測量距離間的差異有關,即

基于區域狀態轉移概率可獲取下一信念區域狀態,因此k+1 階段的信念區域狀態Bk+1為

其中 P r(sn|sm,) 為式 (2).

連續隨機追博弈框架.

信念區域狀態的轉移滿足馬爾科夫特性[38].將追捕群體視為一個整體,并且由于信念區域狀態與追捕群體位置的連續性,因此可建立由六元組組成的基于信念區域狀態的連續隨機博弈G=(I,A,U,,T,R).不失一般性,假設所有追捕者和逃逸者是完全理性的,并且互相知道其他人是完全理性的[15].以下是追博弈六元組具體信息.

1) 參與人: 令I={} 表示理性玩家集合,其中P={Pi,i=1,···,N} 和分別表示追捕者群體和想象逃逸者.

2) 動作:A=AP×表示在追捕群體和逃逸者純動作集上的聯合概率分布集合,其中元素σ=(σP,)∈A被稱為追捕群體和逃逸者的聯合概率動作.

3) 聯合狀態: 聯合狀態集合U={Pos,B} 由追捕群體位置集合Pos和信念區域狀態集合B組成,其中Pos=(XP,YP) 為追捕群體橫坐標與縱坐標集合.

4) 聯合狀態修正概率: 根據修正機制可得聯合狀態修正概率,即()=Pr(==u,Ak=σ,d(P(k),(k))=dk),這表示k階段基于測量距離dk,聯合概率動作σ ∈A,狀態u ∈U轉移到修正狀態u?∈U的概率.

5) 聯合狀態轉移概率: 根據k階段聯合概率動作σ ∈A,已修正的聯合狀態∈U轉移到下一聯合狀態u′∈U的概率為T(u′|)=Pr(Uk+1=u′|==σ).

其中γ1∈{0, 1} 表示領導者是否觸碰邊界及障礙物,若領導者發生碰撞則受到懲罰φ.跟隨者Pi單階段收益為

其中γi ∈{0, 1} 表示跟隨者是否觸碰邊界及障礙物,?i(aP)表示跟隨者的包圍目標.追捕群體的損失為想象逃逸者的收益,因此逃逸者單階段收益為

根據追博弈框架中聯合狀態修正概率與轉移概率定義,可得出如下引理.

引理2.k階段聯合概率動作為σ={σP,},聯合狀態u轉移到下一狀態u′概率為

證明.由更新機制可知狀態u轉移到u′分為兩個部分: 修正與更新,并且聯合狀態u′={pos′,b′},={pos,},pos ∈Pos,pos′∈Pos,b ∈B,b′∈B.因此u轉移到u′的概率為

其中聯合狀態的修正過程只涉及到信念區域狀態b,因此如下等式成立

同時,修正過程僅與領導者純動作有關,所以基于想象逃逸者概率動作與測量距離dk,將式(15)轉化為

然后在狀態更新過程中,追捕群體位置狀態pos與信念區域狀態b是互相獨立的,因此

其中第二個等式中 Pr(pos′|pos,,σP,) 為追捕群體的位置狀態轉移概率,由于位置狀態只與追捕群體自身動作有關,因此Pr(pos′|pos,,σP,)=σP(aP);而 Pr(b′|pos,,σP,) 則表示修正的信念區域狀態到下一階段狀態的轉移概率,由于追捕群體無法獲知想象逃逸者的純動作,因此使用全概率公式,由此第三個等式成立.

令連續隨機博弈G中平穩策略為π={πP,},其表示聯合狀態到聯合動作的映射,即π:U →A.則在聯合狀態u下,π(u) 實際上是在追捕群體和想象逃逸者聯合純動作空間AP×上的概率分布.設初始聯合狀態為u0,在平穩策略π下追捕群體目標函數表達式如下

其中 0<ρ<1 為折扣因子.根據想象逃逸者獎勵函數定義,它的收益是追捕群體的損失,因此

定義 3.若存在一個平穩策略π?={πP?,}使得追捕群體與想象逃逸者累積期望收益分別滿足

則稱π?是博弈G的平穩納什均衡策略[15].

追捕群體與想象逃逸者都是最大化自身累積收益的理性參與人,因此解決此最大化問題就轉變為尋求連續隨機博弈G的平穩納什均衡策略問題,定理1 證明了此博弈存在平穩納什均衡策略.

定理 1.追博弈G存在平穩納什均衡策略.

證明.追捕群體使用平穩策略π,k階段聯合狀態為u,獲得聯合概率動作σ,可寫出追捕群體的折扣收益

其中JP(u′) 表示聯合狀態為u′時追捕群體的累積期望收益,σ={σP,}.將轉移概率 (13) 代入,因此等式二成立;在當前聯合狀態u確定時,下一聯合狀態u′由追捕群體與想象逃逸者的純動作決定,且追逃雙方純動作集有限,則下一聯合狀態u′是有限的,因此等式三成立.

由于區域狀態集合S是有限集,它的子集是有限的.令S為在區域狀態集合上的 B orel-σ代數,則S中具有有限個元素,同時在S上定義一個概率測度p,因此 (S,S,p) 表示概率測度空間.(S,S,p) 的任意開覆蓋都存在有限子覆蓋,因此概率測度空間(S,S,p)是一個緊度量空間,上文定義信念區域狀態集合B是S上的概率分布集合,由此可知B是一個緊度量空間.類似地,可證得連續隨機博弈中動作空間AP和也是緊度量空間.又因為坐標空間Pos是二維有限連續區域,也為緊度量空間,而聯合狀態空間U={Pos,B} 是Pos空間與B空間的乘積,因此U是緊度量空間.

因此Q(JP(u)) 是連續有界的,即算子Q是自映射的.又折扣因子 0<ρ<1,容易看出算子Q是M(u) 上的一個壓縮映射.又空間M(u) 是所有有界Borel函數的集合,因此其是完備度量空間.根據Banach 不動點定理[39],算子Q存在一個唯一的不動點JP?(u),并且滿足.

AP和分別是集合AP和上面的概率分布,因此AP和分別是M1D1和M2D2維單純型,顯然它們是緊凸集.并且零和博弈下,(u,·,·) 是雙線性函數,即FP(u,·,·) 在AP上是凸的,在上是凹的,根據最大最小定理得

而平穩策略π是聯合狀態空間U到動作空間A的可測映射,根據選擇定理[39],可知

注 3.本文采取連續隨機博弈框架與分級制決策過程的主要原因是,追捕群體無法獲得逃逸者位置信息,而逃逸者則擁有全局信息,追逃雙方信息不對稱.追捕群體通過引入想象逃逸者來構建基于信念區域狀態的連續隨機博弈框架,以此實現自身利益最大化.逃逸者由于信息占優,可在獲取追捕群體均衡策略的基礎上,進一步通過構建馬爾科夫框架求解最優策略.

經典貝葉斯博弈亦可處理本文追逃問題,然而每階段最多會產生種區域狀態,并且追逃過程是多階段持續進行的,因此k階段可能出現與成比例的狀態數量,這顯然會導致維度災難.故本文使用基于信念區域狀態的隨機博弈以避免此類情況發生.

2.3 逃逸者的決策過程

與追捕群體使用連續隨機博弈不同,由于真實逃逸者具有全局信息,因此它的最優策略求解可轉變為一個馬爾科夫決策過程.真實逃逸者純動作集與想象逃逸者相同,AE=,用AE=?(AE) 表示AE上的概率分布.用四元組,,>表示MDP,具體如下.

1) 混合狀態: 混合狀態H={U,PosE},由追博弈中聯合狀態U與逃逸者自身坐標PosE組成.

2) 動作:=AP×AE表示決策過程中的動作空間,概率動作={σP,σE}∈為動作空間中的元素,其中σE ∈AE.

3) 混合狀態轉移概率:k階段概率動作∈,則混合狀態h ∈H轉移到下一階段狀態h′∈H的概率為(h′|h,)=Pr(Hk+1=h′|Hk=h,k=).

4) 收益: 令rE(h,)=rE(h,σP,σE) 表示逃逸者的期望收益,由與所有追捕者的相對距離和環境的觸碰懲罰組成.

其中,d(Pi,E) 表示任意追捕者Pi與逃逸者間的相對距離,γE∈{0, 1} 表示逃逸者是否觸碰地圖邊界及障礙物.

令逃逸者平穩策略為πE,它是混合狀態H到動作空間AE的映射.在給定混合狀態h時,πE(h)實際上等價于當前狀態下的概率動作σE.基于連續隨機博弈的追捕群體最優策略πP?,給出逃逸者的累積收益函數

逃逸者尋求自身累積收益最大化,令πˇ?={πP?,πE?}表示最優平穩策略,即滿足

為獲得馬爾科夫決策過程中的相應的貝爾曼最優方程[38],給出如下定義

其中Q(h,σP?,σE) 表示狀態動作對價值函數,h為k時刻下的混合狀態,h′為下一時刻的混合狀態,JE?(h′) 為逃逸者在狀態h′下的期望累積收益.

引理 3.逃逸者的最優貝爾曼方程為

證明.由于概率動作={σP?,σE},狀態h={u,posE},h′={u′,pos′E},其中posE ∈PosE為k時刻下逃逸者的位置,pos′E ∈PosE為下一時刻的位置,因此混合狀態h轉移到下一狀態h′的概率為

由于聯合狀態u的轉移只與追捕群體與想象逃逸者的策略有關,因此第四個等式成立.將式(29)代入式(27) 可得

由于當前狀態posE與u確定,所以下一狀態是由追捕群體與逃逸者的純動作決定,等式三成立.

3 策略求解

本節基于強化學習算法MAPPO (Multi-agent proximal policy optimization)[40],給出了追捕群體平穩納什均衡策略與逃逸者最優策略的求解算法.與傳統算法相比,M APPO 主要基于中心化訓練,去中心化執行,每個智能體都具有單獨的Actorcritic 結構.并且目標函數在訓練中進行小批量更新,既避免了過多策略更新,又提高了訓練穩定性.

真實逃逸者具有全局信息,根據追捕群體的平穩納什均衡策略πP?,進行MDP 最優策略求解.同理,逃逸者可定義出等參數,并不斷更新網絡,直至找到最優策略.

算法1 是追逃問題中追捕群體與逃逸者最優平穩策略的求解過程,第1)行到第14)行求解連續隨機博弈中追捕群體的平穩納什均衡策略.為通過數據抽樣實現智能體的策略更新,將T條包含狀態、動作、獎勵、優勢函數以及值函數的序列分別存入追捕者與逃逸者記憶庫中,即第8)行所示.同時,為提高數據的可用性與訓練效率,進行K次更新,如第9)行所示.基于策略,可進行逃逸策略的求解,即第15)行到第24)行.類似地,第19)行表示將序列存入記憶庫中.

算法 1.最優平穩追逃策略求解算法.

4 數值仿真

本節通過三對一的案例來說明本文方法有效性.仿真環境為Windows10,搭載的CPU 為AMD Ryzen 4800H,顯卡為AMD Radeon Graphics 512 MB.基于Python3.6 搭建封閉二維空間,同時使用Pytorch1.8 深度學習框架進行訓練.追逃環境尺寸及障礙物如圖6 所示,環境中存在三個黑色障礙物,逃逸者為紅色質點E,追捕群體為藍色質點P1,P2,P3.環境地圖被切割為16 個區域,區域狀態集為S={s1,···,s16},相應的信念區域狀態是一個16 維的向量.追捕者運動方向被均勻劃分為8 個:東、東南、南、西南、西、西北、北、東北;運動速度有兩種: 0.4 m/s,0.5 m/s,因此結合靜止動作,所有追捕者均可采取17 個動作.逃逸者運動方向與追捕者一致,而運動速度有三種: 0.4 m/s,0.5 m/s,0.6 m/s,因此結合靜止動作,逃逸者可采取25 個動作.不失一般性,令追捕群體與逃逸者的初始位置分別在地圖的四個方位內隨機產生.抓捕成功的最短距離?設置為追捕群體的最短步長,即0.4 m.

圖6 地圖尺寸Fig.6 Size of map

為獲取追逃問題的最優策略,使用算法1 進行求解.在此算法中 A ctor 網絡與 C ritic 網絡使用兩個全連接層作為隱藏層,每層神經元個數分別為64,32,神經網絡使用 A dam 的梯度更新方式,學習率為0.000 1.算法中追捕群體與逃逸者的記憶庫均為500,策略更新次數K=20,折扣因子ρ=0.99,切割系數?=0.2.此外,對追逃問題重復訓練20 000局,每一局最多運行400 個階段,這樣的訓練獨立進行20 次.

追捕策略的訓練過程如圖7 所示,紅色曲線為追捕群體的平均累積收益曲線,陰影為其訓練方差.可從圖中看出,追捕群體累積收益呈上升趨勢,在訓練10 000 局時逐漸趨于收斂.同時未采取信念修正的追捕訓練效果如圖7 藍色曲線所示.由圖可知,追捕群體收益收斂后約為 -360,而未修正的收益約為 -420,修正狀態的收益提升了近 15%,且紅色陰影小于藍色陰影,即修正狀態的追捕訓練更為穩定.

圖7 追博弈中追捕群體的收益Fig.7 Pursuits＇ reward in the pursuit game

逃逸者策略的訓練過程如圖8 所示,其中紅色曲線為逃逸者的平均累積收益,陰影為其訓練方差.從圖中可以看出逃逸者的收益在13 000 局時趨于收斂,最終穩定,收益約為380.而藍色曲線為未修正狀態的收益,穩定收益約為500.修正狀態的收益較未修正的低了近 3 0%,則使用修正狀態的逃逸者弱于未修正的,即修正狀態的追捕群體強于未修正的.同時兩條曲線方差陰影的對比,說明了使用修正狀態的訓練過程更為穩定.

圖8 MDP 中逃逸者的收益Fig.8 Evader＇s reward in MDP

經統計,訓練完成后追捕群體捕獲成功的平均步數為41 步左右,成功率為 9 5%;未進行狀態修正的追捕群體其捕獲成功的平均步數為43 步,成功率為 8 7%,較修正機制下低了 8 %,可見使用測量距離進行信念修正是行之有效的.為進一步展示追捕訓練的效果,在上述計算最優策略過程中,每隔100 局保存一次模型,即保存了200 個不同模型.同時,對每個模型進行1 000 局的追捕測試,具體測試結果如圖9 所示.從圖中可以看出,隨著逃逸者訓練的進行,其逃脫能力逐步上升,因此被成功捕捉步數相應增加,當對訓練至15 000 局時保存的模型進行測試時,成功捕獲步數已基本趨于穩定.

圖9 算法測試過程Fig.9 Algorithm testing process

為了驗證本文方法的優越性,使用如下幾種算法進行對比: MAPPO[40],MASAC[41],MADDPG[42],幾何估計追捕[33],基于三角定位追捕[34],至少一人全局視野追捕[23],自動追蹤追捕[36],自適應切換追捕[37]以及隨機策略.在對比中,固定所有算法中的逃逸者策略(本文算法1 所求得的逃逸策略).同時為了適應此三對一的例子,對上述部分算法做相應改進,具體如下.

1)幾何估計追捕算法: 文獻[33]聚焦一對一追逃問題,為適應本算例,將其改寫為三對一追捕問題,即追捕群體共享領導者所估計到的位置.

2) 基于三角定位的追捕算法: 文獻[34]中追捕者利用信標,也就是說使用了額外的傳感器對逃逸者進行定位.然而本文中不存在信標,為進行定位,準許每個階段中領導者移動三次,以三次不同的測距信息進行定位,并將此信息共享給跟隨者.

3)自動追蹤追捕算法與自適應切換追捕算法:文獻[36]和[37]研究了一對一追逃問題,為適應本文算例,將其改寫為三對一追捕問題,即所有追捕者均使用距離與距離變化率構建模型以求解追捕策略.

表1 記錄了使用不同算法的追逃測試結果.從此表中發現,當使用MAPPO、MASAC、MADDPG 算法時,智能體進行不斷地試錯與學習,雖具有一定的訓練效果,但由于以上三種算法均未對距離信息進行有效的利用與處理,導致捕獲平均步數較高,并且抓捕成功率低.其中MADDPG 算法使用同策略,并且因為以確定性策略的方式,無法獲得隨機均衡策略,而MAPPO 與MASAC 算法均使用異策略,并且采取了隨機策略的方式,所以捕獲步數多于其余兩種算法.本文決策機制雖基于PPO算法,但其結果優越性主要源于建立了基于信念區域狀態的博弈框架與馬爾科夫決策過程,從表1 可知與僅使用MAPPO 相比,本文算法捕獲平均步數減少了43 步,成功率提高了 3 6%.

表1 結果對比Table 1 Result comparison

同時,幾何估計追捕算法[33]的成功率較本文算法低 2 3%,且所花費的步數是本文算法的近兩倍,可見在本文環境下,該算法對逃逸者的位置估計效果較差.而使用三角定位的追捕算法[34]可精準定位逃逸者的位置,因此捕捉成功率與本文算法接近,但由于追捕群體為獲得定位所需信息,進行了額外的運動,因此抓捕步數多于本文算法.至少一人全局視野的追捕算法[23]在視野范圍內使用了最優追捕策略,使得捕獲成功率較高,但對于視野范圍外的情況,追捕群體沒有作出更為有效處理,從而捕獲步數高出本文算法21 步.并且,通過距離與距離變化率求解追捕策略的自動追蹤算法[36]與自適應切換追捕算法[37],均未直接對逃逸者的位置做估計定位,導致追捕效果較差.最后使用隨機策略進行測試,與預期一致,由于追捕群體未采取任何智能策略而導致其效果最差.此外,通過對比可知,即使是未進行信念狀態修正的本文算法,其測試效果仍優于絕大部分對比算法,體現了使用博弈框架求解平穩納什均衡策略的有效性.

最后,在本文算法的多次測試中隨機抽取4 局,畫出追逃雙方的運動軌跡圖,如圖10 所示.圖中藍色三角形與紅色三角形分別表示為追逃雙方的初始位置,藍色圓點與紅色圓點則分別代表追捕群體與逃逸者的運動軌跡,顏色越深,代表軌跡越新.從圖中看出追捕群體都在朝向逃逸者對其形成合圍之勢,而逃逸者為逃脫追捕,整體運動過程均朝著追捕群體相反的方向運動.

圖10 追捕群體與逃逸者的運動軌跡圖Fig.10 Trajectories of pursuits and evader

5 結論

本文針對僅有距離信息的多智能體追逃問題,提出了一種基于連續隨機博弈與馬爾科夫決策過程的最優策略求解方法.在求解追捕策略中,為了彌補位置信息的缺失,通過引入信念區域狀態對逃逸者位置進行估計,并且使用測量距離對信念區域狀態進行修正.由此搭建了基于信念區域狀態的連續隨機博弈,并證明了此博弈平穩納什均衡策略的存在性.在求解逃逸者策略時,根據追捕群體的最優策略與混合狀態,建立了最優貝爾曼方程,并給出了基于強化學習的追逃策略求解算法.通過與已有算法的對比,驗證了本文方法的有效性.此外,通過追逃群體間簡單的任務分配,可將本文算法直接應用于多對多的追捕問題.但如何在圍捕過程中構建有效的智能體交互與任務切換機制,以實現多對多環境下的高效追捕還有待于進一步研究.