Theses and Dissertations

Advisor

Hansen, Eric A.

Committee Member

Chen, Jingdao

Committee Member

Young, Maxwell

Committee Member

Zhou, Rong

Date of Degree

5-16-2025

Original embargo terms

Immediate Worldwide Access

Document Type

Dissertation - Open Access

Major

Computer Science

Degree Name

Doctor of Philosophy (Ph.D.)

College

James Worth Bagley College of Engineering

Department

Department of Computer Science and Engineering

Abstract

For shortest-path problems with a small number of integer transition costs, it is well-known that the performance of the classic A* algorithm can be improved by using bucketing to reduce priority queue overhead—in particular, by using a bucket queue data structure for the priority queue, instead of a binary heap. This dissertation describes several theoretical and practical extensions of this approach. First, the traditional two-level bucket queue data structure is modified in simple ways to improve the worst-case complexity of its operations, which leads to the first demonstration that the priority queue operations of a two-level bucket queue for A* can have amortized constant-time complexity. Second, and more importantly, a generalization of the bucket queue data structure is introduced, called a bucket heap, that can be used by a large class of bounded-suboptimal and anytime variants of the A* algorithm. Analysis shows that the operations of a bucket heap have improved asymptotic complexity compared to a binary heap. In addition, experiments involving a wide range of search algorithms and domains show that use of a bucket heap leads to faster search and improved suboptimality bounds. Finally, a hybrid algorithmic strategy is proposed that bounds the worst-case number of state re-expansions performed by bounded-suboptimal and anytime search algorithms, which expand states in order of an inadmissible evaluation function. This strategy is most efficiently implemented by using a bucket heap and it guarantees that the number of expansions performed by the algorithm is asymptotically equivalent to the number of expansions performed by A*. Experiments also show that this hybrid approach can lead to further speedup for many search problems, as well as improved suboptimality bounds.

Download

Share

COinS