Heuristic Search as Evidential Reasoning
This work addresses the problem of computational efficiency in heuristic search for AI researchers, presenting a novel method that is not incremental but offers a new approach to resource-constrained problem-solving.
The paper tackles the problem of improving heuristic search efficiency by introducing BPS, a Bayesian Problem Solver that uses probabilistic inference and decision-theoretic control. The result shows that BPS outperforms traditional techniques with significantly less computational effort, achieving better decisions after only a few hundred node expansions compared to millions for the best existing algorithm on the Eight Puzzle.
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