Next: Bibliography Up: Planning Graph Heuristics for Previous: Labelled Uncertainty Graph (

# Cross-World Mutexes

Mutexes can develop not only in the same possible world but also between two possible worlds, as described by [30]. Cross-world mutexes are useful to capture negative interactions in belief state distance measures (mentioned in Section 3). The representation of cross-world mutexes requires another generalization for the labelling of mutexes. Same world mutexes require keeping only one label for the mutex to signify all same possible worlds for which the mutex holds. The extended representation keeps a pair of labels, one for each element in the mutex; if in possible world is mutex with in possible world , we denote the mutex as the pair ( ).

We can compute cross-world mutexes between several worlds of elements and . For example, if and , then to check for all cross-world mutexes we need to consider mutexes for the world pairs , and . We can also check for mutexes in the intersection of the element labels , meaning the only cross world pairs we check for mutexes are , and .

We can say that a formula is reachable from our projected belief state , when considering cross-world mutexes, if for every pair of states in , is reachable. For a pair of states and , is reachable if and for every pair of constituents such that and , there are no two literals in either or that are same-world mutex when , and there is not a mutex between literals in and , across the respective worlds and when . There is a mutex between a pair literals and , respectively from and if there is a mutex such that and .

The computation of cross-world mutexes requires changes to some of the mutex formulas, as outlined next. The major change is to check, instead of all the single possible worlds , all pairs of possible worlds and for mutexes.

Action Mutexes: The action mutexes can now hold for actions that are executable in different possible worlds.

• Interference Interference mutexes do not change for cross-world mutexes, except that there is a pair of labels where ( ), instead of a single label.

• Competing Needs Competing needs change mutexes for cross-world mutexes because two actions and , in worlds and respectively, could be competing. Formally, a cross-world competing needs mutex ( ) exists between and in worlds and if:

Effect Mutexes: The effect mutexes can now hold for effects that occur in different possible worlds.

• Interference Effect interference mutexes do not change for cross-world mutexes, except that there is a pair of labels where ( ), instead of a single label.
• Competing Needs Effect competing needs mutexes change for cross-world mutexes because two effects and , in worlds and respectively, could be competing. Formally, a cross-world competing needs mutex ( ) exists between and in worlds and if:

• Induced Induced mutexes change slightly for cross-world mutexes. The worlds where one effect induces another, remains the same, but the mutex changes slightly.

If in is mutex with in , and induces effect in the possible worlds described by , then there is an induced mutex between in and in (see Figure 12).

Literal Mutexes: The literal mutexes can now hold for literals that are supported in different possible worlds.

• Inconsistent Support changes for cross-world mutexes. A mutex ( ) holds for in and in if where , there is a mutex .

Next: Bibliography Up: Planning Graph Heuristics for Previous: Labelled Uncertainty Graph (
2006-05-26