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.