Coverage Path Planning of Multiple Disconnected Convex Polygons Based on Improved Genetic Algorithm

This paper considers the energy-constrained multi-UAV multi-area coverage path planning problem which is a generic technology backbone of many survey applications using multiple UAVs. The problem is usually NP-hard and may not be solved efficiently taking into consideration the scale of the areas to survey. In this paper, we present a two-step strategy to solve this problem approximately. In the first step, we compute coverage paths controlled by different enter/exit points for each polygon area. In the second step, we propose a genetic algorithm-based approach to determine the access order of multiple areas while simultaneously determining the entry point for each area. The above problem can be modeled as a variant of the vehicle routing problem (VRP) taking into account the limitation of the maximum flight distance of each UAV. The simulation experiment results indicate that our approach is able to plan proper paths for the multi-UAV multi-area coverage mission, while the energy constraint is satisfied at the same time.