Mutex conditions

During the construction of the planning graph, information about the conflict between operators and literals within a layer is maintained. A conflict is called a mutex condition, which means that a pair of literals2.4 or pair of operators is mutually exclusive. Both cannot be chosen simultaneously without leading to some kind of conflict. A pair in conflict is called mutex. For each layer, a mutex relation is defined that indicates which pairs satisfy the mutex condition. A pair, $ o,o' \in
O_i$, of operators is defined to be mutex if any of these conditions is met:

  1. Inconsistent effects: An effect of $ o$ is the negated literal of an effect of $ o'$.
  2. Interference: An effect of $ o$ is the negated literal of a precondition of $ o'$.
  3. Competing needs: A pair of preconditions, one from each of $ o$ and $ o'$, are mutex in $ L_i$.
The last condition relies on the definition of mutex for literals, which is presented next. Any pair, $ l,l' \in L_i$, of literals is defined to be mutex if at least one of the two conditions is met:
  1. Negated literals: $ l$ and $ l'$ form a complementary pair.
  2. Inconsistent support: Every pair of operators, $ o,o' \in
O_{i-1}$, that achieve $ l$ and $ l'$ is mutex. In this case, one operator must achieve $ l$, and the other must achieve $ l'$. If there exists an operator that achieves both, then this condition is false, regardless of the other pairs of operators.
The mutex definition depends on the layers; therefore, it is computed layer by layer during the planning graph construction.

Figure 2.20: The planning graph for the flashlight example. The unlabeled operator vertices correspond to trivial operators. For clarity, the operator and literal names are abbreviated.
\begin{figure}\centerline{\psfig{figure=figs/plangraph,width=\columnwidth} }\end{figure}

Example 2..8 (The Planning Graph for the Flashlight)   Figure 2.20 shows the planning graph for Example 2.6. In the first layer, $ L_1$ expresses the initial state. The only applicable operator is $ RemoveCap$. The operator layer $ O_1$ contains $ RemoveCap$ and three trivial operators, which are needed to maintain the literals from $ L_1$. The appearance of $ \neg
On(Cap,Flashlight)$ enables the battery-insertion operator to apply. Since variables are not allowed in operator definitions in a planning graph, two different operators (labeled as $ I1$ and $ I2$) appear, one for each battery. Notice the edges drawn to $ I1$ and $ I2$ from their preconditions. The cap may also be replaced; hence, $ PlaceCap$ is included in $ O_2$. At the $ L_3$ layer, all possible literals have been obtained. At $ O_3$, all possible operators, including the trivial ones, are included. Finally, $ L_4 = L_3$, and $ O_4$ will be the same as $ O_3$. This implies that the planning graph has stabilized. $ \blacksquare$

Steven M LaValle 2012-04-20