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, , of operators is defined to be mutex if any of these conditions is met:

1. Inconsistent effects: An effect of is the negated literal of an effect of .
2. Interference: An effect of is the negated literal of a precondition of .
3. Competing needs: A pair of preconditions, one from each of and , are mutex in .
The last condition relies on the definition of mutex for literals, which is presented next. Any pair, , of literals is defined to be mutex if at least one of the two conditions is met:
1. Negated literals: and form a complementary pair.
2. Inconsistent support: Every pair of operators, , that achieve and is mutex. In this case, one operator must achieve , and the other must achieve . 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.

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

Steven M LaValle 2012-04-20