Residual-Guided Look-Ahead in AND/OR Search for Graphical Models

We introduce the concept of local bucket error for the mini-bucket heuristics and show how it can be used to improve the power of AND/OR search for combinatorial optimization tasks in graphical models (e.g. MAP/MPE or weighted CSPs). The local bucket error illuminates how the heuristic errors are di...

Full description

Saved in:
Bibliographic Details
Published in:The Journal of artificial intelligence research 2017-10, Vol.60, p.287-346
Main Authors: Lam, William, Kask, Kalev, Larrosa, Javier, Dechter, Rina
Format: Article
Language:English
Subjects:
Artificial intelligence
Combinatorial analysis
Combinatorial optimization
Empirical analysis
Exact solutions
Graphic methods
Heuristic
Informàtica
Informàtica teòrica
Luminance distribution
Mètodes gràfics
Optimització combinatòria
Optimization
Searching
Àrees temàtiques de la UPC
Citations: Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We introduce the concept of local bucket error for the mini-bucket heuristics and show how it can be used to improve the power of AND/OR search for combinatorial optimization tasks in graphical models (e.g. MAP/MPE or weighted CSPs). The local bucket error illuminates how the heuristic errors are distributed in the search space, guided by the mini-bucket heuristic. We present and analyze methods for compiling the local bucket-errors (exactly and approximately) and show that they can be used to yield an effective tool for balancing look-ahead overhead during search. This can be especially instrumental when memory is restricted, accommodating the generation of only weak compiled heuristics. We illustrate the impact of the proposed schemes in an extensive empirical evaluation for both finding exact solutions and anytime suboptimal solutions.
ISSN:1076-9757
1076-9757
1943-5037
DOI:10.1613/jair.5475