Article: Improving Heuristics Through Relaxed Search - An Analysis of TP4 and HSP*a in the 2004 Planning Competition

Skip to first unread message

Feb 23, 2006, 7:36:12 PM2/23/06
JAIR is pleased to announce the publication of the following article:

Haslum, P. (2006)
"Improving Heuristics Through Relaxed Search - An Analysis of TP4 and HSP*a in the 2004 Planning Competition",
Volume 25, pages 233-267.

For quick access via your WWW browser, use this URL:

The h^m admissible heuristics for (sequential and temporal) regression
planning are defined by a parameterized relaxation of the optimal cost
function in the regression search space, where the parameter m offers
a trade-off between the accuracy and computational cost of the
heuristic. Existing methods for computing the h^m heuristic require
time exponential in m, limiting them to small values (m < = 2). The
h^m heuristic can also be viewed as the optimal cost function in a
relaxation of the search space: this paper presents relaxed search, a
method for computing this function partially by searching in the
relaxed space. The relaxed search method, because it computes h^m only
partially, is computationally cheaper and therefore usable for higher
values of m. The (complete) h^2 heuristic is combined with partial h^m
heuristics, for m = 3,..., computed by relaxed search, resulting in a
more accurate heuristic.

This use of the relaxed search method to improve on the h^2 heuristic
is evaluated by comparing two optimal temporal planners: TP4, which
does not use it, and HSP*a, which uses it but is otherwise identical
to TP4. The comparison is made on the domains used in the 2004
International Planning Competition, in which both planners
participated. Relaxed search is found to be cost effective in some of
these domains, but not all. Analysis reveals a characterization of the
domains in which relaxed search can be expected to be cost effective,
in terms of two measures on the original and relaxed search spaces. In
the domains where relaxed search is cost effective, expanding small
states is computationally cheaper than expanding large states and
small states tend to have small successor states.

The article is available via:

-- (also see

-- World Wide Web: The URL for our World Wide Web server is
For direct access to this article and related files try:

-- Anonymous FTP from Carnegie-Mellon University (USA):
The compressed PostScript file is named

For more information about JAIR, visit our WWW or FTP sites, or

Steven Minton
JAIR Managing Editor

Reply all
Reply to author
0 new messages