On the Expressive Power of Non-Linear Merge-and-Shrink Representations

Authors

  • Malte Helmert University of Basel
  • Gabriele Röger University of Basel
  • Silvan Sievers University of Basel

DOI:

https://doi.org/10.1609/icaps.v25i1.13732

Keywords:

classical planning, merge-and-shrink representations, expressive power

Abstract

We prove that general merge-and-shrink representations are strictly more powerful than linear ones by showing that there exist problem families that can be represented compactly with general merge-and-shrink representations but not with linear ones. We also give a precise bound that quantifies the necessary blowup incurred by conversions from general merge-and-shrink representations to linear representations or BDDs/ADDs. Our theoretical results suggest an untapped potential for non-linear merging strategies and for the use of non-linear merge-and-shrink-like representations within symbolic search.

Downloads

Published

2015-04-08

How to Cite

Helmert, M., Röger, G., & Sievers, S. (2015). On the Expressive Power of Non-Linear Merge-and-Shrink Representations. Proceedings of the International Conference on Automated Planning and Scheduling, 25(1), 106-114. https://doi.org/10.1609/icaps.v25i1.13732