Planning Graph Based Reachability Heuristics Daniel Bryce and Subbarao Kambhampati Duration: Half-day Contact: Daniel Bryce, danbryce410@gmail.com 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.