Open List Implementations in A*

Abstract

A* is the most important algorithm in optimal heuristic search. For its implementation, details beyond the scope of textbook descriptions become relevant. One such detail is how A* deals with duplicate states. A common approach is to modify a state's open list entry when a cheaper path to that state is found, updating its key. A binary heap often serves as the underlying data structure despite its suboptimal asymptotic runtime. More complex structures with better asymptotic runtime such as Fibonacci heaps are said to not pay off. A wide-spread alternative is to delay duplicate detection until expansion, allowing multiple entries for the same state on the open list. So far, the effect of these choices has not been studied in isolation for domain-independent planning. We compare early duplicate detection using a binary heap, Fibonacci heap, pairing heap, or bucket priority queue to delayed duplicate detection in order to evaluate whether early duplicate detection can be worth it.