A tutorial on planning graph - Based reachability heuristics

Daniel Bryce, Subbarao Kambhampati

Research output: Contribution to journalArticlepeer-review

30 Scopus citations


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 data structure 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. Planning graphs are a cheap means to obtain informative look-ahead heuristics for search and have become ubiquitous in state-of-the-art heuristic search planners. We present the foundations of planning graph heuristics in classical planning and explain how their flexibility lets them adapt to more expressive scenarios that consider action costs, goal utility, numeric resources, time, and uncertainty.

Original languageEnglish (US)
Pages (from-to)47-83
Number of pages37
JournalAI Magazine
Issue number1
StatePublished - Mar 2007

ASJC Scopus subject areas

  • Artificial Intelligence


Dive into the research topics of 'A tutorial on planning graph - Based reachability heuristics'. Together they form a unique fingerprint.

Cite this