基于赋权Voronoi图的舰载机飞行甲板调运路径规划*

李晓杰　谢　君

(海军工程大学电子工程学院　武汉　430033)

LI Xiaojie　XIE Jun

(Electronic Engineering College，Naval University of Engineering, Wuhan　430033)



基于赋权Voronoi图的舰载机飞行甲板调运路径规划*

李晓杰谢君

(海军工程大学电子工程学院武汉430033)

为解决舰载机这一不规则实体在飞行甲板环境中的调运路径规划问题，提出了一种基于Voronoi图的路径网络生成方法。对舰载机的调运环境和调运实体进行几何建模，采用Voronoi图法进行规划得到路径网络图并赋权，用Dijkstra算法搜索出调运候选路径，并进行了碰撞检测。对某型航母某一时刻的舰载机布列调运进行仿真，结果表明该方法简单合理，能够为舰载机调运指控人员提供决策参考。

舰载机; Voronoi图; 路径规划

LI XiaojieXIE Jun

(Electronic Engineering College，Naval University of Engineering, Wuhan430033)

Class NumberTP391.7

1　引言

航母是一个国家国力强盛的重要标志，其作战任务的完成主要依靠舰载机。现代战争节奏加快，对舰载机的出动回收能力提出了新的要求。在较短的时间内为舰载机规划出一条的合理的调运路径，能够有效缩短舰载机的出动准备时间，从而最大限度地发挥舰载机的作战能力。

舰载机在航母上的调运作业可分为机库调运和飞行甲板调运两部分[1]，二者在调运路径规划方法上具有相似之处，但不同之处在于：机库舰载机布列紧凑，若考虑单架舰载机在此密集环境内的调运移动大都没有实际意义，因此机库调运作业主要是对舰载机出库顺序的编排[2～3]；飞行甲板舰载机布列较为稀疏，且其调运作业的时间要求更高，路径规划意义明显。文献[4]创建了舰载机机库调运作业交通网络，但并没有给出具体的路径规划方法。文献[5～8]基于新兴智能算法，将舰载机简化成质点来搜索最短路径，然而舰载机几何形状不规则，简单的将舰载机视为质点处理并不准确，这就需要对舰载机实体进行合理建模。文献[9]采用矢量数据和栅格数据结构相结合的方法对机库内舰载机实体几何模型进行了描述，可为本文舰载机飞行甲板调运的模型处理提供借鉴。

已有文献大多以调运路径长度为优化指标[10～11]，这实际上只考虑了舰载机沿线段运动的用时，由于舰载机转向时移动较慢，因此舰载机在转向结点处的用时不可忽略。本文以飞行甲板舰载机调运时间为优化指标，通过对调运环境和调运实体进行几何建模，采用Voronoi图进行规划得到路径网络图并赋权，然后采用Dijkstra算法搜索候选路径，并进行碰撞检测。Voronoi图法的优势在于：它倾向于使图中运动实体与障碍物之间的距离最大化，并且Voronoi图法具有超越其他大多数避障技术的可执行性。通过Voronoi图法得到的路径既保证了舰载机调运的安全性要求，又能满足调运作业的时间要求，提高了调运作业效率。

2　调运环境和调运实体几何模型

调运环境和调运实体建模的目的是建立一个便于进行路径规划使用的数学模型。飞行甲板是舰载机起降和停放的主要场所，舰载机是调运活动中最重要的实体。由于几何法在建模方面具有精确、高效的优点，因此采用几何法对飞行甲板和舰载机进行建模。

以美国“尼米兹级”核动力航母为例，其飞行甲板长332.8m，最大宽度78.4m，在对飞行甲板建模时，舰岛、起飞装置、升降机、飞行甲板边缘以外部分可视为舰载机调运过程中的永久障碍物予以保留，作出其几何轮廓模型，其他设施忽略。以左下角某一点为坐标原点，使飞行甲板平面都落入第一象限，x轴水平向右，沿舰艏方向，y轴垂直于x轴向上。作出飞行甲板的外接矩形，飞行甲板上面的永久障碍物等比例画出并定位在坐标系中，并用深色区域表示。飞行甲板几何模型如图1所示(比例尺为1∶100)。

