Probably Approximately Correct Heuristic Search

Proceedings of the International Symposium on Combinatorial Search, 4

Volume

Vol. 4 No. 1 (2011): Fourth Annual Symposium on Combinatorial Search

Full Papers

A* is a best-first search algorithm that returns an optimal solution. w-admissible algorithms guarantee that the returned solution is no larger than w times the optimal solution. In this paper we introduce a generalization of the w-admissibility concept that we call PAC search, which is inspired by the PAC learning framework in Machine Learning. The task of a PAC search algorithm is to find a solution that is w-admissible with high probability. In this paper we formally define PAC search, and present a framework for PAC search algorithms that can work on top of any search algorithm that produces a sequence of solutions. Experimental results on the 15-puzzle demonstrate that our framework activated on top of Anytime Weighted A* (AWA*) expands significantly less nodes than regular AWA* while returning solutions that have almost the same quality.

10.1609/socs.v2i1.18207