Sleep Sets Meet Duplicate Elimination

Proceedings of the International Symposium on Combinatorial Search, 9

Volume

Vol. 9 No. 1 (2016): Ninth Annual Symposium on Combinatorial Search

Long Papers

The sleep sets technique is a path-dependent pruning method for state space search. In the past, the combination of sleep sets with graph search algorithms that perform duplicate elimination has often shown to be error-prone. In this paper, we provide the theoretical basis for the integration of sleep sets with common search algorithms in AI that perform duplicate elimination. Specifically, we investigate approaches to safely integrate sleep sets with optimal (best-first) search algorithms. Based on this theory, we provide an initial step towards integrating sleep sets within A* and additional state pruning techniques like strong stubborn sets. Our experiments show slight, yet consistent improvements on the number of generated search nodes across a large number of standard domains from the international planning competitions.

10.1609/socs.v7i1.18393