R232
On the Impact of Subproblem Orderings on Anytime AND/OR Best-First Search for Lower Bounds
William Lam, Kalev Kask, Rina Dechter, and Javier Larrosa

Abstract
Best-first search can be regarded as an anytime scheme for producing lower bounds on the optimal solution, a characteristic that is mostly overlooked. In this paper we explore this topic in the context of AND/OR best-first search, guided by the mini-bucket heuristic, when solving graphical models. In that context, the impact of the secondary heuristic for subproblem ordering becomes apparent, especially when viewed in the anytime context. Specifically, we show how the concept of bucket errors, introduced recently, can yield effective subproblem orderings in AND/OR search and that it is often superior to the baseline approach which uses the same heuristic for node selection (OR nodes) and for subproblem orderings (AND nodes). Our experiments show an improvement in performance both for proving optimality and also in the anytime performance.

[pdf]