基于改进Voronoi 图的集群无人机区域覆盖方法

陈 捷，刘海颖，2，李志豪，谢远龙

（1.南京航空航天大学航天学院，江苏南京 210016；2.南京应用数学中心，江苏南京 211135）

在当前智能体自主平台处理信息能力以及传感器等任务载荷限制的条件下，面对日益多样化的任务要求和高度复杂的执行环境，智能体的应用方式逐渐趋向于集群协同作业[1-2]。在集群协同作业技术研究中，集群无人系统的区域覆盖一直是研究的热点问题，其指一定数量无人机在相互配合、协同合作中对目标区域进行全局覆盖[3]。在对受灾人员救援以及信号基站搭建等场景进行搜索覆盖时，需要对目标任务区域进行划分与分配。本质上，集群协同覆盖区域分配问题是一种任务规划问题[4]，需要在多种约束条件下，将目标任务根据权重值分配至集群内不同的无人机，其关键部分集中在数学模型的建立、集群控制律等输入的动力学求解以及分区算法设计上[5-6]。

在无人机集群覆盖任务研究中，一般可将覆盖问题大致分为静态覆盖和扫描覆盖两种类型。在静态覆盖中，无人机集群的目标是收敛到期望状态进而优化某些性能标准[7-8]；在扫描覆盖中，集群内无人机因其性能指标随时间而变化，位置也在不断移动[9]。文中针对集群区域覆盖任务规划中定位系统测量不确定性进行研究，目前解决定位不确定性问题的一般方法有概率法[10]、安全轨迹规划[11]以及Voronoi 图法[12-14]。

文中主要讨论的内容为如何实现集群无人机在规划过程中对任务区域的全覆盖，使其覆盖评价指标达到最大；同时对传统Voronoi 图进行改进，设计合理分区算法对无人机责任侦察区域进行分配及规划搜索路径，在保证覆盖质量的前提下实现对目标区域的快速搜索。

1 Voronoi图划分方法设计

1.1 传统Voronoi图原理

传统Voronoi 图应用于集群区域覆盖问题时，无人机位置需要被精确定位[15-16]。目标区间能够通过Voronoi 图在集群内进行分配，每架无人机的责任区域（称为Voronoi 单元）被定义为比集群中任何其他无人机更接近自身的空间区域：

集群中无人机数量为6 架时构成的Voronoi 图如图1 所示。

图1 Voronoi图

目标任务区域的抽象Voronoi 图主要性质为：

其中，Int(·)表示集合论元的内部。

定义无人机i的Delaunary 邻居，表示为Ni，它们是划分网络中Voronoi 单元与无人机i共享一条边的无人机：

1.2 Guaranteed Voronoi图原理

针对传统Voronoi 应用于区域覆盖算法的不足，在其基础上引入无人机固有的位置不确定性，提出一种Guaranteed Voronoi(GV)图划分方法。在任务区域中定义一组不确定区域：

由于集群无人机的GV 图划分结果并不是对空间Ω的完全镶嵌，因此中立区对应于未在网络的任何节点上分配的空间的点集。图2 所示为当集群内含有6 架无人机时的GV 图。

图2 Guaranteed Voronoi图

2 区域覆盖方法设计

将GV 图划分方法应用于集群无人机区域覆盖问题，提高其最终集群覆盖率。具体流程如下：

1）获得无人机状态信息，包括位置信息、高度信息、搭载视觉传感器的水平量θi、纵向量hi以及视域角2δi。

2）建立无人机感知区域，考虑无人机内部GPS固有的不确定性，定义无人机保证感知区域为：

3）使用GV 图将整个任务区域划分为若干子区域，并分配至无人机集群，分配依据为无人机的保证感知区域以及空间权重系数。无人机i获得责任区域后，计算其对应的覆盖质量函数fi()· ：

其中，0 和1 分别对应视觉传感器的最低和最高观测质量。

4）根据计算所得fi()·，结合集群中每架无人机通过GV图得到的重要性因子φ，计算覆盖质量目标：

覆盖质量目标H通过对任务区域内无人机视觉传感器观测质量与分配到的重要性因子积分得到，其能够反映任务无人机集群对于任务区域的覆盖程度。

5）设置集群控制律使得集群覆盖质量目标单调增加，输出无人机期望位置，将所得覆盖质量目标与设定集群覆盖质量目标H＇进行对比，判断是否实现集群最大化覆盖。

3 仿真结果与分析

利用Matlab 对集群无人机区域覆盖方法进行仿真。在仿真实验中，设置任务区域场景为凹形区域，目标区域中所有的位置点赋予同样的重要性，集群覆盖质量目标设置为H＇=8。设定集群无人机都存在定位不确定性，集群无人机初始位置如表1 所示。

表1 集群无人机初始位置

当集群覆盖算法中不考虑视觉传感器观测质量，仅依靠GV 图方法对集群无人机进行区域划分时，集群最终划分位置如图3 所示。

图3 集群最终划分位置

集群无人机覆盖质量目标比变化趋势如图4 所示，当无人机中没有搭载视觉传感器，仅依靠GV 图方法对任务区域进行划分时，集群覆盖质量目标不能达到设定值。

图4 覆盖质量目标比变化图

当集群覆盖算法考虑视觉传感器时，设置机载视觉传感器纵向量限制为=30°，视锥角范围设置为=15°,=35°,∀i∈In，无人机高度范围是zmin=0.3 m，zmax=2.3 m。区域覆盖算法中对集群无人机的控制增益设置为：无人机水平与纵轴方向上Kx=0.25，Ky=0.25，Kz=0.25；视觉传感器水平 量Kth=0.000 5，纵向量Kh=0.000 5，视锥角Kzoom=0.000 5，仿真步长为0.2 s。运行结果如图5 所示，无人机感知区域以灰色填充，保证感知区域的边界以虚线表示。

图5 集群运行最终位置

图6 和图7 分别为集群无人机对任务区域的覆盖率变化曲线以及覆盖质量目标比变化曲线。对于凹形地图，集群区域覆盖任务规划算法能够使集群对任务区域的覆盖率达到90.31%，同时覆盖质量目标随着仿真时间的推移单调增加，最终达到设定目标值。图8 为集群无人机位置误差变化图，对于凹形任务环境中，集群无人机在三个维度上的误差均小于0.1 m，且逐渐收敛到0。

图6 集群运行覆盖率变化图

图7 覆盖质量目标比变化图

图8 集群无人机位置误差变化图

4 结论

针对集群无人机对任务区域的覆盖问题，文中提出一种基于改进GV 图的集群覆盖方法。首先，对传统Voronoi 图进行改进，提出GV 图方法，并对目标任务区域进行划分；其次，建立无人机集群感知区域模型，利用GV 图为集群内无人机分配责任子区域，根据视觉传感器观测质量以及分配的重要性因子计算对应的无人机覆盖质量目标；最后，在覆盖质量目标的约束下，将集群无人机引入局部最优配置，实现对任务区域的最大范围覆盖。通过仿真试验表明，所提区域覆盖方法能够使无人机集群达到最优区域分布，并对目标区域有较高的覆盖率。