Tutorial 8

Trends in Artificial Intelligence Planning

Abstract:

AI Planning has changed a lot in recent years. There are new algorithms and models that follow new formulations and a renewed interest in empirical validation. As a result, more powerful planners exist that scale up better and can solve challenging problems. This includes Graphplan, SAT, CSP, and heuristic search approaches in classical planning; and other approaches for planning with time and resources, and for planning with sensors and incomplete information.

The idea of this tutorial is to provide a coherent and (mostly) self-contained account covering some of the main ideas and results. It is a technical tutorial for those interested in knowing what's going on in the area and for those considering doing research in planning.

Outline:

Heuristic Search:
State space models
Heuristic search algorithms A*, IDA* suboptimal algorithms where heuristics come from

Planning:
Planning as general problem solving
Representing planning problems: Strips, ADL; PDDL
Planning as Heuristic Search: HSP, Graphplan
Sequential vs. Parallel Planning
Automatic derivation of admissible heuristics
Other formulations: SAT, CSP, Model Checking
Planning with time and resources
Planning vs Scheduling

Planning and Control:
Planning with Incomplete Information: Conformant Planning
Planning with Sensing: Contingent Planning
Decision-theoretic Planning: Probabilities and Costs
Markov Decision Processes (MDPs) and Partially Observable MDPs

Accomplishments; Open Challenges

--------

Prerequisites: basic background in Planning and AI (e.g., Strips) as found in any AI textbook

Hector Geffner got his PhD at the UCLA with a dissertation that was co-winner of the 1990 ACM Dissertation Award. He then worked at the IBM TJ Watson Research Center in NY for two years before returning to the Universidad Simon Bolivar where he currently teaches.

Dr. Geffner has been working actively in planning since 1996. He is co-developer (with B. Bonet) of well known planners in AI such as HSP and GPT and of the formulation of 'Planning as Heuristic Search' which is becoming increasingly popular (see recent ECP/AIPS Confs and last AIPS Planning Contest).

He is one of the lectures at the First School in Planning (Cyprus, 10/2000) and along with M. Fox, he is the Planning and Scheduling area co-chair at IJCAI'2001.

Some references

* These and others papers available from my page at www.ldc.usb.ve/~hector