Planning graph definition

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:

$$(L_1,O_1,L_2,O_2,L_3,O_3,\ldots,L_k,O_k,L_{k+1}) .$$ (2.30)

The edges are defined as follows. To each operator $o_i \in O_i$, a directed edge is made from each $l_i \in L_i$ that is a precondition of $o_i$. To each literal $l_i \in L_i$, an edge is made from each operator $o_{i-1} \in O_{i-1}$ that has $l_i$ 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.