多平臺協(xié)同突防航路規(guī)劃

賈正榮,盧發(fā)興,王航宇

(海軍工程大學 兵器工程學院,湖北 武漢 430033)

協(xié)同突防任務要求多個作戰(zhàn)平臺同時或盡可能同時到達指定的位置,并減少航行過程中被攔截的概率[1]。航路規(guī)劃對于多平臺的協(xié)同突防至關重要,相比于一般的協(xié)同任務,協(xié)同突防航路規(guī)劃除了考慮包括航路可行性、障礙規(guī)避、沖突規(guī)避、航程優(yōu)化之外,還需要考慮威脅規(guī)避,即盡可能減少被攔截的概率。另外,為形成飽和突防態(tài)勢,協(xié)同突防一般要求平臺同時到達目標位置,這一要求可以借鑒會和航路規(guī)劃的相關方法。如文獻[2]分析了多機器人在位置環(huán)境中協(xié)同探索的問題,研究給出了會和位置的選取方法,同時給出了到達會和位置的實時規(guī)劃方法;文獻[3]研究了欠驅動機器人的會和問題,給出了一種分布式的反饋控制策略,用于在離散空間內實時控制多機器人到達會和地點?，F(xiàn)有研究大多關注在規(guī)避障礙的條件下給出可行的會和航路,較少涉及航路區(qū)域內存在威脅的情況,而在存在威脅的區(qū)域內執(zhí)行會和任務廣泛存在于實際應用中,有必要針對這種情況進行研究。

航路的表示方法對于航路規(guī)劃至關重要。一般的航路表示方法主要有航路點航路[4-5]、DUBINS航路[6-7]、人工勢場(artificial potential field,APF)航路[8]、插值型航路(或樣條曲線航路)等。其中,插值型航路基于插值函數(shù)生成光滑的航路,可以準確預估航程,同時可以通過調整航路控制點的位置以規(guī)避障礙或威脅[9-10],而航路控制點可以基于各類進化算法進行求解[11-12]?？刹捎貌逯敌秃铰愤M行求解協(xié)同突防航路規(guī)劃問題。

綜上,本文針對多平臺協(xié)同突防航路規(guī)劃問題進行研究,建立優(yōu)化目標函數(shù)與約束條件,考慮多平臺運動過程中所受威脅程度;同時給出多平臺協(xié)同突防航路規(guī)劃求解框架,通過控制點插值型航路構建航路描述與生成模型,基于粒子群優(yōu)化方法(particle swarm optimization,PSO)進行航路參數(shù)求解。

1 問題描述

多個平臺需要到達指定的目標位置以完成某一任務,平臺的運動受到轉彎半徑的約束,即航路的曲率有界。平臺在運動過程中可能被攔截,不同位置的被攔截概率不同。同時,空間中存在一定數(shù)量的障礙,平臺的航路不能經過這些障礙。平臺的初始位置給定,初始航向自由。

需要優(yōu)化不同平臺的航路,使處于不同初始位置的平臺盡量同時到達目標位置,同時減少平臺的航程,并降低累積的被攔截可能性。

協(xié)同突防航路規(guī)劃如圖1所示,圖中平面內的威脅值通過等高線給出。為了盡可能同時到達目標位置,距離目標較遠的平臺-2應當選擇近似直線的航路,雖然這樣可能會增加被攔截的概率;而距離目標較近的平臺-1則選擇了較為彎曲的航路以增加航程;平臺-3與平臺-4則需要在規(guī)避障礙的同時選擇與平臺-1和平臺-2航程接近的航路。

圖1 協(xié)同突防航路規(guī)劃示意圖

可見,應當考慮的優(yōu)化目標包括航路的長度(減少航程)、多平臺航路長度差(盡可能同時到達目標位置)、累積威脅程度(使航路過程被攔截概率盡可能低),而航路規(guī)劃需要考慮的因素包括轉彎半徑約束(使航路可行)、航路交叉約束(多平臺航路間不能交叉)、障礙規(guī)避約束(航路不能經過給定的障礙)。事實上,在本文中航路的構建與優(yōu)化求解與目標函數(shù)、約束條件是松耦合的,改變目標函數(shù)、約束條件,仍然可以使用航路的構建與優(yōu)化求解方法得到航路規(guī)劃方案。

2 協(xié)同突防問題的目標函數(shù)與約束條件

為便于分析,設平臺數(shù)量為np,每個平臺的航路為Li。

2.1 目標函數(shù)

