\documentclass[twocolumn]{article}
\usepackage{times}

\title{Scheduling Earth Observing Fleets Using Evolutionary
Algorithms: Problem Description and Approach }
\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. As the number of satellites (now around 60) increases, the system as a whole will begin to approximate a sensor web. Image collection for these satellites is planned and scheduled by a variety of
software systems using many techniques, but nearly always as separate satellites or even instruments, not as an integrated sensor web. Scheduling EOS sensor webs 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.  All software is written in Java. In this paper we present the first results including
a comparison of separate vs. integrated scheduling of a two satellite constellation and a comparison
of several evolutionary and other optimization techniques; namely genetic algorithms, simulated annealing, squeaky wheel optimization, stochastic hill climbing and iterative sampling.

\section{Introduction}

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 (Muraoka et al. 1998, Potter and Gasch 1998,
Sherwood et al. 1998, and others). Science activities on different
satellites or even different instruments on the same satellite are
typically scheduled independently of one another, requiring the
manual coordination of observations by communicating teams of
mission planners. As sensor webs with large numbers of satellites and 
observation requests develop, manual coordination will no longer
be possible. Schedulers that treat the entire sensor web as a collection of resources will become
necessary to optimize usage.
 There has been some
work toward automatic scheduling of satellite fleets, e.g., Rao, et
al. reported scheduling ground station use, but not imaging
activity, for a fleet of seven Indian Earth imaging satellites (Rao
et al. 1998), and we present some preliminary results here.

Scheduling EOS is complicated by a number of important
constraints. Potin lists some of these constraints as:

\begin{enumerate}
\item Power and thermal availability.
\item Limited imaging segments per orbit.
\item Time required to take each image.
\item Limited on-board data storage. 
\item Transition time between look angles (slewing).
\item Revisit limitations.
\item Cloud cover.
\item Stereo pair acquisition.
\item Ground station availability, especially playback opportunities.
\item Coordination of multiple satellites.

\end{enumerate}

For further detail on the EOS scheduling
problem see Sherwood et al. 1998 and Frank et al. 2002.

We hypothesize that evolutionary algorithms can effectively
schedule Earth imaging satellites, both single satellites and
cooperating fleets. The constraints on such fleets are complex and
the bottlenecks are not always well understood, a condition where
evolutionary algorithms are often more effective than traditional
techniques. Traditional techniques often require a detailed
understanding of the bottlenecks, whereas evolutionary programming
requires only that one can represent solutions, modify solutions,
and evaluate solution fitness, not actually understand how to
reason about the problem or which direction to modify solutions (no
gradient information is required, although it can be used).

To test the hypothesis we have developed a (hopefully) representative set of problems
and software to compare solutions generated by various evolutionary and other optimization techniques. 
We also present data comparing scheduling a two satellite constellation as a (small) sensor web vs. as separate systems.

The next section describes the model problems. This is followed by
a description of the optimization technique comparison software and the results.  Further details on the model problems and software, including parallelization techniques, may be found in [Globus et al. 2002].

\section{Model Problems}

Since our project is designed to consider the scheduling of a
parameterizable generic system, not any particular spacecraft,
sensor, or sensor web, it is important to develop a
set of model problems that exhibit the important aspects of EOS
scheduling now and in the future. In all cases we attempt to base
our model sensors and satellites on hardware currently in orbit,
although the association is quite loose and the parameters are
meant to be representative, not accurate. We have identified and
begun to scope seven problems:

\begin{enumerate}

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

\item A two satellite constellation  with identical satellites from problem one.

\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 sensor web (i.e., a large constellation) of single- and multiple-instrument
satellites communicating directly with the ground.

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

\item A sensor web with a very large number of satellites including satellites with multiple instruments, and requirements to image the same target with different instruments.  This problem presumes much cheaper and more
reliable launch.

\end{enumerate}

Problems 1 and 2 have been implemented.  See [Globus et al. 2002] for addtional model details.

\section{EOS Scheduling by Evolutionary Algorithms and Other Optimization Techniques}

