A Bucket-Based Priority Queue for Bounded-Suboptimal and Anytime A* Search

Abstract

We introduce a priority queue data structure, called a bucket heap, which generalizes the bucket queue commonly used to accelerate A* search for shortest-path problems with a small range of integer transition costs. Unlike a bucket queue, a bucket heap speeds up priority queue operations for bounded-suboptimal and Anytime A* algorithms guided by non-admissible node evaluation functions. It also provides direct access---without any additional overhead---to the underlying bucket queue of A*, which we show can be used to improve search performance in further ways.