Scalable Dynamic Distributed Constraint Optimization with Metareasoning and Application to Continual Satellite Operations

Abstract

Dynamic distributed constraint optimization problems (DDCOPs) provide a general framework for coordinating autonomous agents in changing environments. However, existing DDCOP formulations do not adequately address settings where optimization and execution overlap, resources persist across time, and agents operate under limited computational and communication constraints. We extend the DDCOP model to address these challenges by introducing an execution-aware formulation, together with new algorithms and frameworks for efficiently computing solutions. We develop a general framework for metareasoning in DDCOPs, enabling agents to determine when the estimated benefit of recomputing solutions outweighs its computational cost. We further extend the neighborhood stochastic search algorithm to the dynamic setting, introducing dynamic incremental neighborhood stochastic search (D-NSS), a scalable decomposition-based DDCOP algorithm that efficiently repairs previous solutions in response to problem dynamics. We apply our methods to the real-world application of large-scale satellite scheduling. Deploying autonomy to satellites requires efficient computation and communication in the face of highly dynamic environments. We demonstrate that D-NSS stabilizes to high-quality solutions, outperforming standard DDCOP baselines in solution quality, computation time, and message volume, while our metareasoning framework successfully balances resource conservation with utility. These methods will support the NASA FAME mission, the largest in-space demonstration of distributed multi-agent AI to date.

An earlier version titled "Large-Scale Continual Scheduling and Execution for Dynamic Distributed Satellite Constellation Observation Allocation" appears as an extended abstract in the Proceedings of the 25th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2026)