Analyzing Tie-Breaking Strategies for the A* Algorithm

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

Abstract

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*.
BibTeX
@inproceedings{correa2018analyzing,
  author = {Augusto B. Corrêa and André Grahl Pereira and Marcus Ritt},
  title = {{Analyzing Tie-Breaking Strategies for the A* Algorithm}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2018},
  doi = {10.24963/ijcai.2018/655},
}

Loading related content...

Figure