Conditions for Avoiding Node Re-expansions in Bounded Suboptimal Search
Full Text: 0170.pdf
Many practical problems are too difficult to solve optimally, motivating the need to found suboptimal solutions, particularly those with bounds on the final solution quality. Algorithms like Weighted A*, A*-epsilon, Optimistic Search, EES, and DPS have been developed to find suboptimal solutions with solution quality that is within a constant bound of the optimal solution. However, with the exception of weighted A*, all of these algorithms require performing node re-expansions during search. This paper explores the properties of priority functions that can find bounded suboptimal solution without requiring node re-expansions. After general bounds are developed, two new convex priority functions are developed that can outperform weighted A*.
Citation
J. Chen, N. Sturtevant. "Conditions for Avoiding Node Re-expansions in Bounded Suboptimal Search". International Joint Conference on Artificial Intelligence (IJCAI), (ed: Sarit Kraus), pp 1220-1226, August 2019.| Keywords: | Heuristic Search and Game Playing: Heuristic Search, Heuristic Search and Game Playing: Combinatorial Search and Optimisation |
| Category: | In Conference |
| Web Links: | IJCAI |
| doi |
BibTeX
@incollection{Chen+Sturtevant:IJCAI19,
author = {Jingwei Chen and Nathan R. Sturtevant},
title = {Conditions for Avoiding Node Re-expansions in Bounded Suboptimal
Search},
Editor = {Sarit Kraus},
Pages = {1220-1226},
booktitle = {International Joint Conference on Artificial Intelligence
(IJCAI)},
year = 2019,
}Last Updated: July 03, 2020Submitted by Sabina P
