Decentralized, Decomposition-Based Observation Scheduling for a Large-Scale Satellite Constellation

Deploying multi-satellite constellations for Earth observation re- quires coordinating potentially hundreds of spacecrafts. Centralized approaches to observation scheduling rely on a single controller tasking each satellite. With increasing on-board capability for au- tonomy, we can view the constellation as a multi-agent system (MAS) and employ decentralized scheduling solutions that elimi- nate the need for a centralized scheduler. We formulate the problem as a distributed constraint optimization problem (DCOP) and con- sider a model with limited inter-agent communication. Due to the scale and structure of the problem, many existing DCOP algorithms are infeasible for this application. Our scheduling approach em- ploys a heuristic that produces well coordinated behavior without centralized control or shared knowledge. By partitioning the prob- lem into sub-problems where less agents attempt to schedule less requests, agent actions are more easily coordinated. We outline the construction of a heuristic that performs this decomposition of the global problem. Each sub-problem is a smaller DCOP that serves as a better candidate for applying existing DCOP techniques in both scale and structure. Empirical evaluations highlight the improve- ment from decentralized approaches and advancement towards centralized solutions.