Expansion Counts under Standard A* Tie-Breaking Strategies on the Final Plateau
In the authors' words
In the A* search algorithm, the tie-breaking strategies for nodes with the same -value determines which states A* expands on the final -layer. For nine standard tie-breaking strategies, we show that under a consistent heuristic, every pair has positive-cost instances favoring each strategy over the other by an arbitrarily large additive expansion gap. A parameterized unit-cost grid example also gives unbounded expansion-count ratios between low- with FIFO and LIFO. In unit-cost search with at non-goals, exact heuristic values near the goal lead to complementary extremal results: low- minimizes the number of remaining expansions from a common configuration within the perfect region, while high- maximizes the total number of expansions when every final-plateau state with is a goal predecessor. Finally, with the evaluation function , when at non-goals, every heuristic weight eliminates tie-breaking sensitivity, and all tie-breaking strategies expand the same set of states.
Appeared: Tuesday, September 22. arXiv. Preprint, not yet peer-reviewed.