Combining Graphplan and Heuristic State Search

This planning graph structure is then fed to a heuristic extractor module that is capable of extracting a variety of effective and admissible heuristics, based on our recent theory (Nguyen and Kambhampati 2000). This heuristic, along with the problem specification, and the set of ground actions in the final action level of the planning graph structure are fed to a regression state search planner. To guide a regression search in the state space, a heuristic function needs to evaluate the cost of some set S of subgoals, comprising a regression state from the initial state, in terms of the number of actions required to achieve S from the initial state. This heuristic approximates the cost of a set S as the length of a "relaxed plan" for supporting S, ignoring all the mutex relations, plus the penalty for ignoring these negative interac-88 AI MAGAZINE Yochan is the planning group directed by Subbarao Kambhampati at Arizona State University.