AAAI Publications, Seventh Annual Symposium on Combinatorial Search

Font Size: 
Non-Linear Merging Strategies for Merge-and-Shrink Based on Variable Interactions
Gaojian Fan, Martin Müller, Robert Holte

Last modified: 2014-07-02

Abstract


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.

Keywords


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

Full Text: PDF