AAAI Publications, Twelfth Annual Symposium on Combinatorial Search

Font Size: 
Revisiting Suboptimal Search
Jingwei Chen, Nathan R. Sturtevant, William Doyle, Wheeler Ruml

Last modified: 2019-07-05


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.

Full Text: PDF