基于微分博弈的追逃問題最優(yōu)策略設(shè)計

劉 坤 鄭曉帥 林業(yè)茗 韓 樂 夏元清

在追逃問題中,智能體需要完成追擊或防御任務(wù),如多無人機(jī)對抗[1]、飛行器軌跡規(guī)劃[2]、無人機(jī)打擊[3]等.近年來,追逃問題受到了廣泛的關(guān)注,Zhou等利用維諾圖分割區(qū)域的方法研究了有限區(qū)域內(nèi)多個追捕者對單個逃跑者的抓捕[4],De Simone 等利用模型預(yù)測控制方法研究了存在障礙物的追逃問題[5].博弈論易于建立不同博弈者之間的策略交互模型,且博弈者的策略選擇過程即是系統(tǒng)內(nèi)部的合作或競爭過程.因此,利用博弈論的方法研究追逃問題逐漸成為熱點[6-8].

在經(jīng)典的追逃問題中,系統(tǒng)包含兩組對立的博弈者,一組博弈者作為追捕者,另一組博弈者作為逃跑者.Isaacs 利用微分博弈方法研究了單個追捕者、單個逃跑者的追逃問題,通過定性微分博弈方法獲得了追逃雙方的勝利區(qū)域,并求解出了追逃雙方的最優(yōu)策略[6].進(jìn)一步,Fang 等研究了單個逃跑者和多個追捕者的追逃博弈問題[7],Lin 等研究了有限觀測信息下的追逃微分博弈問題[8].

在導(dǎo)彈打擊、無人機(jī)對抗等實際場景中,通常要考慮存在目標(biāo)的追逃問題.此時,攻擊者相對于目標(biāo)扮演追捕者的角色,相對于防御者扮演逃跑者的角色.因此,攻擊者在抓捕目標(biāo)的同時需要避免被防御者攔截,防御者在保護(hù)目標(biāo)的同時力圖捕獲攻擊者.當(dāng)目標(biāo)為靜態(tài)時,該問題轉(zhuǎn)化為兩人博弈問題.Pachter 等研究了相同速度下攻擊者和防御者的追逃問題[9].Venkatesan 等給出了不同速度下攻擊者和防御者的最優(yōu)策略,并分析了防御者捕獲半徑非零的情形[10].當(dāng)目標(biāo)為動態(tài)時,Li 等基于線性二次型微分博弈,獲得了目標(biāo)固定、目標(biāo)以任意軌跡運(yùn)動及目標(biāo)采取逃跑策略時攻擊者與防御者的最優(yōu)策略[11].Garcia 等采用零和博弈的框架處理主動目標(biāo)防御問題,以攻擊者和目標(biāo)的終端距離作為性能函數(shù),給出了各智能體的閉環(huán)最優(yōu)狀態(tài)反饋策略并得到了博弈的值函數(shù)[12].Liang 等采用定性微分博弈方法,以勝利時間作為性能函數(shù),獲得了基于界柵的雙方最優(yōu)策略和最優(yōu)軌跡[13].以上結(jié)果僅僅考慮了單個攻擊者、單個防御者的情形.

針對多個攻擊者或防御者,Casbeer 等討論了兩個防御者、一個攻擊者的情形,給出了雙方的最優(yōu)策略和安全區(qū)域[14].Chen 等考慮了數(shù)量相同的攻擊者和防御者在有障礙物的二維區(qū)域內(nèi)進(jìn)行博弈,將目標(biāo)分配算法與經(jīng)典的Hamilton-Jacobi-Isaacs方法相結(jié)合,獲得了每個攻擊者和防御者相應(yīng)的最優(yōu)狀態(tài)反饋策略[15].Coon 等考慮了任意數(shù)量攻擊者和防御者的場景,通過等時線的交點確定防御者是否可以成功攔截攻擊者,最后給出了攻擊者在偏離預(yù)定軌跡時仍能被捕獲的充分條件[16].Chipade 等結(jié)合估計函數(shù)方法優(yōu)化目標(biāo)函數(shù),利用Lyapunov 方法獲得了攻擊者、防御者的最優(yōu)策略[17].Yan等通過構(gòu)建界柵劃分多個追捕者、單個逃跑者的勝利區(qū)域,并結(jié)合任務(wù)分配和整數(shù)規(guī)劃算法,最大化追捕者捕獲逃跑者的數(shù)量[18].Garcia 等將微分博弈理論與任務(wù)分配算法相結(jié)合來研究多個追捕者、多個逃跑者的邊界防御問題,求解出了追逃雙方的最優(yōu)策略[19].Sin 等考慮了多個防御者合作攔截多個攻擊者的目標(biāo)防御問題,給出了目標(biāo)沿固定軌跡運(yùn)動時攻防雙方的最優(yōu)策略,但未考慮攻擊者、防御者各自內(nèi)部的通信問題[20].以上研究通常涉及任務(wù)分配,在智能體規(guī)模較大時,求解較為困難.

