Computing Perfect Heuristics in Polynomial Time: On Bisimulation and Merge-and-Shrink Abstraction in Optimal Planning

Raz Nissim 1 Joerg Hoffmann 2 Malte Helmert 3
2 MAIA - Autonomous intelligent machine
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : A* with admissible heuristics is a very successful approach to optimal planning. But how to derive such heuristics automatically? Merge-and-shrink abstraction (M&S) is a general approach to heuristic design whose key advantage is its capability to make very fine-grained choices in defining abstractions. However, little is known about how to actually make these choices. We address this via the well-known notion of bisimulation. When aggregating only bisimilar states, M&S yields a perfect heuristic. Alas, bisimulations are exponentially large even in trivial domains. We show how to apply label reduction -- not distinguishing between certain groups of operators -- without incurring any information loss, while potentially reducing bisimulation size exponentially. In several benchmark domains, the resulting algorithm computes perfect heuristics in polynomial time. Empirically, we show that approximating variants of this algorithm improve the state of the art in M&S heuristics. In particular, a simple hybrid of two such variants is competitive with the leading heuristic LM-cut.
Type de document :
Communication dans un congrès
22nd International Joint Conference on Artificial Intelligence (IJCAI'11), Jul 2011, Barcelona, Spain. 2011
Liste complète des métadonnées

Littérature citée [3 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00592438
Contributeur : Joerg Hoffmann <>
Soumis le : jeudi 12 mai 2011 - 15:31:00
Dernière modification le : samedi 17 février 2018 - 17:46:02
Document(s) archivé(s) le : samedi 13 août 2011 - 02:51:37

Fichier

ijcai11.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00592438, version 1

Collections

Citation

Raz Nissim, Joerg Hoffmann, Malte Helmert. Computing Perfect Heuristics in Polynomial Time: On Bisimulation and Merge-and-Shrink Abstraction in Optimal Planning. 22nd International Joint Conference on Artificial Intelligence (IJCAI'11), Jul 2011, Barcelona, Spain. 2011. 〈inria-00592438〉

Partager

Métriques

Consultations de la notice

241

Téléchargements de fichiers

194