基于Voronoi圖與Bezier曲線算法的反艦導彈航路規劃方法*

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

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

0 引言

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

導彈航路規劃主要是根據任務目標規劃航路,最終規劃出符合戰術要求的最優或者滿意的飛行航跡,以保證圓滿的完成導彈的飛行任務[2]。典型的規劃算法有:Voronoi圖算法[3]、A*算法[4]、粒子群算法[5]、遺傳算法[6]和蟻群算法[7]等。其中,Voronoi圖算法求取最短路徑相對簡便實用。

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

1 航路規劃的約束條件

1.1 最大航程的約束

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

S≤Smax

(1)

1.2 最小轉彎半徑和最小相鄰航路點間距的約束

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

(2)

式中:θ為轉彎角度;rmin為最小轉彎半徑。

1.3 初始航路最小距離

為了確保導彈發射后能調整進入穩定狀態,還需考慮發射后初始航路最小距離L0,1的約束[9],即其值要大于或等于已知參數L1,min:

L0,1≥L1,min

(3)

1.4 導彈末端航路最小距離

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

Ln-1,n≥Ln,min

(4)

1.5 導彈最大轉彎角度

導彈在轉向點進行航向調整時,其角度Ai受其性能影響,必須小于或等于導彈最大轉彎角度,即其值要小于已知參數Amax:

Ai≤Amax

(5)

1.6 航路點最大個數

航路規劃中要盡量減少中途轉向點,從而減小導彈誤差和減少姿態調整時間。即導彈實際航路點個數N要小于或等于已知最大航路點個數Nmax:

N≤Nmax

(6)

1.7 其他約束條件

末端進入航向:導彈在最后攻擊目標時,末制導雷達需要搜索航向,方能準確捕捉目標實施攻擊。

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

2 Voronoi圖算法原理

2.1 威脅導彈航行安全因素的分析

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

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

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

綜上,將高程點作為掩護和威脅的模型,下文統稱威脅點并建立模型,在仿真試驗中將海圖的高程點代表雷達點、山峰點。

2.2 基于Voronoi圖的威脅點模型建立

Voronoi圖在表示點要素相互關系方面具有優勢。在二維平面中,在形成Voronoi圖的點集里,任意的兩點之間連線的垂直平分線所構成的圖形,該圖形包含若干多邊形[11]。通過Voronoi圖可以有效地將威脅點以拓撲結構表示出來。圖1中是以高程點作為節點生成的Voronoi圖。

Voronoi圖數學表示為點集{P0,P1,…,Pn}里的節點Pk,則其區域Rk的定義為:

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

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

(7)

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

2.3 Voronoi圖路徑規劃

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

文中定義轉向角度不小于90°的轉向點所在區域為毛刺尖角區域,下文統稱尖角區。由圖3可以看出以Voronoi圖結構的航路算法中,轉向點個數有5個,轉向角度小于90°的轉向點只有2個,則尖角區有3個。這對于反艦導彈的飛行航路的穩定性與航程距離是十分不利的。

3 Bezier曲線原理

Bezier曲線可以將少量的數據擬合出連續的平滑曲線,這種曲線具有高光滑度和較高精度的特點。

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

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

(8)

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

(9)

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

4 算法的自適應調整

4.1 Bezier曲線自適應調整

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

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

4.2 Bezier曲線折線化航路自適應調整

反艦導彈飛行中要盡量保持直線的航路且轉向次數盡可能的少,轉向角度盡可能的小。

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

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

5 航路仿真實驗

5.1 可行性分析

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

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

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

5.2 比對分析

進一步比對分析所提方法與直線航路、Voronoi圖算法的差異。三種方法的結果如圖13、圖15、圖16所示。仿真結果驗證了在Voronoi圖基礎上的Bezier曲線算法進行航路規劃的可行性和有效性,所求解的可行航路能夠充分確保反艦導彈規避威脅的同時有效的減少飛行航程和轉向點個數。依據發射點、目標點及各轉向點的圖上坐標與經緯度的關系分別計算三種方法的航路航程。

表1 航路對比表

將航程、轉向點個數和轉向角度大于90°的轉向點個數整理后見表1所示。可以得出,通過Bezier曲線折線化的航路,其轉向點個數、轉向角度和航路總航程都優于Voronoi航路,并且更接近理想情況下的直線航路。

6 結束語

經理論分析、試驗論證,得:

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

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

當然對于更多的復雜的實戰問題,海圖中威脅點的威脅程度和威脅半徑可能是多樣的,必須構造相應的加權Voronoi圖,才能在Voronoi圖的各邊獲得最大的安全系數。此外,運用文中所提出的基于Voronoi圖和Bezier曲線算法的混合方法來解決動態不確定環境下反艦導彈航路規劃問題,這也是下一步的研究重點。