Extracting Effective and Admissible State Space Heuristics from the Planning Graph

XuanLong Nguyen and Subbarao Kambhampati, Arizona State University

Graphplan and heuristic state space planners such as HSP-R and UNPOP are two of the most effective approaches for solving classical planning problems. These approaches have hither-to been seen as largely orthogonal. In this paper, we show that the planning graph structure that Graphplan builds in polynomial time, provides a rich substrate for deriving more effective heuristics for state space planners. Specifically, we show that the heuristics used by planners such as HSP-R and UNPOP do badly in several domains due to their failure to consider the interactions between subgoals, and that the mutex information in the planning graph captures exactly this interaction information. We develop several families of heuristics, some aimed at search speed and others at optimality of solutions. Our empirical studies show that our heuristics significantly out-perform the existing state space heuristics


This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.