基于Voronoi圖與Bezier曲線算法的反艦導(dǎo)彈航路規(guī)劃方法*

史 巖,張立華,董受全,賈帥東

(1 海軍大連艦艇學(xué)院海洋測繪系,遼寧大連 116018;2 海軍大連艦艇學(xué)院導(dǎo)彈系,遼寧大連 116018)

0 引言

反艦導(dǎo)彈主要用于攻擊敵方水面艦艇,是對抗海上目標(biāo)的主要制導(dǎo)武器之一。在當(dāng)今海戰(zhàn)中,遠(yuǎn)程超視距情況下的攻擊是交戰(zhàn)各方共同追求的作戰(zhàn)形式[1]。在此情況下,如何以一條相對合適的飛行路徑接近敵方目標(biāo),達(dá)到出其不意的攻擊效果,這是反艦導(dǎo)彈航路規(guī)劃的主要研究方向之一。

導(dǎo)彈航路規(guī)劃主要是根據(jù)任務(wù)目標(biāo)規(guī)劃航路,最終規(guī)劃出符合戰(zhàn)術(shù)要求的最優(yōu)或者滿意的飛行航跡,以保證圓滿的完成導(dǎo)彈的飛行任務(wù)[2]。典型的規(guī)劃算法有:Voronoi圖算法[3]、A*算法[4]、粒子群算法[5]、遺傳算法[6]和蟻群算法[7]等。其中,Voronoi圖算法求取最短路徑相對簡便實(shí)用。

在以Voronoi圖結(jié)構(gòu)的航路算法中,轉(zhuǎn)向點(diǎn)個數(shù)較多和轉(zhuǎn)向角度較大是普遍存在的問題。很多文獻(xiàn)在Voronoi圖結(jié)構(gòu)的基礎(chǔ)上,利用優(yōu)化算法規(guī)劃實(shí)現(xiàn)最短或最優(yōu)路徑,但是在這些方法的規(guī)劃過程中,很容易產(chǎn)生不可飛行的毛刺尖角區(qū)域[8],而多數(shù)學(xué)者選擇規(guī)避這種尖角區(qū),尋找新的路徑。文中提出的算法針對這些毛刺尖角區(qū)域問題進(jìn)行處理,即在Voronoi圖形成的規(guī)劃路徑基礎(chǔ)上,采用Bezier曲線平滑Voronoi圖形成的不可飛行毛刺尖角區(qū)域,再對曲線折線化處理,最終形成滿足約束條件的最優(yōu)航路。所提方法在滿足約束條件的前提下,通過具體算法中自適應(yīng)調(diào)整的過程,使得反艦導(dǎo)彈降低了航程距離和減少了轉(zhuǎn)向次數(shù)與角度,同時也最大程度的保證了反艦導(dǎo)彈的安全性。

1 航路規(guī)劃的約束條件

1.1 最大航程的約束

反艦導(dǎo)彈的飛行航程不可能無限長。這樣使得總航程必須小于或等于一個預(yù)先設(shè)置的最大航程,令其為已知參數(shù)Smax,則航程S的約束條件為:

S≤Smax

(1)

1.2 最小轉(zhuǎn)彎半徑和最小相鄰航路點(diǎn)間距的約束

導(dǎo)彈在任何一個航路轉(zhuǎn)向點(diǎn)(設(shè)為航路點(diǎn)A)處轉(zhuǎn)彎至下一個航路點(diǎn)(設(shè)為航路點(diǎn)B)時,兩航路點(diǎn)之間的距離LA,B需滿足[9]:

(2)

式中:θ為轉(zhuǎn)彎角度;rmin為最小轉(zhuǎn)彎半徑。

1.3 初始航路最小距離

為了確保導(dǎo)彈發(fā)射后能調(diào)整進(jìn)入穩(wěn)定狀態(tài),還需考慮發(fā)射后初始航路最小距離L0,1的約束[9],即其值要大于或等于已知參數(shù)L1,min:

L0,1≥L1,min

(3)

1.4 導(dǎo)彈末端航路最小距離

為了確保導(dǎo)彈最后的攻擊效果,要考慮導(dǎo)彈末端航路最小距離Ln-1,n的約束,即其值要大于或等于已知參數(shù)Ln,min:

Ln-1,n≥Ln,min

(4)

1.5 導(dǎo)彈最大轉(zhuǎn)彎角度

