Factored Symmetries for Merge-and-Shrink Abstractions

Authors

  • Silvan Sievers University of Basel
  • Martin Wehrle University of Basel
  • Malte Helmert University of Basel
  • Alexander Shleyfman Technion, Haifa
  • Michael Katz IBM Haifa Research Lab

DOI:

https://doi.org/10.1609/aaai.v29i1.9642

Keywords:

merge-and-shrink heuristics, symmetries, heuristic search, abstraction heuristics

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.

Downloads

Published

2015-03-04

How to Cite

Sievers, S., Wehrle, M., Helmert, M., Shleyfman, A., & Katz, M. (2015). Factored Symmetries for Merge-and-Shrink Abstractions. Proceedings of the AAAI Conference on Artificial Intelligence, 29(1). https://doi.org/10.1609/aaai.v29i1.9642