Speedy versus Greedy Search

Christopher Makoto Wilt, Wheeler RumlIJCAI 2015

Abstract

In satisficing search, the objective is to find any valid solution as quickly as possible. While Greedy Best-First Search (GBFS) using cost-to-go heuristics ($h$) is the conventional choice, empirical evidence often shows that "Speedy Search"—which uses distance-to-go heuristics ($d$)—is significantly faster. This paper provides a theoretical and structural explanation for this disparity, demonstrating that distance-based heuristics create smaller "local minima" in the search space, allowing algorithms to navigate toward the goal with fewer unproductive expansions.

Introduction

In many real-world AI applications, finding an optimal solution is less important than finding any solution quickly. This is known as satisficing search. The standard approach, Greedy Best-First Search (GBFS), prioritizes nodes with the lowest estimated cost to the goal ($h(n)$). However, researchers have long observed that ignoring actual edge costs and simply estimating the number of steps to the goal ($d(n)$) often results in much faster search times.

Christopher Wilt and Wheeler Ruml's paper, "Speedy versus Greedy Search," moves beyond mere observation to explain why this happens. They argue that the performance of a search algorithm is primarily determined by the size of the local minima it encounters.

The Mechanics of Search Traps

A "local minimum" in a heuristic search is a region of the state space where the heuristic value must increase before the search can progress toward the goal. These regions act as traps: a search algorithm must expand every node within the minimum before it can "climb out" and continue.

Figure 1: A search tree illustrating how distance-to-go (d) and cost-to-go (h) heuristics can diverge.

The authors propose that cost-to-go heuristics are more prone to creating large local minima, especially when edge costs vary significantly. In such landscapes, a sequence of "cheap" actions might lead the search into a deep, unproductive subtree that appears promising because of its low cumulative cost but is actually far from the goal in terms of steps. Distance-to-go heuristics, by treating every action as having a unit cost, provide a smoother gradient that is less likely to be "tricked" by cost variance.

Empirical Evidence across Domains

The authors tested their hypothesis across several classic AI benchmarks, including the Sliding Tile Puzzle, Towers of Hanoi, and TopSpin. By varying the edge costs (e.g., unit, inverse, or square costs), they were able to observe how the divergence between $h$ and $d$ affected search performance.

Table 1: Comparison of local minimum sizes and search expansions across different domains and cost functions.

As shown in Table 1, the difference in local minimum size can be staggering. In the Sliding Tile puzzle with inverse costs, the maximum local minimum for the cost heuristic ($h$) contained 51,532 nodes, whereas the distance heuristic ($d$) had a maximum minimum of only 392 nodes. This structural difference translated directly into search effort: in the Towers of Hanoi with reverse square costs, Greedy search required over 559,000 expansions on average, while Speedy search needed only 36,000.

Key Insights

  • Local Minima are the Primary Bottleneck: The time spent in a search is dominated by "filling up" these heuristic holes.
  • Cost Variance Increases Risk: High variance in operator costs increases the probability of a node being trapped in a local minimum.
  • Distance is a Robust Proxy: Because $d$ has zero cost variance (every step is 1), it is more robust against the "traps" created by varying edge costs.

Conclusion

The superiority of Speedy search is not accidental; it is a direct consequence of the heuristic topology. By focusing on the number of steps rather than the total cost, Speedy search avoids the massive local minima that often plague cost-based heuristics in non-unit cost domains. While Speedy search does not guarantee solution quality, it remains the superior choice for applications where time-to-solution is the critical metric.

Reference: Wilt, C., & Ruml, W. (2015). Speedy versus Greedy Search. Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence (IJCAI 2015), 4331-4337.

Summary updated

BibTeX
@inproceedings{wilt2015speedy,
  author = {Christopher Makoto Wilt and Wheeler Ruml},
  title = {{Speedy versus Greedy Search}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2015},
}
Figure