導(dǎo)彈在轉(zhuǎn)向點(diǎn)進(jìn)行航向調(diào)整時,其角度Ai受其性能影響,必須小于或等于導(dǎo)彈最大轉(zhuǎn)彎角度,即其值要小于已知參數(shù)Amax:

Ai≤Amax

(5)

1.6 航路點(diǎn)最大個數(shù)

航路規(guī)劃中要盡量減少中途轉(zhuǎn)向點(diǎn),從而減小導(dǎo)彈誤差和減少姿態(tài)調(diào)整時間。即導(dǎo)彈實(shí)際航路點(diǎn)個數(shù)N要小于或等于已知最大航路點(diǎn)個數(shù)Nmax:

N≤Nmax

(6)

1.7 其他約束條件

末端進(jìn)入航向:導(dǎo)彈在最后攻擊目標(biāo)時,末制導(dǎo)雷達(dá)需要搜索航向,方能準(zhǔn)確捕捉目標(biāo)實(shí)施攻擊。

人為規(guī)避區(qū)域:防空火力、己友方兵力、第三方兵力這些因素都屬于需要規(guī)避的約束條件。

2 Voronoi圖算法原理

2.1 威脅導(dǎo)彈航行安全因素的分析

陸地地形和導(dǎo)彈本身的特點(diǎn)是威脅反艦導(dǎo)彈安全的主要方面。相對于標(biāo)準(zhǔn)的陸地地圖而言,海圖上的高程點(diǎn)信息相對較少。然而,反艦導(dǎo)彈作為艦載武器,通常要充分考慮的是以海圖為基礎(chǔ)。據(jù)此,可以根據(jù)實(shí)際情況增添標(biāo)準(zhǔn)地圖信息,加以豐富沿岸、島礁區(qū)的高程、地貌信息。

反艦導(dǎo)彈的特點(diǎn)是飛行速度相對于彈道導(dǎo)彈要低的多。而飛行的高度越低,越難被發(fā)現(xiàn),甚至可以依靠高處掩護(hù),如在兩座山峰之間穿行。反艦導(dǎo)彈的飛行高度可以實(shí)現(xiàn)超低空飛行(在10～300 m的高度飛行為超低空飛行[10])。因此高程點(diǎn)處可以作為掩護(hù)的模型。

再者,反艦導(dǎo)彈的主要威脅是雷達(dá)和導(dǎo)彈防御系統(tǒng)(即反導(dǎo)系統(tǒng))。對于雷達(dá)系統(tǒng),其基站大多位于海拔較高的開闊地帶,并且雷達(dá)對超低空和掠海飛行目標(biāo)的偵察能力較低。而反導(dǎo)系統(tǒng),對于超低空飛行導(dǎo)彈的防御能力是比較薄弱的。文中所涉及的海圖高程點(diǎn)作為掩護(hù)點(diǎn)滿足反艦導(dǎo)彈超低空飛行的高度,同時亦可代表雷達(dá)基站的威脅點(diǎn),因此高程點(diǎn)可以作為威脅的模型。

綜上,將高程點(diǎn)作為掩護(hù)和威脅的模型,下文統(tǒng)稱威脅點(diǎn)并建立模型,在仿真試驗(yàn)中將海圖的高程點(diǎn)代表雷達(dá)點(diǎn)、山峰點(diǎn)。

2.2 基于Voronoi圖的威脅點(diǎn)模型建立

Voronoi圖在表示點(diǎn)要素相互關(guān)系方面具有優(yōu)勢。在二維平面中,在形成Voronoi圖的點(diǎn)集里,任意的兩點(diǎn)之間連線的垂直平分線所構(gòu)成的圖形,該圖形包含若干多邊形[11]。通過Voronoi圖可以有效地將威脅點(diǎn)以拓?fù)浣Y(jié)構(gòu)表示出來。圖1中是以高程點(diǎn)作為節(jié)點(diǎn)生成的Voronoi圖。

Voronoi圖數(shù)學(xué)表示為點(diǎn)集{P0,P1,…,Pn}里的節(jié)點(diǎn)Pk,則其區(qū)域Rk的定義為:

Rk={x∈X|d(x,Pk)

j={0,1,2,…,n},j≠k}

(7)

