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

Abstract

Deploying multi-satellite constellations for Earth observation requires coordinating potentially hundreds of spacecraft. With increasing onboard capability for autonomy, we can view the constellation as a multi-agent system (MAS) and employ decentralized scheduling solutions. We analyze the multi-satellite constellation observation scheduling problem (COSP) and formulate it as a distributed constraint optimization problem (DCOP). COSP requires scalable inter-agent communication and computation and consists of millions of variables which, coupled with the assumptions and structure, make existing DCOP algorithms inadequate for this application. We develop a scheduling approach that employs a carefully constructed heuristic, referred to as the Geometric Neighborhood Decomposition (GND) heuristic, to decompose the global DCOP into sub-problems to enable the application of DCOP techniques. We present the Neighborhood Stochastic Search (NSS) algorithm, a decentralized algorithm to effectively solve COSP and other large-scale distributed problems, using decomposition. The experiments confirm the efficacy of the approach against baseline algorithms, and we discuss the generality of NSS, GND, and properties of COSP to other domains.