闕養(yǎng)華，冮鐵強，陳立杰

(廈門大學航空航天學院，廈門 361000)

0 引言

目標攻防博弈(Target Strike and Defense)不同于一般的追逃博弈，因為此時博弈的各方角色已經(jīng)發(fā)生了變化。攻擊方的任務是在確保自身安全的前提下打擊到目標，而防御方的任務是保護目標不被攻擊方打擊，并且嘗試在攻擊方打擊到目標前將其攔截。這些變化使得對目標攻防博弈的求解變得更困難。Isaacs在其著作《Differential games》中提到了一個簡單的目標攻防問題。Boyell在導彈合作作戰(zhàn)的背景下分析了這類情況。Ratnoo等和Shima提出防御方使用視線引導策略攔截攻擊導彈。Zhang等研究了逃避者試圖穿過兩個追捕者之間的博弈問題，利用定性微分對策推導出界柵的存在，并得出逃避者和捕獲者的最優(yōu)策略。Liang等在此基礎上將其中一個捕獲者換成防御的目標，形成了三方(目標、攻擊方、防御方)目標攻防問題，給出了界柵和各方的最優(yōu)策略。Casbeer等、Garcia等和Shaferman等還研究了其他各種合作方式的目標攻防問題。目前來看，目標攻防研究集中在防御方時的防守問題，對于多防御方的目標攻防問題目前研究較少。當增加若干個防御方后，各防御方如何通過合作來達到任務的要求是當前需要解決的重點，這也是本文研究的多防御方目標攻防問題(Multi-Defender Target Strike and Defense)。

由于防御方數(shù)量增加，此時博弈的復雜度也提高了，因此引入決策樹的思想將復雜的多防御方目標攻防問題轉換成易于理解的決策樹模型。決策樹是一種基本的分類和回歸方法，在分類問題中表示基于特征對實例進行分類的過程，分類模型是if-then規(guī)則的集合。決策樹的分類模型比較符合人類的推理并且易于理解。決策樹還具有分類速度快，模型具有可讀性的優(yōu)點。決策樹算法的核心以ID3和C4.5算法為主，分別利用信息增益和信息增益率的大小來選擇分類的候選屬性，直到所有樣本都完全分完為止。復雜的多防御方目標攻防問題一般很難直接確定各方需要采取的最佳策略，例如防御方是否需要采取合作策略，是否可以直接與目標會合。因此,各方?jīng)Q策的內部邏輯還需要進一步梳理清楚，以達到更快的態(tài)勢判斷和決策選擇。

1 多防御方目標攻防問題

1.1 多防御方目標攻防問題模型

多防御方目標攻防問題的模型如圖1所示。假設目標是靜止的，攻擊方和防御方的速度均為常速，分別為

V

和

V

，將攻擊方和防御方的速度方向角度設為其控制變量，其運動學方程如下

圖1 多防御方攻防問題模型Fig.1 The model of multi-defender strike and defense

(1)

(2)

當

V

≥

V

時，防御方一定會將攻擊方提前捕獲。本文討論

V

<

V

的情況，并用

α

=

V

/V

表示兩者的速度關系。

為了簡潔描述目標攻防博弈，以一個防御方為例，將三者間的相對關系作為狀態(tài)量，如圖2所示，新的方程可以寫成

圖2 三者相對位置關系Fig.2 The relative position of the three agents

(3)

(4)

(5)

由Liang等研究成果得出，

A

，

D

的最優(yōu)控制策略為

(6)

(7)

由Liang等研究成果得出，當攻擊方初始狀態(tài)位于攻擊方獲勝區(qū)域時，攻擊方先采取式(6)、式(7)的策略躲避防御方的Apollonius圓，然后直接打擊到目標，這一過程稱為迂回策略。

考慮攻擊方和防御方的捕獲半徑為零。防御方的目標是阻止攻擊方打擊到目標

T

，即

R

>0。與此相反，攻擊方盡可能打擊到目標

T

，并且還不能被防御方攔截到，即

R

=0,

r

>0。如果防御方能夠在攻擊方打擊到目標

T

前就與目標

T

