Incollection,
Planning as Heuristic Search: New Results Recent Advances in AI Planning
volume 1809 of Lecture Notes in Computer Science, chapter 28, Springer Berlin / Heidelberg, Berlin, Heidelberg, (2000)
DOI: 10.1007/10720246\_28
Abstract
In the recent AIPS98 Planning Competition, the hsp planner, based on a forward state search and a domain-independent heuristic, showed that heuristic search planners can be competitive with state of the art Graphplan and Satisfiability planners. hsp solved more problems than the other planners but it often took more time or produced longer plans. The main bottleneck in hsp is the computation of the heuristic for every new state. This computation may take up to 85\% of the processing time. In this paper, we present a solution to this problem that uses a simple change in the direction of the search. The new planner, that we call hsp r, is based on the same ideas and heuristic as hsp , but searches backward from the goal rather than forward from the initial state. This allows hsp r to compute the heuristic estimates only once . As a result, hsp r can produce better plans, often in less time. For example, hsp r solves each of the 30 logistics problems from Kautz and Selman in less than 3 seconds. This is two orders of magnitude faster than blackbox . At the same time, in almost all cases, the plans are substantially smaller. hsp r is also more robust than hsp as it visits a larger number of states, makes deterministic decisions, and relies on a single adjustable parameter than can be fixed for most domains. hsp r, however, is not better than hsp accross all domains and in particular, in the blocks world, hsp r fails on some large instances that hsp can solve. We discuss also the relation between hsp r and Graphplan, and argue that Graphplan can also be understood as a heuristic search planner with a precise heuristic function and search algorithm.
