next up previous
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 $ x$ in possible world $ S$ is mutex with $ x'$ in possible world $ S'$ , we denote the mutex as the pair ( $ \hat{\ell}_k(x) = S, \hat{\ell}_k(x') = S'$ ).

We can compute cross-world mutexes between several worlds of elements $ x$ and $ x'$ . For example, if $ \ell_k(x) = S_1 \vee S_2
\vee S_3$ and $ \ell_k(x') = S_2 \vee S_3$ , then to check for all cross-world mutexes we need to consider mutexes for the world pairs $ (S_1, S_2), (S_1, S_3), (S_2, S_2), (S_2, S_3), (S_3, S_2)$ , and $ (S_3, S_3)$ . We can also check for mutexes in the intersection of the element labels $ \ell_k(x) \wedge \ell_k(x') = S_2 \vee S_3$ , meaning the only cross world pairs we check for mutexes are $ (S_2,
S_2), (S_2, S_3), (S_3, S_2)$ , and $ (S_3, S_3)$ .

We can say that a formula $ f$ is reachable from our projected belief state $ BS_P$ , when considering cross-world mutexes, if for every pair of states in $ BS_P$ , $ f$ is reachable. For a pair of states $ S$ and $ S'$ , $ f$ is reachable if $ S \wedge S' \models \ell_k^*(f)$ and for every pair of constituents $ \hat{S''}, \hat{S'''} \in
\hat{f}$ such that $ S \models \ell_k^*(\hat{S''})$ and $ S' \models
\ell_k^*(\hat{S'''})$ , there are no two literals in either $ \hat{S''}$ or $ \hat{S'''}$ that are same-world mutex when $ S = S'$ , and there is not a mutex between literals in $ \hat{S''}$ and $ \hat{S'''}$ , across the respective worlds $ S$ and $ S'$ when $ S \neq
S'$ . There is a mutex between a pair literals $ l$ and $ l'$ , respectively from $ \hat{S''}$ and $ \hat{S'''}$ if there is a mutex $ (\hat{\ell}_k(l), \hat{\ell}_k(l'))$ such that $ S \models
\hat{\ell}_k(l)$ and $ S' \models \hat{\ell}_k(l')$ .

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 $ S$ , all pairs of possible worlds $ S$ and $ S'$ for mutexes.


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


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


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


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