图1　“尼米兹级”核动力航母飞行甲板模型

对舰载机进行建模时，根据机型特点，舰载机几何结构模型被表示成不同的对称多边形，这里每个多边形就是包围舰载机实体边界的简单平面多边形。为简化问题，以舰载机几何中心作为其旋转中心，若舰载机模型几何中心坐标p(x0,y0)确定，则模型其他顶点坐标即可确定。以“尼米兹级”核动力航母上搭载的两种飞机(F/A-18、E-2C)为例，F/A-18机长17.1m，机宽11.4m；E-2C机长17.54m，机宽24.56m，其模型如图2所示(单位：cm，舰载机比例尺为1∶100)。

图2　航母舰载机几何模型

3　Voronoi图概述

Voronoi图由一组连接两邻点直线的垂直平分线组成的连续多边形组成，对于点集{P1,P2,…,Pn}中某一点Pk，其Voronoi区域Sk定义为

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

(1)

其中，称点集{P1,P2,…,Pn}为该Voronoi图划分的生成元，规划得到的线段称为Voronoi边。普通Voronoi图如图3所示。

图3　普通Voronoi图

一般图形的Voronoi图将生成元扩展到任意形状的平面多边形、线段和点。算法思想是首先在这些几何图形的边界上设点(称为母点)，然后将这些母点视为生成元作出Voronoi图[12]，然后抹去多边形内部的Voronoi边。如图4为一般图形的Voronoi图。

其中小圆点即为母点。本文将图中规划出的Voronoi边视为舰载机调运路径网络来求取舰载机调运候选路径。

图4　一般图形Voronoi图

4　基于赋权Voronoi图的舰载机调运路径规划

舰载机调运路径规划是指舰载机按照某一性能指标，搜索出一条从起始状态到目标状态的最优或近似最优的无碰撞路径。基于Voronoi图法进行舰载机路径规划的思路是：舰载机在调运前进过程中时刻满足一个条件，即若存在可行路径，则路径宽度一定大于等于舰载机本身的宽度，基于此，可以以舰载机机宽的一半长度对障碍物进行缓冲区扩充，而将被调运舰载机视为质点，进而采用Voronoi图法规划出路径网络图，则若存在可行路径，可行路径必存在此路径网络图中，然后对路径网络图进行赋权处理，进而通过Dijkstra算法搜索出候选路径并进行碰撞检测。

基于Voronoi图法的舰载机路径规划步骤为：

1)对非调运舰载机和障碍物进行缓冲区扩充，合理设置母点，作出Voronoi图。

2)将Voronoi图中非调运舰载机和障碍物缓冲区内的Voronoi边删去，得到路径网络图并对图中各条线段赋权。

3)采用Dijkstra算法在赋权路径网络图中找出候选路径。

4)进行碰撞检测，验证所得候选路径的可行性。若可行，则该条候选路径即为所求；若不可行，则只需对已有的赋权路径网络图进行修改，然后返回第3)步。

其流程如图5所示。

4.1作出Voronoi图

以舰载机F/A-18为例，当被调运舰载机为机型F/A-18时，其余舰载机为障碍物，需要进行缓冲区扩充。对于非调运舰载机，以被调运舰载机宽度kf的一半长度进行缓冲区扩充，一种扩充模型如图6所示。

对飞行甲板上的障碍物做相同处理。在调运过程中，由于舰载机可适度伸出飞行甲板边缘，取被调运舰载机机宽kf的四分之一长度，对飞行甲板边缘做缓冲区扩充。

图5　路径规划流程图

图6　舰载机F/A-18缓冲区扩充

舰载机路径规划中Voronoi图法的运用主要在于母点的设置，母点的设置依据以下原则:

1)将障碍物缓冲区边界的端点设置为母点。

2)障碍物缓冲区上的母点个数原则上与其边界长度成正比。

一般来说，母点设置密度越大，则路径规划结果越准确，但路径线段也会越多，造成计算量加大。在设置母点时，应均衡考虑路径规划的精度和计算复杂度。以舰载机F/A-18为例，在其边界端点设置母点以后，在其边长以kf/2的长度为一个区间，均匀设置母点，如图7所示为舰载机F/A-18母点设置(单位：cm，比例尺为1∶100)。

