ABSTRACT

In order to solve the problem that the traditional coverage route planning algorithm has a single style and poor flexibility in the confrontation environment, a genetic algorithm-based surveillance coverage route planning algorithm is proposed to generate a variety of surveillance and coverage routes for monitoring missions. On the basis of the artificial potential field method, the seeds of the excitation potential field are encoded into genes in the form of binary strings, and the diversity of seed patterns is increased by operations such as crossover, mutation, and merging, thereby planning less turning and monitoring. Short time intervals and good confrontation monitoring cover the route. Finally, the algorithm is verified by an example. The results show that the algorithm effectively meets the requirements of monitoring mission coverage route planning.

Keywords:Genetic Algorithm, Artificial Potential Field Method, Drone, Surveillance Coverage Route Planning

基于遗传算法的无人机监视覆盖航路规划 算法研究

李御驰，闫军涛，宋志华，张晗

空军工程大学装备管理与无人机工程学院，陕西 西安

收稿日期：2019年6月9日；录用日期：2019年6月21日；发布日期：2019年6月28日

摘 要

为解决传统覆盖航路规划算法结果样式单一、对抗性环境下灵活性差的问题，提出了基于遗传算法的监视覆盖航路规划算法，生成样式多样、监视任务执行中对抗性好的监视覆盖航路。在人工势场法的基础上，将激发势场的种子编码为二元组串形式的基因，通过交叉、变异、合并等算子的操作增加种子样式的多样性，从而规划出转弯少、监视时间间隔短、对抗性好的监视覆盖航路。最后通过算例对算法进行了验证，结果表明算法有效地满足了监视任务覆盖航路规划的需求。

关键词 :遗传算法，人工势场法，无人机，监视覆盖航路规划

Copyright © 2019 by author(s) and Hans Publishers Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY).

http://creativecommons.org/licenses/by/4.0/

1. 引言

无人机航路规划是指在特定约束条件下，寻找从起始点到目标点并满足无人机性能指标的最优或可行的航路。而覆盖航路规划的任务是确定一条路径，该路径通过感兴趣的区域所有点，同时避免障碍。经过查阅文献，发现由于无人机受到任务区域和性能的约束，关于监视覆盖航路规划的研究较少，大多是关于地面机器人覆盖航路规划的研究。

A. Zelinsky等 [1] 提出了第一种基于网格的覆盖路径规划方法。他们使用网格表示任务区域，并对网格应用完整的覆盖路径规划算法。该方法设定一个起始单元格和一个目标单元格。算法首先给目标网格赋值0，给它周围的所有单元格赋值1。然后，所有与标记1相邻的未标记网格都标记为2。这个过程不断重复，直到标记面到达开始单元格。经过计算距离转换，通过从开始单元格开始选择未访问的赋值最高的相邻单元格来找到覆盖路径。如果两个或两个以上的邻居单元格为相同的值，则随机选择其中一个单元格。

H. Choset等 [2] 提出了一种能够产生完整覆盖路径的简单精确的网格分解技术。他们将任务区域划分成每个网格为梯形的工作空间，并且只处理平面的多边形区域。使用简单的来回运动来覆盖每个单元网格，通过查找与分解相关的邻接网格进行穷举遍历来保证完全覆盖任务区域，详尽的前进规则决定了访问单元格的顺序，最后生成覆盖每个单元格的特定“之”字形路径。

陈海等 [3] 证明了同等能量下无人机转弯过程比直线飞行过程效率低，定义了凸多边形任务区域的长度和宽度，并将凸多边形区域的覆盖航迹规划问题转化为求解凸多边形宽度的问题。他们按照“点边式”宽度算法，找到凸多边形宽度出现时支撑平行线的方向，如果无人机沿该方向利用扫描线对区域进行扫描覆盖，则可以获得最少的转弯次数，也就能够得到最短的飞行路程。但在地形起伏大的任务区域，需要加入地形高程等约束进行三维航路规划。

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

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

