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

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

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

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

在導彈打擊、無人機對抗等實際場景中,通常要考慮存在目標的追逃問題.此時,攻擊者相對于目標扮演追捕者的角色,相對于防御者扮演逃跑者的角色.因此,攻擊者在抓捕目標的同時需要避免被防御者攔截,防御者在保護目標的同時力圖捕獲攻擊者.當目標為靜態(tài)時,該問題轉(zhuǎn)化為兩人博弈問題.Pachter 等研究了相同速度下攻擊者和防御者的追逃問題[9].Venkatesan 等給出了不同速度下攻擊者和防御者的最優(yōu)策略,并分析了防御者捕獲半徑非零的情形[10].當目標為動態(tài)時,Li 等基于線性二次型微分博弈,獲得了目標固定、目標以任意軌跡運動及目標采取逃跑策略時攻擊者與防御者的最優(yōu)策略[11].Garcia 等采用零和博弈的框架處理主動目標防御問題,以攻擊者和目標的終端距離作為性能函數(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īng)典的Hamilton-Jacobi-Isaacs方法相結(jié)合,獲得了每個攻擊者和防御者相應的最優(yōu)狀態(tài)反饋策略[15].Coon 等考慮了任意數(shù)量攻擊者和防御者的場景,通過等時線的交點確定防御者是否可以成功攔截攻擊者,最后給出了攻擊者在偏離預定軌跡時仍能被捕獲的充分條件[16].Chipade 等結(jié)合估計函數(shù)方法優(yōu)化目標函數(shù),利用Lyapunov 方法獲得了攻擊者、防御者的最優(yōu)策略[17].Yan等通過構(gòu)建界柵劃分多個追捕者、單個逃跑者的勝利區(qū)域,并結(jié)合任務分配和整數(shù)規(guī)劃算法,最大化追捕者捕獲逃跑者的數(shù)量[18].Garcia 等將微分博弈理論與任務分配算法相結(jié)合來研究多個追捕者、多個逃跑者的邊界防御問題,求解出了追逃雙方的最優(yōu)策略[19].Sin 等考慮了多個防御者合作攔截多個攻擊者的目標防御問題,給出了目標沿固定軌跡運動時攻防雙方的最優(yōu)策略,但未考慮攻擊者、防御者各自內(nèi)部的通信問題[20].以上研究通常涉及任務分配,在智能體規(guī)模較大時,求解較為困難.

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

基于以上的分析討論,本文主要研究基于線性二次型微分博弈的多個攻擊者、多個防御者和單個目標的追逃問題.首先,針對攻擊者、防御者保持聚合狀態(tài)的情形,分別給出了目標按固定軌跡運動和目標采取逃跑運動時攻防雙方的最優(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是實對稱負定(半負定)矩陣;?表示對稱矩陣中的對稱塊; b lkdiag{A1,···,An} 表示分塊對角矩陣,其主對角線上為方塊矩陣A1,···,An;‖x‖表示向量x的歐幾里得范數(shù),;A?B表示矩陣A和矩陣B的Kronecker 積.

1 問題描述

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

1.1 系統(tǒng)通信拓撲的圖描述

定義 1.有向圖Gd=(Vd,Ed) 表示防御方的通信拓撲,其中,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) 表示攻擊方的通信拓撲,其中,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) 為有向圖,表示攻擊方和防御方之間的通信拓撲,其中,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.

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

1.2 目標沿固定軌跡運動時的攻防博弈建模

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

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

目標沿固定軌跡運動的狀態(tài)方程如下:

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

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

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

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

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

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

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

2 主要結(jié)果

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

2.1 目標沿固定軌跡運動時的攻防雙方的最優(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 目標采取逃跑運動時的博弈

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

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

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

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

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

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

3 仿真

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

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

3.1.1 目標沿固定軌跡運動

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

圖1 防御者通信拓撲Fig.1 The communication topology of defendes

圖2 攻擊者通信拓撲Fig.2 The communication topology of attackers

圖3 防御者與攻擊者之間的通信拓撲Fig.3 The communication topology between defendes and attackers

間的通信拓撲關(guān)系,相應的鄰接矩陣分別為:

假設目標沿固定軌跡做正弦運動,目標狀態(tài)為

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

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

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

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

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

圖4 攻擊者勝利時目標、攻擊者、防御者的運動軌跡Fig.4 Trajectories of the target,attackers and defenders when attackers win

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

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

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

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

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

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

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

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

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

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

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

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

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

3.1.2 目標采取逃跑運動

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

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

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

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

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

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

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

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

目標狀態(tài)為

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

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

4 結(jié)論

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