Distance-based goal-ordering heuristics for Graphplan
Subbarao Kambhampati, Romeo Sanchez · 2000
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. 1 Introduction It has been known for sometime now that the backward search of Graphplan algorithm can be seen as solving a (dynamic) CSP problem [8; 17] . Given this relation, the order in which the backward search considers goals for expansion--the socalled "variable ordering heuristic", and the order in whic...