王红星 马学娇 张长森

摘 要：区域覆盖路径规划技术对于提高无人机搜索的效率和正确率具有重要的意义。 本文针对凹多边形区域， 提出一种区域覆盖算法， 旨在使无人机能够更加高效地完成对指定区域的无遗漏覆盖搜索。 首先， 给出了处理凹多边形区域的凹点、 利用凸分解进行区域划分的的算法流程; 其次， 给出了无人机基于最小多余路径的子区域遍历顺序， 详细描述了无人机对区域的无遗漏覆盖遍历; 最后， 根据仿真实验分析， 证明了该算法的正确性与有效性。

关键词：     無人机; 区域覆盖; 路径规划; 凹多边形; 凸分解

中图分类号：     TJ760; V279  文献标识码：    A  文章编号：     1673-5048（2021）06-0046-07

0 引  言

无人机（Unmanned Aerial Vehicle，  UAV）与有人机相比， 具有无需考虑机载生命的突出特点， 且制造、 维护成本相对较低， 利用率高， 明显契合了时代的需求， 成为有人机的完美补充， 可以替代有人机执行枯燥、 恶劣、 危险、 隐蔽的任务[1]。

随着无人机自主能力和智能化水平不断提高，  无人机不仅在任务侦察、 目标打击等军事领域被广泛应用，  在农业植保、 遥感测绘、 森林消防及影视航拍等民用领域也被大量应用[2-4]。 如何对区域进行高效的无遗漏覆盖一直是无人机技术研究的重点。 文献[5]证明了无人机在转弯过程中比直线飞行耗能高， 并提出了一种基于最小转弯次数的无人机区域覆盖算法; 文献[6]提出了基于最短时间的无人机覆盖路径规划; 文献[7]将凹多边形区域凸分解为若干个子区域后， 采用之字形覆盖策略实现了对多边形区域的无遗漏覆盖， 但凸分解时没有考虑到区域形态， 容易产生狭长等飞行覆盖难度较大的区域; 文献[8]采用直接将凹点删除的方法将凹多边形区域转化成凸多边形区域， 但容易产生大量的多余覆盖区域， 加大了无人机的覆盖任务量; 文献[9]直接对凹多边形区域进行遍历， 虽然简单便捷， 但凹多边形区域往往存在狭长区域， 直接进行遍历容易产生大量转弯路径以及多余路径; 文献[10]提出了一种邻近凹点角平分线的凸分解算法， 该算法不增加新节点， 且分解得到的凸多边形的形态、 大小质量较好。

本文在以上文献研究的基础上， 提出了一种针对凹多边形区域的无人机覆盖路径规划算法， 通过对凹点选择性地删除来消除凹多边形的狭长区域， 在文献[10]的基础上进行改进， 对剩余凹多边形进行凸分解， 然后基于多余路径最短原则确定子区域遍历顺序， 通过寻找最小宽度所对应的边来确定无人机的飞行方向， 利用Dubins算法进行无人机转弯的规划， 实现区域的无遗漏覆盖遍历。

1 问题描述

无人机区域覆盖问题描述如下： 给定一架无人机U和待覆盖有界区域P， 设置无人机的起点和飞行方向， 当无人机完成一次飞行时可实现对区域P的无遗漏覆盖， 并在不产生遗漏区域的前提下使覆盖路径尽可能少、 覆盖时间尽可能短。 实际上， 待覆盖区域多为不规则的凹多边形区域。

为方便研究， 做如下假设： （1）无人机视为一个质点; （2）无人机在飞行过程中飞行高度不变; （3）待覆盖区域地形相对平缓， 地势起伏的影响可忽略不计; （4）无人机的最小转弯半径和探测器的探测半径相等。 根据假设， 简化的无人机探测器探测模型如图1所示。 无人机以速度v飞行， O为无人机在地面上的投影， H， α， β分别为无人机的飞行高度、 水平视场角和垂直视场角。 矩形区域ABCD为无人机的探测区域， 探测面积为L×W， 其中L=2H×tanα， W=2H×tanβ。

2 路径规划算法流程

2.1 凹多边形区域的处理

