1. 引言
无人机覆盖航路规划(Coverage Path Planning, CPP)定义为无人机在满足某种或某些性能指标的前提下避开障碍物和威胁源，规划出一条能够遍历待覆盖区域的最优飞行路线。CPP要求无人机的航路探测区域能够覆盖整个任务区域，是一个遍历的过程。随着无人机技术的发展及应用，覆盖航路规划的应用需求也越来越多，如农业无人机喷洒农药、无人机遥感测绘、无人机侦察监视等。
从查询到的参考文献来看，无人机覆盖航路规划研究比较少，多数是基于模式的覆盖航路规划方法。而关于地面移动机器人的覆盖路径规划问题研究相对较多。无人机覆盖航路规划问题涉及诸多约束条件，如飞行高度、视野面积、转弯半径等。两者虽然在工作环境及一些性能条件有所不同，但在规划原理上基本相似。因此我们尝试对移动机器人的覆盖路径规划方法加以改进，使之能够应用到无人机覆盖航路规划当中去。
Zelinsky等人 [1] 提出的基于网格的覆盖路径规划方法，是将目标区域用网格表示，并对网格应用完整的覆盖路径规划算法。通过设定开始网格和目标网格，从开始网格按波阵面依次进行标号，而障碍区域不进行标号。当计算开始时，通过从开始网格上开始选择相邻网格中未访问的最高标签找到覆盖路径。Gabriely等人 [2] 提出了三种版本的基于栅格地图的STC (span ning tree covering)覆盖算法，实现了离线和在线规划，但该方法只能覆盖大于机器人四倍尺寸的自由空间。
Oussama Khatib等人 [3] 提出了基于人工势场法的覆盖路径规划方法，并引入广义势场(Generalized field)的概念，其基本原理是构造一个虚拟的人工势场，移动机器人作为在二维空间下运动的一个质点，在人工势场的作用下进行运动。规划终点具有负势能，具有吸引力，环境中所分布的障碍物具有正势能，具有排斥力。移动机器人在合力作用下从规划起点开始运动，利用势场势能差滑动至终点。
文献 [1] 中的wavefront覆盖算法属于一种人工势场法，其原理是将待覆盖区域划分为移动机器人同样大小的网格，在地面机器人的路径规划问题中有较好的应用效果。但在无人机覆盖航路规划中无法同样取得较好的效果，一是由于环境特点发生了变化，地面障碍物考虑的要少，任务区域形状更加复杂；二是由于无人机的性能限制，如最小转弯半径、拍摄视野面积等 [4] 。此外还要求在保证较高的覆盖率的同时，还要尽可能降低飞行距离。
综上所述，已有研究中的人工势场法生成覆盖路径已经取得了不错的效果，但是在生成无人机覆盖航路规划中，尤其是在对抗环境下的无人机应用中，覆盖航路的模式需要丰富多样，传统的人工势场法还不能满足需求，目前实际中的解决办法是人工势场法和固定模式法相结合来解决问题 [5] 。在本研究中，我们提出了一种基于wavefront算法和人工势场法的无人机覆盖航路规划算法，可以生成更多更丰富的覆盖航路模式。
2. 改进Wavefront法
2.1. 将任务区域划分为网格
覆盖航路规划中的覆盖实际上是指无人机传感器视场沿着规划的航路对任务区域的动态覆盖。为此我们将任务区域划分成大小合适的网格以规划航路，网格的大小取决于无人机视场在地面的投影，即要保证无人机在特定高度范围可静态地一次覆盖一个网格。
假设无人机的传感器的视场在地面上投影呈梯形，如图1所示。I点为无人机的传感器位置，E为等腰梯形ABCD中AB边的中点，G、F同样如此。同时，IG平分∠EIF。无人机在I点采集的视场为等腰梯形ABCD，如图1所示。
在进行网格划分时，为了使网格代表的实际面积达到最大，取满足精度要求的最远的边作为网格边长。在此我们假设拍摄到的画面中，ABNM范围内满足要求，MNCD范围内不满足要求，即MN为满足要求的最长边，因此将MN长度作为正方形网格的边长。该边长及近边与远边的长度都可根据无人机高度和视场角得出。
俯视角ε为IG与无人机水平高度的夹角，垂直视场角度α (图2中∠EIF)为7˚，水平视场角为β (图2中∠AIB或者∠DIC)。
根据几何角度我们可以得出
进而可以求出势场边界长度
由以上简单的几何公式即可求出视场的面积以及MN即正方形网格的边长。在此次计算中，我们所取的MN作为满足拍摄精度范围的分界线是特殊情况，在实际操作中，只要测出分界线与水平高度的夹角，即可根据以上公式得出网格的边长。
2.2. 改进人工势场法
在人工势场法中，无人机被看作在虚拟势场中运动，被网格的势所吸引，障碍则对无人机表现为斥力 [6] 。无人机在吸引力与斥力的合力作用下，向目标点靠近，经过多次迭代后到达目标点，实现路径规划。我们在此基础上改进人工势场法，将划分为网格的任务区域进行势场值设定，可人工设定无人机沿势场增大或减小的方式进行识别，从而完成对无人机的覆盖航路规划。
已有的人工势场生成方法是选择一个起点和一个终点，从起点开始，采用逐步增加的方法生成人工势场，确定网格所对应的势值 [7] 。这种方法存在的缺点就是生成的势场样式比较单调单一，导致无人机覆盖航路样式的单一，不满足无人机覆盖航路规划对样式多样性的需求，尤其是在军事领域 [8] 。
我们提出了一种改进的方法，引入种子的概念，解决势场生成样式单一的问题。所谓种子就是任务区域网格的一个子集，表示为初始势场值设定为1的网格集合，其他不在种子上的网格的势场值设为0。种子的多样性会直接促成势场的多样性，从而解决航路样式多样性的问题。其基本步骤如下表1所示：
Table 1. Artificial potential field generation steps
表1. 人工势场生成步骤
不同的种子形状代表了人工势场生成时不同类型的起始点，从而生成不同类型的覆盖航路。在我们采用网格与人工势场相结合的方法中，我们根据不同类型的任务区域将种子大致分为以下几种：点、直线型、折线型、环形。
我们以矩形无障碍区域为例，选取直线型种子，迭代生成人工势场如图3。
在实际应用中，我们可以根据任务区域的不同(如区域形状、有无障碍等)，采用不同的种子，从而形成多样的人工势场来解决覆盖航路规划问题。
在生成人工势场的基础上，可以按照以下步骤生成覆盖航路，如下表2所示：
Figure 3. Artificial potential field diagram
图3. 人工势场图
Table 2. Override route generation steps
表2. 覆盖航路生成步骤
3. 计算实验
在此次计算实验中，我们对算法作以下设定：
① 从开始网格开始选择相邻网格中未访问的最低势值。
② 邻居网格均已被覆盖时，选择相邻的最小势值。
我们分别以矩形无障碍区域、五边形无障碍区域、矩形有障碍区域为例，按以上方法步骤进行实验。生成覆盖航路如下：
矩形无障碍区域采用点型种子，生成“回”型与“弓”型相结合的覆盖航路，如图4所示。
五边形无障碍区域采用点型种子，生成“回”型与“弓”型相结合的覆盖航路，如图5所示。
矩形有障碍区域采用环形种子，生成“环”型覆盖航路，如图6所示。
4. 结束语
影响生成的覆盖航路主要有两大因素，一是任务区域的形状以及其中是否存在障碍；二是种子的设定。当我们采用不同的种子时，会生成不同的势场类型。如无障碍矩形区域中通常采用直线型种子，从而生成平行的势场；采用点型种子时，则生成“回”型势场或“回”型与平行相结合的势场。
在实验中，我们分别对不同形状、有无障碍的任务区域采用网格与人工势场相结合的方法按步骤进行实验，得到了想要的覆盖航路。但在实际应用中，任务区域类型是多种多样的，而在这种方法中，不同的种子类型和路径识别机制也使其能够对应生成种类丰富的覆盖航路。
项目基金
国家自然科学基金(71571190)。