A New Result on the Complexity of Heuristic Estimates for the A*
  Algorithm
  Relaxed models are abstract problem descriptions generated by ignoring
constraints that are present in base-level problems. They play an important
role in planning and search algorithms, as it has been shown that the length of
an optimal solution to a relaxed model yields a monotone heuristic for an A?
search of a base-level problem. Optimal solutions to a relaxed model may be
computed algorithmically or by search in a further relaxed model, leading to a
search that explores a hierarchy of relaxed models. In this paper, we review
the traditional definition of problem relaxation and show that searching in the
abstraction hierarchy created by problem relaxation will not reduce the
computational effort required to find optimal solutions to the base- level
problem, unless the relaxed problem found in the hierarchy can be transformed
by some optimization (e.g., subproblem factoring). Specifically, we prove that
any A* search of the base-level using a heuristic h2 will largely dominate an
A* search of the base-level using a heuristic h1, if h1 must be computed by an
A* search of the relaxed model using h2.
