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:

$\displaystyle (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.

Steven M LaValle 2012-04-20