會合，也認為是防御方獲勝，因為此時攻擊方已經(jīng)不可能在確保自身安全的前提下打擊到目標

T

。

1.2 多防御方目標攻防的復雜性

對抗博弈問題中討論和研究最多的是雙方博弈，當博弈的數(shù)量增加到3個及以上時，問題的難度和性質都會發(fā)生變化。隨著博弈參與方數(shù)量的增加，對抗博弈需要考慮的因素也增加，某一方無法像雙方博弈時把注意力都只關注于對方，此時還需考慮其他參與方對自身的影響。由Liang等研究成果可知，當只考慮一個防御方進行攔截時，各方的最優(yōu)策略只需要通過攻擊方初始時的位置即可判斷得出。當防御方增多時，問題就變得復雜。

當多個防御方參與目標攻防時，防御方除了能夠攔截攻擊方，還可以通過與其他的防御方進行配合，以完成單個防御方無法完成的任務，這也叫做“能力涌現(xiàn)”現(xiàn)象。

如圖3所示，有的防御方選擇合作，而有的防御方就會乘機在其他防御方一起去合作攔截攻擊方的時候，選擇直接與目標會合。這種群體所體現(xiàn)出來的智能行為無法再通過簡單的單個參與方初始位置來判斷。因此，本文提出引入決策樹的思想對復雜的多防御方目標攻防問題的各方?jīng)Q策進行合理且快速的判斷。為了應用決策樹思想，需要對參與方的決策類別進行討論。

圖3 防御方群體智能行為Fig.3 Swarm Intelligence behavior of defenders

本文對兩個防御方的目標攻防問題的決策進行討論，說明在多防御方目標攻防問題中決策樹的使用。首先通過訓練樣本集合訓練決策樹模型，再通過測試樣本驗證模型的準確性。

2 多防御方目標攻防問題的決策樹分類模型

為了搭建決策樹模型，首先需要對多防御方的目標攻防問題進行分類并確定分類的標簽。這里將各方的策略作為分類的標準，以初始時刻的各方態(tài)勢作為測試屬性來搭建決策樹模型。根據(jù)不同初始時刻態(tài)勢，可以將各方的策略分為4類，分別用

S

,

S

,

S

,

S

表示。

注意到防御方的地位是等價的，所以各方策略的分類表示為：

S

:

S

-

S

-

S

，

i

=1,2,3,4。

S

和

S

表示防御方的策略，

S

表示攻擊方的策略。具體的策略(以字母

S

表示)中，Arbitrary表示任意策略，Straight表示采用直接朝向目標方向策略，RoundAbout表示采用式(6)、式(7)的策略，Parall表示攻擊方采用平行四邊形法則后的策略，Cooperation表示防御方采取合作策略，為了方便都使用首字母進行代替。

2.1 多防御方目標攻防問題的分類

2.1.1

S

:

A

-

A

-

S

圖

2.1.2

S

:

S

-

A

-

A/A

-

S

-

A

如圖5所示，當目標位于Apollonius圓內時，防御方可以直接朝向目標會合，此時攻擊方無論采取何種策略都無法改變防御方獲勝的結果。攻擊方最好的辦法也只能是盡可能靠近目標，以期對目標造成最大的威脅。從圖5中可以看到，這類情況有3種，分別是目標位于某一個防御方的Apollonius圓內和位于兩個防御方的Apollonius圓交集內。由于

D

D

等價，因此將這3類情況分

(a)

(b)

(c)圖5 目標在Apollonius圓內Fig.5 The target is within the Apollonius circle

類為

S

:

S

-

A

-

A/A

-

S

-

A

，表示某一防御方采取直線朝向與目標會合的策略，攻擊方無論采取何種策略都無法改變結果。2.1.3

S

:

C

-

R

-

P/R

-

C

-

P

圖

為了充分發(fā)揮防御方數(shù)量上的優(yōu)勢，提出一種合作策略，讓防御方的目標變成使得其各自的Apollonius圓相切。如圖7所示，黑色虛線圓代表初始狀態(tài)的Apollonius圓，紅色虛線圓代表相切時的狀態(tài)。Apollonius圓相切后使攻擊方無法直接通過兩個防御方之間的空間，只能繞行更大的范圍來達到摧毀目標的目的，從而增加了攻擊方的燃料消耗。

