Using Alternative Suboptimality Bounds in Heuristic Search
Full Text: 6048-30099-1-PB.pdf
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.
Citation
R. Valenzano, S. Arfaee, J. Thayer, R. Stern, N. Sturtevant. "Using Alternative Suboptimality Bounds in Heuristic Search". ICAPS, (ed: Daniel Borrajo, Subbarao Kambhampati, Angelo Oddi, Simone Fratini), pp 233-241, June 2013.| Keywords: | Suboptimal Search, Alternative Bounding, Heuristic Search, Planning |
| Category: | In Conference |
| Web Links: | AAAI |
BibTeX
@incollection{Valenzano+al:ICAPS13,
author = {Richard Valenzano and Shahab Jabbari Arfaee and Jordan Thayer and
Roni Stern and Nathan R. Sturtevant},
title = {Using Alternative Suboptimality Bounds in Heuristic Search},
Editor = {Daniel Borrajo, Subbarao Kambhampati, Angelo Oddi, Simone Fratini},
Pages = {233-241},
booktitle = {},
year = 2013,
}Last Updated: July 09, 2020Submitted by Sabina P
