edoc

How to relax a bisimulation?

Katz, Michael and Hoffmann, Jörg and Helmert, Malte. (2012) How to relax a bisimulation? In: Proceedings of the 22nd International Conference on Automated Planning and Scheduling (ICAPS 2012). Atibaia, pp. 101-109.

[img]
Preview
PDF - Published Version
170Kb

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

Downloads: Statistics Overview

Abstract

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&SS 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.
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
Publisher:AAAI Press
Note:Publication type according to Uni Basel Research Database: Conference paper
Language:English
Related URLs:
edoc DOI:
Last Modified:19 Nov 2018 14:51
Deposited On:13 Sep 2013 07:57

Repository Staff Only: item control page