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

Deploying multi-satellite constellations for Earth observation requires coordinating potentiallyhundreds of spacecraft. With increasing on-board capability for autonomy, we canview the constellation as a multi-agent system (MAS) and employ decentralized schedulingsolutions. We analyze the multi-satellite constellation observation scheduling problem(COSP) and formulate it as a distributed constraint optimization problem (DCOP). COSPrequires scalable inter-agent communication and computation and consists of millions ofvariables which, coupled with the assumptions and structure, make existing DCOP algorithmsinadequate for this application. We develop a scheduling approach that employsa carefully constructed heuristic, referred to as the Geometric Neighborhood Decomposition(GND) heuristic, to decompose the global DCOP into sub-problems as to enablethe application of DCOP techniques. We present the Neighborhood Stochastic Search(NSS) algorithm, a decentralized algorithm to effectively solve COSP, and other large-scaledistributed problems, using decomposition. The experiments confirm the efficacy of theapproach against baseline algorithms, and we discuss the generality of NSS, GND, andproperties of COSP to other domains.