  The efficient solution of state space search problems is often attempted by
guiding search algorithms with heuristics (estimates of the distance from any
state to the goal). A popular way for creating heuristic functions is by using
an abstract version of the state space. However, the quality of
abstraction-based heuristic functions, and thus the speed of search, can suffer
from spurious transitions, i.e., state transitions in the abstract state space
for which no corresponding transitions in the reachable component of the
original state space exist. Our first contribution is a quantitative study
demonstrating that the harmful effects of spurious transitions on heuristic
functions can be substantial, in terms of both the increase in the number of
abstract states and the decrease in the heuristic values, which may slow down
search. Our second contribution is an empirical study on the benefits of
removing a certain kind of spurious transition, namely those that involve
states with a pair of mutually exclusive (mutex) variablevalue assignments. In
the context of state space planning, a mutex pair is a pair of variable-value
assignments that does not occur in any reachable state. Detecting mutex pairs
is a problem that has been addressed frequently in the planning literature. Our
study shows that there are cases in which mutex detection helps to eliminate
harmful spurious transitions to a large extent and thus to speed up search
substantially.