There are a number of evolutionary algorithms in the literature. We
compare a genetic algorithm (GA),  simulated annealing (SA), stochastic hill
climbing (HC), and iterative sampling (ISAMP) to address EOS scheduling. In addition,
we compare random and squeaky wheel (SW) transmission operators.  Note that although
these techniques can be thought of as evolutionary algorithms, not all practitioners would classify
them this way.

GAs seek to mimic natural evolution's ability to produce highly
functional objects. Natural evolution produces organisms, whereas
GAs can produce schedules, programs, molecular designs, and many
other structures.  Our GA employs the following algorithm:

\begin{enumerate}
\item Represent each schedule with a permutation or a Gantt chart;
each schedule is called an individual
\item Generate a population of individuals with random characteristics
\item Calculate the fitness of each individual
\item Repeat
\begin{enumerate}
\item Randomly select parents with a bias towards better fitness
\item Produce children from the parents a transmission operator:
\begin{enumerate}
\item crossover that combines parts of two parents into a child
\item mutation that modifies a single parent
\end{enumerate}
\item Calculate the fitness of the child
\item Randomly replace individuals of less fitness in the
population with the children
\end{enumerate}
\item Until satisfied according to some minimal convergence criteria

\end{enumerate}

In this paper we compare four search algorithms:

\begin{enumerate}
\item GA (the genetic algorithm described above)
\item HC (stochastic hill climbing) can be thought of as a genetic algorithm with a population of one where only fitter children are allowed to replace the parent. Two cases are investigated: 5 restarts per run and no restarts.
\item SA (simulated annealing) is similar to HC except that worse children can replaces the parent with probability:

%SA equation

Where the temperature starts at 100 and is multiplied by 0.92 every 1000 children (100,000 children are generated per run).
\item ISAMP (interative sampling) is essentially random search in permutation space.
\end{enumerate}

Evolution is guided by a fitness function. The fitness function
must provide a fitness for any possible individual, no matter how
bad, and distinguish between any two individuals, no matter how
close they are.  Our fitness function is
multi-objective. The objectives include:

\begin{enumerate}
\item Maximize the number of images taken (takeImages). 
\item Maximize the priority of the images taken.
\item Minimize total time spent slewing (slew motors wear out).
\item Minimize the sum of the slew angles for the images taken (small slews improve image resolution).
\end{enumerate}

These are manipulated so that lower values are better fitness and then combined into a weighted sum. 

We represent schedules as an ordering of the requested takeImages (a permutation). 
A simple greedy scheduler schedule the requested takeImages in the order indicated by the permutation.  This scheduler currently schedules tasks in keeping with the constraints earliest-first scheduling heuristics, and sensor
availability and slewing constraints.  If a task cannot be placed in the timelines, it is left unscheduled. Simple earliest-first scheduling had some problems, and we discovered
that the algorithm works better if earliest-first starts with a particular imaging window (period where the satellite was within sight of the target) and looks forward, wrapping around if the takeImage cannot be scheduled before the end of the time horizon. %define horizon, why is earliest first not the best?

We handle constraints by representing each resource as a
timeline. Each timeline then takes on appropriate values (i.e., in
use for a sensor, slew motor setting, SSR memory available) at different times.
A task is inserted at the first time available in all the resource timelines and the timelines

For evolution to proceed, we need crossover and mutation operators to create children from parents. We are currently using four mutation operators and one crossover operator. The mutation operators are:

\begin{enumerate}
\item Random swap. This is based on Syswerda and Palmucci's order-based mutation [Syswerda and Palmucci 1991]. Two permutation locations are chosen at random and the task numbers swapped. This is done n times.
\item Squeaky swap. This is the same as random swap except that the tasks to swap are chosen more carefully.  Specifically, a tournament of size n selects both tasks.  One task is chosen that should be moved forward in the permutation. The winning task is (in this order):
\begin{enumerate}
\item unscheduled rather than scheduled
\item higher priority
\item later in the permutation
\end{enumerate}
The other task is chosen assuming it should be moved back in the permutation.  The tournament winner has the opposite characteristics.
\item Placed squeaky swap. In squeaky swap we try to choose tasks that should be moved in particular directions in the permutation, but the direction of motion is not enforced.  In placed squeaky swap a separate tournament is conducted for each task.  The task to move forward is forced to be in the last half of the permutation.  The task to move back is forced to be at least twice as close to the front of the permutation as the task to be moved forward.
\item Cut and rearrange.  This is similar to the cut-set based operators used in the traveling salesman problem community.  The permutation is cut into n pieces and these are put back together in a random order.
\end{enumerate}