目標函數(shù)為加權綜合得到的單一指標,記為加權綜合目標函數(shù),該函數(shù)考慮了3個優(yōu)化因素,分別為平均航路長度、航路長度標準差、累積威脅程度。

①加權綜合目標函數(shù)。

設加權綜合目標函數(shù)為J,則有:

(1)

②平均航路長度。

平均航路長度E(Li)即所有航路長度的均值,有:

(2)

式中:l(Li)為航路i的長度,由于每個平臺對應唯一的航路,因此也使用下標i表示。

③航路長度標準差。

通過航路長度標準差描述多平臺的航路長度差距,作為同時到達的指標,航路長度標準差σ(Li)是所有航路的標準差,有:

(3)

④累積威脅程度。

平臺被攔截的概率通過累積威脅程度表示。本文定義累積威脅程度為航路曲線在威脅空間上的積分,給定空間內的威脅指標函數(shù),其函數(shù)值與位置相關。根據(jù)實際問題特點,可以建立不同的累積威脅程度函數(shù)。

對于給定的威脅指標函數(shù)H(x,y),航路i的累積威脅程度為H(x,y)在曲線Li上的積分為

(4)

式中:dr為曲線積分微元。

在離散形式下,可以表示為

式中:j為實際航路曲線坐標點序號,(xi,jyi,j)T為離散形式下平臺i的第j個航路點,n1為離散形式下航路點的數(shù)量。

2.2 約束條件

①合理航路的判斷。

合理的航路即滿足轉彎半徑約束,不與其他航路交叉,且不經過任意障礙的航路。航路的合理性判斷需要依次進行轉彎半徑判斷、航路交叉判斷以及障礙沖突判斷。

②轉彎半徑判斷。

對于得到的實際航路Li,計算航路上每個位置(xi,jyi,j)T處的曲率半徑ρi,j,有:

(5)

式中,一階導數(shù)與二階導數(shù)可以通過數(shù)值方法得到。

設平臺的最小轉彎半徑為rmin,若有:ρi,j≥rmin,?j,則航路Li通過轉彎半徑判斷。

③航路交叉判斷。

(6)

從而兩線段的交點為以下線性方程的解:

(7)

若同時存在:

(8)

則交點同時位于兩線段上而非線段的延長線上,此時兩線段交叉,存在沖突。若對于任意2條航路的所有線段均不存在交叉,則不存在航路交叉。

④障礙沖突判斷。

障礙通過有序的多邊形頂點位置給出,因此航路與障礙的判斷實質上也是插值航路點線段與障礙邊界線段的相交判斷,具體方法同③。

3 航路的構建與優(yōu)化求解

實際的航路是連續(xù)的曲線,在描述與計算過程中存在一定的不便,因此通過控制點結合插值方法生成實際航路,而航路優(yōu)化過程則直接求解航路控制點。在這種求解框架下,航路的優(yōu)化與航路的構建、求解是相互解耦的,根據(jù)實際需求,當改變問題的目標函數(shù)、約束條件后,仍然可以通過這種航路構建、求解方法進行優(yōu)化。

3.1 基于保形插值的航路生成

插值方法對于插值型航路的特征有主要的影響。本文采用分段保形二次插值方法(shape-preserving piecewise cubic interpolation method,SPCI),采用這種方法的優(yōu)勢在于能夠得到一階連續(xù),且在控制點附近不會改變凹凸性的曲線,這種曲線更符合實際所希望的航路。如圖2所示,相比于一般的非分段樣條插值方法,SPCI方法得到的曲線不會在控制點之間震蕩,更加符合實際情況。

圖2 分段保形二次插值方法與一般樣條插值方法的區(qū)別

由于采用PSO方法進行優(yōu)化,參數(shù)粒子需要參考全局最優(yōu)解,為了避免在優(yōu)化求解過程中數(shù)值差異過大的情況,對航路控制點進行標準化。標準化過程即將實際坐標系下航路變換至標準化坐標系下,在標準化坐標系下平臺初始位置為(0 0)T,目標位置為(1 0)T,如圖3～圖4所示。xψ和yψ為歸一化后的坐標。

圖3 標準化坐標系下的航路控制點

圖4 實際空間中的航路控制點

對于任意一架平臺,航路是連接初始位置與目標位置的曲線,設第i個平臺的航路初始位置為Xps,i,目標位置為Xt。建立Xps,i的標準化坐標系,以Xps,i為原點,Xt-Xps,i向量為x軸。

設向量Xt-Xps,i的極坐標幅角為βi,標準化坐標系下第i個平臺的控制點為Ψi,有:

(9)

