Factored symmetries for merge-and-shrink abstractions

Sievers, Silvan and Wehrle, Martin and Helmert, Malte and Shleyfman, Alexander and Katz, Michael. (2015) Factored symmetries for merge-and-shrink abstractions. In: Proceedings of the 29th AAAI Conference on Artificial Intelligence (AAAI 2015) : January 25 –30, 2015, Austin, Texas, USA. Palo Alto, Calif., pp. 3378-3385.

PDF - Published Version

Official URL: http://edoc.unibas.ch/dok/A6373493

Downloads: Statistics Overview


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.
Faculties and Departments:05 Faculty of Science > Departement Mathematik und Informatik > Informatik > Artificial Intelligence (Helmert)
UniBasel Contributors:Sievers, Silvan and Wehrle, Martin and Helmert, Malte
Item Type:Conference or Workshop Item, refereed
Conference or workshop item Subtype:Conference Paper
Publisher:AAAI Press
Note:Publication type according to Uni Basel Research Database: Conference paper
Related URLs:
edoc DOI:
Last Modified:19 Nov 2018 15:22
Deposited On:05 Jun 2015 08:52

Repository Staff Only: item control page