提取海圖中部分高程點(diǎn)作為威脅點(diǎn),建立在二維平面中航路規(guī)劃的威脅模型并生成Voronoi圖。Voronoi圖的邊是由相鄰兩個威脅點(diǎn)的垂直平分線組成,其構(gòu)成的多邊形內(nèi)的任意點(diǎn)到其威脅點(diǎn)的距離要比到多邊形外的點(diǎn)到威脅點(diǎn)的距離小,即Voronoi圖多邊形的任一條邊上的點(diǎn)是到達(dá)所有威脅點(diǎn)最遠(yuǎn)的點(diǎn),則導(dǎo)彈距離雷達(dá)越遠(yuǎn),越不容易被發(fā)現(xiàn),安全系數(shù)就越高。所以反艦導(dǎo)彈沿Voronoi圖的邊緣飛行時,將會是最安全的。圖2表示的是在電子海圖的基礎(chǔ)上豐富了海陸要素后的Voronoi圖。

2.3 Voronoi圖路徑規(guī)劃

根據(jù)威脅點(diǎn)生成的Voronoi圖,選取發(fā)射點(diǎn)和目標(biāo)點(diǎn)之間的相關(guān)Voronoi圖的節(jié)點(diǎn)作為初始航路點(diǎn),同時搜索最短路徑作為初始的規(guī)劃航路。注意此時的航路會出現(xiàn)不符合約束條件的情況,此時為了提高效率不做出判斷調(diào)整。圖3為依據(jù)Voronoi圖中航路最短路徑形成的初步規(guī)劃航路,其路徑點(diǎn)主要是為下文形成Bezier曲線的航路作為控制點(diǎn)。

文中定義轉(zhuǎn)向角度不小于90°的轉(zhuǎn)向點(diǎn)所在區(qū)域?yàn)槊碳饨菂^(qū)域,下文統(tǒng)稱尖角區(qū)。由圖3可以看出以Voronoi圖結(jié)構(gòu)的航路算法中,轉(zhuǎn)向點(diǎn)個數(shù)有5個,轉(zhuǎn)向角度小于90°的轉(zhuǎn)向點(diǎn)只有2個,則尖角區(qū)有3個。這對于反艦導(dǎo)彈的飛行航路的穩(wěn)定性與航程距離是十分不利的。

3 Bezier曲線原理

Bezier曲線可以將少量的數(shù)據(jù)擬合出連續(xù)的平滑曲線,這種曲線具有高光滑度和較高精度的特點(diǎn)。

將形成Bezier曲線的少量擬合數(shù)據(jù)定義為特征控制點(diǎn),其形狀可以根據(jù)特征控制點(diǎn)位置的變換而改變。通過控制曲線上的起始點(diǎn)、終止點(diǎn),加之其余各點(diǎn)用來定義曲線的導(dǎo)數(shù)、階次,最終產(chǎn)生、編輯圖形的形狀[12]。圖4中以三階Bezier曲線為例,4個控制點(diǎn)擬合出的平滑曲線即為Bezier曲線。移動圖4中的P3點(diǎn),其余各點(diǎn)位置保持不變后形成圖5中的Bezier曲線。由圖5可以看出生成的新曲線改變了原有的曲率(曲率表示曲線彎曲的程度)。

給定(n+1)個特征點(diǎn)Pi(i=0,1,2,…,n),則Bezier曲線方程可以表示為:

(8)

其中,Bi,n(t)為n次Bernstein基函數(shù):

(9)

由于Voronoi圖形成的原理是相鄰兩點(diǎn)的垂直平分線,這樣在成圖時,時常會形成如圖6矩形框中所示的尖角毛刺部分,即在Voronoi圖的反艦導(dǎo)彈航路規(guī)劃時這樣的毛刺尖角是無法實(shí)現(xiàn)機(jī)動飛行的,且反艦導(dǎo)彈每次轉(zhuǎn)向角度越大,其調(diào)整穩(wěn)定航向的時間就越長,航行效率就越低,突防隱蔽的能力就越差。鑒于Bezier曲線對航跡規(guī)劃的路徑點(diǎn)的擬合有高精度平滑的作用(如圖7所示Bezier曲線平滑了不可飛行的毛刺尖角部分),因此可以將其應(yīng)用到平滑圖3所示Voronoi圖構(gòu)建的航路,從而實(shí)現(xiàn)反艦導(dǎo)彈在沿岸、島礁區(qū)的路徑優(yōu)化。

4 算法的自適應(yīng)調(diào)整

4.1 Bezier曲線自適應(yīng)調(diào)整

