利用加权Voronoi图对无人机飞行规划的问题研究*

李洪涛 赵纪初

（1.92941部队 葫芦岛 125001）（2.92728部队 上海 200040）

1 引言

随着通信技术日益成熟，我们对武器战场态势信息的需求也越来越精确，无人机将会承担越来越多的探测和打击任务，不同作战区域的环境，对无人机布置提出了更高更精准的要求，在最优区域划分方面有不少类似的研究，如Huy Trandac利用启发式算法来建立Voronoi多边形，确定二维扇区的边界［1］；唐小波、刘笠等提出了自适应的Voronoi图能力区划方法，使得配电站设置更合理高效，解决了部分区域电源覆盖面不全的问题［2］；戴福青提出了Power图的划分方法研究，将扇区结构特征作为约束条件，应用遍历搜索算法来搜索寻优，得到最终优化的扇区［3］。在无人机航迹规划方面，李亚女［4］、赵文婷［5］都利用了“V图的边的被探测概率最小”这一性质进行了航迹搜索和航迹优化。

2 定义及其相关算法

在能力范围的可视化方面，Voronoi图具有其独特的优势。该算法是由俄国数学家Georgy Fedo—seevich Voronoi首次提出，并以他的名字来命名。其在计算机辅助设计、图形图像处理、地理信息系统、智能决策领域以及优化算法［6］等方面有着广泛的用途。当所有触发单元的扩张能力或权重相同时，生成的是如图1（a）的标准V图，若权值不同生成的是如图1（b）的加权V图。

图1 标准Voronoi图与加权Voronoi图直观对比

这里关键的参数就是触发点扩展系数以及权重的问题，可以对体系对抗能力、态势感知能力和目标搜索能力进行评估。有许多方法可用于描述和计算作战能力，例如，武器装备性能指数方法［7］和徐瑞恩提出的AHP方法是普遍接受的方法，赵青松和其他相关学者［8］提出的武器装备系统控制能力空间中还有“层次性、协作性、松耦合性、多目标性和涌现性”的五个特征。加权Voronoi图的图像生成过程比较复杂，节点越多，其生成的Delaunay剖分三角网就越多，结构越复杂［9～10］。

3 飞行区域威胁能力划分

3.1 威胁能力指数

在实际飞行区域能力分析时，不同的能力指数根据目标对应属性有相应的计算方式，有基于云模型推理的方法、基于模糊的MODM方法、基于TOPSIS的方法、基于灰靶理论的方法等，不同的方式方法有不同的侧重点，一般采用多种方式计算而后进行一致性检验来评估威胁值。在下文中，每个飞行临近区域的威胁能力值用作Voronoi图的加权系数。由徐瑞恩提出的幂指数方法用于表示某种向量Y=（Y1，Y2，L，yi，L，YN），其单个节点的N个指标的表现，用I来表示单个区域威胁的效益指数，有I=Q（Y），其中，Q（Y）的具体形式为

式中：wi为幂指数；yi为影响飞行半径的环境因素或性能指标；K为调整因子，在比较不同型号飞行器，或计数与多个不同环境参考下的能力指数形成威胁边界之间的能力关系，这种方法相当于对不同偏好影响进行了指数的归一化，使不同的能力指数的生成处于能力评估的同一框架内，因此将其称为对无人机威胁能力一致性的调整系数。

等权条件下生成的威胁边界如图2所示，红色部分为飞行器在限制条件下的威胁范围，绿色部分为环境因素对威胁区域的控制包络。本文用Matlab随机生成15个区域节点和若干个环境限制点作为需要进行威胁区域划分的对象，分析在不同偏好权值的条件下组成的最大威胁范围。根据不同型号及其环境限制因素设定不同的威胁能力权值生成加权Voronoi图，如图3所示，其中各区域对应的能力指数转化成权值，一般采用标准计算法如下：

图2 相同威胁能力指数对应的威胁边界示意图

图3 不同威胁能力指数对应的威胁边界示意图

图4 对无人机探测区域的地形进行加权化生成的Voronoi控制边界示意图