為了便于求解大規(guī)模問題,Li 等考慮了追逃雙方之間的通信,將基于圖論的控制律引入追逃問題,但僅獲得了追逃雙方的局部最優(yōu)策略[21].在有些實際場景中,要求博弈的某一方內(nèi)部的所有智能體在保持聚合狀態(tài)的同時完成一定的任務(wù),即保持較近的距離,從而保證彼此的通信連接.Mejia 等討論了一組追捕者追捕一組逃跑者的情形,基于通信拓?fù)鋱D考慮了有限時間捕獲和漸近會合情況,給出了追逃雙方在各自聚合狀態(tài)下的納什均衡策略和最大最小策略,但僅考慮了追逃兩方之間的博弈[22].

基于以上的分析討論,本文主要研究基于線性二次型微分博弈的多個攻擊者、多個防御者和單個目標(biāo)的追逃問題.首先,針對攻擊者、防御者保持聚合狀態(tài)的情形,分別給出了目標(biāo)按固定軌跡運(yùn)動和目標(biāo)采取逃跑運(yùn)動時攻防雙方的最優(yōu)策略.然后,針對攻擊者、防御者保持分散狀態(tài)的情形,采用二分圖最大匹配算法為防御者匹配攻擊者,將多個攻擊者、多個防御者的追逃問題轉(zhuǎn)化為多組兩人零和微分博弈,求解出了攻防雙方的最優(yōu)策略.最后,數(shù)值仿真驗證了所提策略的有效性.

符號說明. R 表示實數(shù)域; Rn表示n維實數(shù)列向量組成的集合; Rn×m表示n×m維實數(shù)矩陣組成的集合;In表示n×n維的單位矩陣; 0m×n表示m×n維的零矩陣;AT表示矩陣A的轉(zhuǎn)置;A-1表示矩陣A的逆;M表示鄰接矩陣;A?0(A?0) 表示矩陣A是實對稱正定(半正定) 矩陣;A?0(A?0) 表示矩陣A是實對稱負(fù)定(半負(fù)定)矩陣;?表示對稱矩陣中的對稱塊; b lkdiag{A1,···,An} 表示分塊對角矩陣,其主對角線上為方塊矩陣A1,···,An;‖x‖表示向量x的歐幾里得范數(shù),;A?B表示矩陣A和矩陣B的Kronecker 積.

1 問題描述

本文中,追逃博弈問題考慮存在目標(biāo)、攻擊者和防御者三方,攻擊者試圖攻擊目標(biāo),而防御者試圖攔截攻擊者以阻止其攻擊目標(biāo).當(dāng)攻擊者捕獲目標(biāo)或者防御者成功攔截攻擊者時,博弈結(jié)束.攻擊方的任務(wù)是在保持聚合狀態(tài)的同時攻擊目標(biāo),而防御方的任務(wù)在保持聚合狀態(tài)的同時保護(hù)目標(biāo),攔截攻擊方.

1.1 系統(tǒng)通信拓?fù)涞膱D描述

定義 1.有向圖Gd=(Vd,Ed) 表示防御方的通信拓?fù)?其中,Vd={1,2,···,m} 表示m個防御者的集合,Ed ?Vd×Vd表示防御方內(nèi)部邊的集合.對于邊 (i,p),其權(quán)重為αip≥0.防御者i在圖Gd中的鄰居集合用Nd(i) 來表示.定義Dd為關(guān)聯(lián)矩陣,Wd為權(quán)重矩陣,那么圖Gd的Laplacian 矩陣為Ld=定義2.有向圖Ga=(Va,Ea) 表示攻擊方的通信拓?fù)?其中,Va={1,2,···,l} 表示l個攻擊者的集合.Ea ?Va×Va表示攻擊者內(nèi)部邊的集合.賦予邊 (j,q) 權(quán)重值βjq≥0.攻擊者j在圖Ga中的鄰居集合用Na(j) 來表示.定義Da為關(guān)聯(lián)矩陣,Wa為權(quán)重矩陣,那么圖Ga的Laplacian 矩陣為La=

