Bounded Suboptimal Search: A Direct Approach Using Inadmissible Estimates
Jordan T. Thayer, Wheeler Ruml
Bounded suboptimal search algorithms offer shorter solving times bysacrificing optimality and instead guaranteeing solution costs withina desired factor of optimal. Typically these algorithms use a singleadmissible heuristic both for guiding search and bounding solutioncost. In this paper, we present a new approach to bounded suboptimalsearch, Explicit Estimation Search, that separates these roles,consulting potentially inadmissible information to determine searchorder and using admissible information to guarantee the cost bound.Unlike previous proposals, it successfully combines estimates ofsolution length and solution cost to predict which node will lead mostquickly to a solution within the suboptimality bound. An empiricalevaluation across six diverse benchmark domains shows that ExplicitEstimation Search is competitive with the previous state of the art indomains with unit-cost actions and substantially outperformspreviously proposed techniques for domains in which solution cost andlength can differ.