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 shows that within CAltAlt, using the relaxed plan heuristic and changing the way we compute mutexes on the can drastically alter performance. Often, the cross-world mutexes are so numerous that building the takes too much time. To see if we could reduce graph construction overhead without hindering performance, we evaluated 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 , 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 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 's ability to out-scale .