How to Relax a Bisimulation? - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2012

How to Relax a Bisimulation?

Résumé

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.
Fichier principal
Vignette du fichier
RR-7901.pdf (261.01 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-00677299 , version 1 (09-03-2012)

Identifiants

  • HAL Id : hal-00677299 , version 1

Citer

Michael Katz, Joerg Hoffmann, Malte Helmert. How to Relax a Bisimulation?. [Research Report] RR-7901, INRIA. 2012. ⟨hal-00677299⟩
172 Consultations
98 Téléchargements

Partager

Gmail Facebook X LinkedIn More