Path Planning for UAV to Cover Multiple Separated Convex Polygonal Regions

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-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.