文献[5]证明了无人机在转弯过程中消耗的能量比直线飞行过程大得多， 给出了凸多边形跨度和宽度的定义， 并提出了覆盖凸多边形区域时最短飞行路径的方法， 即无人机沿着垂直于宽度的方向飞行， 可得到最少转弯次数和最短飞行路径。 此算法针对凸多边形搜索区域， 若搜索区域为不规则的凹多边形， 需要将凹多边形区域处理为凸多边形区域， 然后进行遍历。 在对凹点进行处理时， 首先要找到凹点， 一般采用向量的叉积来判断顶点是否为凹点。 设存在两个向量P（x1， y1）和Q（x2， y2）， 则两向量的叉积可表示为

王红星， 等： 一种凹多边形区域的无人机覆盖路径规划算法

P×Q=x1·y2-x2·y1

该结果是一个标量， 且具有以下性质：

（1） 若P×Q>0， 则Q在P的逆时针方向。

（2） 若P×Q=0， 则Q和P共线。

（3） 若P×Q<0， 则Q在P的顺时针方向。

因此， 设Vi-1（xi-1， yi-1）， Vi（xi， yi）， Vi+1（xi+1， yi+1）为多边形区域的三个相邻顶点， 构成的两个向量为Vi-1Vi和ViVi+1， 则两向量叉积为

F=Vi-1Vi×ViVi+1=（xi-xi-1）·（yi+1-yi）-（xi+1-xi）·（yi-yi-1）

根据叉积性质判断， 当F>0时， 顶点Vi为凸点; 当F<0时， 两向量的公共顶点Vi为凹点所在位置。

文献[8]通过遍历凹多边形顶点， 连接凹点两边相邻的顶点， 可将凹点删除， 以此将凹多边形转换为凸多边形。 如图2所示， 凹多边形ABCDEF经过遍历找到凹点C， 删除边BC和边CD后连接顶点B和D， 以此删除凹点C， 得到了凸多边形ABDEF。 这种方式虽然简单便捷并且可以在一定程度上减少转弯次数， 但产生的多余搜索区域BCD面积过大， 过多地增加了无人机直线飞行距离， 加重了无人机的搜索任务量， 降低搜索效率。 因此这种处理方法是不合理的， 并不适用于所有的凹多边形。

为了避免产生过多的多余搜索区域以及得到形态较好的区域， 本文对凹点进行选择性地消除， 对此引入两个参考量： Parea， θ 。 其中Parea=Sredu/Sall， Sredu为连接凹点两边相邻顶点后产生的多余三角形区域面积， Sall为整个区域的面积， 设定合适的面积比例阈值， 当Parea不超过所设阈值， 即产生的多余覆盖面积相对于整个区域可以忽略不计时， 可以用连接上一顶点与下一顶点的方法来消除凹点。 多余三角形面积公式Sredu=1/2·a·b·sinθ， 其中a和b为凹点相邻两边长度， θ为凹点外角角度， 由正弦函数单调性可知， 在0°到90°之间θ的值与sinθ的值成正比， 在90°到180°之间， θ的值与sinθ的值成反比。 当Parea超过阈值但sinθ的值较小时， 说明凹点相邻两边边长较长， 此时θ值较大或较小， 当θ值较小时如图3（a）所示将产生狭长的搜索区域， 增加无人机的转弯次数， 不利于无人机的机动转弯， 因此， 将θ也作为一个参考量， 设定合适的角度阈值， 当θ超过所设阈值时， 用同样的方法消除凹点。

图3是凹多边形处理的一个实例， 将凹多边形的顶点按顺时针输入， 并设置好面积覆盖比例阈值N和角度阈值θmin， 按顶点顺序依次进行遍历， 在图3（a）中遍历到顶点C为凹顶点， 然后依次计算三角形BCD的面积与ABCDEF整个区域面积的比值， 以及顶点C的外角度数。 若所得面积比值小于设定的阈值， 或者顶点C的外角在设定的角度阈值范围内， 则如图3（b）所示， 删除边BC和CD， 连接BD， 消除凹顶点C并更新顶点集。 该过程伪代码如图4所示，  其中a和 b为凹点两边边长， θ为凹点外角角度。 对凹点有选择性地消除， 可以减少凹多边形的狭长区域或面积过小的区域， 在一定程度上减少无人机的转弯次数， 有利于无人机任务的执行。

