Enhancing CBBA Convergence and Optimality Guarantees in Multiagent Task Allocation

The Consensus-Based Bundle Algorithm (CBBA) is a leading approach for decentralized task allocation, offering conflict-free task assignments within a bounded number of iterations and a 50% optimality guarantee for utility functions with Diminishing Marginal Gains (DMG). However, we identify three limitations: (1) the Time-Discounted Reward utility function proposed with CBBA is not always DMG, (2) the optimality guarantee may not hold even with DMG functions, and (3) the algorithm can be inefficient as it incurs unnecessary idle iterations after convergence. To address these issues, we propose three key contributions. For limitation (1), we introduce the Repeated Path Times utility function, which is DMG in all cases and aligns with Min-Sum and Makespan objectives. Regarding point (2), we develop Global CBBA (GCBBA), a variant algorithm that leverages global consensus to restore the 50% optimality guarantee under DMG and ensures bounded convergence for any bundle-monotonic objective. Finally, to address limitation (3), we design a decentralized early convergence detection method to improve efficiency. Experimental results show that GCBBA significantly accelerates convergence on large-scale problems compared to the baseline CBBA.

Authors

• Alexandre Kha
• Aurélie Beynier
• Christophe Labreuche
• Mathieu Marchand

Keywords

No keywords are indexed for this paper.