Technical Report No. 185 - Abstract

Joerg Hoffmann
Where Ignoring Delete Lists Works: Local Search Topology in Planning Benchmarks

During the last five years, the planning community has seen vast progress in terms of the sizes of benchmark examples that domain-independent planners can tackle successfully. The key technique behind this progress is the use of heuristic functions based on relaxing the planning task at hand, where the relaxation is to assume that all delete lists are empty. The success of such methods in many of the current benchmarks suggests that in those task's state spaces relaxed goal distances yield a heuristic function of high quality. Investigating a large range of planning domains, I prove that the latter is indeed the case. I identify several key characteristics of local search topology under relaxed goal distances, concerning the non-existence of unrecognized dead ends, as well as constant upper bounds on the difficulty of escaping local minima and benches. These characteristics occur in the majority of the current benchmarks. This explains the recent success of heuristic planners. Specifically, it follows that FF's search algorithm, using an idealized heuristic function, is a polynomial solving mechanism in (at least) eleven commonly used benchmark domains. The proofs shed light on what the structural reasons are behind the topological phenomena, giving hints on how these phenomena might be automatically recognizable. I discuss the consequences of my findings on ways of benchmarking in planning.