Technical Report No. 133 - Abstract

Joerg Hoffmann
A Heuristic for Domain Independent Planning and its Use in an Enforced Hill-climbing Algorithm

The standard approach to obtain a heuristic is to relax the problem P at hand into a simpler problem P'. The optimal solution length for situations in P' can then be used as an admissible estimate for the difficulty of situations in P. Applying this to domain independent planning, one encounters serious problems: a planning problem P can easily be relaxed into P' by ignoring the delete lists of the operators, but, as the authors of HSP point out, computing the length of an optimal solution plan for P' is still NP-hard. What one can, however, compute efficiently, is some plan that solves P'. In this paper, we introduce a method for doing so. The relaxed plans obtained this way give a good estimate for the length of a real solution, and they can also be used in a simple manner to guide action selection during planning. Using these informations, excellent results can be obtained by employing a simple search strategy that proceeds towards the goal in a greedy manner. The Algorithm we propose is complete on deadlock-free domains. With a greedy search strategy, it can not guarantee the solution plans to be optimal. In spite of this, it finds optimal, or close to optimal, plans in most cases. Often, it solves the problems almost without any search at all.