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:
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