Bucket Aggregation in Bucket-Based Priority Queues for Heuristic Search

Abstract

Bucket-based priority queues can reduce the overhead of priority queue operations for A* and related bounded-suboptimal and anytime variants, especially when transition costs are small integers. The buckets are usually indexed by both f-cost (primary) and h-cost (secondary), which enables efficient tie-breaking and priority ordering. However, when solution costs are large and the heuristic is informative, the number of secondary buckets within a primary bucket can become very large, leading to bucket sparsity that degrades performance. To address this, we introduce a simple aggregation method that restores bucket density while preserving standard solution-quality guarantees. We demonstrate its effectiveness in several benchmark domains.