0 citations0 references

The Spurious Path Problem in Abstraction

Proceedings of the International Symposium on Combinatorial Search2021Vol. 6(1), pp. 18–27

Citations Over Time

Abstract

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.

Related Papers

→ The well-tempered semaphore(2002)5 cited
→ The well-tempered semaphore(2002)4 cited
VxWorks Semaphore Applied in Task Synchronization(2004)
→ On implementing semaphores with sets(1979)8 cited
→ Extending synchronization PVM mechanisms(1996)1 cited