Abstract
Distributed constraint optimization problems (DCOPs) provide a popular framework for distributed decision making under limited communication, but many real-world instances are too large to solve monolithically. We address this challenge from two complementary directions.
First, we revisit the connection between DCOPs and potential games, adapting modern online learning algorithms for equilibrium finding to DCOPs. Our findings show that these algorithms are competitive with representative incomplete DCOP algorithms.
Next, we turn to decomposition frameworks for large-scale DCOPs, motivated by large-scale decentralized satellite scheduling. We propose a new framework that separates a DCOP into two interacting subproblems: a high-level meta-DCOP for task allocation, and independent local optimization problems for scheduling. To couple the two levels, we develop a novel iterative pricing method that updates the meta-level utilities using feedback from the local optimizers.
Combining our online learning methods with our iterative pricing framework, we achieve near-optimal performance on real-world decentralized satellite scheduling problem instances, fulfilling over 99% of observation requests compared to 87% for state-of-the-art baselines.
Blogger's Review: This paper presents an innovative solution for large-scale satellite scheduling using distributed constraint optimization, particularly the integration of online learning and iterative pricing. It demonstrates effectiveness in complex distributed environments and holds significant practical application value. Future research may explore potential extensions of this approach.