Planning and Scheduling for Fleets of Earth Observing Satellites

We address the problem of scheduling observations for a collection of Earth Observing Satellites. This scheduling task is a difficult optimization problem, involving multiple satellites, hundreds of requests, constraints on when and how to service each request, and resources such as instruments, recording devices, transmitters, and ground stations. High-fidelity models are required to ensure the validity of schedules. At the same time, the size and complexity of the problem makes it unlikely that systematic search methods will be able to produce good solutions in a reasonable amount of time. This paper presents an approach to solving the Earth Observing Satellite scheduling problem that involves: 1) modeling of the problem using a constraint-based language, 2) a stochastic greedy search algorithm for finding solutions, and 3) heuristics based on a generalized contention measure for guiding the search.