The Spurious Path Problem in Abstraction

Proceedings of the International Symposium on Combinatorial Search, 8

Volume

Vol. 8 No. 1 (2015): Eighth Annual Symposium on Combinatorial Search

Full Papers

Abstraction is a powerful technique in search and planning. A fundamental problem of abstraction is that it can create spurious paths, i.e., abstract paths that do not correspond to valid concrete paths. In this paper, we define spurious paths as a generalization of spurious states. We show that spurious paths can be categorized into two types: state-independent spurious paths and state-specific spurious paths. We present a practical method that eliminates state-independent spurious paths, as well as state-specific spurious paths when integrated with mutex detection methods. We provide syntactical conditions under which our method can remove state-independent spurious paths completely. We demonstrate that eliminating spurious paths can improve a heuristic substantially, even in abstract spaces that are free of spurious states.

10.1609/socs.v6i1.18356