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.
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.
- 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.
- 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.
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