将符合条件的凹点删除后， 若剩余顶点中还存在凹点， 则在文献[10]中邻近凹点角平分线的凸分算法基础上进行剖分。 图5是凹点剖分的一个实例， 首先遍历多边形找到凹点V1， 为了使剖分后得到的多边形形态更好， 在凹点两边反向延长线之间的区域中选择剖分点， 即选择区域A中的点， 为了成功剖分， 判断区域中的可视点， 将可视点作为候选剖分点。 可视点的定义为： 多边形中的顶点与凹点连接形成的线段， 全部在多边形内部或上面， 这样的顶点就是凹点的可视点。 根据可视点定义， 顶点V1位于区域A中的可视点有V4， V5， V6 ， V8 和V9， 即作为V1的候选剖分点， 然后做V1的角平分线， 为了尽可能多地消除凹点， 判断候选剖分点的凹凸性， 若存在凹点， 则只计算凹点与角平分线间的垂直距离; 若只存在凸点， 则计算所有凸点与角平分线间的垂直距离， 选择距离最短的点作为剖分点。 若候选剖分点为空， 则以凹点角平分线与多边形的交点为剖分点。 如图5所示， V1的候选剖分点中存在V5， V8两个凹点， 因此， 只需计算V5， V8与角平分线间的垂直距离， 经计算， 顶点V8距离角平分线距离最短， 因此选择顶点V8作为凹点V1的剖分點。 剖分后得到多边形V1V2V3V4V5V6V7V8和V8V9V10V11V1， 判断两个多边形的凹凸性， 若还存在凹多边形， 则重复以上步骤， 若都是凸多边形， 则停止凸分解， 该过程伪代码如图6所示。

2.2 无人机区域覆盖算法

2.2.1 子区域的遍历

将区域完成凸分解后将形成若干个子区域， 接下来的任务是对子区域进行覆盖搜索， 根据文献[5]中的宽度求解算法， 可求出各个子区域的宽度及对应的飞行方向。 如图7所示， 设无人机的探测半径为R， 凸多边形ABCD最小宽度所对应的边为CD， 最小宽度所对应的顶点为A， 做两条平行于CD的直线， 其中一条与边CD的距离为R， 另一条与顶点A的距离为R， 分别交多边形于p1， p2， p3， p4， 这四个点皆可作为区域的驶入点， 是区域的候选驶入点。 当驶入点确定后， 驶出点也就确定了， 即一个驶入点对应一个驶出点。 两个子区域由上一子区域的驶出点和下一子区域的驶入点连接， 两点（x1， y1）、 （x2， y2）间的路径距离为欧式距离， 计算公式为： d=（x2-x1）2+（y2-y1）2。 两点间的路径为子区域间的连接路径， 连接路径为多余路径。 为了节省无人机的能量消耗， 应使多余路径尽可能短， 因此， 当选择子区域驶入点时， 总是选择与上一子区域驶出点路径距离d最小的候选驶入点作为下一子区域驶入点。

确定子区域遍历顺序时， 需要找到一条覆盖所有子区域， 并且多余路径最少的区域遍历顺序。 这个问题类似于旅行商问题（Traveling Salesman Problem，  TSP）， TSP是一个NP-hard问题， 国内外学者对此进行了大量研究。 结合实际， 由于现实中研究的子区域数量相对较少， 可以将问题抽象为小规模的TSP。 本文结合DFS深度优先搜索算法进行求解， 规定两个子区域若有公共点， 则这两个子区域是相邻关系， 创建子区域邻接表， 用1表示两个子区域相邻， 0表示不相邻。 首先确定初始子区域以及初始驶入点， 根据子区域邻接表， 利用DFS深度优先搜索算法找到所有从初始子区域出发的遍历顺序， 然后根据遍历区域个数找到遍历所有子区域的遍历顺序， 最后计算各个遍历顺序的总的多余路径（所有子区域间多余路径之和）， 选择总多余路径最少的遍历顺序进行遍历。 在此注意， 若从规定的初始子区域找不到一条可以遍历全部子区域的遍历路线， 则更换初始子区域。

2.2.2 覆盖算法分析

