Planning as heuristic search

In the AIPS98 Planning Contest, the HSP planner showed that heuristic searc h planners can be competitive with state-of-the-art Graphplan and SAT plann ers. Heuristic search planners like HSP transform planning problems into pr oblems of heuristic search by automatically extracting heuristics from Stri ps encodings. They differ from specialized problem solvers such as those de veloped for the 24-Puzzle and Rubik's Cube in that they use a general decla rative language for stating problems and a general mechanism for extracting heuristics from these representations. In this paper, we study a family of heuristic search planners that are base d on a simple and general heuristic that assumes that action preconditions are independent. The heuristic is then used in the context of best-first an d hill-climbing search algorithms, and is tested over a large collection of domains. We then consider variations and extensions such as reversing the direction of the search for speeding node evaluation, and extracting inform ation about propositional invariants for avoiding dead-ends. We analyze the resulting planners, evaluate their performance, and explain when they do b est. We also compare the performance of these planners with two state-of-th e-art planners, and show that the simplest planner based on a pure best-fir st search yields the most solid performance over a large set of problems. W e also discuss the strengths and limitations of this approach, establish a correspondence between heuristic search planning and Graphplan, and briefly survey recent ideas that can reduce the current gap in performance between general heuristic search planners and specialized solvers. (C) 2001 Elsevi er Science B.V. All rights reserved.