Biographical information: Dr. Jeremy Frank received his PhD in computer science from the University of California at Davis. He has worked at NASA Ames Research Center since 1997. His research interests include Artificial Intelligence-based approaches to planning and scheduling, constraint reasoning, combinatorial optimization and game theoretic approaches to multi-criteria optimization. In his copious spare time, he is an avid cook, photographer, war-gamer, potter and story-teller.

A joint CSE and JDEHP Colloquium

Thursday, October 28, 2004.

Refreshments: 3:30 p.m.
Talk: 4:00 p.m., 115 Avery Hall

Joint work with Elif Kurklu and Michael A.K. Gross

We describe an innovative solution to the problem of scheduling astronomy observations for the Stratospheric Observatory for Infrared Astronomy, an airborne observatory. The problem contains complex constraints relating the feasibility of an astronomical observation to the position and time at which the observation begins, telescope elevation limits 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 setting up observations by repositioning the aircraft). The problem also includes optimization criteria such as maximizing observing time while simultaneously minimizing total flight time. We describe a method to search for good flight plans that satisfy all constraints. This novel approach combines heuristic search, biased stochastic sampling, continuous optimization techniques, and well-founded approximations that eliminate feasible solutions but greatly reduce computation time.

A lecture at CSCE 421/821

Friday, October 29, 2004,

111 Avery Hall

Constraint Reasoning in Zero Gravity

Much research in constraint reasoning is performed on simple problems that are solved once. Typically (but not always), these problems consist of constraints on 2 variables and a homogeneous, extensional representation of the constraint with bit matrices. Considerable effort has gone into optimizing filtering algorithms and heuristics for such problems. However, NASA applications (both for on-board control systems and tools used by mission control) consist of heterogeneous constraints, often over mixtures of discrete and continuous quantities, that change over time. Furthermore, constraint reasoning systems do not exist in isolation, and often there are additional limitations that influence how these problems must be solved in practice. I will present a critical survey of constraint reasoning research in light of NASA's needs. I will describe work performed at NASA to apply constraint reasoning approaches to planning and scheduling technology applicable to a wide variety of NASA missions.

Required reading for class: Ari Jonsson, Paul Morris, Nicola Muscettola, Kanna Rajan and Ben Smith. "Planning in Interplanetary Space: Theory and Practice." In the Proceedings of the Fifth International Conference on Artificial Intelligence Planning and Scheduling, 2000
Recommended reading for class: Jeremy Frank and Ari Jonsson. "Constraint-Based Attribute and Interval Planning." Journal of Constraints Special Issue on Constraints and Planning, vol. 8 no 4, 2003.

Friday, October 29, 2004, with students right after class, Avery Hall 348. (Perhaps around 12:00 p.m. to allow set up time.)