Focusing on What Really Matters: Irrelevance Pruning in Merge-and-Shrink

Authors

  • Álvaro Torralba Saarland University
  • Peter Kissmann Saarland University

DOI:

https://doi.org/10.1609/socs.v6i1.18353

Keywords:

merge-and-shrink, irrelevance pruning, simulation relations

Abstract

Merge-and-shrink (M&S) is a framework to generate abstraction heuristics for cost-optimal planning. A recent approach computes simulation relations on a set of M&S abstractions in order to identify states that are better than others. This relation is then used for pruning states in the search when a "better" state is already known. We propose the usage of simulation relations inside the M&S framework in order to detect irrelevant transitions in abstract state spaces. This potentially simplifies the abstraction allowing M&S to derive more informed heuristics. We also tailor M&S to remove irrelevant operators from the planning task. Experimental results show the potential of our approach to construct well-informed heuristics and simplify the planning tasks prior to the search.

Downloads

Published

2021-09-01