Revisiting Suboptimal Search
Full Text: 18324-78943-1-PB.pdf
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.
Citation
J. Chen, N. Sturtevant, W. Doyle, W. Ruml. "Revisiting Suboptimal Search". Symposium on Combinatorial Search, (ed: Pavel Surynek, William Yeoh), pp 18-25, July 2019.| Keywords: | |
| Category: | In Conference |
| Web Links: | AAAI |
BibTeX
@incollection{Chen+al:SoCS19,
author = {Jingwei Chen and Nathan R. Sturtevant and William J. Doyle and
Wheeler Ruml},
title = {Revisiting Suboptimal Search},
Editor = {Pavel Surynek, William Yeoh},
Pages = {18-25},
booktitle = {Symposium on Combinatorial Search},
year = 2019,
}Last Updated: July 03, 2020Submitted by Sabina P
