An Atom-Centric Perspective on Stubborn Sets

Proceedings of the International Symposium on Combinatorial Search, 13

Volume

Vol. 13 No. 1 (2020): Thirteenth Annual Symposium on Combinatorial Search

Long Papers

Stubborn sets are an optimality-preserving pruning technique for factored state-space search, for example in classical planning. Their applicability is limited by their computational overhead. We describe a new algorithm for computing stubborn sets that is based on the state variables of the state space, while previous algorithms are based on its actions. Typical factored state spaces tend to have far fewer state variables than actions, and therefore our new algorithm is much more efficient than the previous state of the art, making stubborn sets a viable technique in many cases where they previously were not.

10.1609/socs.v11i1.18535