基于決策樹的多防御方目標(biāo)攻防決策

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

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

0 引言

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

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

1 多防御方目標(biāo)攻防問題

1.1 多防御方目標(biāo)攻防問題模型

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

V

和

V

，將攻擊方和防御方的速度方向角度設(shè)為其控制變量，其運(yùn)動學(xué)方程如下

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

(1)

(2)

當(dāng)

V

≥

V

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

V

<

V

的情況，并用

α

=

V

/V

表示兩者的速度關(guān)系。

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

圖2 三者相對位置關(guān)系Fig.2 The relative position of the three agents

(3)

(4)

(5)

由Liang等研究成果得出，

A

，

D

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

(6)

(7)

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

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

T

，即

R

>0。與此相反，攻擊方盡可能打擊到目標(biāo)

T

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

R

=0,

r

>0。如果防御方能夠在攻擊方打擊到目標(biāo)

T

前就與目標(biāo)

T

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

T

。

1.2 多防御方目標(biāo)攻防的復(fù)雜性

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

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

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

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

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

2 多防御方目標(biāo)攻防問題的決策樹分類模型

為了搭建決策樹模型，首先需要對多防御方的目標(biāo)攻防問題進(jìn)行分類并確定分類的標(biāo)簽。這里將各方的策略作為分類的標(biāo)準(zhǔn)，以初始時刻的各方態(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表示采用直接朝向目標(biāo)方向策略，RoundAbout表示采用式(6)、式(7)的策略，Parall表示攻擊方采用平行四邊形法則后的策略，Cooperation表示防御方采取合作策略，為了方便都使用首字母進(jìn)行代替。

2.1 多防御方目標(biāo)攻防問題的分類

2.1.1

S

:

A

-

A

-

S

圖

2.1.2

S

:

S

-

A

-

A/A

-

S

-

A

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

D

D

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

(a)

(b)

(c)圖5 目標(biāo)在Apollonius圓內(nèi)Fig.5 The target is within the Apollonius circle

類為

S

:

S

-

A

-

A/A

-

S

-

A

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

S

:

C

-

R

-

P/R

-

C

-

P

圖

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

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

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

(8)

W

,

W

是基于距離威脅的權(quán)重

(9)

同樣，將

D

的運(yùn)動離散化，在每個離散時間Δ

t

，其下一時刻的位置由

D

1,+1=

Round

-

About

(

A

,

D

1,)得出，

RoundAbout

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

D

的目標(biāo)是盡快使

AD

的Apollonius圓與

AD

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

(10)

其中,

用最速下降法求解下一步

D

的運(yùn)動方向，梯度向量和步長為

(11)

Δ

t

為離散步長，故

D

的迭代方程為

D

2,+1=

D

2,+

sd

()

(12)

2.1.4

S

:

S

-

R

-

R/R

-

S

-

R

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

D

單獨去攔截攻擊方

A

，而

D

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

D

直接與目標(biāo)會合更快。

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

2.2 生成決策樹模型

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

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

(13)

(14)

(15)

式中，

H

代表初始時刻目標(biāo)

T

是否在Apollonius圓內(nèi)；

H

代表初始時刻

T

>

T

是否成立，其中

T

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

T

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

H

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

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

表1 訓(xùn)練樣本集合

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

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ù)。

對樣本集合進(jìn)行信息增益計算，每輪計算都選出信息增益最高的作為測試屬性，如圖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 舉例決策樹模型的應(yīng)用

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

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

目標(biāo)點位于

T

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

T

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

(19)

(20)

(21)

通過計算可知

(22)

所以

H

=0。

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

S

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

D

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

A

和一個防御方

D

時，目標(biāo)完全暴露在攻擊方的視線之內(nèi)，攻擊方只要采取直線朝向目標(biāo)進(jìn)攻即可打擊到目標(biāo)獲得勝利。

D

位于攻擊方

A

和目標(biāo)

T

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

A

和一個防御方

D

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

(a) t=0 s

(b) t=58.5 s

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

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

例2 目標(biāo)位于

Apollonius

圓內(nèi)

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

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

H

，很容易得到

(23)

所以初始時刻，目標(biāo)位于

AD

的Apollonius圓內(nèi)，故

H

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

S

。

D

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

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

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

4 總結(jié)與展望

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

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

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

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