圖7 兩個Apollonius圓相切Fig.7 Two Apollonius circles are tangent

圖8 平行四邊形合成Fig.8 Parallelogram composition

(8)

W

,

W

是基于距離威脅的權重

(9)

同樣，將

D

的運動離散化，在每個離散時間Δ

t

，其下一時刻的位置由

D

1,+1=

Round

-

About

(

A

,

D

1,)得出，

RoundAbout

策略由公式(6)和(7)確定。

D

的目標是盡快使

AD

的Apollonius圓與

AD

的Apollonius圓相切。可以得到初始時兩圓最近點之間的距離表達式

(10)

其中,

用最速下降法求解下一步

D

的運動方向，梯度向量和步長為

(11)

Δ

t

為離散步長，故

D

的迭代方程為

D

2,+1=

D

2,+

sd

()

(12)

2.1.4

S

:

S

-

R

-

R/R

-

S

-

R

除了使防御方的Apollonius圓相切外，另一種合作方式比較直觀，某一防御方盡可能地拖住攻擊方，另外一個防御方直接與目標會合。如圖9所示，

D

單獨去攔截攻擊方

A

，而

D

直接朝向目標與其會合，這樣的結果就是防御方獲勝，因為攻擊方采用迂回策略沒有比

D

直接與目標會合更快。

圖9 D2直接與目標會合，D1攔截攻擊方AFig.9 Defender turns directly with the target

2.2 生成決策樹模型

決策樹分類模型依據(jù)分類指標進行劃分，由根到葉的順序進行劃分，包含一個根節(jié)點、若干個內部節(jié)點和葉節(jié)點。

對抗開始時，根據(jù)多防御方目標攻防問題的初始態(tài)勢，將不同的初始態(tài)勢進行分類特征值得計算，具體如下

(13)

(14)

(15)

式中，

H

代表初始時刻目標

T

是否在Apollonius圓內；

H

代表初始時刻

T

>

T

是否成立，其中

T

表示某一防御方計算其直接與目標會合時需要的時間，

T

表示另一防御方計算單獨拖延攻擊方時攻擊方能夠打擊到目標的時間；

H

表示初始時刻攻擊方與目標之間是否被Apollonius圓擋住。

決策樹模型的構建需要通過一定數(shù)量的訓練樣本進行訓練。樣本集合通過隨機選取不同的初始坐標位置，確定不同初始位置時的攻防雙方策略組合而獲得，訓練樣本中包含初始狀態(tài)參量、分類特征值、分類標簽，訓練樣本如表1所示。

表1 訓練樣本集合

決策樹分類算法中ID3算法依據(jù)信息增益作為測試屬性選擇標準來構造決策樹。信息增益的計算如下

Gain

(

A

,

S

)=

Info

(

S

)-

Info

(

A

,

S

)

(16)

式中，

A

為某個屬性，

S

為整個樣本集合。

Info

(

S

)表示確定

S

中一個元素的類別所需要的信息量，

Info

(

A

,

S

)表示在已知屬性

A

的取值后，確定

S

中一個元素的類別所需的信息量。其定義分別如下

(17)

(18)

式中，

p

為樣本集合

S

中第

i

類樣本所占比例，|

S

|是子集

S

的記錄個數(shù)。

對樣本集合進行信息增益計算，每輪計算都選出信息增益最高的作為測試屬性，如圖10所示，直到樣本集中所有分類都被完全分好為止。

圖10 每次各屬性的信息增益計算Fig.10 Information gain calculation for each attribute each time

由圖10可知，第1輪對3個屬性分別計算其信息增益，最大值的是

Gain

(,

S

)=0

.

98，所以首先選擇作為測試屬性。以此類推，第2輪中

Gain

(,

S

)=0

.

98，第3輪中

Gain

(,

S

)=0

.

81，經(jīng)過3輪計算分類后，所有的樣本都完全分類。

由此得到?jīng)Q策樹各輪的測試屬性，用來生成最終的決策樹模型。得到的決策樹模型如圖11所示。

