Analyzing Tie-Breaking Strategies for the A* Algorithm

Analyzing Tie-Breaking Strategies for the A* Algorithm

Augusto B. Corrêa, André G. Pereira, Marcus Ritt

Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence
Main track. Pages 4715-4721. https://doi.org/10.24963/ijcai.2018/655

For a given state space and admissible heuristic function h there is always a tie-breaking strategy for which A* expands the minimum number of states [Dechter and Pearl, 1985]. We say that these strategies have optimal expansion. Although such a strategy always exists it may depend on the instance, and we currently do not know a tie-breaker that always guarantees optimal expansion. In this paper, we study tie-breaking strategies for A*. We analyze common strategies from the literature and prove that they do not have optimal expansion. We propose a novel tie-breaking strategy using cost adaptation that has always optimal expansion. We experimentally analyze the performance of A* using several tie-breaking strategies on domains from the IPC and zero-cost domains. Our best strategy solves significantly more instances than the standard method in the literature and more than the previous state-of-the-art strategy. Our analysis improves the understanding of how to develop effective tie-breaking strategies and our results also improve the state-of-the-art of tie-breaking strategies for A*.
Keywords:
Planning and Scheduling: Theoretical Foundations of Planning
Heuristic Search and Game Playing: Heuristic Search
Planning and Scheduling: Search in Planning and Scheduling