Decentralized Multi-UAV Trajectory Task Allocation in Search and Rescue Applications

Abstract

Multi-UAV systems have significant potential to enhance search and rescue (SAR) operations, since a search area can be covered faster than current approaches when multiple UAVs operate in parallel. While recent advancements within the field of multi-robot coverage planning have yielded promising results, current algorithms are predominately centralized. In this paper, we present a generalization of the well-known decentralized consensus-based bundle algorithm (CBBA), that enables efficient task allocation in multi-UAV SAR operations. The generalized algorithm considers tasks as trajectories between two points where the traversal direction for each task is optimized in the task allocation process. We carry out a series of simulation-based experiments on benchmark problems and compare our results to a state-of-the-art centralized solution. We find that our novel decentralized approach yields times to completion similar to those achieved with a centralized coverage path planning approach, with only 1.9% overhead cost. We furthermore find that our approach performs 6% better than point allocations while scaling well with the number of UAVs involved in the search effort.