Sleep Sets Meet Duplicate Elimination

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 du- plicate 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.