A *layered graph* is a graph that has its vertices partitioned
into a sequence of *layers*, and its edges are only permitted to
connect vertices between successive layers. The *planning graph*
is a layered graph in which the layers of vertices form an
alternating sequence of literals and operators:

(2.30) |

The edges are defined as follows. To each operator , a directed edge is made from each that is a precondition of . To each literal , an edge is made from each operator that has as an effect.

One important requirement is that no variables are allowed in the operators. Any operator from Formulation 2.4 that contains variables must be converted into a set that contains a distinct copy of the operator for every possible substitution of values for the variables.

Steven M LaValle 2012-04-20