edoc

Computing perfect heuristics in polynomial time : on bisimulation and merge-and-shrink abstractions in optimal planning

Nissim, Raz and Hoffmann, Jörg and Helmert, Malte. (2011) Computing perfect heuristics in polynomial time : on bisimulation and merge-and-shrink abstractions in optimal planning. In: Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence (IJCAI 2011). Menlo Park (Calif.), pp. 1983-1990.

[img]
Preview
PDF - Published Version
682Kb

Official URL: http://edoc.unibas.ch/dok/A6002665

Downloads: Statistics Overview

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.
Faculties and Departments:05 Faculty of Science > Departement Mathematik und Informatik > Informatik > Artificial Intelligence (Helmert)
UniBasel Contributors:Helmert, Malte
Item Type:Conference or Workshop Item, refereed
Conference or workshop item Subtype:Conference Paper
Bibsysno:Link to catalogue
Publisher:IJCAI/AAAI
Note:Publication type according to Uni Basel Research Database: Conference paper
Language:English
Related URLs:
Identification Number:
Last Modified:19 Nov 2018 16:43
Deposited On:13 Sep 2013 07:50

Repository Staff Only: item control page