Voronoi圖生成的初次的航路,提取其航路點(diǎn)作為待生成的Bezier曲線的控制點(diǎn),進(jìn)而生成Bezier曲線平滑后的航路。如果此時的航路穿越或十分接近某個威脅點(diǎn)(如圖8所示矩形框中不滿足條件的區(qū)域)，通過改變所選區(qū)域內(nèi)Bezier曲線的控制點(diǎn),達(dá)到曲線遠(yuǎn)離威脅點(diǎn)的目的，將這個過程稱為Bezier曲線為滿足航路規(guī)劃的自適應(yīng)過程(圖9為自適應(yīng)調(diào)整過程中的一條曲線航路)。

具體過程:圖8所示的矩形框中,顯示了Bezier曲線規(guī)劃航路與威脅點(diǎn)相交的情況。此時,以一定的距離間隔,應(yīng)用循環(huán)程序調(diào)整初次生成的Voronoi圖規(guī)劃路徑的航路點(diǎn)位置,從而調(diào)整Bezier曲線的形狀。圖9所示將發(fā)射點(diǎn)至目標(biāo)點(diǎn)的矩形平分為A、B區(qū)域進(jìn)行自適應(yīng)調(diào)整,調(diào)整方向分別為向著遠(yuǎn)離發(fā)射點(diǎn)和目標(biāo)點(diǎn)的縱坐標(biāo)軸進(jìn)行的。即在A區(qū)域中Bezier曲線的控制點(diǎn)向著遠(yuǎn)離發(fā)射點(diǎn)的縱坐標(biāo)軸調(diào)整直至滿足約束條件。同理,在B區(qū)域中Bezier曲線的控制點(diǎn)向著遠(yuǎn)離目標(biāo)點(diǎn)的縱坐標(biāo)軸調(diào)整直至滿足約束條件。在圖9中,連接發(fā)射點(diǎn)至目標(biāo)點(diǎn)的折線段為自適應(yīng)調(diào)整過程中生成Bezier曲線控制點(diǎn)逐點(diǎn)連線組成的折線。自適應(yīng)調(diào)整后的最終結(jié)果,即發(fā)射點(diǎn)至目標(biāo)點(diǎn)的Bezier曲線航路,見圖10所示。

4.2 Bezier曲線折線化航路自適應(yīng)調(diào)整

反艦導(dǎo)彈飛行中要盡量保持直線的航路且轉(zhuǎn)向次數(shù)盡可能的少,轉(zhuǎn)向角度盡可能的小。

導(dǎo)彈航路最理想的狀態(tài)是一條直線命中目標(biāo)點(diǎn),但為了最大程度的保證飛行過程中的安全(即低空躲避雷達(dá)等反制導(dǎo)武器的威脅或者低空掩護(hù)),需要依靠地理地形等信息進(jìn)行隱蔽,將曲線進(jìn)行折線化處理成分段直線的航路對導(dǎo)彈更為有利。

自適應(yīng)折線化與Bezier曲線航路自適應(yīng)調(diào)整的過程類似,首先以曲線的橫軸中間位置將曲線進(jìn)行折線化(此時折線次數(shù)計為2),判斷每個分段生成的折線航路是否滿足遠(yuǎn)離威脅點(diǎn)的約束條件,若不滿足則每個分段直線上再次折線化,滿足就跳出循環(huán)。圖11是經(jīng)過4次折線后得到的滿足約束條件的規(guī)劃航路(圖中虛線所示),折線航路的節(jié)點(diǎn)即為轉(zhuǎn)向點(diǎn)(圖中圓圈處標(biāo)識4個轉(zhuǎn)向點(diǎn))。

5 航路仿真實(shí)驗(yàn)

5.1 可行性分析

選定某沿岸島礁區(qū),采用直線航路、Voronoi圖航路、Bezier折線航路三種方法,規(guī)劃反艦導(dǎo)彈航路,比對分析上述三種方法規(guī)劃航路的差異。為了簡化模型,依照第1節(jié)所述,不考慮其他約束條件,設(shè)定某型反艦導(dǎo)彈航路規(guī)劃的約束參數(shù)[13]:最大航程Smax=260 km,最小轉(zhuǎn)彎半徑rmin=10 km,發(fā)射后的初始航路最小距離L1,min=30 km,末端航路最小距離Ln,min=35 km,最大轉(zhuǎn)彎角度Amax=90°,最大航路點(diǎn)個數(shù)Nmax=10。由測量控制點(diǎn)高程信息作為威脅點(diǎn)生成的Voronoi圖(見圖12)。將起始發(fā)射點(diǎn)設(shè)為Bezier曲線的首個控制點(diǎn),將目標(biāo)的位置點(diǎn)設(shè)為最后一個控制點(diǎn)。

