Subproblem Ordering Heuristics for AND/OR Best-First Search

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 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.