嚴(yán)航,付興建

(北京信息科技大學(xué) 自動(dòng)化學(xué)院,北京 100192)

0 引言

在復(fù)雜的作戰(zhàn)環(huán)境中,如何利用無(wú)人機(jī)實(shí)現(xiàn)合理的戰(zhàn)略規(guī)劃以獲取最大化的收益,已成為許多研究者探索的重點(diǎn)問題。

在無(wú)人機(jī)的路徑規(guī)劃方面,文獻(xiàn)[1]提出了一種修正人工勢(shì)場(chǎng)的動(dòng)態(tài)路徑規(guī)劃算法,來(lái)預(yù)測(cè)動(dòng)態(tài)障礙物的位置。文獻(xiàn)[2]在傳統(tǒng)人工勢(shì)場(chǎng)法的基礎(chǔ)上,增加了一個(gè)轉(zhuǎn)向力,來(lái)加快無(wú)人機(jī)的動(dòng)態(tài)避障過程。文獻(xiàn)[3]針對(duì)多無(wú)人機(jī)提出了一種有效的基于改進(jìn)人工勢(shì)函數(shù)的路徑規(guī)劃方法,通過引入旋轉(zhuǎn)勢(shì)場(chǎng),無(wú)人機(jī)可以有效地?cái)[脫常見的局部最小值和振蕩。文獻(xiàn)[4]將A*算法和Q-learning算法相結(jié)合,提高了無(wú)人機(jī)路徑的可靠性和安全性。文獻(xiàn)[5]提出了一種新型非線性模型預(yù)測(cè)控制方法,來(lái)預(yù)測(cè)動(dòng)態(tài)障礙物的軌跡,提前規(guī)劃無(wú)人機(jī)的航線。

在無(wú)人機(jī)的對(duì)抗博弈方面,文獻(xiàn)[6]提出了一種分布式無(wú)人機(jī)群的部署方法,制定了擁塞博弈來(lái)模擬無(wú)人機(jī)群之間的交互功能。文獻(xiàn)[7]描述了一個(gè)非線性模型預(yù)測(cè)控制器,在敵我雙方追逐博弈時(shí),預(yù)測(cè)敵機(jī)下一步的行動(dòng),為無(wú)人機(jī)提供了三個(gè)維度的規(guī)避機(jī)動(dòng)決策。文獻(xiàn)[8]建立了一個(gè)非合作攻防博弈模型,提出一種改進(jìn)的量化收益方法,準(zhǔn)確地計(jì)算包括防守方反擊收益在內(nèi)的博弈均衡,從而有效地預(yù)測(cè)敵方的攻擊動(dòng)作。文獻(xiàn)[9]研究了N-聯(lián)盟非合作博弈的納什均衡問題,提出基于極值尋求的方法來(lái)估計(jì)成本函數(shù)的梯度,以兩個(gè)無(wú)人機(jī)群在領(lǐng)土防御場(chǎng)景中的對(duì)抗分析,驗(yàn)證所提策略的有效性。

將無(wú)人機(jī)的路徑規(guī)劃和對(duì)抗博弈相結(jié)合的研究鮮有報(bào)道。本文提出一種動(dòng)態(tài)人工勢(shì)場(chǎng)法,將敵方無(wú)人機(jī)作為動(dòng)態(tài)障礙物,我方要通過敵方無(wú)人機(jī)的防區(qū),進(jìn)而兩者之間形成了動(dòng)態(tài)對(duì)抗博弈。建立敵我雙方對(duì)抗博弈模型,采用精英蟻群算法求出雙方的納什均衡策略。在納什均衡策略中,雙方無(wú)人機(jī)一旦改變策略,只會(huì)減少己方的收益。

1 問題描述

本文提出的無(wú)人機(jī)對(duì)抗博弈有兩個(gè)參與者,即參與者1為我方無(wú)人機(jī),參與者2為敵方無(wú)人機(jī)。我方的首要目標(biāo)為穿越敵方無(wú)人機(jī)的防區(qū),敵方目標(biāo)為巡邏和防守所在的防區(qū)。在敵我雙方對(duì)抗博弈的過程中,雙方都在尋找最優(yōu)的策略,使得己方收益達(dá)到最大。

在二維平面建立雙方無(wú)人機(jī)的動(dòng)力學(xué)模型為

(1)

式中:(x,y)為無(wú)人機(jī)的位置;v為無(wú)人機(jī)的速度;θ為無(wú)人機(jī)運(yùn)動(dòng)方向與x軸的夾角;ω為無(wú)人機(jī)的角速度;a為無(wú)人機(jī)的加速度。

2 動(dòng)態(tài)人工勢(shì)場(chǎng)法

人工勢(shì)場(chǎng)法由Khatib于1986年提出。該方法思想如下:設(shè)無(wú)人機(jī)在虛擬勢(shì)場(chǎng)中受到兩個(gè)力的作用,一個(gè)是目標(biāo)對(duì)其的吸引力,另一個(gè)是障礙物上的排斥力。通過兩個(gè)力之間的相互作用,無(wú)人機(jī)能夠避開環(huán)境中的障礙物,并到達(dá)目標(biāo)位置[10]。

然而,傳統(tǒng)人工勢(shì)場(chǎng)法在遇到環(huán)境中存在動(dòng)態(tài)障礙物或者目標(biāo)為移動(dòng)物體的情況時(shí),其路徑規(guī)劃和避障效果不佳[11]。本文在人工勢(shì)場(chǎng)法的基礎(chǔ)上,加入速度斥力和速度引力因素,提出動(dòng)態(tài)人工勢(shì)場(chǎng)法(dynamic artificial potential field method,DAPF)。

(2)

(3)

圖1 動(dòng)態(tài)人工勢(shì)場(chǎng)法的排斥力Fig.1 Repulsive force of dynamic artificial potential field method

則,考慮速度斥力后的排斥力公式如下:

(4)

(5)

(6)

動(dòng)態(tài)人工勢(shì)場(chǎng)法的吸引力如圖2所示,其中,吸引力及其兩個(gè)分量可以表示為

(7)

(8)

(9)

圖2 動(dòng)態(tài)人工勢(shì)場(chǎng)法的吸引力Fig.2 Attraction of dynamic artificial potential field method

3 無(wú)人機(jī)對(duì)抗博弈

本文建立的無(wú)人機(jī)對(duì)抗博弈模型,主要分為博弈參與者集合、策略集、支付函數(shù)和納什均衡策略求解四個(gè)方面。博弈參與者為動(dòng)態(tài)人工勢(shì)場(chǎng)法中介紹的敵我雙方無(wú)人機(jī)。其余三方面的內(nèi)容將在本節(jié)中介紹。

3.1 雙方無(wú)人機(jī)的策略集

設(shè)我方有n架無(wú)人機(jī),集合為{ξ1,ξ2,…,ξn},敵方有m架無(wú)人機(jī),集合為{ψ1,ψ2,…,ψm}。我方對(duì)抗?fàn)顟B(tài)為xij(i=1,2,…,n;j=1,2,…,m),xij=1表示我方無(wú)人機(jī)選擇攻擊敵方,xij=0表示我方選擇逃離該敵方防區(qū)。敵方對(duì)抗?fàn)顟B(tài)為yij(i=1,2,…,n;j=1,2,…,m),yij=1表示敵方無(wú)人機(jī)攻擊我方,yij=0表示敵方無(wú)人機(jī)放棄攻擊,堅(jiān)守防區(qū)。

