Expansion Counts under Standard A* Tie-Breaking Strategies on the Final Plateau

Abstract:In the A* search algorithm, the tie-breaking strategies for nodes with the same $f$-value determines which states A* expands on the final $f$-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-$h$ with FIFO and LIFO. In unit-cost search with $h > 0$ at non-goals, exact heuristic values near the goal lead to complementary extremal results: low-$h$ minimizes the number of remaining expansions from a common configuration within the perfect region, while high-$h$ maximizes the total number of expansions when every final-plateau state with $h=1$ is a goal predecessor. Finally, with the evaluation function $f_{\alpha} = g + \alpha h$, when $h>0$ at non-goals, every heuristic weight $0 \leq \alpha<1$ eliminates tie-breaking sensitivity, and all tie-breaking strategies expand the same set of states.

Artificial Intelligence (cs.AI)

arXiv:2609.23293 [cs.AI]

(or arXiv:2609.23293v1 [cs.AI] for this version)

https://doi.org/10.48550/arXiv.2609.23293 Focus to learn more arXiv-issued DOI via DataCite (pending registration)

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.