On Computational Complexity of Automorphism Groups in Classical Planning

Authors

  • Alexander Shleyfman Technion - Israel Institute of Technology

Abstract

Symmetry-based pruning is a family of powerful methods for reducing search effort in planning as heuristic search. Applying these methods requires first establishing an automorphism group that is then used for pruning within the search process. Despite the growing popularity of state-space symmetries in planning techniques, the computational complexity of finding the automorphism group of a compactly represented planning task has not been formally established. In a series of reductions, we show that computing the automorphism group of a grounded planning task is GI-hard. Furthermore, we discuss the presentations of these symmetry groups and list some of their drawbacks.

Downloads

Published

2021-05-25

How to Cite

Shleyfman, A. (2021). On Computational Complexity of Automorphism Groups in Classical Planning. Proceedings of the International Conference on Automated Planning and Scheduling, 29(1), 428-436. Retrieved from https://ojs.aaai.org/index.php/ICAPS/article/view/3507