Additional operators are in development and testing.

The crossover operator is only used in the genetic algorithm.  The operator is Syswerda and Palmucci's position-based crossover [Syswerda and Palmucci 1991]. N permutation positions are chosen.  These are copied from the father to the child.  The remaining task numbers fill in the other positions in the father in the order they appear in the mother.

In many runs, several different transmission operators were used. In these cases, the transmission operator is chosen at random each time a child is produced.

%graphic


\section{Results}

A variety of search techniques and transmission operators were tested on a single problem with the following characteristics
\begin{enumerate}
\item one week operations.
\item two satellite in sun synchronous orbit one minute apart.
\item each satellite had the same single instrument.
\item instruments could slew up to 48 degrees cross-track in either direction at a rate of 50 seconds/degree.
\item 4200 takeImage targets were randomly distributed around the globe; 123 of these never came into view of either satellite. 
\item each takeImage requires 24 seconds of viewing.  
\item each takeImage had a priority between 1 and 5 (higher priority is more important).
\item each run (a combination of a particular search technique and transmission operators) was repeated 94 times (jobs). 
\item 100,000 children were produced by each job. 
\end{enumerate}

The main results comparing search techniques and transmission operators (various forms of mutation and crossover) can be found in tables 1 and 2.   A few observations from these tables:

\begin{enumerate}
\item Simulated annealing is clearly the best search technique.  
\item Random swap mutations beat the smarter 'squeaky' mutation where the tasks to swap are chosen more carefully (a counter intuitive result)
\item Multiple swaps are better than a single swap
\end{enumerate}

These observations should not, however, be taken too seriously.  First of all, this is a single problem and results may vary when the full range of the model problems are addressed.  Second, the squeaky algorithms can stand improvement and may someday outperform the random operators.  Nonetheless, if these results stand up, there are some important implications.  

\begin{enumerate}
\item Simulated annealing requires less memory than the genetic algorithm and does not require crossover operators, making it better performing, more efficient, and easier to implement the transmission operators.
\item Random swaps outperform the 'smarter' squeaky swaps, making random swaps better performing, faster, and easier to implement.
\item One should allow multiple random swaps, in spite of the minor increase in code complexity.
\end{enumerate}

\begin{table*}
\begin{center}
\begin{tabular}{|c|c|c|c|} \hline

search algorithm & transmission operators &mean & standard deviation \\ \hline
SA	& 1-9 swap & 					2171 & 27 \\ \hline
SA	& 1 swap &  						2354 & 36 \\ \hline
HC	5 restarts & 1-9 swaps & 		2539 & 45 \\ \hline
HC	5 restarts & 1 swap &			2564 & 43 \\ \hline
HC 0 restarts & 1 swap &			2575	 & 40 \\ \hline
SA & 1 squeaky swap &				2772 & 46 \\ \hline
SA & 1 placed squeaky swap & 	2814 & 42 \\ \hline
HC & 1 squeaky swap & 			2868	 & 45 \\ \hline
GA population = 100 & 	crossover and 1 swap & 3007 & 55 \\ \hline
GA population = 100 & 1-5 cut and rearranges & 3008 & 56 \\ \hline
SA & 1-5 cut and rearranges & 		3012	 & 52 \\ \hline

\end{tabular}

\caption{Comparison of search techniques and transmission operators by mean fitness of 94 runs of 100,000 children each.
Techniques are ordered by performance (low values indicate better fitness).
All values are rounded of to the next lowest whole number. It's clear that simulated annealing (SA) and multiple random swaps produces the most fit schedules.  All differences are statistically significant (as measured by Student's Ttest) except HC with 0 and 5 restarts with 1 swap, and the worst three.}
\label{TAB:summary}
\end{center}
\end{table*}


