夏阳升，石建迈，孙博良，陈超
国防科技大学 湖南省长沙市 410073
摘 要 针对小型无人机在战场区域侦察中的应用，提出了一种多无人机完成复杂区域覆盖侦察任务的新的路径规划技术。分析了覆盖扫描中地面扫描宽度与无人机和其携带相机性能之间的关系，并研究了如何根据目标区域几何特征选取扫描模式的方法，设计了基于梯形分解的凹多边形分解方法并在此基础上设计了多无人机区域覆盖路径规划方法。
关键词 多无人机，复杂区域覆盖，路径规划
引用格式
DOI
无人飞机具有成本低、生存能力强、无人员损失风险、机动性好等优点，已经成为世界各国战场侦察的重要工具，并在近几次局部战争中发挥了重要的作用[1]。在民用领域，如农业、野外搜救、森林防火等领域，无人机也有着广阔的应用前景。
对目标区域进行覆盖从而获取该区域的所有详细信息是一项典型战场侦察任务。随着区域覆盖任务量的扩大以及执行任务过程中突发性的增强，一些研究人员开始专注于考虑使用多个无人机的解决方案，多无人机系统的使用具有许多优点，例如由于覆盖工作的划分而减少了总任务时间，引入了容错功能，当一架无人机出现故障时，可以将其覆盖区域分配给另一架无人机。
面向复杂区域的多无人机覆盖扫描路径规划技术重点解决复杂形状、广阔区域的扫描式信息收集任务中的路径规划，通过优化多架无人机协同完成复杂区域的扫描飞行路径，提高整体区域信息采集的效率。针对该问题的特点，设计了高效的多无人机区域覆盖路径规划方法。
1 无人机扫描间距计算
无人机区域覆盖路径规划的前提是要知道无人机在地面上的扫描间距。我们首先需要计算出无人机飞行高度h，其可以由下式计算得出：
.png)
其中GSD是地面分辨率，是指在拍摄图像上区分两个目标的最小间距。f是相机焦距，u是相机的像元尺寸。当无人机搭载的相机及其像素确定之后，f和u也随之确定了。由上式可知无人机的飞行高度越高，地面分辨率即图像的清晰度和精度越低。
.png)
图1 无人机飞行高度与航拍图像地面宽度和长度的关系
如图1所示，当我们得到无人机的飞行高度时，根据相机的视角fov可以计算得出无人机的航拍图像地面宽度和长度：
.png)
其中W是航拍图像的宽度，是相机在宽度方向的水平视角。通过公式（2）计算得到的航拍图像地面宽度并不等于无人机扫描间距，这是因为无人机航拍图像应该具有一定的重叠率，目的是满足后期的图像拼接要求，主要是旁向重叠率。
.png)
其中ws为图像的旁向重叠率。 这里我们得到无人机区域扫描间距的大小，即D的值，用于后面覆盖路径具体的规划。
2 无人机扫描方式选取方法
应用无人机对一个区域进行覆盖扫描时，主要有两种扫描模式，即割草式扫描模式[2]和螺旋式扫描模式[3]。两种扫描模式具体定义如下：
螺旋式扫描模式：无人机从覆盖区域的中心开始，然后以恒定的螺旋间距向外逆时针螺旋扫描，直到覆盖完整个区域。也可从最外开始，螺旋向内扫描。
割草式扫描模式：无人机以平行航迹往复推进的方式从覆盖区域边缘开始以等间隔距离扫描，直到覆盖完整个区域。
本文根据覆盖区域与圆的接近程度选择不同的扫描模式。我们通常用圆度来描述一个多边形接近圆的程度，很多文献都研究了圆度的定义和计算方法[4]，Bai等人[5]提出了一个用于计算交通指示牌圆度的方法，该方法比较适合用于本文的多边形圆度计算，因此本文使用该方法计算多边形的圆度，计算公式如下：
.png)
其中S是多边形的面积，L是多边形的周长，当多边形越接近于圆时，C越接近于1，反之C越接近于0。然后设计实验找出多边形圆度与扫描方式选取之间的关系。结果表明当多边形是正五边形(C=0.86)时，两种扫描模式的扫描时间基本相同。因此，通过试验观测可以总结如下近似规律：当覆盖区域的圆度小于0.86时，割草式扫描模式较优；当圆度大于0.86时，螺旋式扫描模式较优。
3 覆盖区域凹凸性的判定与分解
3.1 多边形凹凸性的判定
首先应该对覆盖区域的凹凸性进行判断。目前已经有很多方法可以用来判断多边形的凹凸性，本文使用多边形顶点的向量外积来判定多边形的凹凸性。其原理是凸多边形的每个顶点都应该拥有相同的转向，即凸多边形的每个顶点都应该是凸点。
假设是多边形P的一个随机顶点，和是的两个相邻顶点。则的凹凸性可通过向量积Q的值进行判断。
.png)
当一个多边形存在凹点时，该多边形是凹多边形，当该多边形所有的顶点都是凸点时，该多边形时凸多边形。
3.2 凹多边形的分解
将凹多边形分解成一系列的凸多边形有很多种方法，比如梯形分解[6]、三角分解[7]和近似分解[8]等等。本文使用基于梯形分解方法来对凹多边形进行分解。理想情况下最短的路径拥有最少的转弯次数[9]。当沿着多边形长轴进行区域覆盖时，无人机的转弯次数最少，因此本课题设计的分解方式是平行于多边形长轴进行分解的。
凸多边形的长轴定义如下：
对于每一条边，分别计算该多边形中不属于这条边的顶点到这条边的距离，把这些距离中的最大值记为这条边的跨度。比较所有边的跨度，最小跨度所对应的那条边就是该凸多边形的长轴。
凸多边形的长轴能够通过上述定义直接找到，对于凹多边形，我们首先使用Akl等人[10]提出的凸包生成算法来给凹多边形生成其对应的凸包，然后将其凸包所对应的长轴看作是该凹多边形的长轴。
基于梯形分解方法和多边形长轴的定义本文设计了凹多边形分解方法，具体过程如下：
首先将凹多边形沿着与其长轴平行的方向进行梯形分解，其次当两个相邻的凸多边形的一条边彼此重合并且两者长轴彼此平行时，可以将它们合并，该过程可以有效地减少凸多边形的数量，避免无人机在不同凸多边形之间的不必要转移。最后使用割草式扫描模式产生的无人机区域覆盖路径。
3.3 多无人机协同覆盖区域的分解与分配
本文研究所采用的所有无人机都是同一类型的，则其最大扫描面积计算如下：
.png)
其中为无人机的最大飞行时间，为无人机的扫描宽度。此时根据扫描区域的面积可以计算得到无人机的数量：
.png)
其中表示向上取整，这么做是确保所有无人机的总覆盖面积之和要大于待覆盖区域面积。此时m份子区域每个区域的面积占总面积的百分比为：
.png)
对于任意一个给定的扫描区域，首先判断该区域适合使用哪种扫描方式，如果该区域适合使用螺旋式扫描模式，则将覆盖整个区域的螺旋扫描线等分为m份，将它们分别分配给m架无人机，这样相互协同的无人机各自的飞行路径也就规划好了，这种情况下无多人机协同路径规划较好处理。
但是如果采用割草式扫描模式时，使用在上一节设计的区域分解方法将其分解为一系列凸多边形子区域，这里应该明确地是该方法对将一个面积较大的凸多边形分解成一系列小块的凸多边形也同样适用。
图2展示的是采用割草式模式时多无人机协同覆盖区域分配方法。这里首先输入扫描区域和无人机相应的信息，计算得到无人机数量m以及分配给每一架无人机的子覆盖区域面积占总面积的百分比。使用前面设计的多边形分解方法将该区域分解成一系列凸多边子区域，分别计算这些子区域的面积和占比。从第一块子区域开始经过一系列的区域合并以及分解我们将扫描区域按面积比例等分成m份，这m份子区域每一份都会有一架对应的无人机对其进行扫描。
.png)
图2 采用割草式扫描模式时多无人机覆盖区域分配方法
.png)
图3 采用割草式扫描模式时多无人机协同覆盖区域分配及路径生成过程
图3给出了一个面积较大的凹多边形的多无人机协同覆盖区域分解与扫描路径生成示例。该示例中，待覆盖多边形的总面积为4202.03 m2，无人机的最大扫描面积为1500 m2，带入公式（7）中计算得到无人机的数量m=3。给每架无人机分配的扫描区域面积占覆盖区域总面积的比例Pu=33.33%。图3（a）表示使用上一节设计的基于梯形分解的凹多边形分解方法将该凹多边形分解为一系列凸多边形子区域，并分别计算出它们各自的面积占总面积的百分比。图3（b）表示使用图2设计的方法将整个覆盖区域分解成等比例的3块子区域，并将这3块子区域分配给3架无人机，而图3（c）表示使用上一节设计的基于梯形分解的凹多边形分解方法分别将这3块子区域分解成一系列凸多边形并进行合并的过程。图3（d）显示了使用割草式扫描模式为每一架无人机规划的覆盖路径。3中不同颜色的圆表示3架无人机不同的扫描路径起点和终点。
4 小结
随着智能化、无人化、自主化技术的快速发展，小型无人机在军事和民用各个领域中发挥着越来越大的作用。本文提出了一种面向复杂区域的多无人机覆盖路径规划技术。在其中解决了基于覆盖区域几何特性的无人机扫描模式选取问题，并设计了基于梯形分解的凹多边形分解方法，最后在此基础上设计了多无人机区域覆盖路径规划方法。
本研究通过探讨战场情报侦察、野外搜救、农业监控等实际应用背景下的多无人机区域覆盖路径规划问题，帮助构建无人机区域覆盖的智能信息采集系统，能够对既定区域，自动规划无人机区域覆盖路径，为后期构建功能完备、敏捷响应、常态运行的无人化信息采集体系提供技术指导。
参考文献
[1] 杨晨，张少卿，孟光磊. 多无人机协同任务规划研究[J]. 指挥与控制学报，2018, 004(003):234-248.
[2] Choset H, Acar E, Rizzi A A, et al. Exact cellular decompositions in terms of critical points of morse functions[C]//Proceedings 2000 ICRA. Millennium Conference. IEEE International Conference on Robotics and Automation. Symposia Proceedings (Cat. No. 00CH37065). IEEE, 2000, (3): 2270~2277.
[3] Moon S W, Shim D H C. Study on path planning algorithms for unmanned agricultural helicopters in complex environment[J]. International Journal of Aeronautical and Space Sciences, 2009, 10(2): 1~11.
[4] Mehlhorn K, Shermer T C and Yap C K. A complete roundness classification procedure. Proceedings of the thirteenth annual symposium on Computational geometry. 1997, 21(2).
[5] Bai B Q. “Traffic ban sign extraction based on color and circularity,” Electronic Design Engineering, 2011, 19(6): 150~153.
[6] Seidel R. A simple and fast incremental randomized algorithm for computing trapezoidal decompositions and for triangulating polygons[J]. Computational Geometry, 1991, 1(1): 51~64.
[7] Lee D T, Schachter B J. Two algorithms for constructing a Delaunay triangulation[J]. International Journal of Computer & Information Sciences, 1980, 9(3): 219~242
[8] Lien J M, Amato N M. Approximate convex decomposition of polygons[J]. Computational Geometry, 2006, 35(1-2): 100~123.
[9] Xu A, Viriyasuthee C, Rekleitis I. Optimal complete terrain coverage using an unmanned aerial vehicle[C]//2011 IEEE International conference on robotics and automation. IEEE, 2011: 2513~2519.
[10] Akl S G, Toussaint G T. A fast convex hull algorithm. Information Processing Letters, 1978, 7(5): 219~222.
[基金项目] 本文系国家自然科学基金项目(71771215)
[作者简介]
夏阳升（1995.05-），男，汉，江西省赣州市人，国防科技大学系统工程学院2018级硕士研究生，主要研究方向为车辆路径规划、启发式设计。
石建迈（1980.10-），男，汉，河北辛集，国防科技大学，管理科学与工程，博士，副研究员，主要研究方向为任务规划、智能规划。
孙博良（1986.12-），男，汉，河南洛阳，国防科技大学，控制科学与工程，博士，讲师，主要研究方向为目标工程。
陈 超（1977.11-），男，汉，河南漯河，国防科技大学，管理科学与工程，博士，教授，主要研究方向为任务规划、目标工程。