A Multi-Trip Task Assignment for Early Target Inspection in Squads of Aerial Drones
Abstract—Fleets of cooperative drones are a powerful tool in monitoring critical scenarios requiring early anomaly discovery and
intervention. Due to limited energy availability and application requirements, drones may visit target points in consecutive trips, with
recharging and data offloading in between. To capture timeliness of intervention and prioritize early coverage, we propose the new
notion of Weighted Progressive Coverage, which is based on the definition of time dependent weights. Weighted progressive coverage
generalizes classic notions of coverage, as well as a new notion of accumulative coverage specifically designed to address trip
scheduling. We show that weighted progressive coverage maximization is NP-hard and propose an efficient polynomial algorithm,
called Greedy and Prune (GaP), with guaranteed approximation. By means of simulations we show that GaP performs close to the
optimal solution and outperforms a previous approach in all the considered performance metrics, including coverage, average
inspection delay, energy consumption, and computation time, in a wide range of application scenarios. Through prototype experiments
we also confirm the theoretical and simulation analysis, and demonstrate the applicability of our algorithm in real scenarios.