How to Relax a Bisimulation?

Michael Katz 1 Joerg Hoffmann 1, 2 Malte Helmert 3
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 :
Communication dans un congrès
22nd International Conference on Automated Planning and Scheduling (ICAPS), Jun 2012, Atibaia, Brazil. 2012
Liste complète des métadonnées

Littérature citée [12 références]  Voir  Masquer  Télécharger
Contributeur : Olivier Buffet <>
Soumis le : vendredi 14 décembre 2012 - 09:15:02
Dernière modification le : mardi 18 décembre 2018 - 16:40:21
Document(s) archivé(s) le : vendredi 15 mars 2013 - 03:45:25


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


  • HAL Id : hal-00765027, version 1



Michael Katz, Joerg Hoffmann, Malte Helmert. How to Relax a Bisimulation?. 22nd International Conference on Automated Planning and Scheduling (ICAPS), Jun 2012, Atibaia, Brazil. 2012. 〈hal-00765027〉



Consultations de la notice


Téléchargements de fichiers