background image
IJCAI-2016 Tutorial:
Introduction to Planning Models and Methods
Hector Geffner
DTIC Department
ICREA & Universitat Pompeu Fabra
Barcelona, Spain
Blai Bonet
Departamento de Computación
Universidad Simón Bolívar
Caracas, Venezuela
1. Brief Description of the Tutorial
Planning is the model-based approach to autonomous behavior where the agent behavior is
derived automatically from a model. In the tutorial, we will look at the variety of models
used in AI planning and the methods that have been developed for solving them. The goal is
to provide a modern and coherent view of planning that is comprehensive but not shallow.
Roughly, we'll follow our 2013 book, A Concise Introduction to Models and Methods for
Automated Planning. H. Geffner and B. Bonet. Synthesis Lectures on AI and ML. Morgan
and Claypool, 2013.
2. More Detailed Description
While planning is one of the oldest areas in AI, it has changed a great deal over the last few
years, becoming at the same time, more mathematical and more empirical. Planning is best
conceived as the model-based approach to autonomous behavior where the agent behavior is
derived automatically from a model. In this sense, it contrasts with model-free approaches,
where the agent behavior results from learning, and programming-based approaches, where
the agent behavior is hardwired.
A planner accepts a compact description of a model representing the initial situation,
actions, sensors, and goal of an agent, and automatically produces the agent controller.
While the basic planning models assume complete state information, deterministic actions,
and hard goals, other models relax these assumptions. Since the models are all intractable
in the worst case, the main challenge is planning is computational: scaling up to large
models represented in compact form.
1
background image
In the course, we will look at the variety of models used in AI planning, and the tech-
niques that have been developed for solving them. We will also look at the use of these
models for both behavior generation and recognition. The goal is to provide a modern and
coherent view of planning that is comprehensive but not shallow.
3. Tentative Outline
• Planning and Autonomous Behavior
• Planning Models: Classical, Conformant, Sensing, MDPs, POMDPs
• Representing Planning Models in Compact Form: Languages
• Computation: Classical Planning
‐ Classical Planning as Heuristic Search
‐ Classical Planning as SAT
‐ Extensions: helpful actions, landmarks, multi-queue best first search
‐ Complexity, Width-based Search
‐ Status and Scope of Classical Planning
• Beyond Classical Planning
‐ Top down approaches: Native Solvers for MDPs and POMDPs, Value Iteration,
Policy Iteration, RTDP, UCT; Off-line vs. On-line Planning methods
‐ Bottom up approaches: Transformations into Classical Planning: Soft goals, goal
(and plan) recognition, derivation of finite state controllers, temporal extended
goals
‐ Approximation Methods for dealing with uncertainty and partial observability:
‐ Use and scope of classical replanning methods
• Challenges
• Wrap up
4. Slides
The slides of the AAAI-2014 tutorial, that is similar, can be found at http://www.dtic.upf.edu/
~hgeffner/Tutorial/AAAI-2014-Tutorial.pdf. We plan to update these slides and place them
at http://www.dtic.upf.edu/~hgeffner/Tutorial/IJCAI-2016-Tutorial-Description.pdf for
IJCAI-2016.
2
background image
5. Target Audience
Tutorial is addressed to students and researchers interested in autonomous behavior and
cognitive science. Prerequisites include basic math and algorithmics, and some introduction
to AI course, although not strictly necessary. A lot of technical material will be covered
but the tutorial will be mostly self-contained.
6. Relevance
Planning is one of the oldest and most central subareas of AI. It represents the model-based
approach to autonomy, where predictive models are used to infer the control. The goal of
the tutorial is to provide a modern and coherent view of planning that is comprehensive
but not shallow.
7. Short Bios
Hector Geffner is an ICREA Research professor at the Universitat Pompeu Fabra in Barcelona.
He is interested in models of reasoning, learning, and action, in people and machines. He
has a PhD from UCLA and received the 1990 ACM Dissertation Award, and the 2009,
2010, and 2014 ICAPS Influential Paper Awards. Geffner is a fellow of AAAI and ECCAI.
Blai Bonet is a professor at the Universidad Simón Bolívar in Caracas, Venezuela. His
main research interests are automated planning, knowledge representation and search. He
has a PhD degree from UCLA, and received the 2009 and 2014 ICAPS Influential Paper
Awards. He is AE Editor of the AI Journal and JAIR.
3