Layer-by-layer construction

The planning graph is constructed layer by layer, starting from $L_1$. In the first stage, $L_1$ represents the initial state. Every positive literal in $S$ is placed into $L_1$, along with the negation of every positive literal not in $S$. Now consider stage $i$. The set $O_i$ is the set of all operators for which their preconditions are a subset of $L_i$. The set $L_{i+1}$ is the union of the effects of all operators in $O_i$. The iterations continue until the planning graph stabilizes, which means that $O_{i+1} = O_i$ and $L_{i+1} = L_i$. This situation is very similar to the stabilization of value iterations in Section 2.3.2. A trick similar to the termination action, $u_T$, 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, $l$, a trivial operator is constructed for which $l$ 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 $O_i$ may contain some trivial operators, in addition to operators from the initially given set $O$. 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.