  The hm 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 theheuristic. Existing methods
for computing the hm heuristic require time exponential in m, limiting them to
small values (m andlt= 2). The hm 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 hm only
partially, is computationally cheaper and therefore usable for higher values of
m. The (complete) hm heuristic is combined with partial hm 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 hm 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.
