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
- Planning as Heuristic Search: New Results; B. Bonet & H. Geffner;
Proceedings European Planning Conference (ECP-99), 1999,
Springer.
- Admissible Heuristics for Planning: P. Haslum & H. Geffner;
Proc. Artificial Intelligence Planning and Scheduling
(AIPS-2000), AAAI Press.
- Planning with Incomplete Information as Heuristic Search in Belief
Space; B. Bonet and H. Geffner, Proc. Artificial Intelligence
Planning and Scheduling (AIPS-2000), AAAI Press.
- Planning and Control: A Unifying View", B. Bonet and H. Geffner.