图7　舰载机F/A-18母点设置

利用Voronoi图法规划得出的路径网络图中，并不一定包含给定的起始点和目标点，因此需要对已经建立的路径网络按就近无碰规则生成包含起始点和目标点的路径图。如果起始点和目标点都在路径网络中，则不需要处理。如果起始点和目标点都不在路径网络中，则在起始点和目标点附近网络路径上作一点并分别与起始点和目标点相连接，这样就可以找到一条从起始点到目标点的路径。

4.2Dijkstra算法找出候选路径

对得出的路径网络图进行最优路径搜索，必要时可先对路径赋权值，然后进行路径搜索。本文以调运时间为优化指标，设置舰载机在沿直线段调运时的单位距离用时为tl，线段距离为s，在某结点处(转向角度为θ，顺时针转向θ取值为正，反之为负)的转弯用时为tz，并规定tz的取值满足以下条件：

(2)

由于结点处转向值具有多个维度，因此需要分别计算各条路径通过该结点的时间长短。处理方法是将该结点所连各条线段的另一端点(即非此路径结点)相连接，从而将该结点转弯用时等价为直线调运用时。图8(a)为某一结点连接的各条边，则将时间长短作为权值赋值如图8(b)所示。

舰载机调运路径网络图经赋权处理后，便可以采用图论中的Dijkstra算法求解。Dijkstra算法用于计算一个节点到其他所有节点的最短路径，其主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。算法思想为：设G=(V,E)是一个带权有向图，把图中顶点集合V分成两组，第一组为已求出最短路径的顶点集合(用S表示，初始时S中只有一个源点，以后每求得一条最短路径，就将顶点加入到集合S中，直到全部顶点都加入到S中)，第二组为其余未确定最短路径的顶点集合(用U表示)，按最短路径长度的递增次序依次把第二组的顶点加入S中。在加入的过程中，总保持从源点v到S中各顶点的最短路径长度不大于从源点v到U中任何顶点的最短路径长度。

图8　路径网络图赋权

根据Dijkstra算法，在当前赋权网络图中可以求出一条最短路径，称之为舰载机调运候选路径。

4.3舰载机碰撞检测模型

这样得到的候选路径不一定是可行路径，以舰载机F/A-18为例，其形状机长大于机宽，导致在结点处转弯时有可能与障碍物发生碰撞，因此需要在路径结点处进行舰载机碰撞检测[13]。

进行碰撞检测需要在结点处进行舰载机转向计算。以舰载机外接矩形作为其碰撞检测模型，假设舰载机长度为cf，宽度为kf，舰载机的转向中心坐标为p(x0,y0)，则舰载机的转向半径r为

(3)

图9　舰载机转向影响区

转向影响区的计算方法为：舰载机以点p为圆心，以r为半径，旋转角度为θ。如图9所示，深色区域即为转向影响区。

通过计算转向影响区与障碍物是否有重叠，即可判断舰载机在结点处是否与障碍物发生碰撞。若检测到碰撞，则在赋权网络图中删除连接此结点的两条线段或将两条线段权值设置为无穷大，表示此路不可行，然后返回步骤3)重新对修改后的赋权网络图进行候选路径搜索。

5　仿真验证

以“尼米兹级”核动力航母为例，某一时刻舰载机在飞行甲板上的布列如图10所示，其中位置S为被调运舰载机起始位置，G为被调运舰载机目标位置。

图11为对飞行甲板障碍物进行缓冲区处理。在缓冲区边缘取母点，然后作出Voronoi图。为简化计算，已将缓冲区合并处理，并取合并后的缓冲区母点坐标进行计算。图12为使用Matlab进行Voronoi图规划得到的路径网络图，图13中实线段为使用Dijkstra算法搜索得到的调运候选路径。

图10　舰载机飞行甲板布列图

图11　飞行甲板障碍物缓冲区处理

图12　飞行甲板Voronoi图

图13　舰载机调运最短路径

将候选路径结点坐标按照路径顺序取出，其坐标和转向角度如表1所示。