2.1. 任务区域网格化

规划监视覆盖航路时必须考虑到无人机执行任务的区域，简单易行的任务区域划分可以极大方便覆盖航路生成，所以我们把任务区域网格化。网格化就是要将任务区域划分为规则的网格，网格的大小由无人机监视器视场在地面的投影大小决定。那么任务区域就可以使用网格的集合来表示了，设为A。网格要小于这个投影区域的大小，但又要尽可能的大。若无人机的飞行高度为h，垂直视场角为 $\alpha$ ，水平视场角为 $\lambda$ ，俯视角为 $\beta$ 。假设在地面的视场为梯形ABCD如图1所示， $N,K,F$ 分别为边 $AB,PQ,CD$ 的中点，OK为 $\angle NOF$ 的角平分线。则网格的边长最大可以为：

$PQ=2OK\tan \lambda /2$

图1. 无人机监视视场

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

人工势场法 [7] 就是为任务区域设定一个虚拟的人工势场，每个网格上设定一个数字代表网格的势值。覆盖航路规划算法从一个起始的网格出发，按照一定的规则沿着势场运动，最终会形成一个覆盖航路。覆盖航路的生成样式和势场值的设置以及运动规则密切相关，不同的势场值设置方法以及规则，生成的覆盖航路不同。

传统的基于人工势场的覆盖航路生成方法是在两个点之间，按照势值递增的趋势生成势场，然后依据势场生成航路，算法在避障以及覆盖效率方面有不错的效果，但是生成的样式比较单一。为了丰富势场的样式，我们将势场生成的起始态势进行了改进，并将这种起始的态势成为种子。

所谓种子就是在势场生成算法开始的时候，设定的一个势值不为0的网格的集合，设为 $S\subset A$ 。传统的人工势场法中，种子S只包含一个网格。基于种子概念的人工势场法生成覆盖航路的过程如下：

步骤1：选择任务区域网格集合的一个子集作为种子S，并设其网格的势值均为1，其他网格的势值为0；

步骤2：并行地更新势值为0的网格的势值，从其邻居网格中选择势值最大的网格作为激发格，并设当前网格的势值为激发格势值 + 1；

步骤3：重复运行步骤2直到所有的网格势值均为非零，转步骤4；

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

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

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

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

1) 转弯角度总值最小

每个转弯通常意味着无人机在转弯后再次减速并再次加速的额外成本，所以要减少最小化路径中的转弯(次数、角度)来增加监视的效率。这里我们采用统计航路中所有拐弯角度总和的办法来度量航路的这一个性能，并将这个总和称为拐弯角度总值

$z_1={\displaystyle \sum _{i=1}^n{q}_i}$

其中， $q_i$ 为航路上第i个转弯的角度，拐弯角度总值越小的航路，越有利于增加监视效率。

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

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

$z_2={\displaystyle \sum _{i\in A}{w}_i}$

$z_3={\left[\frac{\left[{\left(w_1-\overline{w}\right)}^2+{\left(w_2-\overline{w}\right)}^2+\cdots +{\left(w_n-\overline{w}\right)}^2\right]}{n}\right]}^{\frac{1}{2}}$

其中， $w_i$ 为网格i的势值。

3) 航路的可预测性要小

监视任务的性质决定了无人机被发现的概率越小越好，所以覆盖航路的可预测性至关重要。当覆盖航路越不容易被预测判断时，无人机执行任务越不容易被发现，任务的成功率和可靠性越高。若覆盖航路被预测出时，敌方可根据预测避开无人机或采取措施迷惑无人机，导致任务失败。

这里我们简单地利用种子更新的周期来评估可预测性的大小，也就是种子更新越频繁，覆盖航路样式的变换越频繁，航路就越不容易被预测

$z_4=T^{-1}$

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

3.1. 基因编码

