Large-Scale Continual Scheduling and Execution for Dynamic Distributed Satellite Constellation Observation Allocation
This addresses the problem of efficient autonomous control for Earth-observing satellite constellations, forming the foundation for NASA's FAME mission, though it appears incremental as it builds on existing DDCOP approaches.
The paper tackles the challenge of enabling autonomous scheduling and execution for large satellite constellations by proposing new online algorithms for dynamic distributed constraint optimization problems, showing through simulation that their D-NSS algorithm converges to near-optimal solutions and outperforms baselines in solution quality, computation time, and message volume.
The size and capabilities of Earth-observing satellite constellations are rapidly increasing. Leveraging distributed onboard control, we can enable novel time-sensitive measurements and responses. However, deploying autonomy to large multiagent satellite systems necessitates algorithms with efficient computation and communication. We tackle this challenge and propose new, online algorithms for large-scale dynamic distributed constraint optimization problems (DDCOP). We present the Dynamic Multi-Satellite Constellation Observation Scheduling Problem (DCOSP), a new formulation of DDCOPs that models integrated scheduling and execution. We construct an omniscient offline algorithm to compute the novel optimality condition of DCOSP and present the Dynamic Incremental Neighborhood Stochastic Search (D-NSS) algorithm, an incomplete online decomposition-based DDCOP approach. We show through simulation that D-NSS converges to near-optimal solutions and outperforms DDCOP baselines in terms of solution quality, computation time, and message volume. Our work forms the foundation of the largest in-space demonstration of distributed multiagent AI to date: the NASA FAME mission.