Article: Where `Ignoring Delete Lists' Works: Local Search Topology in Planning Benchmarks
jai...@ptolemy.arc.nasa.gov
Hoffmann, J. (2005)
"Where `Ignoring Delete Lists' Works: Local Search Topology in Planning Benchmarks",
Volume 24, pages 685-758.
For quick access via your WWW browser, use this URL:
http://www.jair.org/abstracts/hoffmann05b.html
Abstract:
Between 1998 and 2004, 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 unprecedented success of such methods,
in many commonly used benchmark examples, calls for an understanding
of what classes of domains these methods are well suited for.
In the investigation at hand, we derive a formal background to such
an understanding. We perform a case study covering a range of 30
commonly used STRIPS and ADL benchmark domains, including all
examples used in the first four international planning competitions.
We *prove* connections between domain structure and local search
topology -- heuristic cost surface properties -- under an idealized
version of the heuristic functions used in modern planners. The
idealized heuristic function is called h^+, and differs from the
practically used functions in that it returns the length of an
*optimal* relaxed plan, which is NP-hard to compute. We identify
several key characteristics of the topology under h^+,
concerning the existence/non-existence of unrecognized dead ends, as
well as the existence/non-existence of constant upper bounds on the
difficulty of escaping local minima and benches. These distinctions
divide the (set of all) planning domains into a taxonomy of classes
of varying h^+ topology. As it turns out, many of the 30
investigated domains lie in classes with a relatively easy topology.
Most particularly, 12 of the domains lie in classes where FF's
search algorithm, provided with h^+, is a polynomial solving
mechanism.
We also present results relating h^+ to its approximation as
implemented in FF. The behavior regarding dead ends is provably the
same. We summarize the results of an empirical investigation showing
that, in many domains, the topological qualities of h^+ are
largely inherited by the approximation. The overall investigation
gives a rare example of a successful analysis of the connections
between typical-case problem structure, and search performance. The
theoretical investigation also gives hints on how the topological
phenomena might be automatically recognizable by domain analysis
techniques. We outline some preliminary steps we made into that
direction.
The article is available via:
-- comp.ai.jair.papers (also see comp.ai.jair.announce)
-- World Wide Web: The URL for our World Wide Web server is
http://www.jair.org/
For direct access to this article and related files try:
http://www.jair.org/abstracts/hoffmann05b.html
-- Anonymous FTP from Carnegie-Mellon University (USA):
ftp://ftp.cs.cmu.edu/project/jair/volume24/hoffmann05b.ps
The compressed PostScript file is named hoffmann05b.ps.Z
An online appendix is also available, named hoffmann05b-appendix1.ps
For more information about JAIR, visit our WWW or FTP sites, or
contact jai...@isi.edu
--
Steven Minton
JAIR Managing Editor