根据文献[5]中的方法， 可求出凸多边形区域的最小宽度以及最小宽度所对应的边和顶点。 本文采用扫描线方式进行覆盖遍历， 扫描线与最小宽度所对应的边平行。 即无人机沿着扫描线直线飞行， 当飞行至区域边界时转向， 反方向沿下一扫描线直线飞行， 如此反复， 直至覆盖完整个区域。 为方便描述， 本文将无人机的最小转弯半径和探测半径记为R， 待探测多边形区域的最小宽度记为w， 最小宽度所对应的边记为E， 最小宽度所对应的顶点记为V。 要想将整个子区域完全遍历， 最少需要[w/2R]+1条扫描线覆盖区域。 为方便研究， 在此规定： （1）搜索区域的最小宽度w远远大于无人机的探测半径R; （2）当第n-1条扫描线扫描后的剩余区域宽度大于R并小于2R时， 第n条扫描线与第n-1条扫描线之间的距离为R， 若剩余区域宽度大于2R， 则扫描线间距为2R， 若小于R， 则扫描线覆盖完毕。 因此， 每一条扫描线与子区域都有两个交点， 两交点间距离即为扫描线的探测长度， 记为Lscan， 则无人机的探测区域为Lscan×2R的矩形区域， 而当无人机到达区域边界就转弯时， 探测到的区域可能不会完全覆盖扫描线的待探测区域， 此时需要无人机飞行更多的路程， 然后转弯。 因此要根据情况更新每条扫描线的起点和终点， 以确保没有遗漏区域。

以对扫描线终点更新为例， 如图8（a）所示， 待探测区域为多边形ABCDE， 区域最小宽度所对应的边为CD， 最小宽度所对应的顶点为A， 无人机从靠近边CD的一侧开始遍历， 虚线PQ为无人机沿扫描线的一条直线飞行航迹， 起点和终点为P和Q， 航迹待探测区域为多边形FGCD。 若无人机到达区域边界就进行转弯， 则无人机的实际探测区域为FHID， 产生了遗漏区域QCI， 不能完全覆盖待探测区域， 因此无人机需要多行进一段距离至点N， 才能完成对区域的无遗漏覆盖。

求点N的方法为： 按输入顶点顺序顺时针对顶点和边进行编号1， 2， …， n， 规定第n条边包含第n个顶点， 不包含第n+1个顶点。 设置两个参数LE， LV。 因为无人机从靠近边CD的一侧开始遍历， 令LE=R， 需要计算PQ与顶点A的距离D′V， 若D′V≥R， 令LV=R， 否则， 令LV=D′V。 若无人机是从靠近顶点A的一侧开始遍历的， 则令LV=R， 计算PQ与边CD的距离DE， 若DE≥R， 令LE=R， 否则， 令LE=DE。 分别在PQ靠近边CD和顶点A的两端做平行于PQ且与PQ距离分别为LE和LV的直线， 如图8（a）所示， 两条直线为FG和DC， 与多边形分别相交于点F， G和点D， C， 过扫描线终点一侧的交点G和C分别做垂直于PQ的两条直线， 垂足点为M和N。 根据各交点的坐标与边的坐标范围， 判断交点在哪条边上， 判断交点G和C是否在多边形的同一条边上， 若是， 则说明交点G和C之间是直线段， 没有出现其他顶点， 若不是， 如图8（b）所示， 说明两交点之间不是直线段， 而含有其他顶点， 此時需过两交点之间的所有顶点做垂直于PQ的直线， 并记录垂足点。 最后， 根据各垂足点坐标与线段PQ的关系判断垂足点是否在线段PQ上， 若都在， 则不需要更新扫描线终点， 否则， 选取不在线段PQ上且与扫描线终点Q距离最远的垂足点作为新的扫描线终点。 图8（a）中选择点N代替点Q， 更新后无人机的扫描区域变为FJCD， 完全包含了待覆盖区域FGCD， 实现了区域的无遗漏覆盖。 起点的更新方法与终点的更新方法相同。 上述过程的流程图如图9所示。

无人机到达扫描线终点时， 需要进行转弯进入下一条扫描线。 无人机具有最小转弯半径的限制， 如图10所示， 若无人机的最小转弯半径R小于等于二分之一的两条航迹之间距离d时， 在完成转弯运动后， 两条航带之间没有缝隙的紧密衔接， 不会出现搜索盲区[2]。 而当无人机的最小转弯半径大于二分之一航迹间距离时， 如图11所示， 由于不能紧密衔接会产生扫描盲区。 因此本文采用Dubins曲线算法进行无人机转弯处的航迹规划。

