Failure-Aware Tasking for Teams of Drones

Abstract

Teams of drones have been proposed for many monitoring and data collection applications, including forest fire monitoring, search and rescue, disaster response, and infrastructure inspection. However, robot systems can be stochastic, and uncertainty arises when operating environments are dynamic or hostile. This paper investigates the problem of assigning drones to tasks where the probability that a given group of drones can cooperatively complete a task follows a Poisson-Binomial distribution. We show how to determine if a solution exists and how to calculate an upper bound on the optimal solution. We present a variation of the branch-and-bound algorithm – termed Branch-and-Match – that is tailored to our problem and always finds an optimal solution at the cost of computation time. For a more tractable approach, we present a heuristics-based algorithm – termed M+ILS – that turns the problem into a balanced matching problem to find an initial solution then runs a variation of the Iterated Local Search (ILS) algorithm. Our M+ILS algorithm is applicable to distributed scenarios but finds suboptimal solutions. We evaluate these various algorithms in a simulated forest fire monitoring scenario based on the characteristics of a fleet of real drones. Our empirical results show that the M+ILS algorithm finds solutions with an average performance gap of 2.68% compared to the optimal solution found using the Branch-and-Match algorithm.