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:
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
- Inconsistent effects: An effect of is the negated
literal of an effect of .
- Interference: An effect of is the negated literal
of a precondition of .
- Competing needs: A pair of preconditions, one from each
of and , are mutex in .
The mutex definition depends on the layers; therefore, it is computed
layer by layer during the planning graph construction.
- Negated literals: and form a complementary pair.
- 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 planning graph for the flashlight
example. The unlabeled operator vertices correspond to trivial
operators. For clarity, the operator and literal names are
(The Planning Graph for the Flashlight)
shows the planning graph for Example
. In the first layer,
expresses the initial
state. The only applicable operator is
. The operator
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
appear, one for each battery. Notice the edges drawn to
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,
will be the same as
. This implies that the planning graph
Steven M LaValle