直線航路如圖13所示,雖然直線航路避開了威脅點(diǎn),但是反艦導(dǎo)彈的安全性無法得到最大程度的保證。應(yīng)用Voronoi圖路徑航路方法,在Voronoi圖中選取初次航路的節(jié)點(diǎn)作為控制點(diǎn)。經(jīng)過Bezier曲線自適應(yīng)調(diào)整的過程,設(shè)計出一條平滑曲線的航跡路線(見圖14)。Voronoi圖航路和由其控制點(diǎn)生成的Bezier曲線航路對比如圖15所示。

依照第4節(jié)折線化航路進(jìn)行自適應(yīng)的調(diào)整。在本例中曲線折線次數(shù)為4次,生成的最終航路轉(zhuǎn)向點(diǎn)3個(見圖16),加以海陸要素后得到的反艦導(dǎo)彈從發(fā)射點(diǎn)攻擊目標(biāo)點(diǎn)的規(guī)劃航路的效果見圖17所示,可見飛行航路規(guī)避了威脅點(diǎn)的同時又減少了轉(zhuǎn)向的次數(shù),同時也減少了大角度轉(zhuǎn)向的次數(shù)。

5.2 比對分析

進(jìn)一步比對分析所提方法與直線航路、Voronoi圖算法的差異。三種方法的結(jié)果如圖13、圖15、圖16所示。仿真結(jié)果驗(yàn)證了在Voronoi圖基礎(chǔ)上的Bezier曲線算法進(jìn)行航路規(guī)劃的可行性和有效性,所求解的可行航路能夠充分確保反艦導(dǎo)彈規(guī)避威脅的同時有效的減少飛行航程和轉(zhuǎn)向點(diǎn)個數(shù)。依據(jù)發(fā)射點(diǎn)、目標(biāo)點(diǎn)及各轉(zhuǎn)向點(diǎn)的圖上坐標(biāo)與經(jīng)緯度的關(guān)系分別計算三種方法的航路航程。

表1 航路對比表

將航程、轉(zhuǎn)向點(diǎn)個數(shù)和轉(zhuǎn)向角度大于90°的轉(zhuǎn)向點(diǎn)個數(shù)整理后見表1所示?？梢缘贸?通過Bezier曲線折線化的航路,其轉(zhuǎn)向點(diǎn)個數(shù)、轉(zhuǎn)向角度和航路總航程都優(yōu)于Voronoi航路,并且更接近理想情況下的直線航路。

6 結(jié)束語

經(jīng)理論分析、試驗(yàn)論證,得:

1)根據(jù)建立的已知威脅分布情況,采用Voronoi圖對待規(guī)劃區(qū)域進(jìn)行劃分,假設(shè)想定中各威脅點(diǎn)的威脅程度相當(dāng),進(jìn)而得到對應(yīng)于威脅模型的Voronoi圖。在初次航路規(guī)劃的基礎(chǔ)上采用Bezier曲線來平滑航路。通過自適應(yīng)的過程生成曲線并折線化成分段直線的航路,兩次自適應(yīng)的處理過程使得算法的可靠性進(jìn)一步增強(qiáng)。

2)文中算法是以Voronoi圖路徑規(guī)劃為基礎(chǔ),即最大程度的兼顧了反艦導(dǎo)彈的安全性。在通過Bezier曲線處理的過程中,曲線的平滑和折線化后的拆分航路,使得反艦導(dǎo)彈在飛行過程中的大角度轉(zhuǎn)向得以消除,在飛行航程和轉(zhuǎn)向點(diǎn)個數(shù)上有所減少,因此該方法具有一定的優(yōu)越性和可行性,其算法自適應(yīng)的過程相對于傳統(tǒng)的路徑規(guī)劃具有一定的借鑒作用。

當(dāng)然對于更多的復(fù)雜的實(shí)戰(zhàn)問題,海圖中威脅點(diǎn)的威脅程度和威脅半徑可能是多樣的,必須構(gòu)造相應(yīng)的加權(quán)Voronoi圖,才能在Voronoi圖的各邊獲得最大的安全系數(shù)。此外,運(yùn)用文中所提出的基于Voronoi圖和Bezier曲線算法的混合方法來解決動態(tài)不確定環(huán)境下反艦導(dǎo)彈航路規(guī)劃問題,這也是下一步的研究重點(diǎn)。