Analyzing Tie-Breaking Strategies for the A* Algorithm

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

Abstract

While the A search algorithm is a cornerstone of automated planning, the impact of tie-breaking strategies on its efficiency is often overlooked. This paper investigates the performance of A in domains with zero-cost actions, where standard tie-breaking strategies frequently lead to exhaustive searches of the final $f$-layer. We present a novel "cost-adaptation" strategy that modifies operator costs to prioritize shorter paths among those with equal optimal costs. Theoretical analysis reveals that even perfect heuristics can fail under standard tie-breaking, while our proposed strategy guarantees optimal expansion under certain conditions. Empirical results across standard planning benchmarks demonstrate that cost-adapted tie-breaking significantly improves coverage and reduces state expansions compared to state-of-the-art methods.

Introduction

The A algorithm expands states in order of their estimated total cost, $f(s) = g(s) + h(s)$, where $g(s)$ is the cost to reach the state and $h(s)$ is a heuristic estimate of the cost to the goal. In many real-world problems, particularly those with zero-cost actions, many states share the same $f$-value, creating what is known as an "f-layer" or a "final plateau." When the heuristic is "pathological"—meaning it fails to distinguish between states on the optimal path and others in this final layer—A must rely on a tie-breaking strategy ($\tau$) to decide which state to expand next.

The Challenge of Zero-Cost Domains

Zero-cost domains present a significant challenge for standard search algorithms. Consider a logistics problem where moving an empty truck has a cost of zero. In such cases, the search space can explode because A* might explore an arbitrary number of zero-cost sequences before reaching the goal. Standard tie-breaking, which typically favors smaller $h$-values, is often insufficient to navigate these plateaus efficiently.

Theoretical Limits of Standard Tie-Breaking

A surprising finding of this research is that even a perfect heuristic ($h^*$) does not guarantee optimal state expansion when used in standard tie-breaking. As shown in the counterexamples below, strategies like $[f^*, h^*]$ or $[f^*, \hat{h}^*]$ (where $\hat{h}$ is the distance-to-go) can still lead the search down arbitrarily long zero-cost paths that do not progress toward the goal.

Counterexamples showing that standard tie-breaking strategies using perfect heuristics ($h^*$ or $\hat{h}^*$) can still lead to non-optimal state expansions in the presence of zero-cost actions.

The Cost-Adaptation Strategy

To address these limitations, the authors propose a "cost-adapted" heuristic, $h_c$. This strategy involves adding a constant $c$ to the cost of every operator in the domain.

  1. Theoretical Strategy: The authors prove that using the order $[g+h, g+h^*_\epsilon]$ (where $h^*_\epsilon$ is the perfect heuristic calculated with a tiny added cost $\epsilon$ to every action) results in optimal expansion. This forces the algorithm to prefer the "shortest" path (in terms of number of steps) among all paths with the "cheapest" total cost.
  2. Practical Strategy: Since $h^*$ is generally unknown, the researchers tested approximations such as $h+1$ (adding 1 to every cost) or $h_\epsilon$ (adding a tiny fraction) using common heuristics like $h^{LM-cut}$ and $h^{FF}$.

This approach effectively uses $g$ in the tie-breaker to account for the "effort" already spent, penalizing unnecessarily long paths even if they have zero total cost.

Empirical Performance

The researchers evaluated these strategies using 1,104 instances from the International Planning Competition (IPC) and 620 specialized zero-cost domain instances. The results were definitive: the cost-adapted $h^{FF}_{+1}$ strategy solved 152 more instances than standard $h$-breaking methods.

Scatter plot comparing state expansions of the cost-adapted FF heuristic against standard methods, highlighting the significant reduction in search effort across various problem instances.

In zero-cost domains, the cost-adapted strategies often reduced state expansions by orders of magnitude. Furthermore, this strategy outperformed the previous state-of-the-art deterministic tie-breaker by a margin of 24 instances, demonstrating its robustness and efficiency.

Conclusion

Tie-breaking is a critical but frequently ignored component of heuristic search. By shifting from standard $h$-breaking to a cost-adapted approach, researchers can significantly mitigate the "plateau" problem in zero-cost domains. While theoretical guarantees of optimality require consistent heuristics, the practical application of cost adaptation ($h+1$) provides a powerful and easily implemented improvement for A* search in complex automated planning tasks.

Summary updated

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},
}
Figure