Factored Symmetries for Merge-and-Shrink Abstractions
Abstract
Merge-and-shrink heuristics crucially rely on effective reduction techniques, such as bisimulation-based shrinking, to avoid the combinatorial explosion of abstractions. We propose the concept of factored symmetries for merge-and-shrink abstractions based on the established concept of symmetry reduction for state-space search. We investigate under which conditions factored symmetry reduction yields perfect heuristics and discuss the relationship to bisimulation. We also devise practical merging strategies based on this concept and experimentally validate their utility.
Cite
Text
Sievers et al. "Factored Symmetries for Merge-and-Shrink Abstractions." AAAI Conference on Artificial Intelligence, 2015. doi:10.1609/AAAI.V29I1.9642Markdown
[Sievers et al. "Factored Symmetries for Merge-and-Shrink Abstractions." AAAI Conference on Artificial Intelligence, 2015.](https://mlanthology.org/aaai/2015/sievers2015aaai-factored/) doi:10.1609/AAAI.V29I1.9642BibTeX
@inproceedings{sievers2015aaai-factored,
title = {{Factored Symmetries for Merge-and-Shrink Abstractions}},
author = {Sievers, Silvan and Wehrle, Martin and Helmert, Malte and Shleyfman, Alexander and Katz, Michael},
booktitle = {AAAI Conference on Artificial Intelligence},
year = {2015},
pages = {3378-3385},
doi = {10.1609/AAAI.V29I1.9642},
url = {https://mlanthology.org/aaai/2015/sievers2015aaai-factored/}
}