基于微分博弈的追逃問題最優策略設計

劉 坤 鄭曉帥 林業茗 韓 樂 夏元清

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

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

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

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

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

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

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

1 問題描述

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

1.1 系統通信拓撲的圖描述

定義 1.有向圖Gd=(Vd,Ed) 表示防御方的通信拓撲,其中,Vd={1,2,···,m} 表示m個防御者的集合,Ed ?Vd×Vd表示防御方內部邊的集合.對于邊 (i,p),其權重為αip≥0.防御者i在圖Gd中的鄰居集合用Nd(i) 來表示.定義Dd為關聯矩陣,Wd為權重矩陣,那么圖Gd的Laplacian 矩陣為Ld=定義2.有向圖Ga=(Va,Ea) 表示攻擊方的通信拓撲,其中,Va={1,2,···,l} 表示l個攻擊者的集合.Ea ?Va×Va表示攻擊者內部邊的集合.賦予邊 (j,q) 權重值βjq≥0.攻擊者j在圖Ga中的鄰居集合用Na(j) 來表示.定義Da為關聯矩陣,Wa為權重矩陣,那么圖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) 只包含攻防雙方之間的通信而不包含各自內部的通信.邊 (p,q) 表示防御者p可以獲取攻擊者q的信息,賦予其權重γpq≥0;反之,邊(q,p) 表示攻擊者q可以獲取防御者p的信息.智能體r在圖G中的全部鄰居用集合N(r) 來表示.定義D為關聯矩陣,W為權重矩陣,那么圖G的Laplacian 矩陣為L=DWDT.

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

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

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

防御方具有m個防御者,其狀態方程如下:

目標沿固定軌跡運動的狀態方程如下:

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

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

加權距離式(6)可以轉化為如下形式:

類似地,攻擊方的任務是在保持聚合狀態的同時捕獲目標.因此,攻擊者j需要優化的加權距離可以表示為:

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

加權距離式(8)可以轉化為如下形式:

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

2 主要結果

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

2.1 目標沿固定軌跡運動時的攻防雙方的最優策略

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

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

2.2 目標采取逃跑運動時的博弈

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

2.3 攻擊者、防御者分散狀態下的追逃策略

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

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

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

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

3 仿真

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

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

3.1.1 目標沿固定軌跡運動

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

圖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

間的通信拓撲關系,相應的鄰接矩陣分別為:

假設目標沿固定軌跡做正弦運動,目標狀態為

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

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

設置防御者的初始狀態為:

攻擊者的初始狀態為:

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

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

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

攻擊者初始狀態為:

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

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

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

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

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

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

設置防御者的初始狀態為:

攻擊者的初始狀態為:

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

圖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 的防御者和攻擊者數量,當目標采取逃跑策略時,選取式(37) 中的權重系數,防御者的初始狀態為:

攻擊者的初始狀態為:

逃跑者的初始狀態為:

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

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

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

當攻擊者采取分散狀態進行攻擊時,參數設置如下:博弈時域選擇tf=3 s,權重系數為:

其中,s={1,2,3}.系統初始狀態為:

目標狀態為

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

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

4 結論

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