Bipartite Cooperative Coevolution for Energy-Aware Coverage Path Planning of UAVs

The coverage path planning of UAVs is a complex optimization problem in practice, especially for those involving multiple target areas. It is challenging to comprehensively plan the inter-area visiting order and the intra-area coverage paths simultaneously. Due to the battery limitation, usually the task can hardly be finished by a single UAV, and instead a fleet of UAVs are required. In this paper, we first formulate an energy-aware multi-UAV multi-area coverage path planning (EM2CPP) model, in order to characterize the practical path planning requirements of UAVs in complex conditions. Subsequently, to accomplish the optimization task, we propose a bipartite cooperative coevolution (BiCC) algorithm that coevolves an inter-area path planning and an intra-area path planning components to obtain good solutions. The basic operators in BiCC, such as the initialization and the reproduction operators, are tailored for the task of EM2CPP. Besides, we also develop a fast heuristic algorithm for EM2CPP, which is able to produce approximate solutions in a short time. Simulations on real-world datasets validate the good performance of the proposed methods.