定義3.二分圖G=(V,E) 為有向圖,表示攻擊方和防御方之間的通信拓?fù)?其中,V=Vd ∪Va={1,2,···,m,m+1,···,m+l} 表示m個防御者和l個攻擊者的集合,E?V×V表示雙方之間邊的集合.圖G=(V,E) 只包含攻防雙方之間的通信而不包含各自內(nèi)部的通信.邊 (p,q) 表示防御者p可以獲取攻擊者q的信息,賦予其權(quán)重γpq≥0;反之,邊(q,p) 表示攻擊者q可以獲取防御者p的信息.智能體r在圖G中的全部鄰居用集合N(r) 來表示.定義D為關(guān)聯(lián)矩陣,W為權(quán)重矩陣,那么圖G的Laplacian 矩陣為L=DWDT.

假設(shè) 1.對于追逃博弈問題,假設(shè)攻擊方、防御方都能獲取目標(biāo)的狀態(tài)信息,且能夠獲取鄰居的狀態(tài)信息.圖Gd=(Vd,Ed) 和Ga=(Va,Ea) 都是連通圖.

1.2 目標(biāo)沿固定軌跡運(yùn)動時的攻防博弈建模

下面對攻防雙方在保持各自聚合狀態(tài),目標(biāo)沿固定軌跡運(yùn)動時的追逃博弈問題進(jìn)行建模.

防御方具有m個防御者,其狀態(tài)方程如下:

目標(biāo)沿固定軌跡運(yùn)動的狀態(tài)方程如下:

防御方需要在保持聚合狀態(tài)的同時保護(hù)目標(biāo),并攔截攻擊方.因此,防御者i需要優(yōu)化的加權(quán)距離可以表示為:

其中,第一項是防御者i與其鄰居Nd(i) 的距離加權(quán)和,為防御者聚合項,第二項是防御者i與其可以觀測到的攻擊者N(i) 的距離加權(quán)和,第三項為防御者i可以觀測到的攻擊者N(i) 和目標(biāo)T的距離之和.

加權(quán)距離式(6)可以轉(zhuǎn)化為如下形式:

類似地,攻擊方的任務(wù)是在保持聚合狀態(tài)的同時捕獲目標(biāo).因此,攻擊者j需要優(yōu)化的加權(quán)距離可以表示為:

其中,第一項是攻擊者j與其鄰居Na(j) 的距離加權(quán)和,為攻擊者聚合項,第二項是攻擊者j與其可以觀測到的防御者N(j) 的距離加權(quán)和,第三項為攻擊者j與目標(biāo)T的距離.

加權(quán)距離式(8)可以轉(zhuǎn)化為如下形式:

在博弈過程中,每個智能體需要最小化自己的成本函數(shù),用v-i表示防御者i可觀測到的所有攻擊者策略的加權(quán)和,即:

2 主要結(jié)果

本節(jié)首先給出目標(biāo)按固定軌跡運(yùn)動時的攻防雙方的最優(yōu)策略,并進(jìn)一步設(shè)計目標(biāo)采取逃跑運(yùn)動時的攻防雙方的最優(yōu)策略.然后,針對攻防雙方保持分散狀態(tài)的情形,采用二分圖最大匹配算法為防御者匹配攻擊者,將多個攻擊者、多個防御者的追逃問題轉(zhuǎn)化為多組兩人零和微分博弈進(jìn)行求解.

2.1 目標(biāo)沿固定軌跡運(yùn)動時的攻防雙方的最優(yōu)策略

根據(jù)式(5)、式(10)和式(11)博弈模型,下面定理給出攻擊者、防御者雙方在保持各自聚合狀態(tài)下的最優(yōu)狀態(tài)反饋策略.

