\documentclass{article}

\title{Scheduling Earth Observing Satellites with Evolutionary Algorithms}
\author{Al Globus, James Crawford, Jason Lohn and Anna Pryor}
\begin{document}
\maketitle

\section{Abstract}

A growing fleet of NASA, commercial, and foreign Earth observing
satellites (EOS) uses a variety of sensing technologies for
scientific, mapping, defense and commercial activities. Image collection
for these satellites is planned and scheduled by a variety of
software systems using many techniques.
Scheduling EOS is complicated by a number of important
constraints, including: 
power and thermal availability,
limited imaging segments per orbit,
time required to take each image,
limited on-board data storage,
transition time between look angles (slewing),
revisit limitations,
cloud cover,
stereo pair acquisition,
ground station availability and
coordination of multiple satellites.

We hypothesize that evolutionary algorithms can effectively
schedule Earth imaging satellites. The constraints are complex and
the bottlenecks are not well understood, a condition where
evolutionary algorithms are often effective. This is, in part, because evolutionary algorithms
require only that one can represent solutions, modify solutions,
and evaluate solution fitness.

To test the hypothesis we have developed a representative set of problems
and evolutionary software to solve them [Globus et al. 2001]. The model problems are:

\begin{enumerate}

\item A single satellite with a slewable instrument modeled on ASTER slewing
 and the Landsat ETM.

\item A single agile satellite with one instrument. Here the whole spacecraft is
slewed, rather than the instrument relative to the spacecraft.

\item A single satellite with multiple instruments (one of which is
slewable). 

\item A large constellation of single- and multiple-instrument
satellites communicating directly with the ground. This seeks to
mimic hypothetical future Ôsensor webs.Õ 

\item A large constellation of single-instrument slewable
satellites communicating with an in-orbit communications system
based on high-data-rate lasers.

\item The same as problem five, but with a much larger number of
satellites, multiple instruments, and requirements to image the
same target with different instruments.  This problem presumes much cheaper and more
reliable launch.

\end{enumerate}

There are a number of evolutionary algorithms in the literature. We
are using a genetic algorithm (GA) and simulated annealing (SA) to address EOS scheduling. 
Schedules are represented as a permutation on the imaging tasks (takeImages). A fast, simple scheduler places tasks one at a time, in permutation order, into the timeline.
We have successfully scheduled problem one with 2100 takeImages
and a two satellite constellation with 4200 takeImages with a one week time horizon.
In both cases simulated annealing beat the genetic algorithm, producing near perfect schedules
in the face of imaging time window, slewing, and SSR (onboard memory) constraints.

Taking an average of 96 runs, on problem one SA was able to schedule 857 (out of a possible 900 given the SSR constraint) takeImages vs. 817 for GA.  The difference was statistically significant.  The very best SA run was able to schedule 895 takeImages (5 less than perfect). 

On the two satellite problem, SA was able to schedule an average of 2178 (out of 2250 from SSR constraints) takeImages vs. 2001 for GA with a statistically significant difference. The best SA run was able to schedule 2213 takeImages (37 from perfect).

\section{References}

\parskip 5pt

\noindent
[Globus et al. 2001] Al Globus, James Crawford, Jason Lohn, and Robert Morris, "Scheduling Earth Observing Fleets Using Evolutionary Algorithms: Problem Description and Approach,"  \textit{Proceedings of the 3rd International NASA Workshop on Planning and Scheduling for Space}, NASA, Houston Texas, 27-29 October, 2002. 

\end{document}
