AAAI Publications, Tenth Symposium of Abstraction, Reformulation, and Approximation

Font Size: 
Using Coarse State Space Abstractions to Detect Mutex Pairs
Mehdi Sadeqi, Robert C. Holte, Sandra Zilles

Last modified: 2013-06-19

Abstract


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.

Full Text: PDF