Strengthening Canonical Pattern Databases with Structural Symmetries

Sievers, Silvan and Wehrle, Martin and Helmert, Malte and Katz, Michael. (2017) Strengthening Canonical Pattern Databases with Structural Symmetries. In: Proceedings of the 10th Annual Symposium on Combinatorial Search (SoCS 2017). pp. 91-99.

[img] PDF - Published Version

Official URL: https://edoc.unibas.ch/59279/

Downloads: Statistics Overview


Symmetry-based state space pruning techniques have proved to greatly improve heuristic search based classical planners. Similarly, abstraction heuristics in general and pattern databases in particular are key ingredients of such planners. However, only little work has dealt with how the abstraction heuristics behave under symmetries. In this work, we investigate the symmetry properties of the popular canonical pattern databases heuristic. Exploiting structural symmetries, we strengthen the canonical pattern databases by adding symmetric pattern databases, making the resulting heuristic invariant under structural symmetry, thus making it especially attractive for symmetry-based pruning search methods. Further, we prove that this heuristic is at least as informative as using symmetric lookups over the original heuristic. An experimental evaluation confirms these theoretical results.
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:16 Mar 2018 12:34
Deposited On:16 Mar 2018 12:33

Repository Staff Only: item control page