Are We There Yet? — Estimating Search Progress

Abstract

Heuristic search is a general problem solving technique. While most evaluations of heuristic search focus on the speed of search, there are relatively few techniques for predicting when search will end. This paper provides a study of progress estimating techniques for optimal, suboptimal, and bounded suboptimal heuristic search algorithms. We examine two previously proposed techniques, search velocity and search vacillation, as well as two new approaches, path-based estimation and distribution-based estimation. We find that both new approaches are better at estimating the remaining amount of search effort than previous work in all three varieties of search, occasionally erring by less than 5%.