Dubins曲线是在确定起始点切线方向和满足曲率约束的条件下， 连接两个二维平面的最短路径， Dubins曲线证明了两点之间的路径必然存在， 任何路径都可以由两段圆弧航线和一条直线组成[11]。 如图12所示， 由A点到B点的Dubins曲线一共有LSL， RSR， RSL， LSR， RLR

和LRL六种类型， 其中L表示逆时针圆弧运动， R表示顺时针圆弧运动， S表示直线运动， 箭头方向代表物体的运动方向。 因此， 当确定了无人机转弯的起始点运动方向以及最小转弯半径时， 可利用Dubins曲线来规划无人机转弯路径。

3 仿真示例

给定一个顶点数为15的多边形P， 按顺时针排序坐标为

V=（v1， v2， v3…， v15）{（2 050， 6 450）， （4 430， 8 670）， （2 050， 12 650）， （6 450， 11 440）， （7 150， 10 150）， （10 420， 10 940）， （9 550， 8 550）， （11 050， 11 150）， （11 120， 8 580）， （15 450， 7 510）， （11 530， 5 140）， （8 230， 2 480）， （8 950， 8 000）， （7 750， 2 350）， （7 070， 6 490）}

无人机的探测半径及最小转弯半径为0.18×103 m， 待覆盖区域如图13所示。 设置面积覆盖比例阈值为0.025， 当消除凹点后产生的多余覆盖区域与整个区域的面积比值小于等于0.025时， 可将凹点删除， 角度阈值为10°， 即当区域角度小于10°， 产生过于狭长的区域时， 将凹点进行删除。 将凹点删除后的区域如图14所示。

判断消除凹点后的多边形区域是否还存在凹点， 若不存在则直接遍历， 若还存在凹点则对区域进行凸分解， 分解后的区域如图15所示。 设置区域1为初始区域， 无人机起始点如图16中所示， 从区域1出发共有四条可以完全遍历区域的路径， 根据各子区域起始点确定各子区域间的多余路径， 四条路径及其产生的多余路径长度如表1所示， 因此选择路径1作为子区域遍历顺序。 根据各子区域起始点， 用扫描线覆盖各个子区域， 扫描线即为无人机的覆盖直线航迹。 为了避免出现扫描盲区， 根据区域形态更新扫描线起始点， 更新后的扫描线如图16所示， 最后无人机通过Dubins曲线进行转弯覆盖， 无人机的覆盖路径如图17所示。

表2为三种不同覆盖方式下无人机在区域P内航迹的总路程和总转弯次数的比较， 其中， 分割预处理覆盖

算法是将凹多边形凸分解为若干个子区域， 然后对各个子区域进行覆盖， 凸多边形覆盖算法是通过消除凹点的方法， 先将凹多边形转换成最小凸多边形， 然后再对区域进行覆盖。 由表2可见， 本文提出的算法通过消除待覆盖区域中的狭长区域， 可大大减少转弯次数， 相比于直接进行凸分解， 极大减少了转弯次数， 降低了无人机转弯过程中能量的损耗， 而相较于凸多边形覆盖算法， 则极大降低了多余覆盖区域， 减少了覆盖总路径， 提高了无人机的效率。

4 结  论

本文针对现有无人机区域覆盖算法的不足， 提出了一种改进的凹多边形区域覆盖算法， 通过消除凹多边形狭长及不易进行机动转弯的区域， 减少了无人机的转弯次数， 同时也避免了过多多余覆盖区域的产生， 并且对凸分解后的区域找到了产生多余路径最少的区域遍历顺序， 通过对扫描线起始点的更新， 可避免扫描盲区的产生， 实现对区域的无遗漏覆盖。 本文算法有效帮助无人机降低能量损耗， 提高搜索效率和正确率。

在实际应用中， 无人机的搜索区域往往是不规则的曲变形区域， 此时可以将不规则的区域逼近为多边形区域， 然后再用本文算法对其进行覆盖， 同时可以根据各区域目标出现的概率和以往搜索的成功率等为参考， 进一步优化无人机的遍历路径。

参考文献：

[1] Austin R. Unmanned Aircraft Systems[M]. Chichester： John Wiley & Sons，  Ltd，  2010.

[2] 段海滨，  申燕凯，  赵彦杰，  等. 2019年无人机热点回眸[J]. 科技导报，  2020，  38（1）： 170-187.

