基于DAPF與EACO算法的無人機博弈策略

嚴航,付興建

(北京信息科技大學 自動化學院,北京 100192)

0 引言

在復雜的作戰環境中,如何利用無人機實現合理的戰略規劃以獲取最大化的收益,已成為許多研究者探索的重點問題。

在無人機的路徑規劃方面,文獻[1]提出了一種修正人工勢場的動態路徑規劃算法,來預測動態障礙物的位置。文獻[2]在傳統人工勢場法的基礎上,增加了一個轉向力,來加快無人機的動態避障過程。文獻[3]針對多無人機提出了一種有效的基于改進人工勢函數的路徑規劃方法,通過引入旋轉勢場,無人機可以有效地擺脫常見的局部最小值和振蕩。文獻[4]將A*算法和Q-learning算法相結合,提高了無人機路徑的可靠性和安全性。文獻[5]提出了一種新型非線性模型預測控制方法,來預測動態障礙物的軌跡,提前規劃無人機的航線。

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

將無人機的路徑規劃和對抗博弈相結合的研究鮮有報道。本文提出一種動態人工勢場法,將敵方無人機作為動態障礙物,我方要通過敵方無人機的防區,進而兩者之間形成了動態對抗博弈。建立敵我雙方對抗博弈模型,采用精英蟻群算法求出雙方的納什均衡策略。在納什均衡策略中,雙方無人機一旦改變策略,只會減少己方的收益。

1 問題描述

本文提出的無人機對抗博弈有兩個參與者,即參與者1為我方無人機,參與者2為敵方無人機。我方的首要目標為穿越敵方無人機的防區,敵方目標為巡邏和防守所在的防區。在敵我雙方對抗博弈的過程中,雙方都在尋找最優的策略,使得己方收益達到最大。

在二維平面建立雙方無人機的動力學模型為

(1)

式中:(x,y)為無人機的位置;v為無人機的速度;θ為無人機運動方向與x軸的夾角;ω為無人機的角速度;a為無人機的加速度。

2 動態人工勢場法

人工勢場法由Khatib于1986年提出。該方法思想如下:設無人機在虛擬勢場中受到兩個力的作用,一個是目標對其的吸引力,另一個是障礙物上的排斥力。通過兩個力之間的相互作用,無人機能夠避開環境中的障礙物,并到達目標位置[10]。

然而,傳統人工勢場法在遇到環境中存在動態障礙物或者目標為移動物體的情況時,其路徑規劃和避障效果不佳[11]。本文在人工勢場法的基礎上,加入速度斥力和速度引力因素,提出動態人工勢場法(dynamic artificial potential field method,DAPF)。

(2)

(3)

圖1 動態人工勢場法的排斥力Fig.1 Repulsive force of dynamic artificial potential field method

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

(4)

(5)

(6)

動態人工勢場法的吸引力如圖2所示,其中,吸引力及其兩個分量可以表示為

(7)

(8)

(9)

圖2 動態人工勢場法的吸引力Fig.2 Attraction of dynamic artificial potential field method

3 無人機對抗博弈

本文建立的無人機對抗博弈模型,主要分為博弈參與者集合、策略集、支付函數和納什均衡策略求解四個方面。博弈參與者為動態人工勢場法中介紹的敵我雙方無人機。其余三方面的內容將在本節中介紹。

3.1 雙方無人機的策略集

設我方有n架無人機,集合為{ξ1,ξ2,…,ξn},敵方有m架無人機,集合為{ψ1,ψ2,…,ψm}。我方對抗狀態為xij(i=1,2,…,n;j=1,2,…,m),xij=1表示我方無人機選擇攻擊敵方,xij=0表示我方選擇逃離該敵方防區。敵方對抗狀態為yij(i=1,2,…,n;j=1,2,…,m),yij=1表示敵方無人機攻擊我方,yij=0表示敵方無人機放棄攻擊,堅守防區。

3.2 無人機對抗博弈支付函數

支付函數是博弈中參與者所獲得的收益水平的函數,是每一個參與者在某種策略環境下所能獲得的可能收益。支付函數不僅與每個參與者自身所選擇的策略有關,還與其他參與者在同一環境下所選擇的策略有關。因此,它也可以看作是所有參與者的戰略或行動的函數。

設我方n架無人機價值S={s1,s2,…,si,…,sn},敵方m架無人機的價值為G={g1,g2,…,gj,…,gm},目標點歸一化的綜合價值為σ。

我方無人機的收益函數可表示為

(10)

式中:β為目標位置價值的權重系數;σ為目標點的綜合價值;wmi為我方無人機導彈的價值;gj為第j架敵方無人機的價值;Υij為第i架我方無人機對第j架敵方無人機的攻擊成功概率;gmax為我方收益的最大值。