定理 1.考慮系統(tǒng)(5),防御者i和攻擊者j的成本函數(shù)分別為式(10)和式(11),那么,防御者i的最優(yōu)策略

2.2 目標(biāo)采取逃跑運(yùn)動時的博弈

下面考慮目標(biāo)可以控制自身狀態(tài)來躲避攻擊者的攻擊,即目標(biāo)也參與博弈,選擇自己的策略,其狀態(tài)方程如下:

2.3 攻擊者、防御者分散狀態(tài)下的追逃策略

當(dāng)攻擊方?jīng)]有保持聚合狀態(tài),而是選擇分散狀態(tài)進(jìn)行攻擊時,相應(yīng)地,防御方也采取分散狀態(tài)對攻擊者進(jìn)行攔截.此時,每個防御者需要提前選擇自己的攔截對象.本節(jié)研究攻擊者、防御者分散狀態(tài)下各自的最優(yōu)策略,設(shè)計的策略適用于攻擊者數(shù)量小于等于防御者數(shù)量(l≤m)的情形,為簡單起見,只考慮目標(biāo)靜止時的博弈.

在本節(jié)中,用二分圖G來描述攻擊者與防御者之間的通信拓?fù)?假設(shè)個體間通信是雙向的,那么,防御者可以采用二分圖的最大匹配算法[24]為自己選定攔截對象,防御者只能攔截自己可以觀測到的攻擊者.

當(dāng)防御者選定自己的攔截對象后,多攻擊者、多防御者追逃問題轉(zhuǎn)化為多組兩人零和博弈的情形.對于防御者i,假設(shè)匹配的攻擊者為j,定義zs=,則有:

不失一般性,假設(shè)目標(biāo)點在原點,即xT=[0,···,0]T∈R2n,那么,防御者需要優(yōu)化的加權(quán)距離可以表示為:

3 仿真

在本節(jié)中,首先選取防御者和攻擊者數(shù)量為m=3,l=3,分別給出聚合狀態(tài)下防御者勝利和攻擊者勝利兩種情況下雙方及目標(biāo)的運(yùn)動軌跡,并分析成本函數(shù)中權(quán)重系數(shù)的影響.進(jìn)一步,分別考慮防御者和攻擊者數(shù)量為m=5,l=3 和m=3,l=5的情形.同時,給出目標(biāo)采取逃跑運(yùn)動時的博弈結(jié)果.最后,考慮防御者、攻擊者分散狀態(tài)下的追逃策略.每個智能體均采用雙積分動力學(xué)模型.此外為了便于計算,成本函數(shù)中的R-i,Ri,R-j,Rj均取對應(yīng)維數(shù)的單位矩陣.

3.1 防御者、攻擊者聚合狀態(tài)下的追逃問題策略仿真

3.1.1 目標(biāo)沿固定軌跡運(yùn)動

考慮防御者數(shù)量m=3,攻擊者數(shù)量l=3.圖1～3 分別給出了防御者、攻擊者內(nèi)部和兩方之

圖1 防御者通信拓?fù)銯ig.1 The communication topology of defendes

圖2 攻擊者通信拓?fù)銯ig.2 The communication topology of attackers

圖3 防御者與攻擊者之間的通信拓?fù)銯ig.3 The communication topology between defendes and attackers

間的通信拓?fù)潢P(guān)系,相應(yīng)的鄰接矩陣分別為:

假設(shè)目標(biāo)沿固定軌跡做正弦運(yùn)動,目標(biāo)狀態(tài)為

當(dāng)目標(biāo)被捕獲或所有攻擊者被攔截,提前終止博弈.設(shè)置防御者攔截半徑和攻擊者捕獲半徑都為0.2 m,采樣時間為0.05 s,終端時間tf為10 s,權(quán)重系數(shù)為:

其中,i∈Vd={1,2,3},j∈Va={1,2,3}.

設(shè)置防御者的初始狀態(tài)為:

攻擊者的初始狀態(tài)為:

根據(jù)定理1 中的最優(yōu)策略式(14)和式(15),以及注1 中的求解過程,可以得到如圖4 所示防御者、攻擊者和目標(biāo)的運(yùn)動軌跡.博弈結(jié)果為攻擊者3 在未被防御者攔截的前提下成功捕獲目標(biāo),攻擊者取得勝利.

