206 Chapter 9 Heuristics in Planning
with respect to an a priori given upper bound. However, experience shows that h
1
is not as informative as h
0
. It usually leads to a much less focused search.
The idea behind h
1
can be extended in order to produce a more informative
heuristic that is still admissible. Instead of considering that the distance to a set g is
the maximum distance to a proposition p ∈ g , we estimate it to be the maximum
distance to a pair of propositions {p, q}∈g . This new estimate
2
is defined accord-
ing to the three following recursive equations (in addition to the termination cases
that remain as in Formulas 9.1):
2
(s, p) = min
a
{1 +
2
(s, precond(a)) | p ∈ effects
+
(a)}
2
(s, {p, q}) = min{
min
a
{1 +
2
(s, precond(a)) |{p, q}⊆effects ...