Distributed Constraint Optimization via Online Learning and Iterative Pricing with Application to Large-Scale Satellite Scheduling

Large-scale Distributed Constraint Optimization Problems (DCOPs) are often too complex to solve monolithically due to their NP-hard nature and the density of constraint graphs in real-world applications like satellite constellation scheduling. The authors seek a scalable, decentralized approach that can coordinate high-level task assignments while respecting complex, local physical constraints such as orbital visibility, memory limits, and slewing maneuvers.

The paper proposes a two-pronged strategy. First, it adapts modern online learning algorithms—specifically variants of Regret Matching (RM)—to solve DCOPs by treating them as potential games. These algorithms are lightweight, requiring only local communication, and are shown to be competitive with existing incomplete DCOP solvers. Second, the authors introduce an iterative pricing framework that decomposes the global DCOP into a high-level task allocation problem and independent local scheduling subproblems. The local solvers provide feedback to the meta-level DCOP through assignment-dependent prices, which penalize allocations that are physically infeasible for the local agents.

The combination of online learning and iterative pricing significantly improves performance in decentralized satellite scheduling. By decoupling the high-level coordination from the low-level scheduling constraints, the system can handle large-scale constellations more effectively than monolithic approaches. The experimental results demonstrate that this framework fulfills over 99% of observation requests in simulated real-world scenarios, substantially outperforming the 87% completion rate of state-of-the-art baselines. Furthermore, the authors show that standard stabilization heuristics like damping can actually degrade performance when used with online learning, suggesting that convergence toward an equilibrium is a robust search heuristic for these problems.