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:
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.