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 literals^2.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.

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$