圖4 攻擊者勝利時目標(biāo)、攻擊者、防御者的運(yùn)動軌跡Fig.4 Trajectories of the target,attackers and defenders when attackers win

在保持式(37)中權(quán)重系數(shù)不變的情況下,改變防御者和攻擊者的初始狀態(tài),設(shè)置防御者初始狀態(tài)為:

攻擊者初始狀態(tài)為:

根據(jù)定理1 中的式(14)和式(15)得到防御者勝利的博弈結(jié)果,三方的運(yùn)動軌跡如圖5 (a)所示.

進(jìn)一步,研究式(37)中防御者和攻擊者的權(quán)重系數(shù)變化對仿真結(jié)果的影響,分別調(diào)整權(quán)重系數(shù)(參數(shù)分別表示攻擊者和防御者的聚合程度,效果相似,此處省略分析),得到防御者、攻擊者和目標(biāo)的運(yùn)動軌跡圖5 (b)～5 (f),以及攻防雙方的成本函數(shù)圖6 (b)～6 (f).通過圖5 (a)和5 (b)、圖6 (a)和6 (b)可以看出,減小權(quán)重系數(shù),即防御者聚合程度降低,相應(yīng)地防御者攔截攻擊者的重視程度相對提高,使得防御者攔截時間縮短,攻擊者成本函數(shù)增大.通過圖5 (a)和5 (c)、圖6 (a)和6 (c)可以看出,減小權(quán)重系數(shù),即防御者對攔截攻擊者的重視程度降低,使得防御者攔截時間明顯增加,攻擊者與目標(biāo)間距離增大,相應(yīng)地攻擊者成本函數(shù)增大.通過圖5 (a)和5 (d)、圖6 (a)和6 (d)可以看出,增大權(quán)重系數(shù),即防御者對阻止攻擊者攻擊目標(biāo)的重視程度提高,使得防御者在攔截攻擊者的同時讓攻擊者遠(yuǎn)離目標(biāo),攔截時間增加,攻擊者成本函數(shù)增大.

通過圖5 (a)和5 (e)、圖6 (a)和6 (e)可以看出,增大權(quán)重系數(shù),即攻擊者對躲避防御者的重視程度提高,攻擊者與防御者之間的距離增大,使得防御者攔截時間明顯增加,防御者的成本函數(shù)快速增大.由于攻擊者與目標(biāo)之間的距離增大,防御者成本函數(shù)相應(yīng)地減小.最后,通過圖5 (a)和5 (f)、圖6 (a)和6 (f)可以看出,增大權(quán)重系數(shù),即攻擊者對攻擊目標(biāo)的重視程度提高,使得攻擊者成功地在防御者攔截前捕獲目標(biāo).由于攻擊者在接近目標(biāo)的同時減小了與防御者之間的距離,防御者成本函數(shù)相應(yīng)地減小.

圖5 防御者勝利時權(quán)重系數(shù)調(diào)整目標(biāo)、攻擊者、防御者的運(yùn)動軌跡Fig.5 Trajectories of the target,attackers and defenders with different weight coefficients when defendes win

圖6 防御者勝利時權(quán)重系數(shù)調(diào)整目標(biāo)、攻擊者、防御者的成本函數(shù)Fig.6 Cost functions of the target,attackers and defenders with different weight coefficients when defendes win

上述考慮的是防御者和攻擊者數(shù)量相等,進(jìn)一步討論數(shù)量不等時的情形.在不改變雙方權(quán)重系數(shù)式(37)的前提下,考慮m=3,l=5 的情形,此時通信拓?fù)鋱D的鄰接矩陣分別為:

設(shè)置防御者的初始狀態(tài)為:

攻擊者的初始狀態(tài)為:

如圖7 所示,由于攻擊者數(shù)量的增加,防御者無暇顧及攔截所有的攻擊者,最終攻擊者3 順利捕獲目標(biāo).類似地,考慮m=5,l=3 即防御者數(shù)量多于攻擊者的情況.如圖8 所示,防御者在保持聚合的基礎(chǔ)上,在距離目標(biāo)較遠(yuǎn)的位置攔截所有攻擊者.

