基于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曲线算法的混合方法来解决动态不确定环境下反舰导弹航路规划问题,这也是下一步的研究重点。