Abstract
Many practical problems are too difficult to solve
optimally, motivating the need to found suboptimal
solutions, particularly those with bounds on the fi-
nal 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*