Subbarao Kambhampati and Romeo Sanchez Nigenda
We will discuss the shortcomings of known variable and value ordering strategies for Graphplan’s backward search phase, and propose a novel strategy that is based on a notion of the difficulty of achieving the corresponding subgoal. The difficulty of achievement is quantified in terms of the structure of the planning graph itself--specifically, the earliest level of the planning-graph at which that subgoal appears. We will present empirical results showing the surprising effectiveness of this simple heuristic on benchmark problems. We will end by contrasting the way distance-based heuristics are used in Graphplan and state-search planners like UNPOP, HSP and HSP-R.