某型无人机群的监视覆盖任务航路规划

Route Planning of Surveillance Coverage Mission for a Certain Type of UAV Group

摘要: 利用无人机群执行监视任务，在边界和区域管控、反恐防爆监视以及军事应用中具有很高的效费比。无人机群监视覆盖航路规划算法是提升无人机群监视任务效率和能力的核心算法。传统覆盖航路规划算法结果样式单一、对抗性环境下灵活性差，区域划分方法不便于计算机自动生成。本文提出了基于人工势场和遗传算法的监视覆盖航路规划算法，生成样式多样、监视任务执行中对抗性好的监视覆盖航路。在人工势场法的基础上，将激发势场的种子编码为二元组串形式的基因，通过交叉、变异、合并等算子的操作增加种子样式的多样性，从而规划出转弯少、监视时间间隔短、对抗性好的监视覆盖航路。最后通过算例对算法进行了验证，结果表明算法有效地满足了监视任务覆盖航路规划的需求。

Abstract: Using drones to carry out surveillance tasks has a high efficiency cost ratio in border and regional control, anti-terrorism and explosion-proof surveillance and military applications. The route planning algorithm of UAV group surveillance coverage is the core algorithm to improve the efficiency and capability of UAV group surveillance task. The traditional coverage route planning algorithm results in a single style, poor flexibility in the adversarial environment, and the area division method is not convenient for automatic computer generation. In this paper, a surveillance coverage route planning algorithm based on artificial potential field and genetic algorithm is proposed to generate a variety of surveillance coverage routes with good adversary in the execution of surveillance tasks. On the basis of the artificial potential field method, the seed of excitation potential field is encoded as a gene in the form of binary string, and the diversity of seed pattern is increased through the operation of crossover, mutation, merge and other operators, so as to plan a surveillance coverage route with fewer turns, short surveillance interval and good antagonism. Finally, an example is given to verify the algorithm, and the results show that the algorithm can effectively meet the needs of surveillance mission coverage route planning.

1. 引言

无人机航路规划是指在特定约束条件下，寻找从起始点到目标点并满足无人机性能指标的最优或可行的航路，耗费小的路径不仅节省了无人机运行的成本，也增大了无人机完成任务的成功率，并且安全性高的路径也能提高无人机的存活率。覆盖航路规划CPP (Coverage Path Planning)是指要为无人机规划一条能通过所有感兴趣的点的路径，是无人机监视任务规划中需要解决的关键问题之一。

近期，受2019新型冠状病毒(COVID-19)影响，国外许多国家下达了行动管制令，以色列等多个国家军队和警察运用无人机对城市内的居民进行监视，以确定居民的动向。加拿大一公司开发出“流行病无人机”平台，利用无人机监视体温，在人群中寻找表现出症状的人。在我国，多个省市都动用了人脸辨识相机系统、监视器及监控无人机来侦测隔离者的动向，全方位多角度，高密度监控，无人机群的监视覆盖运用目前比较广泛。

李御驰 [1] 等提出了一种基于遗传算法的无人机监视覆盖航路规划算法。对监视覆盖航路进行建模，将任务区域网格化，将势场种子编码成二元串组基因后进行算子操作，利用遗传算法生成监视覆盖航路，并在最后进行仿真。

李艳庆 [2] 等提出了一种基于遗传算法的多无人机航路规划方法。通过对无人机的转弯角进行基因编码，将多无人机的监视面积覆盖率作为适应度函数，并进行相应的遗传操作，依据实时监视面积覆盖率最大原则，对多无人机协同区域监视进行航路规划。

陈海等 [3] 证明了从能量角度来看无人机转弯过程比直线飞行过程效率低，定义了凸多边形任务区域的长度和宽度，并将凸多边形区域中的最短飞行路程问题转化为求凸多边形的最小跨度问题。他们按照“点边式”宽度算法，提出凸多边形宽度出现时，支撑平行线必与一条边重合，无人机沿宽度出现时支撑平行线的方向飞行才能获得最少的转弯次数，也就能够得到最短的飞行路程。但在地形起伏大的任务区域，需要加入地形高程等约束进行三维航路规划。