\begin{table*}
\begin{center}
\begin{tabular}{|c|c|c|c|} \hline

search algorithm & transmission operators &mean & standard deviation \\ \hline
SA	& 1-9 swap &						1873 & 30 \\ \hline
SA	& 1 swap &						2077 & 39 \\ \hline
HC	5 restarts & 1-9 swaps &		2287 & 49 \\ \hline
HC 5 restarts & 1 swap &			2313 & 47 \\ \hline
HC 0 restarts & 1 swap &			2327 & 43 \\ \hline
SA & 1 squeaky swap &				2527 & 50 \\ \hline
SA & 1 placed squeaky swap &		2559 & 46 \\ \hline
HC & 1 squeaky swap &				2625 & 48 \\ \hline
SA & 1-5 cut and rearranges & 		2737 & 58 \\ \hline
GA population = 100 & 1-5 cut and rearranges & 2754 & 60 \\ \hline
GA population = 100 & 	crossover and 1 swap & 2759 & 59 \\ \hline
\end{tabular}

\caption{Comparison of search techniques and transmission operators by mean sum or priorities of takeImages not scheduled.
Techniques are ordered by performance (low values indicate better fitness). Only the worst three are not statistically different, and these are where the order is different than when fitness controls the order.}
\label{TAB:summary}
\end{center}
\end{table*}

A second experiment compared GA with one swap operator on two problems: in the first, each satellite was randomly assigned half of the takeImages; in the second, either satellite was allowed to execute any takeImage.

%present integrated vs separate sat scheduling data here


\section{Future Work}

%HBSS,student teacher, ant colony
%rest of the problems
%additional constraints

\section{Summary}

Earth imaging satellite constellation scheduling is a complex task
with many variables and interacting constraints. We are defining a
set of representative model problems intended to exercise
scheduling software in the relevant dimensions. We hypothesize that
evolutionary programming can solve the EOS scheduling problem
effectively and have begun the development of software to test this
hypothesis on the model problems. This software is also being
designed to compare permutation vs. Gantt chart representations and
squeaky-wheel vs. blind transmission operators.

\section{Acknowledgements}

This work was funded by NASA's Computing, Information, \&
Communications Technology Program, Advanced Information Systems
Technology Program (contract AIST-0042), and by the Intelligent
Systems Program. Thanks to Alex Herz, Orbit Logic, Inc. and Jerald
Arp, PhD., Manager of Technical Support, Space Imaging LLC for
information regarding current EOS systems. Thanks also to Jennifer
Dungan, Jeremy Frank, and Bonnie Klein for reviewing this paper and
to Jennifer Dungan, Jeremy Frank, Robert Morris and David Smith for many helpful
discussions. 

\section{References}

\parskip 5pt

\noindent
Frank, J.;  Jonsson, A.; Morris, R.; and Smith, D. 2002. Planning
and Scheduling for Fleets of Earth Observing Satellites. In
proceedings of the 6th International Symposium on Artificial
Intelligence, Robotics, Automation and Space 2002 Montreal, June
18-22.

\noindent
Frank, J.; and Jonsson, A. 2002. Constraint-based
Attribute and Interval Planning, to appear in the Journal of
Constraints, Special Issue on Constraints and Planning.

\noindent
Globus, A.; Langhirt E.; Livny M.; Ramamurthy R.; Solomon M.; 
Traugott S. 2000. JavaGenes and Condor: Cycle-Scavenging Genetic
Algorithms, Java Grande 2000, sponsored by ACM SIGPLAN, San
Francisco, California, 3-4 June
2000. 
%people.nas.nasa.gov/~globus/papers/JavaGrande2000/JavaGrandePaper.html

\noindent
Globus, A. 2001. Towards 100,000 CPU Cycle-Scavenging by Genetic Algorithms,
NAS technical report NAS-0-011, October 2001.
%people.nas.nasa.gov/~globus/papers/Cycle-ScavengingGA/paper.html.

