Path Planning for UAV to Cover Multiple Separated Convex Polygonal Regions
Path Planning for UAV to Cover Multiple Separated Convex Polygonal Regions
复制标题
DOI：
10.1109/access.2020.2980203
复制
发表时间：
2020-01-01
期刊：
影响因子：
3.9
通讯作者：
Jin, Lei
中科院分区：
文献类型：
--
作者：
Xie, Junfei;Carrillo, Luis Rodolfo Garcia;Jin, Lei
在土地评估、搜索救援、精准农业等无人机应用中，常常需要无人机对多个空间分布区域进行测量。要执行这些应用，关键步骤之一是规划无人机的路径，以快速覆盖所有区域。新的路径规划问题，我们称之为TSP-CPP问题，可以看作是旅行商问题（TSP）和覆盖路径规划（CPP）问题，这还没有得到很好的研究文献中的集成。本文对TSP-CPP问题进行了系统的研究。特别是，我们首先提供了一个混合整数规划制定这个新的问题，然后介绍了CPP方法覆盖一个单一的凸多边形区域。基于这种方法，我们然后开发了两种方法来解决TSP-CPP问题，包括1）一个动态规划的精确方法，可以找到（近）最优的旅游，和2）一个启发式的方法，可以非常有效地生成高质量的图尔斯。通过全面的理论分析和仿真研究，我们证明了所提出的方法的最优性和效率。
In many unmanned aerial vehicle (UAV) applications such as land assessment, search and rescue, and precision agriculture, UAVs are often required to survey multiple spatially distributed regions. To perform these applications, one of the key steps is to plan the path for the UAV to quickly cover all regions. The new path planning problem explored here, which we call the TSP-CPP problem, can be viewed as an integration of the traveling salesman problem (TSP) and the coverage path planning (CPP) problem, which has not been well studied in the literature. In this paper, we conduct a systematic investigation on the TSP-CPP problem. In particular, we first provide a mixed integer programming formulation for this new problem, and then introduce a CPP method for covering a single convex polygonal region. Based on this method, we then develop two approaches to solve the TSP-CPP problem, including 1) a dynamic programming & x2013;based exact approach that can find the (near) optimal tour, and 2) a heuristic approach that can generate high-quality tours very efficiently. Through comprehensive theoretical analyses and simulation studies, we demonstrate the optimality and efficiency of the proposed approaches.