New Results in Bounded-Suboptimal Search
Maximilian Fickert, Tianyi Gu, Wheeler Ruml
[AAAI-22] Main Track
Abstract:
In bounded-suboptimal heuristic search, one attempts to find a solution that costs no more than a prespecified factor of optimal as quickly as possible. This is an important setting, as it admits faster-than-optimal solving while retaining some control over solution cost. In this paper, we investigate several new algorithms for bounded-suboptimal search, including novel variants of EES and DPS, the two most prominent previous proposals, and methods inspired by recent work in bounded-cost search that leverages uncertainty estimates of the heuristic. We perform what is, to our knowledge, the most comprehensive empirical comparison of bounded-suboptimal search algorithms to date, including both search and planning benchmarks, and we find that one of the new algorithms, a simple alternating queue scheme, significantly outperforms previous work.
Introduction Video
Sessions where this paper appears
-
Poster Session 4
Blue 4
-
Poster Session 8
Blue 4
-
Oral Session 4
Blue 4
