Mutex Pair Detection for Improving Abstraction-based Heuristics

Abstract

Problem solving is a very important aspect of arti cial intelligence. This thesis focuses on problems that can be formulated as search problems in a state space. Since blindly searching in a large state space is usually not enough for solving real world problems, it is required to equip the search algorithms with heuristics (estimates of the distance from any state to the goal) to guide the search. Further, the more accurate the heuristic function the more e cient the heuristic search algorithm will be. A popular way for creating domain-independent heuristic functions is by using abstraction, an abstract (coarse) version of the state space. However, the quality of abstraction-based heuristic functions, and thus the speed of search, can su er 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. In general, two types of harm can be caused by spurious transitions when using abstraction to de ne a heuristic: increasing the number of abstract states and decreasing the quality of the heuristic. Our quantitative study of these harmful e ects con rms that these harms can be quite remarkable, illustrating the importance of avoiding spurious transitions in some way. For this purpose, we need to know that spurious transitions are divided into two categories: those that involve spurious states and those that do not. A spurious state is an abstract state in the abstract state space for which no corresponding state in the reachable component of the original state space exists. While there is no straightforward approach for detecting all spurious transitions, transitions involving spurious states can be detected by nding the spurious states they connect to. To date, there is no feasible method known for detecting all spurious states. The approach we pursue in this work is to identify those spurious states that contain a pair of variable-value assignments that are mutually exclusive (mutex). 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. In an empirical evaluation, we show 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. We propose two mutex detection methods in this work: The Missing Mass Method (MMM) and the Coarse Abstractions method. MMM is based on sampling reachable states. In all the testbeds we experimented with, MMM either works perfectly, i.e., nds all and only the mutex pairs, or it is near-perfect. The Coarse Abstractions method is based on exhaustive search in a collection of very small abstract state spaces. While in general Coarse Abstractions may miss some mutex pairs, we provide a formal guarantee that Coarse Abstractions nds all mutex pairs under a simple and quite natural condition. In the meantime, it is also shown that Coarse Abstractions may nd all mutex pairs even if the formal guarantee is not satis ed. We also provide a condition under which h2, a state-of-the-art mutex detection method, is guaranteed to detect all mutex pairs.