Merge-and-shrink abstraction : a method for generating lower bounds in factored state spaces

Helmert, Malte and Haslum, Patrik and Hoffmann, Joerg and Nissim, Raz. (2014) Merge-and-shrink abstraction : a method for generating lower bounds in factored state spaces. Journal of the ACM, Vol. 61, H. 3 , no. 16. pp. 1-63.

Full text not available from this repository.

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

Downloads: Statistics Overview


Many areas of computer science require answering questions about reachability in compactly described discrete transition systems. Answering such questions effectively requires techniques to be able to do so without building the entire system. In particular, heuristic search uses lower-bounding (``admissible``) heuristic functions to prune parts of the system known to not contain an optimal solution. A prominent technique for deriving such bounds is to consider abstract transition systems that aggregate groups of states into one. The key question is how to design and represent such abstractions. The most successful answer to this question are pattern databases, which aggregate states if and only if they agree on a subset of the state variables. Merge-and-shrink abstraction is a new paradigm that, as we show, allows to compactly represent a more general class of abstractions, strictly dominating pattern databases in theory We identify the maximal class of transition systems, which we call factored transition systems, to which merge-and-shrink applies naturally, and we show that the well-known notion of bisiruilarity can be adapted to this framework in a way that still guarantees perfect heuristic functions, while potentially reducing abstraction size exponentially. Applying these ideas to planning, one of the foundational subareas of artificial intelligence, we show that in some benchmarks this size reduction leads to the computation of perfect heuristic functions in polynomial time and that more approximate merge-and-shrink strategies yield heuristic functions competitive with the state of the art.
Faculties and Departments:05 Faculty of Science > Departement Mathematik und Informatik > Informatik > Artificial Intelligence (Helmert)
UniBasel Contributors:Helmert, Malte
Item Type:Article, refereed
Article Subtype:Research Article
Publisher:ACM Press
Note:Publication type according to Uni Basel Research Database: Journal article
Related URLs:
Identification Number:
Last Modified:08 May 2015 08:45
Deposited On:10 Apr 2015 09:12

Repository Staff Only: item control page