Weighted best first search for MAP

Abstract

The paper considers Weighted Best First (WBF) search schemes, popular for path-finding domain, as approximations and as anytime schemes for the MAP task. We demonstrate empirically the ability of these schemes to effectively provide approximations with guaranteed suboptimality and also show that as anytime schemes they can be competitive on some benchmarks with one of the best state-of-the-art scheme, Depth-First Branch-and-Bound.