AAAI Publications, Eighth Annual Symposium on Combinatorial Search

Font Size: 
Empowering Mini-Bucket in Anytime Heuristic Search with Look-Ahead: Preliminary Evaluation
William Lam, Kalev Kask, Rina Dechter

Last modified: 2015-05-18


The paper explores the potential of look-ahead methods within the context of AND/OR search in graphical models using the Mini-Bucket heuristic for combinatorial optimization tasks (e.g., weighted CSPS or MAP inference). We study how these methods can be used to compensate for the approximation error of the initially generated Mini-Bucket heuristics, within the context of anytime Branch-And-Bound search.


graphical models; search; heuristics

Full Text: PDF