Cooperative path planning for multiple UAVs in dynamic and uncertain environments

This paper addresses the problem of cooperative path planning for a fleet of unmanned aerial vehicles (UAVs). The paths are optimized to account for uncertainty/adversaries in the environment by modeling the probability of UAV loss. The approach extends prior work by coupling the failure probabilities for each UAV to the selected missions for all other UAVs. In order to maximize the expected mission score, this stochastic formulation designs coordination plans that optimally exploit the coupling effects of cooperation between UAVs to improve survival probabilities. This allocation is shown to recover real-world air operations planning strategies, and to provide significant improvements over approaches that do not correctly account for UAV attrition. The algorithm is implemented in an approximate decomposition approach that uses straight-line paths to estimate the time-of-flight and risk for each mission. The task allocation for the UAVs is then posed as a mixed-integer linear program that can be solved using CPLEX.