Jordan T. Thayer, Wheeler Ruml
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 problem of solving shortest-path problems as quickly as possible while guaranteeing that solution costs are bounded within a specified factor of optimal. 38 years after its publication, weighted A* remains the best-performing algorithm for general-purpose bounded suboptimal search. However, it typically returns solutions that are better than a given bound requires. 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.
Subjects: 15.7 Search; 1.11 Planning
Submitted: Jun 27, 2008