Faster han Weighted A*: An Optimistic Approach to Bounded Suboptimal Search

Planning, scheduling, and other applications of heuristic search often demand we tackle problems that are too large to solve optimally. In this paper, we address the prob-lem of solving shortest-path problems as quickly as possi-ble while guaranteeing that solution costs are bounded within a specified factor of optimal. 38 years after its publica-tion, weighted A * remains the best-performing algorithm for general-purpose bounded suboptimal search. However, it typ-ically returns solutions that are better than a given bound re-quires. We show how to take advantage of this behavior to speed up search while retaining bounded suboptimality. We present an optimistic algorithm that uses a weight higher than the user’s bound and then attempts to prove that the resulting solution adheres to the bound. While simple, we demonstrate that this algorithm consistently surpasses weighted A * in four different benchmark domains including temporal planning and gridworld pathfinding