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

Proceedings of the International Symposium on Combinatorial Search, 8

Volume

Vol. 8 No. 1 (2015): Eighth Annual Symposium on Combinatorial Search

Full Papers

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.

10.1609/socs.v6i1.18353