3.2 無(wú)人機(jī)對(duì)抗博弈支付函數(shù)

支付函數(shù)是博弈中參與者所獲得的收益水平的函數(shù),是每一個(gè)參與者在某種策略環(huán)境下所能獲得的可能收益。支付函數(shù)不僅與每個(gè)參與者自身所選擇的策略有關(guān),還與其他參與者在同一環(huán)境下所選擇的策略有關(guān)。因此,它也可以看作是所有參與者的戰(zhàn)略或行動(dòng)的函數(shù)。

設(shè)我方n架無(wú)人機(jī)價(jià)值S={s1,s2,…,si,…,sn},敵方m架無(wú)人機(jī)的價(jià)值為G={g1,g2,…,gj,…,gm},目標(biāo)點(diǎn)歸一化的綜合價(jià)值為σ。

我方無(wú)人機(jī)的收益函數(shù)可表示為

(10)

式中:β為目標(biāo)位置價(jià)值的權(quán)重系數(shù);σ為目標(biāo)點(diǎn)的綜合價(jià)值;wmi為我方無(wú)人機(jī)導(dǎo)彈的價(jià)值;gj為第j架敵方無(wú)人機(jī)的價(jià)值;Υij為第i架我方無(wú)人機(jī)對(duì)第j架敵方無(wú)人機(jī)的攻擊成功概率;gmax為我方收益的最大值。

