Abstract
Distributed constraint optimization (DCOP) is an important framework for coordinated multiagent decision making. We address a practically useful variant of DCOP, called resource-constrained DCOP (RC-DCOP), which takes into account agents' consumption of shared limited resources. We present a promising new class of algorithm for RC-DCOPs by translating the underlying coordination problem to probabilistic inference. Using inference techniques such as expectation-maximization and convex optimization machinery, we develop a novel convergent message-passing algorithm for RC-DCOPs. Experiments on standard benchmarks show that our approach provides better quality than previous best DCOP algorithms and has much lower failure rate. Comparisons against an efficient centralized solver show that our approach provides near-optimal solutions, and is significantly faster on larger instances.
Introduction
In multiagent systems, agents often need to coordinate to maximize a global objective while sharing limited resources, such as sensors with finite batteries or teams scheduling meetings within a strict travel budget. This is modeled as a Resource-Constrained Distributed Constraint Optimization Problem (RC-DCOP).
The challenge is twofold: finding the optimal solution is NP-hard, causing complete solvers to struggle with scaling, and existing approximate solvers like Max-Sum often fail to find any feasible solution when resource constraints are tight. These approximate methods become unstable, leading to high failure rates where agents cannot agree on a plan that respects the budget.
Methodology
This research bridges the gap between decision-making and probabilistic inference using the "planning-as-inference" paradigm. The discrete RC-DCOP is first transformed into a continuous Quadratic Program (QP). While non-convex, this relaxation allows the use of powerful optimization tools. The QP is then recast as a problem of maximizing the likelihood of a "reward variable" in a mixture of Bayesian networks.
To solve this, the authors apply the Expectation-Maximization (EM) algorithm. Unlike standard DCOPs, the "Maximization" step for RC-DCOPs requires handling resource constraints, which the authors address using Dual Optimization and Block Coordinate Descent (BCD). They prove that the optimal update for agents' internal probabilities involves finding the root of a specific rational function, which can be done efficiently via local message-passing. The resulting algorithm, solveRCDCOP, ensures the system converges to a stable solution through nested loops of local messages between agents and resource nodes.
Experimental Results
The algorithm was evaluated on standard DCOP benchmarks: random graphs (30 and 40 nodes) and graph coloring problems (20 to 50 nodes). Comparisons were made against Max-Sum (implemented in Frodo 2.0) and the state-of-the-art centralized exact solver, toulbar2.
Key findings include:
- Stability: The EM approach demonstrated a failure rate of less than 5% across all benchmarks. In contrast, Max-Sum failed to find feasible solutions in over 30% of cases for 40-node random graphs, and over 50% in some settings.
- Quality: Compared to the centralized optimal solver, the EM algorithm consistently achieved solutions with 95-99% of the optimal utility.
- Scalability: For large, dense instances, the EM algorithm was significantly faster. While toulbar2 often hit its 1-hour time limit, EM typically converged within 3 minutes.
Conclusion
By reframing RC-DCOPs as a probabilistic inference task, this work provides a message-passing algorithm that is more stable than Max-Sum and more scalable than centralized solvers. While EM is guaranteed to reach a local optimum, its robustness in experiments suggests it is a powerful tool for complex multiagent coordination. Future work may extend this framework to dynamic environments where resource availability changes over time.
Summary updated