A mutex pair in a state space is a pair of assignments of values to state variables that does not occur in any reachable state. Detecting mutex pairs is a problem that has been addressed frequently in the planning literature. In this paper, we present the Coarse Abstraction (CA) method, a new efficient method for detecting mutex pairs in state spaces represented with multi-valued variables. CA detects mutex pairs based on exhaustive search in a collection of very small abstract state spaces. While in general CA may miss some mutex pairs, we provide a formal guarantee that CA finds all mutex pairs under a simple and quite natural condition. Using this formal guarantee, we prove that these properties hold for a range of common benchmark domains. We also show that CA can find all mutex pairs even if the formal guarantee is not satisfied. Finally, we show that CA's effectiveness depends on how the domain is represented, and that it can fail to find mutex pairs in some domains and representations.

A popular way to create domain-independent heuristic functions is by using abstraction, where an abstract (coarse) version of the state space is derived from the original state space. An abstraction-based heuristic is usually implemented using a pattern database, a lookup table of (abstract state, heuristic value) pairs. Efficient representation and compression of pattern databases has been the topic of substantial ongoing research. In this paper, we present a novel domain-independent algorithm for this purpose using acyclic r-partite random hypergraphs. The theoretical and experimental results show that our proposed algorithm provides a consistent representation that works well across planning problem domains and provides a good trade-off between space usage and lookup time. Thus, it is suitable to be a standard efficient representation for pattern databases and a benchmark method for other pattern database representation/compression methods.