AI Seminar
     -------------------------------
     Thursday, May 27th, 2004
     3:30 pm - 5:00 pm
     175 ATL (Large Conference Room)

     "Choosing Objectives in Over-Subscription Planning"

     David E. Smith
     NASA Ames Research Center




----------------------------------
Many NASA planning problems are over-subscription problems ­ that is,
there are a large number of possible goals of differing value, and the
planning system must choose a subset that can be accomplished within the
limited time and resources available. Examples include planning for
telescopes like Hubble, SIRTF, and SOFIA; scheduling for the Deep Space
Network; and planning science experiments for a Mars rover. Unfortunately,
most existing planning systems are not designed to deal with problems like
this ­ they expect a well-defined conjunctive goal and terminate in
failure unless the entire goal can be achieved. In this talk I will
describe some new techniques for over-subscription problems that assist a
classical planner in choosing which goals to achieve, and the order in
which to achieve them. These techniques use plan graph cost-estimation
techniques to construct an orienteering problem, which is then used to
provide heuristic advice on the goals and goal order that should be
considered by a planner.