Mixed Discrete and Continuous Algorithms for Scheduling Airborne
NASA Ames Research
ABSTRACT: We describe the problem of scheduling astronomy observations for
the Stratospheric Observatory for Infrared Astronomy, an airborne
problem requires maximizing the number of requested observations scheduled
subject to a mixture of discrete and continuous constraints relating the
of an astronomical observation to the position and time at which the
observation begins, telescope elevation limits, Special Use Airspace
available fuel. Solving the problem requires making discrete choices
(e.g. selection and sequencing of observations) and continuous ones
(e.g. takeoff time
and setup actions for observations by repositioning the aircraft).
We describe a novel combination of
Squeaky Wheel Optimization (SWO), an incomplete algorithm designed to solve
scheduling problems, with previously devised numerical optimization methods
and stochastic sampling approaches, as well as heuristics based on
reformulations of the SFPP to traditional OR scheduling problems. We
show that this new
algorithm efficiently finds good quality flight plans.
Dr. Jeremy Frank is an employee of NASA at NASA Ames Research
Center. I work in Code TI in the Autonomous Systems and
Robotics area, and am Group Lead of the
Planning and Scheduling Group.
I completed my PhD in Computer Science at U.C. Davis. I also have
a BA in Mathematics from Pomona College and an MS in Computer Science
from U.C. Davis. My academic interests include Artificial Intelligence,
particularly planning, scheduling and combinatorial optimization and search.
My recreational interests include ceramics, photography, cooking, short story readings,
gaming, mathematics, and history. I have a 20 month old daughter.
Last modified: Fri Aug 8 11:38:17 CST 2006