Using Alternative Suboptimality Bounds in Heuristic Search


  • Richard Valenzano University of Alberta
  • Shahab Jabbari Arfaee University of Alberta
  • Jordan Thayer Smart Information Flow Technologies
  • Roni Stern Harvard University
  • Nathan Sturtevant University of Denver



Suboptimal Search, Alternative Bounding, Heuristic Search, Planning


Most bounded suboptimal algorithms in the search literature have been developed so as to be epsilon-admissible. This means that the solutions found by these algorithms are guaranteed to be no more than a factor of (1 + ε) greater than optimal. However, this is not the only possible form of suboptimality bounding. For example, another possible suboptimality guarantee is that of additive bounding, which requires that the cost of the solution found is no more than the cost of the optimal solution plus a constant gamma.

In this work, we consider the problem of developing algorithms so as to satisfy a given, and arbitrary, suboptimality requirement. To do so, we develop a theoretical framework which can be used to construct algorithms for a large class of possible suboptimality paradigms. We then use the framework to develop additively bounded algorithms, and show that in practice these new algorithms effectively trade-off additive solution suboptimality for runtime.




How to Cite

Valenzano, R., Jabbari Arfaee, S., Thayer, J., Stern, R., & Sturtevant, N. (2013). Using Alternative Suboptimality Bounds in Heuristic Search. Proceedings of the International Conference on Automated Planning and Scheduling, 23(1), 233-241.