Decentralized Task Assignment with Precedence Constraints Using Approximate Message Passing Algorithm

Abstract This paper proposes a novel decentralized task assignment algorithm, called constrained task assignment and scheduling via approximate message passing (CTAS-AMP), for solving the constrained task assignment with scheduling (CTAS) problem, where tasks must be assigned to agents while respecting precedence constraints. Existing decentralized methods such as consensus-based bundle algorithm (CBBA) and its variants are limited in handling complex temporal dependencies. To address this, we model CTAS as a maximum a posteriori (MAP) estimation problem within a graphical model that includes agent, task, and constraint nodes. Using max-product belief propagation, we derive four types of messages and propose an iterative algorithm that computes, exchanges, and refines these messages under practical approximations. To satisfy constraints, the proposed method incorporates dedicated conflict resolution and refinement steps. Simulation results show that CTAS-AMP consistently generates feasible solutions that fully satisfy all precedence constraints, and demonstrates strong performance and robustness, particularly in scenarios with high variance in task rewards, compared to existing approaches such as coupled constrained CBBA.