普通的基因编码 [8] 以01字符串编码为主，但这种编码形式不利于种子的直观表示，并且经过交叉变异等操作后，经常会产生非可行解。因此，我们采用二元组串的形式进行编码，每个网格可以对应平面直角坐标系上的一个唯一坐标，而种子是网格的集合，这样种子就可以编码成一个二元组串的形式。

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

1) 交叉算子

交叉 [9] [10] 是指通过交换两个个体中的部分基因位产生新的基因。从种群中选取两个个体配对，在选定的节点上各截取一部分基因相互交换，即产生新的基因，组成两个全新的个体。如图2。

2) 变异算子

经过交叉过后的新基因某个或某些基因位会产生变异，从而产生一定概率的不可预测性性波动，进而增加种群进化的多样性。通过变异不仅可以改善航路规划的随机性，使航路的可选择性更加丰富多样，通过种子的改变，产生下一步进行的更多可能的新的种子。还可以增加算法的局部搜索能力，使得路径选择的方向更加广阔，在面对新的信息时有更多适合的航路。

对于椭圆形种子的基因变异，改变的是椭圆形的形状参数(如位置、长轴与x轴夹角、轴的长短)。如图3。

3) 合并算子

根据本问题的特殊性，提出一种新的算子，称为合并算子，也就是将两个种子基因进行直接合并而生成基因。如图4。

图2. 交叉操作

图3. 变异操作

图4. 合并操作

3.3. 监视覆盖航路生成

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

步骤1：初始化种子群，在种群中选择一个种子，在任务区域网格中生成势场，无人机位于起始位置 $\left(x_0,y_0\right)$ ， $t=0$ ，设定种子更新的周期T。

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

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

4. 仿真实验

为了对算法进行测试，我们建立了30*30的任务区域网格，每个网格看作图 $G=\left(V,E\right)$ 中的一个点，所有的点构成图G的点集V，对于一个网格，我们定义其邻居为与其相邻的八个网格，映射到图G中，就是点之间只有存在邻居关系的时候，才有边相连。

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

在航路生成的过程中，每隔30*30仿真步长统计一次航路的性能参数，也就是转弯角度总值、人工势场势总值、网格势场最大值、网格势场值的标准差等参数，其中目标函数中的不可预测性，认为其与种群更新周期T成反比，也就是T越大，不可预测性越差，反之，不可预测性越好，极端情况下，当T为无穷大的时候，不可预测性最差。

初始势场采用点型种子生成，如图5所示。

图5. 初始势场

为了更加连贯和度量一致的观察航路规划算法的统计，在达到势场更新周期，对势场进行更新的时候，要进行一定的处理，使得任务网格的总势保持不变，也就是假设新的种子生成的势场总值为 $P_1$ ，更新之前的总值为 $P_0$ ，则要将新生成的势场除以一个常数

$P_1/P_0$

进行了50*900个仿真步长的仿真，也就是理想情况下可以对任务区域进行最大50次的覆盖监视，得到的结果如图6所示。

从仿真结果来看，转弯角度总值分布比较平稳，位于111到245之间。势场总值也比较平稳，初始几个周期的总势值比较大是因为初始势场生成设置的原因，网格势场最大值以及标准差也存在这样的现象。

5. 小结

本文通过结合人工势场法对无人机任务区域生成网格势场，在监视覆盖航路的约束条件下，将势场

图6. 结果分析

种子编码成二元串组基因后进行算子操作，产生更多新的种子，增加航路变化的多样性。通过仿真验证算例的转弯角度总值、势场总值、网格势场最大值、势场标准差等结果，表明本算法可以满足监视覆盖航路多样性和对抗性的需求。

文章引用

李御驰,闫军涛,宋志华,张 晗. 基于遗传算法的无人机监视覆盖航路规划算法研究
Research on Algorithm of UAV Monitoring Coverage Path Planning Based on Genetic Algorithm[J]. 计算机科学与应用, 2019, 09(06): 1208-1215. https://doi.org/10.12677/CSA.2019.96135

参考文献