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.

• Interference Interference mutexes do not change for cross-world mutexes, except that there is a pair of labels where ( $\hat{\ell}_k(a) = BS_P, \hat{\ell}_k(a') = BS_P$ ), instead of a single label.

• Competing Needs Competing needs change mutexes for cross-world mutexes because two actions $a$ and $a'$ , in worlds $S$ and $S'$ respectively, could be competing. Formally, a cross-world competing needs mutex ( $(\hat{\ell}_k(a) = S, \hat{\ell}_k(a') = S'$ ) exists between $a$ and $a'$ in worlds $S$ and $S'$ if:

  $$\exists_{l \in \rho^e(a), l' \in \rho^e(a')} (\hat{\ell}_k(l)=S, \hat{\ell}_k(l')=S')$$

  
  
  
  

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 ( $\hat{\ell}_k( \varphi^i(a)) = BS_P, \hat{\ell}_k(\varphi^j(a')) = BS_P$ ), instead of a single label.
• Competing Needs Effect competing needs mutexes change for cross-world mutexes because two effects $\varphi^i(a)$ and $\varphi^j(a')$ , in worlds $S$ and $S'$ respectively, could be competing. Formally, a cross-world competing needs mutex ( $\hat{\ell}_k(\varphi^i(a)) = S, \hat{\ell}_k(\varphi^j(a')) = S'$ ) exists between $\varphi^i(a)$ and $\varphi^j(a')$ in worlds $S$ and $S'$ if:

  $$\exists_{l \in \rho^i(a), l' \in \rho^j(a')} (\hat{\ell}_k(l)=S, \hat{\ell}_k(l')=S')$$

  
  
  
  
• 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 $\varphi^j(a)$ in $\hat{\ell}_k(\varphi^j(a))$ is mutex with $\varphi^{h}(a')$ in $\hat{\ell}_k(\varphi^h(a'))$ , and $\varphi^i(a)$ induces effect $\varphi^j(a)$ in the possible worlds described by $\ell_k(\varphi^i(a)) \wedge \ell_k(\varphi^j(a))$ , then there is an induced mutex between $\varphi^i(a)$ in $\hat{\ell_k}(\varphi^j(a)) \wedge \ell_k(\varphi^i(a))$ and $\varphi^h(a')$ in $\hat{\ell_k}(\varphi^{h}(a'))$ (see Figure 12).

  Figure 12: Example of a cross-world induced effect mutex.

  

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 ( $\hat{\ell}_k(l) = S, \hat{\ell}_k(l') = S'$ ) holds for $l$ in $S$ and $l'$ in $S'$ if $\forall \varphi^i(a), \varphi^j(a') \in {\cal E}_{k-1}$ where $l \in \varepsilon^i(a), l' \in \varepsilon^j(a')$ , there is a mutex $\hat{\ell}_{k-1}(\varphi^i(a)) = S, \hat{\ell}_{k-1}(\varphi^j(a')) = S')$ .