敵方無人機收益函數為

(11)

式中:J為防區價值的權重系數;ξ為防區的綜合價值;si為第i架我方無人機的價值;μij為第j架敵方無人機對第i架我方無人機的攻擊成功概率;smax為敵方收益的最大值。

綜上所述,敵我雙方無人機的支付函數為

Hij=α1R-α2C

(12)

式中:i∈[1,κ],j∈[1,λ];α1、α2為收益權重系數,且α1+α2=1。

則雙方無人機對抗博弈的支付矩陣為

(13)

式中:Hκλ表示我方無人機采用第κ策略,而敵方無人機采用第λ策略時的支付值。

3.3 無人機對抗博弈納什均衡解

(14)

定義如下適應度函數[13]:

(15)

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

根據定義1可知,當且僅當s為博弈的納什均衡策略時,適應度函數取最小值0。

4 精英蟻群優化算法

傳統蟻群算法不適用于無人機對抗博弈的納什均衡求解問題[14]。為此,本文在蟻群算法的基礎上,提出一種精英蟻群優化(elite ant colony optimization,EACO)算法。

4.1 對立學習

在EACO算法中,通過隨機產生的初始種群來開始搜索最佳解。當初始種群接近最優解,則可較快找到可行解。相反地,當種群遠離最優解區域時,則搜索需要較長的時間,甚至無法找到最優解。

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

(16)

4.2 精英成員劃分

經過種群初始化后,可根據適應度函數(15),計算出蟻群中各個螞蟻的適應度值,適應度較優的作為精英螞蟻,其它剩余螞蟻為普通螞蟻,賦予相應的信息素強度。

蟻群中的普通螞蟻根據當前的信息素強度和適應度函數計算轉移概率。

(17)

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

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

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

(18)

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

4.3 精英變異

為了避免陷入局部最優,對精英螞蟻進行變異操作,產生適應度函數更優的蟻群。

(19)

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

完成一次進化后,更新所有螞蟻的信息素強度和適應度值。

(20)

4.4 EACO算法具體步驟

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

步驟2 采用對立學習思想改變種群成員初始位置。

步驟3 根據適應度函數計算蟻群中每只螞蟻的適應度值,將蟻群分為精英螞蟻和普通螞蟻。

步驟4 根據式(17)計算普通螞蟻的轉移概率。

步驟5 根據式(19)對精英螞蟻進行變異操作,產生適應度函數更優的螞蟻。

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

步驟7 當達到最大迭代次數時,停止迭代,否則返回步驟2。

4.5 EACO算法復雜度分析

優化算法的時間復雜度可以通過算法語句的循環執行次數進行衡量。在EACO算法中,重復循環次數與最大迭代次數Tmax、蟻群規模M有關。步驟1中時間復雜度為O(M);步驟2引入對立學習和步驟3劃分精英螞蟻,時間復雜度并未增加;步驟4計算轉移概率和步驟5進行變異操作,時間復雜度并未增加;步驟6更新整個種群位置,復雜度為O(M×Tmax)。算法整體復雜度不高,運行效率較好。

5 仿真研究

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

(21)

(22)

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

表1 敵我雙方無人機策略集Table 1 UAV strategy set of both sides

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

圖3為敵我雙方無人機采用動態人工勢場法的對抗博弈納什均衡策略航跡圖。從圖中可以看出,我方無人機U2避開敵方兩架無人機,成功到達目標區域;敵方無人機A3和A4協同攻擊我方無人機U1,最終在位置(-64,-8)處攻擊成功。在雙方無人機對抗博弈中,納什均衡策略是雙方的最優策略,妄想改變策略的一方將會損失更大。

圖3 動態人工勢場法的納什均衡策略Fig.3 Nash equilibrium strategy of dynamic artificial potential field method

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

算法參數設置為:種群規模為50,最大迭代次數為100;EACO算法中精英螞蟻數量為10,信息素揮發系數λ1=0.6;參考文獻[15]設置PSO算法中的個體與群體學習因子為c1=c2=1.4;GA算法中交叉與變異概率為p1=0.4、p2=0.2;參考文獻[16]設置ERPSO算法中的克隆變異的個數為l1=25,重新初始化個體數l2=25,誤差閾值為e=0.05。4種算法在相同仿真環境中進行50次獨立實驗。

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

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

6 結束語

本文提出了一種動態人工勢場法,在人工勢場法的基礎上,增加了速度斥力和速度引力因素,并將該方法應用到多無人機對抗博弈策略的研究中。通過構建敵我雙方支付函數,建立了雙方對抗博弈模型。采用精英蟻群算法,更加高效地計算出雙方的納什均衡策略。最后,仿真結果表明了動態人工勢場法和精英蟻群算法的有效性。