The planning graph is constructed layer by layer, starting from .
In the first stage, represents the initial state. Every
positive literal in is placed into , along with the negation
of every positive literal not in . Now consider stage . The
set is the set of all operators for which their preconditions
are a subset of . The set is the union of the effects
of all operators in . The iterations continue until the planning
graph stabilizes, which means that
and
. This situation is very similar to the stabilization of value
iterations in Section 2.3.2. A trick similar to the
termination action, , is needed even here so that plans of
various lengths are properly handled. In Section 2.3.2, one
job of the termination action was to prevent state transitions from
occurring. The same idea is needed here. For each possible literal,
, a *trivial operator* is constructed for which is the only
precondition and effect. The introduction of trivial operators
ensures that once a literal is reached, it is maintained in the
planning graph for every subsequent layer of literals. Thus, each
may contain some trivial operators, in addition to operators
from the initially given set . These are required to ensure that
the planning graph expansion reaches a steady state, in which the
planning graph is identical for all future expansions.

Steven M LaValle 2012-04-20