Bounded Suboptimal Search: A Direct Approach Using Inadmissible Estimates

Thayer, Jordan Tyler; Ruml, Wheeler

doi:10.5591/978-1-57735-516-8/IJCAI11-119

Bounded Suboptimal Search: A Direct Approach Using Inadmissible Estimates

Jordan Tyler Thayer, Wheeler Ruml

Download BibTeX Cite

Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence. Pages 674-678.

https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-119

Abstract

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.

Jordan Tyler Thayer, and Wheeler Ruml. 2011. Bounded Suboptimal Search: A Direct Approach Using Inadmissible Estimates. In Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11. IJCAI, 674–678. https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-119

@inproceedings{ijcai2011p119,
  title     = {Bounded Suboptimal Search: A Direct Approach Using Inadmissible Estimates},
  author    = {Thayer, Jordan Tyler and Ruml, Wheeler},
  booktitle = {Proceedings of the Twenty-Second International Joint Conference on
               Artificial Intelligence, {IJCAI-11}},
  publisher = {AAAI Press/International Joint Conferences on Artificial Intelligence},
  editor    = {Toby Walsh},
  pages     = {674--678},
  year      = {2011},
  month     = {7},
  doi       = {10.5591/978-1-57735-516-8/IJCAI11-119},
  url       = {https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-119},
}

TY  - CPAPER
TI  - Bounded Suboptimal Search: A Direct Approach Using Inadmissible Estimates
AU  - Thayer, Jordan Tyler
AU  - Ruml, Wheeler
T2  - Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11
PB  - AAAI Press/International Joint Conferences on Artificial Intelligence
PY  - 2011
SP  - 674
EP  - 678
DO  - 10.5591/978-1-57735-516-8/IJCAI11-119
UR  - https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-119
ER  -