圖7 m=3,l=5 時目標(biāo)、攻擊者、防御者的運(yùn)動軌跡Fig.7 Trajectories of the target,attackers and defenders with m=3,l=5

圖8 m=5,l=3 時目標(biāo)、攻擊者、防御者的運(yùn)動軌跡Fig.8 Trajectories of the target,attackers and defenders with m=5,l=3

3.1.2 目標(biāo)采取逃跑運(yùn)動

考慮m=3,l=3 的防御者和攻擊者數(shù)量,當(dāng)目標(biāo)采取逃跑策略時,選取式(37) 中的權(quán)重系數(shù),防御者的初始狀態(tài)為:

攻擊者的初始狀態(tài)為:

逃跑者的初始狀態(tài)為:

目標(biāo)采取逃跑行動的博弈結(jié)果如圖9 所示,在初始時刻攻擊者處于目標(biāo)和防御者之間的位置.在運(yùn)動過程中,目標(biāo)朝著三個攻擊者聚合的反方向逃跑,使得防御者順利地實現(xiàn)對攻擊者的攔截.

圖9 目標(biāo)采取逃跑行動時目標(biāo)、攻擊者、防御者的運(yùn)動軌跡Fig.9 Trajectories of the target,attackers and defenders when the target adopts an escape strategy

3.2 防御者、攻擊者分散狀態(tài)下的追逃問題策略仿真

當(dāng)攻擊者采取分散狀態(tài)進(jìn)行攻擊時,參數(shù)設(shè)置如下:博弈時域選擇tf=3 s,權(quán)重系數(shù)為:

其中,s={1,2,3}.系統(tǒng)初始狀態(tài)為:

目標(biāo)狀態(tài)為

首先,采用二分圖的最大匹配算法為每個防御者匹配攔截對象此時,最優(yōu)分配方案為防御者1 攔截攻擊者1,防御者2 攔截攻擊者3,防御者3 攔截攻擊者2.通過終端值Ps(tf) 進(jìn)行反向迭代,可以得到對應(yīng)Riccati 方程的解.最后,可以得到最優(yōu)策略下智能體的運(yùn)動軌跡如圖10 所示.此時,防御者1在坐標(biāo)點 (－0.3,－0.1) 成功攔截了攻擊者1,防御者2 在坐標(biāo)點 (0.5,－0.3) 成功攔截了攻擊者3,防御者3 在坐標(biāo)點 (－0.2,0.4) 成功攔截了攻擊者2,三個防御者分別成功攔截了自己匹配到的攻擊者,攻擊方勝利.

圖10 防御者、攻擊者分散狀態(tài)下攻擊者、防御者的運(yùn)動軌跡Fig.10 Trajectories of attackers and defenders when defenders and attackers stay distributed

4 結(jié)論

本文采用線性二次型微分博弈的方法研究了追逃博弈問題.首先,當(dāng)攻防雙方保持各自聚合狀態(tài),分別設(shè)計了目標(biāo)按固定軌跡運(yùn)動和目標(biāo)采取逃跑行動時攻防雙方的最優(yōu)策略.其次,當(dāng)攻防雙方保持分散狀態(tài),采用二分圖最大匹配算法為防御者匹配攻擊者,將多個攻擊者、多個防御者的追逃問題題轉(zhuǎn)化為多組兩人零和微分博弈,求解出了攻防雙方的最優(yōu)策略.最后,數(shù)值仿真驗證了所提方法的有效性.在追逃問題中,隨著攻防雙方個體增多,拓?fù)浣Y(jié)構(gòu)更加復(fù)雜,大規(guī)模數(shù)據(jù)將會增加網(wǎng)絡(luò)的通信負(fù)擔(dān)和系統(tǒng)的計算負(fù)擔(dān).而云控制系統(tǒng)[26]利用云計算高效的運(yùn)算能力,具有實時性強(qiáng)、可靠性高等優(yōu)點.因此,未來可以考慮將上述算法擴(kuò)展到云控制系統(tǒng).本文在分析攻防雙方分散狀態(tài)下的追逃博弈問題時,只考慮了防御者數(shù)量大于或等于攻擊者的場景.未來可以研究當(dāng)攻擊者數(shù)量大于防御者時,具有一定優(yōu)勢的防御者需要連續(xù)攔截多個攻擊者的情形.