Non-Linear Merging Strategies for Merge-and-Shrink Based on Variable Interactions
- Gaojian Fan
- Martin Müller
- Robert Holte, Department of Computing Science, University of Alberta
Merge-and-shrink is a general method for deriving accurate abstraction heuristics. We present two novel nonlinear merging strategies, UMC and MIASM, based on variable interaction. The principle underlying our methods is to merge strongly interacting variables early on. UMC measures variable interaction by weighted causal graph edges, and MIASM measures variable interaction in terms of the number of necessary states in the abstract space defined by the variables. The methods partition variables into clusters in which the variable interactions are strong, and merge variables within each cluster before merging the clusters. Our experimental results show that our new merging strategies often produce better heuristics in terms of the number of nodes expanded by A∗ . On certain IPC benchmark domains, tasks that cannot be solved by existing methods can be solved with minimum search effort using the heuristics created by our methods.
Citation
G. Fan, M. Müller, R. Holte. "Non-Linear Merging Strategies for Merge-and-Shrink Based on Variable Interactions". Symposium on Combinatorial Search, (ed: Stefan Edelkamp, Roman Barták:), pp 53-61, August 2014.| Keywords: | |
| Category: | In Conference |
| Web Links: | AAAI |
BibTeX
@incollection{Fan+al:SoCS14,
author = {Gaojian Fan and Martin Müller and Robert Holte},
title = {Non-Linear Merging Strategies for Merge-and-Shrink Based on Variable
Interactions},
Editor = {Stefan Edelkamp, Roman Barták:},
Pages = {53-61},
booktitle = {Symposium on Combinatorial Search},
year = 2014,
}Last Updated: June 30, 2020Submitted by Sabina P
