Heuristic Search as Evidential Reasoning
  BPS, the Bayesian Problem Solver, applies probabilistic inference and
decision-theoretic control to flexible, resource-constrained problem-solving.
This paper focuses on the Bayesian inference mechanism in BPS, and contrasts it
with those of traditional heuristic search techniques. By performing sound
inference, BPS can outperform traditional techniques with significantly less
computational effort. Empirical tests on the Eight Puzzle show that after only
a few hundred node expansions, BPS makes better decisions than does the best
existing algorithm after several million node expansions
