208 Chapter 9 Heuristics in Planning
the planning-graph structure approximates the distance
∗
(s
0
, g ) with an estimate
G
(s
0
, g ) that is the level of the first layer of the graph such that g ⊆ P
i
and
no pair of g is in µP
i
. This is very close to
2
, as defined in Formulas 9.3. The
difference between
G
(s
0
, p) and
0
is that
2
counts each action individually with
a cost of 1, because it is a state-space distance, whereas
G
(s
0
, g ) counts all the
independent actions of a layer with a total cost of 1.
It is simple to modify Formulas 9.3 to get exactly the distance estimates
G
(s
0
, g )
defined from the planning-graph structure. We modify the second equation to state
that a pair (p, q) is reachable in one step if either there is a single action achieving ...