Non-Linear Merging Strategies for Merge-and-Shrink Based on Variable Interactions


  • Gaojian Fan University of Alberta
  • Martin Müller University of Alberta
  • Robert Holte University of Alberta


optimal planning, merge-and-shrink, non-liner merging


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. Experiment results show that our merging strategies outperform existing merging strategies in general and can produce heuristics that give perfect guidance for solving tasks that previous methods cannot even solve.