Threshold Bundle-based Task Allocation for Multiple Aerial Robots

Abstract

This paper focuses on the large-scale task allocation problem for multiple Unmanned Aerial Vehicles (UAVs). One of the great challenges with task allocation is the NP-hardness for both computation and communication. This paper proposes an efficient decentralised task allocation algorithm for multiple UAVs to handle the NP-hardness while providing an optimality bound of solution quality. The proposed algorithm can reduce computational and communicating complexity by introducing a decreasing threshold and building task bundles based on the sequential greedy algorithm. The performance of the proposed algorithm is examined through Monte-Carlo simulations of a multi-target surveillance mission. Simulation results demonstrate that the proposed algorithm achieves similar solution quality compared with benchmark task allocation algorithms but consumes much less running time and consensus steps.