Simpler Bounded Suboptimal Search

It is commonly appreciated that solving search problems optimally can take too long. Bounded suboptimal search algorithms trade increased solution cost in a principled way for reduced solving time. Explicit Estimation Search (EES) is a recent state-of-the-art algorithm for bounded suboptimal search. Although it tends to expand fewer nodes than alternative algorithms, its per-node expansion overhead is much higher, causing it to sometimes take longer. In this paper, we present simplified variants of EES (SEES) and an earlier algorithm, A∗ (SA∗ ), that use different implementations of the same motivating ideas to significantly reduce search overhead and implementation complexity. In an empirical evaluation, we find that SEES matches or outperforms classic bounded suboptimal search algorithms, such as WA∗, on all domains tested. We also confirm that, while SEES and SA∗ expand roughly the same number of nodes as their progenitors, they solve problems significantly faster and are much easier to implement. This work widens the applicability of state-ofthe-art bounded suboptimal search by making it easier to deploy.

Authors

• Matthew Hatem
• Wheeler Ruml University of New Hampshire

Keywords

No keywords are indexed for this paper.