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

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

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

0 引言

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

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

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

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

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

V

和

V

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

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

(1)

(2)

當(dāng)

V

≥

V

時(shí)，防御方一定會(huì)將攻擊方提前捕獲。本文討論

V

<

V

的情況，并用

α

=

V

/V

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

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

圖2 三者相對(duì)位置關(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ū)域時(shí)，攻擊方先采取式(6)、式(7)的策略躲避防御方的Apollonius圓，然后直接打擊到目標(biāo)，這一過(guò)程稱為迂回策略。

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

T

，即

R

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

T

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

R

=0,

r

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

T

前就與目標(biāo)

T

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

T

。

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

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

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

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

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

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

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

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

S

,

S

,

S

,

S

表示。

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

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)攻防問(wèn)題的分類

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

D

D

等價(jià)，因此將這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)會(huì)合的策略，攻擊方無(wú)論采取何種策略都無(wú)法改變結(jié)果。2.1.3

S

:

C

-

R

-

P/R

-

C

-

P

圖

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

圖7 兩個(gè)Apollonius圓相切Fig.7 Two Apollonius circles are tangent

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

(8)

W

,

W

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

(9)

同樣，將

D

的運(yùn)動(dòng)離散化，在每個(gè)離散時(shí)間Δ

t

，其下一時(shí)刻的位置由

D

1,+1=

Round

-

About

(

A

,

D

1,)得出，

RoundAbout

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

D

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

AD

的Apollonius圓與

AD

的Apollonius圓相切?？梢缘玫匠跏紩r(shí)兩圓最近點(diǎn)之間的距離表達(dá)式

(10)

其中,

用最速下降法求解下一步

D

的運(yùn)動(dòng)方向，梯度向量和步長(zhǎng)為

(11)

Δ

t

為離散步長(zhǎng)，故

D

的迭代方程為

D

2,+1=

D

2,+

sd

()

(12)

2.1.4

S

:

S

-

R

-

R/R

-

S

-

R

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

D

單獨(dú)去攔截攻擊方

A

，而

D

直接朝向目標(biāo)與其會(huì)合，這樣的結(jié)果就是防御方獲勝，因?yàn)楣舴讲捎糜鼗夭呗詻](méi)有比

D

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

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

2.2 生成決策樹(shù)模型

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

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

(13)

(14)

(15)

式中，

H

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

T

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

H

代表初始時(shí)刻

T

>

T

是否成立，其中

T

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

T

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

H

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

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

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

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

Gain

(

A

,

S

)=

Info

(

S

)-

Info

(

A

,

S

)

(16)

式中，

A

為某個(gè)屬性，

S

為整個(gè)樣本集合。

Info

(

S

)表示確定

S

中一個(gè)元素的類別所需要的信息量，

Info

(

A

,

S

)表示在已知屬性

A

的取值后，確定

S

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

(17)

(18)

式中，

p

為樣本集合

S

中第

i

類樣本所占比例，|

S

|是子集

S

的記錄個(gè)數(shù)。

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

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

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

Gain

(,

S

)=0

.

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

Gain

(,

S

)=0

.

98，第3輪中

Gain

(,

S

)=0

.

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

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

圖11 決策樹(shù)模型Fig.11 Decision tree model

3 舉例決策樹(shù)模型的應(yīng)用

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

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

目標(biāo)點(diǎn)位于

T

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

T

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

(19)

(20)

(21)

通過(guò)計(jì)算可知

(22)

所以

H

=0。

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

S

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

D

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

A

和一個(gè)防御方

D

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

D

位于攻擊方

A

和目標(biāo)

T

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

A

和一個(gè)防御方

D

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

(a) t=0 s

(b) t=58.5 s

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

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

例2 目標(biāo)位于

Apollonius

圓內(nèi)

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

同樣按照決策樹(shù)模型的測(cè)試順序。首先計(jì)算

H

，很容易得到

(23)

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

AD

的Apollonius圓內(nèi)，故

H

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

S

。

D

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

圖13 D1直接與T會(huì)合Fig.13 D1rendezvous directly with T

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

4 總結(jié)與展望

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

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

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

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