Decentralized task allocation with coupled constraints in complex missions

Abstract—This paper presents a decentralized algorithm that can create feasible assignments for a network of autonomous agents in the presence of coupled constraints. The coupled constraints are introduced to address complex mission charac-teristics that include assignment relationships, where the value of a task is conditioned on whether or not another task has been assigned, and temporal relationships, where the value of a task is conditioned on when it is performed relative to other tasks. The new algorithm is developed as an extension to the consensus-based bundle algorithm (CBBA), introducing the notion of pessimistic or optimistic bidding strategies and the relative timing constraints between tasks. This extension, called Coupled-constraint CBBA (CCBBA), is compared to the baseline in a complex mission simulation and is found to outperform the baseline, particularly for task-rich scenarios. I