式中:k為航路控制點序號,航路控制點數(shù)量為nc,此處的航路控制點是用于生成航路的參數(shù)(并非航路點),結合SPCI方法,可以得到最終的航路點?？紤]到SPCI方法需要至少4個控制點,而平臺初始位置與目標位置,即標準化坐標系下的(0 0)T與(1 0)T,已經提供了2個點,因此航路控制點數(shù)量nc≥2。

設實際坐標系下的控制點向量為Ti,則標準化坐標系下的控制點Ψi到實際坐標系下控制點Ti的變換為

(10)

基于控制點位置,通過SPCI生成實際的航路。SPCI方法在文獻[13]中已經有詳細的描述,文中不再贅述,并記SPCI算子為λ,對于實際坐標系下的控制點Ti,可以得到實際航路曲線Li為

Li=λ(Ti)

(11)

3.2 基于PSO的航路控制點優(yōu)化

多平臺的航路通過控制點基于插值方法生成,因此協(xié)同航路優(yōu)化等同于優(yōu)化調整控制點,對于這種難以得到梯度信息且優(yōu)化參數(shù)為連續(xù)形式的復雜優(yōu)化問題,可以通過PSO方法進行求解。PSO方法的優(yōu)化過程為

(12)

式中:ξ為優(yōu)化參數(shù);V為優(yōu)化參數(shù)的等效速度或等效梯度;p為序號;ω∈[0,1]為慣性系數(shù),c1∈[0,1]與c2∈[0,1]為優(yōu)化控制系數(shù);r1與r2為在[0,1]內按照均勻分布隨機生成的系數(shù),為優(yōu)化過程增加隨機因素;ξl為局部最優(yōu)解,即單個粒子更新過程中的最優(yōu)解;ξg為全局最優(yōu)解,即所有粒子的歷史最優(yōu)解。優(yōu)化參數(shù)為所有航路控制點參數(shù)構成的向量,即ξ=(T1T2…Tnp)。

具體的優(yōu)化流程包含2個部分,分別為粒子群初始化與粒子群優(yōu)化。其中,粒子群初始化即生成給定數(shù)量且滿足約束條件的粒子群,如圖所示;粒子群優(yōu)化即不斷更新粒子群直至收斂并輸出全局最優(yōu)解,如圖5～圖6所示。

圖5 粒子群初始化流程

圖6 粒子群優(yōu)化流程

在優(yōu)化過程中,可能存在粒子更新后對應的航路不符合約束條件的情況,然而,由于粒子群初始化時已經生成了滿足約束條件的初始解,每個粒子的歷史局部最優(yōu)解總是存在的,因此可以保證存在可行解。

4 仿真分析

為驗證方法正確性并分析優(yōu)化參數(shù)對于方法求解的影響,進行仿真分析。首先進行方法可行性分析;然后針對不同的場景,調整優(yōu)化參數(shù),分析優(yōu)化參數(shù)取值不同時結果的差異。

分別在3個場景下進行協(xié)同航路規(guī)劃,場景設置參數(shù)如表1所示。表中,nob為障礙數(shù)量,ntr為威脅區(qū)域數(shù)量。

表1 場景設置

在不同場景下進行協(xié)同突防航路規(guī)劃,權值系數(shù)取0.3(平均航路長度)、0.3(航路長度標準差)、0.4(累積威脅程度),控制點數(shù)量nc取8個。得到的結果如圖7～圖9所示。

圖7 場景1航路規(guī)劃結果

圖8 場景2航路規(guī)劃結果

圖9 場景3航路規(guī)劃結果

不同場景下的3個優(yōu)化指標以及加權綜合目標函數(shù)值如表2所示。

表2 指標數(shù)值

圖7～圖9與表2的結果驗證了方法的有效性,方法能夠求解得到不相互沖突且規(guī)避障礙的可行航路;圖中航路均能夠一定程度地規(guī)避威脅區(qū)域;在同時到達方面,當航路標準差的權值為0.3時,航路長度標準差在1 km以下。特別地,由于場景3中沒有障礙,因而得到航路規(guī)劃結果的航路標準差為0.001 km。

5 結束語

本文提出了一種用于多平臺協(xié)同突防航路規(guī)劃的方法框架,方法特點主要包括:①給出了多平臺協(xié)同突防航路規(guī)劃的框架,框架中的目標函數(shù)、約束條件均可以根據(jù)實際需求更改而不影響求解流程;②除了考慮減少航程以及盡可能同時到達外,還考慮了航路上的累積威脅程度;③航路符合轉彎半徑約束,且一階連續(xù);④生成的航路不相互交叉,不與給定的障礙沖突。