Duan Haibin，  Shen Yankai，  Zhao Yanjie，  et al. Review of Technological Hotspots of Unmanned Aerial Vehicle in 2019[J]. Science & Technology Review，  2020，  38（1）： 170-187.（in Chinese）

[3] 段海滨，  张岱峰，  范彦铭，  等. 从狼群智能到无人机集群协同决策[J]. 中国科学： 信息科学，  2019，  49（1）： 112-118.

Duan Haibin，  Zhang Daifeng，  Fan Yanming，  et al. From Wolf Pack Intelligence to UAV Swarm Cooperative Decision-Making[J]. Scientia Sinica ： Informationis，  2019，  49（1）： 112-118.（in Chinese）

[4] Duan H B，  Yang Q，  Deng Y M，  et al. Unmanned Aerial Systems Coordinate Target Allocation Based on Wolf Behaviors[J]. Science China Information Sciences，  2018，  62（1）： 1-3.

[5] 陈海，  王新民，  焦裕松，  等. 一种凸多边形区域的无人机覆盖航迹规划算法[J]. 航空学报，  2010，  31（9）： 1802-1808.

Chen Hai，  Wang Xinmin，  Jiao Yusong，  et al. An Algorithm of Coverage Flight Path Planning for UAVs in Convex Polygon Areas[J]. Acta Aeronautica et Astronautica Sinica，  2010，  31（9）： 1802-1808.（in Chinese）

[6] Avellar G S，  Pereira G A，  Pimenta L C，  et al. Multi-UAV Routing for Area Coverage and Remote Sensing with Minimum Time[J]. Sensors，  2015，  15（11）： 27783-27803.

[7] Li Y，  Chen H，   Er M J，  et al. Coverage Path Planning for UAVs Based on Enhanced Exact Cellular Decomposition Method[J]. Mechatronics，  2011，  21（5）： 876-885.

[8] Vinh K，  Gebreyohannes S，  Karimoddini A. An Area-Decomposition Based Approach for Cooperative Tasking and Coordination of UAVs in a Search and Coverage Mission[C]∥ IEEE Aerospace Conference，  2019.

[9] 王自亮，  羅德林，  吴顺祥. 凹多边形区域覆盖无人机航迹规划方法[J]. 航空兵器，  2019，  26（1）： 95-100.

Wang Ziliang，  Luo Delin，  Wu Shunxiang. A UAV Path Planning Method for Concave Polygonal Area Coverage[J]. Aero Weaponry，  2019，  26（1）： 95-100.（in Chinese）

[10] 何立恒，  鮑其胜，  王志杰. 邻近凹点角平分线的多边形顶点快速凸分算法研究及应用[J]. 南京林业大学学报： 自然科学版，  2013，  37（5）： 165-168.

He Liheng，  Bao Qisheng，  Wang Zhijie. Research and Application on Algorithm for Decomposing a Concave Polygon into Convex Poly-gons of Adjacent Angle Bisector of Concave Point and Vertex of Polygon[J]. Journal of Nanjing Forestry University： Natural Sciences Edition，  2013，  37（5）： 165-168.（in Chinese）

[11] Dubins L E. On Curves of Minimal Length with a Constraint on Average Curvature，  and with Prescribed Initial and Terminal Positions and Tangents[J]. American Journal of Mathematics，  1957，  79（3）： 497.

An Algorithm of Coverage Path Planning for

UAV in Concave Polygon Area

Wang Hongxing， Ma Xuejiao*， Zhang Changsen

（Henan Polytechnic University， Jiaozuo 454002，  China）

Abstract： Coverage path planning technologies is of great significance for improving the efficiency and accuracy of UAV search. This paper proposes a area coverage path planning（CPP） algorithm for the concave polygon area，  which aims to enable UAV to complete the coverage search of the specified area more efficiently. Firstly，  the algorithm flow is given by dealing with concave points in concave polygon area and dividing the area by convex decomposition. Secondly，  the traverse sequence of the subarea is given based on the minimum redundant path，  and the covering traverse without omission of the area by UAV are discribed in detail. Finally，  the correctness and effectiveness of the proposed algorithm are proved by simulation experiments.

Key words： UAV; area coverage; path planning; concave polygon; convex decomposition