How to Relax a Bisimulation?


  • Michael Katz Saarland University
  • Joerg Hoffmann Saarland University
  • Malte Helmert University of Basel



Planning, Heuristic Search, Abstractions


Merge-and-shrink abstraction (M&S) is an approach for constructing admissible heuristic functions for cost-optimal planning. It enables the targeted design of abstractions, by allowing to choose individual pairs of (abstract) states to aggregate into one. A key question is how to actually make these choices, so as to obtain an informed heuristic at reasonable computational cost. Recent work has addressed this via the well-known notion of bisimulation. When aggregating only bisimilar states -- essentially, states whose behavior is identical under every planning operator -- M&S yields a perfect heuristic. However, bisimulations are typically exponentially large. Thus we must relax the bisimulation criterion, so that it applies to more state pairs, and yields smaller abstractions. We herein devise a fine-grained method for doing so. We restrict the bisimulation criterion to consider only a subset K of the planning operators. We show that, if K is chosen appropriately, then M&S still yields a perfect heuristic, while abstraction size may decrease exponentially. Designing practical approximations for K, we obtain M&S heuristics that are competitive with the state of the art.




How to Cite

Katz, M., Hoffmann, J., & Helmert, M. (2012). How to Relax a Bisimulation?. Proceedings of the International Conference on Automated Planning and Scheduling, 22(1), 101-109.