敵方無(wú)人機(jī)收益函數(shù)為

(11)

式中:J為防區(qū)價(jià)值的權(quán)重系數(shù);ξ為防區(qū)的綜合價(jià)值;si為第i架我方無(wú)人機(jī)的價(jià)值;μij為第j架敵方無(wú)人機(jī)對(duì)第i架我方無(wú)人機(jī)的攻擊成功概率;smax為敵方收益的最大值。

綜上所述,敵我雙方無(wú)人機(jī)的支付函數(shù)為

Hij=α1R-α2C

(12)

式中:i∈[1,κ],j∈[1,λ];α1、α2為收益權(quán)重系數(shù),且α1+α2=1。

則雙方無(wú)人機(jī)對(duì)抗博弈的支付矩陣為

(13)

式中:Hκλ表示我方無(wú)人機(jī)采用第κ策略,而敵方無(wú)人機(jī)采用第λ策略時(shí)的支付值。

3.3 無(wú)人機(jī)對(duì)抗博弈納什均衡解

(14)

定義如下適應(yīng)度函數(shù)[13]:

(15)

式中:s={η1,η2,…,ηn}為博弈的混合策略;ai∈Si為局中人i的策略集合。

根據(jù)定義1可知,當(dāng)且僅當(dāng)s為博弈的納什均衡策略時(shí),適應(yīng)度函數(shù)取最小值0。

4 精英蟻群優(yōu)化算法

傳統(tǒng)蟻群算法不適用于無(wú)人機(jī)對(duì)抗博弈的納什均衡求解問題[14]。為此,本文在蟻群算法的基礎(chǔ)上,提出一種精英蟻群優(yōu)化(elite ant colony optimization,EACO)算法。

4.1 對(duì)立學(xué)習(xí)

在EACO算法中,通過隨機(jī)產(chǎn)生的初始種群來(lái)開始搜索最佳解。當(dāng)初始種群接近最優(yōu)解,則可較快找到可行解。相反地,當(dāng)種群遠(yuǎn)離最優(yōu)解區(qū)域時(shí),則搜索需要較長(zhǎng)的時(shí)間,甚至無(wú)法找到最優(yōu)解。

對(duì)立學(xué)習(xí)(opposed learning)是一種機(jī)器智能的新方法。對(duì)于初始種群,對(duì)立學(xué)習(xí)可將所有初始成員位置取反,如式(16)所示:

(16)

4.2 精英成員劃分

經(jīng)過種群初始化后,可根據(jù)適應(yīng)度函數(shù)(15),計(jì)算出蟻群中各個(gè)螞蟻的適應(yīng)度值,適應(yīng)度較優(yōu)的作為精英螞蟻,其它剩余螞蟻為普通螞蟻,賦予相應(yīng)的信息素強(qiáng)度。

蟻群中的普通螞蟻根據(jù)當(dāng)前的信息素強(qiáng)度和適應(yīng)度函數(shù)計(jì)算轉(zhuǎn)移概率。

(17)

式中:p(i,j)為普通螞蟻i向精英螞蟻j的轉(zhuǎn)移概率;f(Xi)和f(Xj)分別為普通螞蟻i和精英螞蟻j的適應(yīng)度函數(shù)值;τ(j)為精英螞蟻j的信息素強(qiáng)度值;m為精英螞蟻的數(shù)量;τ(s)和f(Xs)分別為精英螞蟻s的信息素強(qiáng)度值和適應(yīng)度函數(shù)值。