覆盖航路规划问题在机器人领域 [4] [5] [6] 有较多的研究。但是，如果将这些方法应用于监视飞行器的覆盖路径生成，则在一次覆盖后，其对手可以很容易地掌握这些路径的规律性，不能满足监视任务的不可预测性和覆盖任务目标的频繁性要求。

本文首先在任务区域网格化模型的基础上，提出了区域划分的方法，然后建立了基于遗传算法规划无人机群监视覆盖航路。

2. 区域划分方法

对于多无人机覆盖航路规划，需要对各个无人机进行任务分配。假定无人机群有 架无人机。一般而言，根据无人机的数量把指定区域划分为相互隔离的子区域，且子区域的数量与无人机的数量相同。

2.1. 任务区域网格化

对于要监视的目标区域，必须做到全覆盖。首先需要对目标区域进行网格化处理，使我们可以通过访问网格节点的方式实现对目标区域的覆盖，这里我们采用正方形的网格进行网格化。网格化处理时需要让无人机能够无缝隙的覆盖目标区域的各个网格，假设无人机的探测范围在地面的投影是以自身为圆心、以r为半径的圆形区域，则网格的大小需要根据无人机的探测半径r来决定。因此，我们可以将覆盖问题转化为网格扫描问题，任务区域就可以使用网格的集合来表示，设为A。网格要小于这个投影区域的大小，但又要尽可能的大。如图1所示，则网格的边长 最大可以为：

$c=\sqrt{2}r$

Figure 1. Grid unit distance

图1. 网格单位距离

2.2. 矩形任务区域划分

对于矩形任务目标区域，我们采取简单的平均分配的方式。对于无人机编队，有n架无人机，将矩形任务区域进行n等分。为便于无人机的部署，采用沿着矩形的X轴方向进行等分的方式，如图2所示。一般而言，定义长边所在为X轴。

2.3. 不规则任务区域划分

实际情况中，更多的任务目标区域往往是不规则的形状。

人工势场法 [4] 是由Khatib提出的一种虚拟力法。它的基本思想是将移动机器人在周围环境中的运动，设计成一种抽象的人造引力场中的运动，目标点对移动机器人产生“引力”，障碍物对其产生“斥力”，最后通过求合力来控制移动机器人的运动。我们引入势场的概念对目标区域进行划分，将目标区域均分给 个无人机，也即划分责任区。不规则图形的最小外接矩形如图3所示。

Figure 2. Rectangle target area partition

图2. 矩形目标区域划分

Figure 3. Irregular target region

图3. 不规则目标区域

我们在不规则的区域平面内均匀分布随机生成的点，点与点的距离 $c=\sqrt{2}r$，每个点的势值为0。点的集合为S。

利用势值的概念对任务区域进行划分的步骤如下：

步骤一：任务区域的点集合S中分散地生成n个种子点，分别命名为 $Z_1,Z_2,\cdots ,Z_n$，并设其网格的势值均为1，其他网格的势值为0。

为了避免种子点过于紧密，对于任意两种子点的距离 $\left|x_m{x}_n\right|$ ( 其中 $m<n$ )，如若 $\exists \left|x_1{x}_2\right|<\frac{2x_0}{n}$，则重新生成种子点。

步骤二：并行地更新势值为0的网格的势值，从与种子点距离为1的邻居网格中按照一定的规则，这些规则可能是顺时针第一个、逆时针第一个、上、下、左、右、随机等，选择势值为零的网格作为激发格，并设当前网格的势值为激发格势值 + 1。

步骤三：依次将距离 + 1，持续激发新的网格；当某一邻居网格的势值不为零时，跳过该网格的扩展。

步骤四：重复运行步骤二、三直到所有的网格势值均为非零，转步骤五。

步骤五：n个种子点衍生出来的区域则为n架无人机的责任区。

由于是并行操作，最后得出的n个责任区大小会尽可能的相等。

利用该方法划分不规则区域如图4所示。

