Joint Deployment and Coverage Path Planning for Capsule Airports with Multiple Drones

Abstract

Due to the advantages of low cost and high flexibility, drones have been applied to urban surveillance, vegetation monitoring, and other fields with the need for coverage of regions. To expand UAVs’ coverage, we designed the Capsule Airport (CA) to recharge and restore drones and provide take-off and landing services. Meanwhile, the combination of drones’ coverage path planning (CPP) and the deployment of CAs is a crucial problem with few relevant studies. We propose a solution approach to the CPP problem based on selecting scanning patterns and trapezoidal decomposition. In addition, we construct a 0–1 integer programming model to minimize the cost of the distance between CAs and the scanning missions. Specifically, a solution approach based on greedy and clustering heuristics is designed to solve this problem. Furthermore, we then develop a local-search-based algorithm with the operators of CA location exchange and drone scanning mission exchange to further optimize the solution. Random instances at different sizes are used to validate the performance of proposed algorithms, through which the sensitivity analysis is conducted with some factors. Finally, a case study based on the Maolichong forest park in Changsha, China, is presented to illustrate the application of the proposed method.

Keywords

• drone
• capsule airport
• coverage path planning
• deployment
• heuristic