Subproblem ordering heuristics for AND/OR best-first search

Best-first search can be regarded as anytime scheme for producing lower bounds on the optimal solution, a characteristic that is mostly overlooked. We explore this topic in the context of AND/OR best-first search, guided by the MBE heuristic, when solving graphical models. In that context, the impac...

Full description

Saved in:
Bibliographic Details
Published in:Journal of computer and system sciences 2018-06, Vol.94, p.41-62
Main Authors: Lam, William, Kask, Kalev, Larrosa, Javier, Dechter, Rina
Format: Article
Language:English
Subjects:
Artificial intelligence
Combinatorial optimization
Graphic methods
Graphical models
Heuristic search
Informàtica
Intel·ligència artificial
Mètodes gràfics
Optimització combinatòria
Àrees temàtiques de la UPC
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Best-first search can be regarded as anytime scheme for producing lower bounds on the optimal solution, a characteristic that is mostly overlooked. We explore this topic in the context of AND/OR best-first search, guided by the MBE heuristic, when solving graphical models. In that context, the impact of the secondary heuristic for subproblem ordering may be significant, especially in the anytime context. Indeed, our paper illustrates this, showing that a new concept of bucket errors can advise in providing effective subproblem orderings in AND/OR search for both exact and anytime solutions. •Subproblem ordering impacts the performance of AND/OR Best-First search.•Look-ahead (and thus MBE bucket errors) can be used to guide subproblem ordering.•Several schemes to approximate bucket errors are proposed to deal with overhead.
ISSN:0022-0000
1090-2724
DOI:10.1016/j.jcss.2017.10.003