在确定如何设定飞行路径对探测区域全覆盖问题上，则可以导入附带探测属性和指标能力的Voronoi图。在对于部分无需探测的区域或者已探知后对覆盖区域的影响，则可以通过删除节点或者降低节点权重系数的方式来呈现威胁覆盖边界，分析需要如何重新规划路径来弥补探测覆盖区。在不增加新路径的情况下可以通过移动邻近无人机位置来弥补该区域探测能力缺失。

图形的能力重构受到各武器节点加权距离最大的限制和区域环境因素的限定，从力学角度上可以看成加权Voronoi图中各节点之间具有保持最佳作用力与反作用力的性能。在加权Voronoi图中的动力传播机制就是各节点设定的加权值，并且这里分析的例子是属于相对均匀网络模型，不存在连接不相邻节点之间的链接关系或者是权值极大的关键节点。

3.2 无人机配置区域复杂度分析

无人机布置考虑的环境因素不仅仅包含了地形限制，同时需要考虑该区域敌我人员和装备等流动个体的影响，通过模型的建立可以分析图形的聚集密度、区域复杂度、邻近点指数等数据，从而来辅助宏观上的态势分析和战术布局，例如图5就是以环境影响和目标流动因素为因子构建的无人机群布点复杂度示意图。图中利用GIS工具提取了大量地图中可供分析的节点和线段，仍采用Delaunay三角剖分法对该区域进行复杂程度分析。通过构建后的图形呈现，可以根据情况适当合理地调整无人机部署，以及管理区域内与武器控制有关的资源。

图5 加入部分影响因子的无人机配置区域复杂度示意图

在更大分析要素中，各个武器装备节点类型属性不同，机动能力各不相同，因此，复杂度区域划分要考虑到可移动单位速度、目标类型甚至天气情况等。例如，移动速度权值设定上可以采用公式：

式中：Wi为目标速度权系数；Ti，Tj为不同机动能力的无人机通过该片区的时间，T为所有武器在该区域单元所停留的时间。若需要布置无人机对沿岸地域搜索，则需要考虑风力、降雨量、浪高等因素，通过数据归一化结合比重系数来计算该区域的权系数，其中加权Voronoi图的发生元可以设定为表示沿岸的线段和滩涂岛礁，或者自行添加参考点作为发生元，其权系数计算公式为

式中：Wk海域海况和天气权系数；Ai为风力、降雨量、浪高等数据处理后的权系数值；Ti为不同海域和天气情况下无人机正常通过指定区域所用时间；T为飞行器平均穿越指定区域所用的时间。因此，不同偏好的复杂情况分析就可以采用该复杂度对应的加权值带入发生元用以生成相应的加权Voronoi图。另外，假设我们只考虑4种复杂因子：i，j，k，l。那么在数据分析中，区域综合的复杂度计算可采用公式：

TC=Wi+Wj+Wk+Wl

在图5中我们可以比较直观地看出1区目标的复杂度较高、CV值大、因此该区域无人机群探测打击的威胁能力较高、地域人员装备情况也较为复杂。而2区相对复杂度低、能力分布较平均、地域人员装备情况较为简单。因此可推测在一般情况下，CV值和TC值是成正比的，也就是说复杂度越高的区域，其威胁能力分布也呈现出较为集中的特点。因此在无人机飞行规划的部署配置以及区域管控上，可以综合分析需要重点布置的范围和人员装备调整区域，使其在资源利用控制上更为合理高效。

4 结语

本文以无人机探测威胁能力为例，提出将作战武器能力和环境信息要素进行融合，利用Voronoi图将武器控制区域划分为有限个单元，根据不同的任务需求，将偏好的能力系数转换成相应的加权值，然后通过生成的Delaunay几何图形进行仿真分析。在无人机区域威胁分析中提出统计复杂度，将区域中飞行器平均穿越时间和其它战场态势信息生成复杂度权值用于生成Voronoi图，呈现效果较好，便于相关人员进行有针对性的研究分析。