Computational Complexity of Symmetry Identification in Finite-Domain Planning
Keywords:
Symmetry identification, finite-domain planning, algorithm analysis, symmetry breakingAbstract
Symmetry identification plays a crucial role in enhancing the efficiency of planning algorithms by reducing redundant computations. In this paper, we investigate the computational complexity of identifying symmetries in finite-domain planning problems. We analyze various algorithms and their complexity in terms of time and space requirements, focusing on both theoretical bounds and practical implications. Our findings highlight the challenges and opportunities in leveraging symmetry for optimizing planning processes.
References
Blum, A.L. and Furst, M.L., 1997. Fast planning through planning graph analysis. Artificial Intelligence, 90(1-2), pp.281-300.
Hoffmann, J. and Nebel, B., 2001. The FF planning system: Fast plan generation through heuristic search. Journal of Artificial Intelligence Research, 14, pp.253-302.
Edelkamp, S. and Helmert, M., 2001. Planning with pattern databases. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI) (Vol. 17, No. 1, pp. 635-642).
Published
Issue
Section
License
Copyright (c) 2021 MUKTAR (Author)
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