3. 监视覆盖航路规划问题建模

3.1. 人工势场法生成覆盖航路

人工势场法生成覆盖航路规划算法是指从一个起始的网格出发，按照一定的规则沿着势场运动，最终会形成一个覆盖航路。覆盖航路的生成样式和势场值的设置以及运动规则密切相关，不同的势场值设置方法以及规则，生成的覆盖航路不同。

Figure 4. Irregular division

图4. 不规则区域划分

传统的基于人工势场的覆盖航路生成方法是在两个点之间，按照势值递增的趋势生成势场，然后依据势场生成航路，算法在避障以及覆盖效率方面有不错的效果，但是生成的样式比较单一。

我们根据区域划分生成的人工势场应用人工势场的发现进行覆盖航路规划；包括两个步骤：

步骤1：无人机从起始网格出发，移动向势值最小的邻居网格，并将起始网格标记为已覆盖。

步骤2：无人机不停地向势值最小的未覆盖的邻居网格移动。

3.2. 监视覆盖航路的目标函数

根据无人机监视任务的性质，监视覆盖航路的优劣主要取决于覆盖航路实际执行的效率和效果，也就是要更快、更频繁、更不可预测地完成对任务区域的覆盖监视，这就要求航路的转弯的次数和角度要少、对单个网格的监视间隔要小、航路变换多样。因此，监视覆盖航路规划的目标函数主要有以下几个：

1) 转弯角度总值最小

功耗受转弯总数影响。在整个飞行任务中需要转多少弯是一个主要问题。根据前文我们可以得知，无人机在飞行过程中，拐弯的次数越少，消耗的能量和时间等资源就越少，航路的优越性越好。

对此，我们使用航路中所有拐弯角度总和 $z_1$ 来度量航路的这一个性能，并将这个总和称为拐弯角度总值。

$z_1={\displaystyle \underset{i=1}{\overset{n}{\sum }}{q}_i}$

其中， $q_i$ 为航路上第i个转弯的角度， $z_1$ 越小，效率越高。

2) 最大转弯角度

也即是无人机在航路规划中允许的最大转弯角度，对于相邻的两点 $\left(x_m,y_m\right)$， $\left(x_{m-1},y_{m-1}\right)$，需要满足

$\left|\arctan \left(\frac{y_m-y_{m-1}}{x_m-x_{m-1}}\right)\right|\le \theta$

其中 $\theta$ 角是无人机行驶过程中的最大转弯角度。

3) 网格上的势的总值及标准差最小化

为了反映对网格监视间隔的大小，我们提出了一种势值动态增加的机制，也就是在计算推进的过程中，所有网格的势值也在同步增加，但是刚刚覆盖过的网格的势值清零，这样，在计算过程中，网格的势值就与监视间隔的大小成正比，如果网格监视间隔时间大，则网格势值的增加就多。这样，就可以用网格的动态势值来评价对网格监视间隔。因此我们利用任务区域网格势值的总值、标准差来评价监视覆盖的效率。

我们可以利用任务区域的总势场值这项指标来判断覆盖航路的效率，

$Z_3={\displaystyle \underset{i=n}{\sum }{m}_i}$

并使用任务区域的势场值的标准差来确定航路的稳定性

$M=\frac{Z_3}{n}$

$Z_4=\sqrt[2]{\frac{{\left(m_1-M\right)}^2+{\left(m_2-M\right)}^2+\cdots +{\left(m_n-M\right)}^2}{n}}$

4) 航路的可预测性要小

对于监视任务，为使无人机的路线不被预测，应当不具有规律性，不可预测性越高航路越优越。

对此，我们选择使用遗传算法中的种子更新时间T来度量航路的不可预测性

$Z_5=T^{-1}$

4. 基于遗传算法的监视覆盖航路规划算法

4.1. 基因编码

最常用的基因编码方式是二进制编码 [7]，也即是01字符串。但是在航路规划中，若使用二进制编码，在进行遗传算法的变异、交叉、合并等算子时，会容易产生不可行的个体，大大降低了算法的效率和可行性。为了让产生的新的航路位置节点可行，我们使用二维坐标组作为基因编码。

