Abstract
We tackle two long-standing problems related to
re-expansions in heuristic search algorithms. For
graph search, A* can require ?(2n) expansions,
where n is the number of states within the final
f bound. Existing algorithms that address this
problem like B and B’ improve this bound to
?(n2). For tree search, IDA* can also require
?(n2) expansions. We describe a new algorithmic
framework that iteratively controls an expansion
budget and solution cost limit, giving rise to new
graph and tree search algorithms for which the
number of expansions is O(n log C?), where C?
is
the optimal solution cost. Our experiments show
that the new algorithms are robust in scenarios
where existing algorithms fail. In the case of tree
search, our new algorithms have no overhead over
IDA* in scenarios to which IDA* is well suited
and can therefore be recommended as a general
replacement for IDA*