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

Nissim, Raz; Hoffmann, Jörg; Helmert, Malte

doi:10.5591/978-1-57735-516-8/IJCAI11-331

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

Raz Nissim, Jörg Hoffmann, Malte Helmert

Download BibTeX Cite

Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence. Pages 1983-1989.

https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-331

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.

Raz Nissim, Jörg Hoffmann, and Malte Helmert. 2011. Computing Perfect Heuristics in Polynomial Time: On Bisimulation and Merge-and-Shrink Abstraction in Optimal Planning. In Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11. IJCAI, 1983–1989. https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-331

@inproceedings{ijcai2011p331,
  title     = {Computing Perfect Heuristics in Polynomial Time: On Bisimulation and Merge-and-Shrink Abstraction in Optimal Planning},
  author    = {Nissim, Raz and Hoffmann, Jörg and Helmert, Malte},
  booktitle = {Proceedings of the Twenty-Second International Joint Conference on
               Artificial Intelligence, {IJCAI-11}},
  publisher = {AAAI Press/International Joint Conferences on Artificial Intelligence},
  editor    = {Toby Walsh},
  pages     = {1983--1989},
  year      = {2011},
  month     = {7},
  doi       = {10.5591/978-1-57735-516-8/IJCAI11-331},
  url       = {https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-331},
}

TY  - CPAPER
TI  - Computing Perfect Heuristics in Polynomial Time: On Bisimulation and Merge-and-Shrink Abstraction in Optimal Planning
AU  - Nissim, Raz
AU  - Hoffmann, Jörg
AU  - Helmert, Malte
T2  - Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11
PB  - AAAI Press/International Joint Conferences on Artificial Intelligence
PY  - 2011
SP  - 1983
EP  - 1989
DO  - 10.5591/978-1-57735-516-8/IJCAI11-331
UR  - https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-331
ER  -