4.2. 交叉、变异产生新的基因

1) 交叉算子

交叉 [8] [9] 是指通过就是两个个体把一部分或者多部分的基因相互交换从而产生新的个体。

2) 变异算子

基因发生突变就叫变异，会产生一定概率的不可预测性性波动，进而增加种群进化的多样性。通过变异可以增加航路规划的随机性，使航路的可选择性更加丰富多样。

3) 合并算子

在本问题中，提出一种合并算子，也即将两个基因进行合并操作而生成新的基因。如图5。

Figure 5. Merge operation

图5. 合并操作

4.3. 监视覆盖航路生成

基于遗传算法 [10] 的监视覆盖航路生成算法的步骤如下所示：

步骤1：初步骤1：初始化种群，生成种子，并确定种群的更新周期T，在任务区域网格中生成势场，无人机从起始位置 $\left(x_0,y_0\right)$ 出发，此时时间 $t=0$，移动向势值最小的邻居网格，并将起始网格标记为已覆盖。

步骤2：仿真步长向前推进 $t=t+1$，势场中所有网格的势值增加某个数值p，无人机从当前位置移动到势值最大的邻居网格 $\left(x,y\right)$ 中，网格 $\left(x,y\right)$ 的势值清零。当达到种子更新周期条件的时候，对种群进行交叉变异操作，并选择一个基因，重新生成任务区域网格的势场。

步骤3：当生成的覆盖航路满足要求的时候，停止计算。

5. 仿真实验

为了对算法进行测试，我们使用四架无人机完成对一个区域的监视任务。首先对目标区域进行划分，生成四个子区域，各无人机在各自责任区内基于遗传算法的航路规划。

对于任意一架无人机，其责任区为30*30的任务区域网格，我们选用点型、线型两种典型的人工势场种子编码产生遗传算法的初始种群。设定仿真每向前推进一步，所有点的人工势场均增加0.001，种群更新的机制为按照仿真时间进行更新，周期为T，也就是每向前推进T时间，利用算子更新遗传算法的种群，并从种群中随机选择一个种子更新当前的势场，继续生成航路。

在航路生成的过程中，每完成一次区域覆盖就对航路的性能参数进行测试统计，性能参数包括无人机转弯角度总值、区域网格势场总值、网格势场最大值、网格势场值的标准差等。

初始势场采用点型种子生成，四架无人机的初始势场如图6所示。

Figure 6. Initial potential field

图6. 初始势场

在多无人机路径规划时，为适应监视任务性质的要求，在任务过程中要调整各个无人机的责任区。以本次仿真为例，使用四架无人机进行监视覆盖任务，每进行5*900个仿真步长，也即是无人机分别对各自的责任区域进行了五次监视覆盖之后，重新分配一次责任区；因为遗传算子的变异特性，单无人机在子区域内的覆盖路径已经具有不确定性。

从仿真结果来看，转弯角度总值分布比较平稳，势场总值也比较平稳，网格势场最大值、势场标准差除初始外趋于平稳，无人机在子区域内能较好的生成预测性较小的航路。

6. 小结

本文通过结合人工势场法运用势场的概念对目标任务区域进行划分，并且依据势场对各个无人机进行初步路径规划，在监视覆盖航路的约束条件下，将势场种子编码成二元串组基因后进行算子操作，产生更多新的种子，增加航路变化的多样性。通过仿真验证算例的转弯角度总值、势场总值、网格势场最大值、势场标准差等结果，表明本算法可以满足监视覆盖航路多样性和对抗性的需求。最后通过在监视过程中定期改变各无人机责任区，增加监视路径的不确定性，以适应监视覆盖的要求。

仿真结果如下，图7~10所示。

Figure 7. Total turning angle

图7. 转弯角度总值

Figure 8. Total potential field

图8. 势场总值

Figure 9. Standard deviation

图9. 网格势场值的标准差

Figure 10. Maximum grid potential

图10. 网格势场最大值