普通螞蟻i根據(jù)式(17)的轉(zhuǎn)移概率p(i,j)選擇是否下一步向精英螞蟻j移動(dòng)。

Xi(t+1)=αXi(t)+(1-α)Xj(t)

(18)

式中:Xi(t+1)為t+1時(shí)刻普通螞蟻i的位置;Xi(t)和Xj(t)分別為t時(shí)刻普通螞蟻i和精英螞蟻j的位置;α為(0,1)內(nèi)產(chǎn)生的一個(gè)隨機(jī)數(shù)。

4.3 精英變異

為了避免陷入局部最優(yōu),對(duì)精英螞蟻進(jìn)行變異操作,產(chǎn)生適應(yīng)度函數(shù)更優(yōu)的蟻群。

(19)

式中:Xj(t)和Xj(t+1)分別為精英螞蟻j變異前和變異后的位置;β1為(0,1)內(nèi)的隨機(jī)數(shù);T和Tmax分別為當(dāng)前迭代次數(shù)和最大迭代次數(shù)。

完成一次進(jìn)化后,更新所有螞蟻的信息素強(qiáng)度和適應(yīng)度值。

(20)

4.4 EACO算法具體步驟

步驟1 初始化參數(shù),確定最大迭代次數(shù)Tmax、蟻群規(guī)模M。

步驟2 采用對(duì)立學(xué)習(xí)思想改變種群成員初始位置。

步驟3 根據(jù)適應(yīng)度函數(shù)計(jì)算蟻群中每只螞蟻的適應(yīng)度值,將蟻群分為精英螞蟻和普通螞蟻。

步驟4 根據(jù)式(17)計(jì)算普通螞蟻的轉(zhuǎn)移概率。

步驟5 根據(jù)式(19)對(duì)精英螞蟻進(jìn)行變異操作,產(chǎn)生適應(yīng)度函數(shù)更優(yōu)的螞蟻。

步驟6 更新所有螞蟻的信息素強(qiáng)度和適應(yīng)度值,重新選擇精英螞蟻和普通螞蟻。

步驟7 當(dāng)達(dá)到最大迭代次數(shù)時(shí),停止迭代,否則返回步驟2。

4.5 EACO算法復(fù)雜度分析

優(yōu)化算法的時(shí)間復(fù)雜度可以通過算法語(yǔ)句的循環(huán)執(zhí)行次數(shù)進(jìn)行衡量。在EACO算法中,重復(fù)循環(huán)次數(shù)與最大迭代次數(shù)Tmax、蟻群規(guī)模M有關(guān)。步驟1中時(shí)間復(fù)雜度為O(M);步驟2引入對(duì)立學(xué)習(xí)和步驟3劃分精英螞蟻,時(shí)間復(fù)雜度并未增加;步驟4計(jì)算轉(zhuǎn)移概率和步驟5進(jìn)行變異操作,時(shí)間復(fù)雜度并未增加;步驟6更新整個(gè)種群位置,復(fù)雜度為O(M×Tmax)。算法整體復(fù)雜度不高,運(yùn)行效率較好。

5 仿真研究

設(shè)在復(fù)雜環(huán)境中,我方兩架無(wú)人機(jī)要穿越敵方防區(qū),到達(dá)目標(biāo)區(qū)域,在飛行途中,遇到敵方兩架無(wú)人機(jī)。我方兩架無(wú)人機(jī)為(U1,U2),其價(jià)值分別為s1=93、s2=91;敵方兩架無(wú)人機(jī)為(A3,A4),其價(jià)值分別為g1=112、g2=114;我方無(wú)人機(jī)的目標(biāo)區(qū)域的綜合價(jià)值σ=180,其權(quán)重系數(shù)β=0.5;敵方的防區(qū)的綜合價(jià)值ξ=100,其權(quán)重系數(shù)J=0.8;雙方收益權(quán)重系數(shù)為α1=0.6、α2=0.4;雙方導(dǎo)彈的價(jià)值為wmi=wmj=10。雙方無(wú)人機(jī)攻擊成功概率公式如下所示:

(21)

