Balanced Multi-Region Coverage Path Planning for Unmanned Aerial Vehicles

Nowadays, Unmanned Aerial Vehicles (UAVs) are playing increasingly important roles in agriculture, rescuing and surveillance due to their small size, low cost and strong adaptability. Coverage Path Planning (CPP) is a fundamental problem for UAV applications, which means to find a path covering all the targets or regions of interest. Researches on CPP in a single region have been studied for decades, but rare to be devoted to covering multiple scattered regions of multiple UAVs. This paper proposes an attempt to solve this problem in a short time and take the task balance of multiple UAVs into account meanwhile. This work constructs a model for multiple UAVs to cover scattered regions firstly. In view of the high computational complexity of the precise solution, we keep innovating a heuristic measure based on the model to make the solving process feasible. To settle the problem of imbalanced time consumption caused by super regions, we improve the previously built model furthermore. A series of experiments validated that the presented approaches exhibit the effectiveness and balance of time consumption in diverse scenarios.

I. Introduction

Nowadays, UAVs play increasingly important roles in many real-life applications such as real-time monitoring, wireless coverage, searching and rescuing [1]–[3]. As one of the important foundations of UAV applications, Coverage Path Planning (CPP) that aims to find a pathway or pathways to cover the targets or regions of interest, has received significant research attention. The traditional research on CPP can be divided into three groups: multiple UAVs traverse the interior of a single region, a single UAV traverses multiple scattered regions, and multiple UAVs traverse multiple scattered regions.