Conditions for Avoiding Node Re-expansions in Bounded Suboptimal Search

Conditions for Avoiding Node Re-expansions in Bounded Suboptimal Search

Jingwei Chen, Nathan R. Sturtevant

Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence
Main track. Pages 1220-1226. https://doi.org/10.24963/ijcai.2019/170

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*.
Keywords:
Heuristic Search and Game Playing: Heuristic Search
Heuristic Search and Game Playing: Combinatorial Search and Optimisation