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

摘要: 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 to merge strongly interacting variables early on. measures interaction by weighted causal graph edges, MIASM in terms of the number necessary states abstract space defined variables. partition into clusters which interactions are strong, within each cluster before clusters. Our experimental results show that new strategies often produce better heuristics nodes expanded A . On certain IPC benchmark domains, tasks cannot be solved existing can with minimum search effort using created methods.