(22)

表1為敵我雙方無(wú)人機(jī)的策略集,根據(jù)式(12)和(13),求出雙方無(wú)人機(jī)對(duì)抗博弈支付矩陣:

表1 敵我雙方無(wú)人機(jī)策略集Table 1 UAV strategy set of both sides

采用EACO算法求解出的納什均衡點(diǎn)為0.077,即,我方納什均衡策略為U1和U2都選擇逃離,敵方策略為A3攻擊U1,A4攻擊U1。

圖3為敵我雙方無(wú)人機(jī)采用動(dòng)態(tài)人工勢(shì)場(chǎng)法的對(duì)抗博弈納什均衡策略航跡圖。從圖中可以看出,我方無(wú)人機(jī)U2避開敵方兩架無(wú)人機(jī),成功到達(dá)目標(biāo)區(qū)域;敵方無(wú)人機(jī)A3和A4協(xié)同攻擊我方無(wú)人機(jī)U1,最終在位置(-64,-8)處攻擊成功。在雙方無(wú)人機(jī)對(duì)抗博弈中,納什均衡策略是雙方的最優(yōu)策略,妄想改變策略的一方將會(huì)損失更大。

圖3 動(dòng)態(tài)人工勢(shì)場(chǎng)法的納什均衡策略Fig.3 Nash equilibrium strategy of dynamic artificial potential field method

為進(jìn)一步驗(yàn)證本文提出的精英蟻群算法求解無(wú)人機(jī)對(duì)抗博弈納什均衡的有效性,采用無(wú)人機(jī)對(duì)抗博弈支付矩陣Ω作為測(cè)試函數(shù),將本文提出來(lái)的EACO算法與粒子群優(yōu)化(particle swarm optimization,PSO)算法[15]、遺傳算法(genetic algorithm,GA)、精英改選機(jī)制的粒子群優(yōu)化(elite re-election particle swarm optimization,ERPSO)算法[16]進(jìn)行對(duì)比。

算法參數(shù)設(shè)置為:種群規(guī)模為50,最大迭代次數(shù)為100;EACO算法中精英螞蟻數(shù)量為10,信息素?fù)]發(fā)系數(shù)λ1=0.6;參考文獻(xiàn)[15]設(shè)置PSO算法中的個(gè)體與群體學(xué)習(xí)因子為c1=c2=1.4;GA算法中交叉與變異概率為p1=0.4、p2=0.2;參考文獻(xiàn)[16]設(shè)置ERPSO算法中的克隆變異的個(gè)數(shù)為l1=25,重新初始化個(gè)體數(shù)l2=25,誤差閾值為e=0.05。4種算法在相同仿真環(huán)境中進(jìn)行50次獨(dú)立實(shí)驗(yàn)。

表2為4種算法的性能對(duì)比結(jié)果。由表2可知,與PSO算法、GA算法和ERPSO算法相比,EACO算法所求的適應(yīng)度值最優(yōu),最優(yōu)適應(yīng)度值為4.185 1×10-6;EACO算法平均迭代次數(shù)最少,比PSO算法減少67.85%,比GA算法減少88%,比ERPSO算法減少40%。這表明本文算法能顯著降低迭代次數(shù)、提高計(jì)算精度和收斂速度,適合應(yīng)用于求解無(wú)人機(jī)對(duì)抗博弈的納什均衡問題。

表2 四種算法性能對(duì)比Table 2 Performance comparison of the four algorithms

6 結(jié)束語(yǔ)

本文提出了一種動(dòng)態(tài)人工勢(shì)場(chǎng)法,在人工勢(shì)場(chǎng)法的基礎(chǔ)上,增加了速度斥力和速度引力因素,并將該方法應(yīng)用到多無(wú)人機(jī)對(duì)抗博弈策略的研究中。通過構(gòu)建敵我雙方支付函數(shù),建立了雙方對(duì)抗博弈模型。采用精英蟻群算法,更加高效地計(jì)算出雙方的納什均衡策略。最后,仿真結(jié)果表明了動(dòng)態(tài)人工勢(shì)場(chǎng)法和精英蟻群算法的有效性。