\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. 

\noindent
[Globus et al. 2002] Al Globus, Madhu Menon, Deepak Srivastava "JavaGenes: Evolving Molecular Force Field Parameters with Genetic Algorithm,"  \textit{Computer Modeling in Engineering and Science}, volume 3, number 5, pages 557-576, 


\noindent
Husbands P. 1994. Genetic Algorithms for Scheduling, AISR Quarterly,
number 89.

\noindent
Joslin, D.E.; Clements D.P.  1999 .Squeaky Wheel Optimization, Journal of
Artificial Intelligence Research, Volume 10, pages 353-373.

\noindent
Lamaitre, M.; Verfaillie, G.; Bataille, N. 1998. Sharing the Use of
a Satellite: an Overview of Methods, SpaceOps 1998, 1-5 June,
Tokyo, Japan.

\noindent
Lamaitre, M.; Verfaillie, G.; Frank, J.; 
Lachiver, J.; Bataille, N. 2000. How to Manage
the New Generation of Agile Earth Observation Satellites, SpaceOps
2000, sponsored by the Centre National dÕEstudes Spatialles (CNES)
of France.

\noindent
Litzkow, M.; Livny, M.; Mutka, M.W.  1988.
Condor - a Hunter of Idle Workstations, Proceedings of the 8th
International Conference of Distributed Computing Systems, pages
104-111.

\noindent
Montana, D.J. 2001. A Reconfigurable Optimizing
Scheduler, Proceedings of the Genetic and Evolutionary Computation
Conference, San Francisco, California, 7-11 July 2001, pages
1159-1166.

\noindent
Muraoka, H.; Cohen, R.H.; Ohno T.; Doi, N. 1998. Aster Observation
Scheduling Algorithm, SpaceOps 1998, 1-5 June, Tokyo, Japan.

\noindent
Rao, J.D.; Soma, P.; Padmashree, G.S. 1998.  Multi-Satellite
Scheduling System for LEO Satellite Operations, SpaceOps 1998, 1-5
June, Tokyo, Japan.

\noindent
Potin, P. 1998. End-To-End Planning Approach for Earth
Observation Mission Exploitation, SpaceOps 1998, 1-5 June, Tokyo,
Japan.
%www.nasda.go.jp/SpaceOps/paper98/track2/2b008.pdf.

\noindent
Potter W.; Gasch, J.  1998. A Photo Album of Earth: Scheduling
Landsat 7 Mission Daily Activities, SpaceOps 1998, 1-5 June, Tokyo,
Japan.

\noindent
Sherwood, R.; Govindjee, A.; Yan, D.; Rabideau, G.; Chien, S.;
Fukunaga, A. 1998. Using ASPEN to Automate EO-1 Activity Planning,
Proceedings of the 1998 IEEE Aerospace Conference, Aspen, CO,
March.
%www-aig.jpl.nasa.gov/public/planning/papers/ieee98\_eo1.pdf.

\noindent
Syswerda G.; Palmucci, J. 1991.  The Application of Genetic
Algorithms to Resource Scheduling, Proceedings of the Fourth
International Conference on Genetic Algorithms, University of
California, San Diego, 13-16 July 1991, Richard K. Belew and Lashon
B. Booker, editors, pages 502-508.

\noindent
Whitley, D.; Starkweather, T.; Fuquay, D. 1990.
Scheduling Problems and Traveling Salesmen: the Genetic Edge
Recombination Operator, Proceedings of the Third International
Conference on Genetic Algorithms, pages 133-140.

\noindent
Wolfe, W.J.; Sorensen, S.E. 2000.
Three Scheduling Algorithms Applied to the Earth Observing Systems
Domain,  Management Science, volume 46, number 1, January 2000,
pages 148-168.

\noindent
Yamaguchi, Y.; Kawakami, T.; Kahle, A.B.; Pniel, M.; Tsu, H. 1998.
Aster Mission Planning and Operations Concept, SpaceOps 1998, 1-5
June, Tokyo, Japan.


\end{document}
