Mutexes

Mutexes are used to help determine when a belief state is unreachable. Mutexes improve the pruning power of heuristics by accounting for negative interactions. The mutexes are only used to improve our heuristics, so it is reasonable to compute only a subset of the mutexes. We would like to know which mutexes are the most cost effective because the number of possible mutexes we can find is quite large.

We can use several schemes to compute a subset of the mutexes. The schemes combine different types of mutexes with types of cross-world checking. The mutex types are: computing no mutexes (NX), computing only static interference mutexes (StX), computing (StX) plus inconsistent support and competing needs mutexes - dynamic mutexes (DyX), and computing (DyX) plus induced mutexes - full mutexes (FX). The cross-world checking (see appendix B) reduction schemes are: computing mutexes across same-worlds (SX) and computing mutexes across pairs of worlds in the intersection (conjunction) of element labels (IX).

Table 4: Results for CAltAlt using $h^{LUG}_{RP}$ with mutex schemes. The data is Graph Construction Time (ms)/All Other Time (ms)/# Expanded Nodes, ``TO'' indicates a time out (20 minutes) and ``-'' indicates no attempt.

Table 4 shows that within CAltAlt, using the relaxed plan heuristic and changing the way we compute mutexes on the $LUG$ can drastically alter performance. Often, the cross-world mutexes are so numerous that building the $LUG$ takes too much time. To see if we could reduce graph construction overhead without hindering performance, we evaluated $h_{RP}^{LUG}$ when the LUG is built (a) considering all cross-world relations, for the schemes (NX), (StX), (DyX), and (FX); and (b) same-world relations for the schemes (DyX-SX) and (FX-SX), and (c) cross-world relations for all possible worlds pairs in the intersection of element's labels (DyX-IX) and (FX-IX).

The results show that simpler problems like BT and BTC do not benefit as much from advanced computation of mutexes beyond static interference. However, for the Rovers and Logistics problems, advanced mutexes play a larger role. Mainly, interference, competing needs, and inconsistent support mutexes are important. The competing needs and inconsistent support mutexes seem to have a large impact on the informedness of the guidance given by the $LUG$ , as scalability improves most here. Induced mutexes don't improve search time much, and only add to graph computation time. A possible reason induced mutexes don't help as much in these domains is that all the actions have at most two effects, an unconditional and conditional effect. Reducing cross-world mutex checking also helps quite a bit. It seems that only checking same-world mutexes is sufficient to solve large problems. Interestingly, the $MG$ graphs compute same-world interference, competing needs, and inconsistent support mutexes within each graph, equating to the same scenario as (DyX-SX), however, the LUG provides a much faster construction time, evidenced by the $LUG$ 's ability to out-scale $MG$ .