How to Relax a Bisimulation?

Michael Katz 1 Joerg Hoffmann 1 Malte Helmert 2
1 MAIA - Autonomous intelligent machine
Inria Nancy - Grand Est, LORIA - AIS - Department of Complex Systems, Artificial Intelligence & Robotics
Abstract : 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.
Type de document :
[Research Report] RR-7901, INRIA. 2012
Liste complète des métadonnées

Littérature citée [11 références]  Voir  Masquer  Télécharger
Contributeur : Joerg Hoffmann <>
Soumis le : vendredi 9 mars 2012 - 15:07:03
Dernière modification le : jeudi 11 janvier 2018 - 06:25:23
Document(s) archivé(s) le : lundi 26 novembre 2012 - 10:25:50


Fichiers produits par l'(les) auteur(s)


  • HAL Id : hal-00677299, version 1


Michael Katz, Joerg Hoffmann, Malte Helmert. How to Relax a Bisimulation?. [Research Report] RR-7901, INRIA. 2012. 〈hal-00677299〉



Consultations de la notice


Téléchargements de fichiers