Skip to Main content Skip to Navigation
Conference papers

How to Relax a Bisimulation?

Michael Katz 1 Joerg Hoffmann 1, 2 Malte Helmert 3
1 MAIA - Autonomous intelligent machine
Inria Nancy - Grand Est, LORIA - AIS - Department of Complex Systems, Artificial Intelligence & Robotics
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&S 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.
Document type :
Conference papers
Complete list of metadata

Cited literature [12 references]  Display  Hide  Download

https://hal.inria.fr/hal-00765027
Contributor : Olivier Buffet <>
Submitted on : Friday, December 14, 2012 - 9:15:02 AM
Last modification on : Tuesday, December 18, 2018 - 4:40:21 PM
Long-term archiving on: : Friday, March 15, 2013 - 3:45:25 AM

File

icaps12b.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00765027, version 1

Collections

Citation

Michael Katz, Joerg Hoffmann, Malte Helmert. How to Relax a Bisimulation?. 22nd International Conference on Automated Planning and Scheduling (ICAPS), Jun 2012, Atibaia, Brazil. ⟨hal-00765027⟩

Share

Metrics

Record views

249

Files downloads

251