表1　路径节点数据

然后采用作图法在实体图中将路径结点处调运影响区域标出，若与障碍物有重叠，则此路不可行；否则，此路即为所求路径。如图14舰载机在调运结点处与障碍物无重叠区域，表明此路可行。

仿真结果表明，该算法简单合理，在路径客观存在的情况下，能在已知给定的环境中利用Voronoi图法迅速规划出路径网络图，并由此求解得到舰载机调运路径。

6　结语

本文在对已知的飞行甲板环境和舰载机实体进行建模的基础上，研究了Voronoi图法在舰载机调运作业中的应用，为飞行甲板舰载机调运寻找一条从给定的起始点到目标点的满足无碰条件的最优路径，并进行了仿真验证。结果表明，将Voronoi图法应用于航母舰载机调运路径规划是可行的，该方法能够有效提高舰载机的调运效率，并且能够为其他工程领域的优化问题提供借鉴。

图14　路径结点碰撞检测

[1] 刘钦辉,邱长华,王能建.考虑空间约束的舰载机作业调度模型研究[J].哈尔滨工程大学学报，2012，33(11)：1435-1439.

[2] 刘亚杰,李忠猛,谢君.基于Petri网的舰载机出库调度建模方法[J].火力与指挥控制，2015，40(9)：152-156.

[3] 桂周，刘爱东.某型航母舰载机机库内调运方法设计[J].计算机与现代化，2014(11)：110-112.

[4] 杨炳恒，韩峰，王海东等.舰载机机库调运作业路径[J].舰船科学技术，2012，34(8)：141-143.

[5] 熊华，齐玉东，司维超等.基于GA算法的舰载机舰面移动路径规划[J].价值工程，2014，7：35-37.

[6] 李耀宇，朱一凡，齐鸣等.舰载机甲板布列调运优化方法研究[J].指挥控制与仿真，2013，35(2)：125-131.

[7] 司维超，韩维，史玮韦.基于PSO算法的舰载机舰面布放调度方法研究[J].航空学报，2012,33(11)：2048-2056.

[8] 司维超，韩维，宋岩等.基于多种群协作混沌智能算法的舰载机出动调度[J].计算机应用研究，2013，30(2)：454-457.

[9] 刘亚杰，翁辉，陈晓山.一种基于“矢栅结合”的机库舰载机调运作业环境建模方法[J].装甲兵工程学院学报，2014，28(2)：75-78.

[10] 司维超，齐玉东，韩维.基于融合Dijkstra的凸壳算法的舰载机机库调运规划[J].系统工程与电子技术，2015，37(3)：583-588.

[11] 刘亚杰，李忠猛，陈晓山.考虑空间约束的机库舰载机调运路径规划方法[J].海军工程大学学报，2014，26(3)：100-103.

[12] 张有会.关于一般图形Voronoi图的近似构造法的研究[J].数值计算与计算机应用，2002(3)：216-225.

[13] 张智，林圣琳，夏桂华等.舰载机甲板调运过程避碰路径规划研究[J].哈尔滨工程大学学报，2014，35(1)：9-15.

Path Planning of Carrier-borne Aircrafts on Flight Deck Motion Schedule Based on Assigned Weights Voronoi Diagram*

To solve the problem of path planning of irregular carrier-borne aircrafts motion schedule on flight deck, a generation method of path network was proposed based on Voronoi diagram. This paper modeled the motion schedule environment and entities of carrier-borne aircrafts, used Voronoi diagram method plan path to get path network diagram and assigned weights to the segments of path network diagram, used Dijkstra algorithm search out motion schedule candidate path, and did the collision detection. The motion schedule simulation result of a certain time carrier-borne aircrafts allocation showed that this method was simple and reasonable, and can provide decision reference for command and control officer of carrier-borne aircrafts motion schedule.

carrier-borne aircrafts, Voronoi diagram, path planning

2016年2月31日,

2016年3月12日

李晓杰,男,硕士研究生,研究方向：系统工程。谢君，女，博士，副教授，研究方向：系统工程。

TP391.7

10.3969/j.issn.1672-9730.2016.08.011