Faster Bounded-Cost Search Using Inadmissible Estimates


  • Jordan Thayer University of New Hampshire
  • Roni Stern Ben-Gurion University of the Negev
  • Ariel Felner Ben-Gurion University of the Negev
  • Wheeler Ruml University of New Hampshire



heuristic search, search, bounded cost


Many important problems are too difficult to solve optimally. A traditional approach to such problems is bounded suboptimal search, which guarantees solution costs within a user-specified factor of optimal. Recently, a complementary approach has been proposed: bounded-cost search, where solution cost is required to be below a user-specified absolute bound. In this paper, we show how bounded-cost search can incorporate inadmissible estimates of solution cost and solution length. This information has previously been shown to improve bounded suboptimal search and, in an empirical evaluation over five benchmark domains, we find that our new algorithms surpass the state-of-the-art in bounded-cost search as well, particularly for domains where action costs differ.




How to Cite

Thayer, J., Stern, R., Felner, A., & Ruml, W. (2012). Faster Bounded-Cost Search Using Inadmissible Estimates. Proceedings of the International Conference on Automated Planning and Scheduling, 22(1), 270-278.