Revisiting Suboptimal Search

Suboptimal search algorithms can often solve much larger problems than optimal search algorithms, and thus have broad practical use. This paper returns to early algorithms like WA*, A*_e and Optimistic search. It studies the commonalities between these approaches in order to build a new bounded-suboptimal algorithm. Combined with recent research on avoiding node re-expansions in bounded-optimal search, a new solution quality bound is developed, which often provides proof of the solution bound much earlier during the search. Put together, these ideas provide a new state-of-the-art in bounded-optimal search.