Coverage Planning for Multiple Unmanned Aerial Vehicles with Guaranteed Deadlines

Several situations may require monitoring a known region where dynamic events, such as forest fires, wildlife, or public spaces, are happening. The present work develops a set of algorithms to perform autonomous navigation in similar situations. The algorithms' requirements are essentially two: complete coverage of the region and set different visitation intervals for different points in the region. The first purpose of the work is to formalize the problem, creating a way to represent the evolution of the considered phenomena over time. It is performed through the discretization of the region and the creation of a point-wise priority function. In the algorithms developing process, specific requirements are considered taking into account different needs. To meet them, both centralized algorithms and a decentralized one are presented. The centralized algorithms can be distinguished considering what they look for: a Maxima Search algorithm searches for the next destination (reached with n steps of the vehicles), choosing the one with the higher priority, while the MPC-based algorithm searches for the best next step considering the time evolution of a function of the priority function. In this case, the step is the distance traveled in the minimum interval of time with the constant velocity considered. The decentralized algorithm bases its navigation on one of the centralized ones. It requires a mechanism to divide the area into regions of interest associated with each vehicle and update their information. The mechanism is forcing the vehicles to meet periodically. During this meeting, the priority information is updated, and the region is sub-divided. In the end, the performance of the different algorithms are compared, and their strengths and weaknesses are highlighted.