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.

Deploying multi-satellite constellations for Earth observation requires coordinating potentially hundreds of spacecraft. With increasing on-board capability for autonomy, we can view the constellation as a multi-agent system (MAS) and employ decentralized scheduling solutions. We formulate the problem as a distributed constraint optimization problem (DCOP) and desire scalable inter-agent communication. The problem consists of millions of variables which, coupled with the structure, make existing DCOP algorithms inadequate for this application. We develop a scheduling approach that employs a well-coordinated heuristic, referred to as the Geometric Neighborhood Decomposition (GND) heuristic, to decompose the global DCOP into sub-problems as to enable the application of DCOP algorithms. We present the Neighborhood Stochastic Search (NSS) algorithm, a decentralized algorithm to effectively solve the multi-satellite constellation observation scheduling problem using decomposition. In full, we identify the roadblocks of deploying DCOP solvers to a large-scale, real-world problem, propose a decomposition-based scheduling approach that is effective at tackling large scale DCOPs, empirically evaluate the approach against other baseline algorithms to demonstrate the effectiveness, and discuss the generality of the approach.