Mixed Discrete and Continuous Algorithms for Scheduling Airborne Astronomy Observations

Jeremy Frank

NASA Ames Research

ABSTRACT: We describe the problem of scheduling astronomy observations for the Stratospheric Observatory for Infrared Astronomy, an airborne telescope. The problem requires maximizing the number of requested observations scheduled subject to a mixture of discrete and continuous constraints relating the feasibility of an astronomical observation to the position and time at which the observation begins, telescope elevation limits, Special Use Airspace limitations, and 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.

Deepak Ramachandran
Last modified: Fri Aug 8 11:38:17 CST 2006