R236
Residual-Guided Look-Ahead in AND/OR Search for Graphical Models
William Lam, Kalev Kask, Javier Larrosa, and Rina Dechter

Abstract
We introduce the notion of local bucket error in mini-bucket heuristics and use this to push the power of AND/OR search for combinatorial optimization tasks in graphical models (e.g. MAP/MPE or weighted CSPs). The local bucket error gives an understanding of how errors are distributed in the search space guided by the mini-bucket heuristic. This is instrumental in making the classic method of look-ahead cost-effective in improving the heuristic. We provide a framework for look-ahead and empirically show that it is cost-effective in improving the current state-of-the-art mini-bucket heuristic, especially when memory is restricted, for both evaluating exact solutions and for generating anytime solutions.

[pdf]