Planning Graph Based Reachability Heuristics

Tutorial presented at ICAPS 2006

..and at IJCAI 2007

Subbarao Kambhampati Daniel Bryce
Arizona State University
Tempe, AZ 85287-5406

Presenter Biographies: [txt]

Tutorial Description

The primary revolution in automated planning in the last decade has been the very impressive scale-up in planner performance. A large part of the credit for this can be attributed squarely to the invention and deployment of powerful reachability heuristics. Most, if not all, modern reachability heuristics are based on a remarkably extensible datastructure called the planning graph--which made its debut as a bit player in the success of Graphplan, but quickly grew in prominence to occupy the center-stage.

In this tutorial, we will start with a discussion of the foundations of reachability analysis with planning graphs. We will then discuss the many ways of applying this analysis to develop scalable planners. Starting with classical planning, we will discuss heuristics for cost-based planning, over-subscription planning, planning with resources, temporal planning, non-deterministic planning as well as stochastic planning.

The intended audience is new researchers in planning or experienced researchers from another specialization. The audience should have some familiarity with classical planning models, and preferably also temporal and non-deterministic plannning.

Outline: [txt]

ICAPS 06 Materials

Slides: [ppt][pdf]

Audio:[mp3 #1 (Rao)] [mp3 #2 (Dan) ] [mp3 #3 (Rao) ]

IJCAI-07 Materials

Syllabus: [txt]

Slides: [ppt]

Audio:[wav #1] [wav #2]

Technical Report

We also have a survey article on planning graph heuristics that contains most of the material covered in the tutorial.

How to skin a planning graph for fun and profit: A Tutorial on Planning Graph Based Reachability Heuristics.
Daniel Bryce and Subbarao Kambhampati. ASU CSE TR-06-007,AI Magazine Vol 27, No. 4, Winter 2006

You are visitor number to this page!