圖11 決策樹模型Fig.11 Decision tree model

3 舉例決策樹模型的應用

例1 防御方協(xié)同配合

表2 例1的數(shù)據(jù)集

目標點位于

T

(0,-3)。攻擊方所攜帶的燃料只允許其飛行400 s。1)第一步，按照決策樹模型依次進行決策。首先計算目標

T

是否位于某一個Apollonius圓內。通過初始狀態(tài)攻擊方和防御方的位置和速度比值關系可以得到攻擊方與兩個防御方的Apollonius圓方程。

(19)

(20)

(21)

通過計算可知

(22)

所以

H

=0。

根據(jù)決策樹模型，此時已經(jīng)將結果分類出來了，在該例子中給定的初始狀態(tài)下，分類結果是

S

，防御方采取讓兩個Apollonius圓相切圍堵攻擊方進攻路線的策略。仿真模擬結果如圖12所示。初始時刻，

D

位于整個戰(zhàn)場的左邊，距離目標較遠。并且如果只有攻擊方

A

和一個防御方

D

時，目標完全暴露在攻擊方的視線之內，攻擊方只要采取直線朝向目標進攻即可打擊到目標獲得勝利。

D

位于攻擊方

A

和目標

T

之間，并且其Apollonius圓擋住了攻擊方的視線。同樣，如果只有攻擊方

A

和一個防御方

D

，攻擊方也可采取迂回策略打擊到目標點獲得勝利。所以，任何一個防御方單獨與攻擊方對抗都無法獲勝。

(a) t=0 s

(b) t=58.5 s

(c) t=400 s圖12 防御方實施合作策略Fig.12 Defenders implement cooperative strategy

兩個防御方通過協(xié)作達到圖12(b)狀態(tài)，在(b)處，新的兩個Apollonius圓相切。攻擊方此時無法再繼續(xù)通過穿越兩個防御方之間來打擊目標點的方式取得勝利，必須重新規(guī)劃新的攻擊路線。防御方通過相切的方式，延長了攻擊方的飛行時間，使得攻擊方無法在燃料耗盡前打擊到目標。

例2 目標位于

Apollonius

圓內

表3 例2的數(shù)據(jù)集

同樣按照決策樹模型的測試順序。首先計算

H

，很容易得到

(23)

所以初始時刻，目標位于

AD

的Apollonius圓內，故

H

=1。該例的初始狀態(tài)下，分類結果是

S

。

D

只要采取直線朝向目標的策略即可獲勝，不管攻擊方采取何種策略都無法改變。仿真結果如圖13所示。

圖13 D1直接與T會合Fig.13 D1rendezvous directly with T

事實上，攻擊方在一開始就意識到已經(jīng)不可能獲勝了，它只能朝著距離目標最近的點前進，以期對目標造成該情形下的最大威脅和傷害。

4 總結與展望

本文以兩個防御方的目標攻防問題為例討論了決策樹在多防御方目標攻防問題的應用。建立了問題的決策樹模型，利用決策樹思想與人們思考模式相近的優(yōu)點，達到通過快速簡單的判斷得出多防御方目標攻防問題中各方的決策策略。主要結論如下：

1)提出了一種多防御方目標攻防對抗問題中多個防御方之間的合作方式。使攻擊方、防御方Apollonius圓相切能夠有效地阻止攻擊方按照原先的路線進攻，迫使攻擊方重新規(guī)劃路線。并且利用平行四邊形法則得到受多個防御方影響后攻擊方的運動，利用了基于距離威脅的權重函數(shù)對平行四邊形法則進行加權計算。

2)利用決策樹的思想對多防御方目標攻防問題分類并決策。通過對每個候選測試屬性信息增益的計算，建立了適用于多個防御方目標攻防問題下的決策樹模型。

本文以兩個防御方作為背景說明決策樹思想在目標攻防問題上的應用，對于具有更多防御方的對抗場景，其合作方式也會變得比較復雜，因此還需要在更多防御方之間的合作方式上再進行更多的研究,但是決策樹模型的思路大體上是一致的。