Local Minima, Heavy Tails, and Search Effort for GBFS

Eldan Cohen, J. Christopher BeckIJCAI 2018 · OpenReview

Abstract

Problem difficulty for greedy best first search (GBFS) is not entirely understood, though existing work points to deep local minima and poor correlation between the h-values and the distance to goal as factors that have significant negative effect on the search effort. In this work, we show that there is a very strong exponential correlation between the depth of the single deepest local minima encountered in a search and the overall search effort. Furthermore, we find that the distribution of local minima depth changes dramatically based on the constrainedness of problems, suggesting an explanation for the previously observed heavy-tailed behavior in GBFS. In combinatorial search, a similar result led to the use of randomized restarts to escape deep subtrees with no solution and corresponding significant speed-ups. We adapt this method and propose a randomized restarting GBFS variant that improves GBFS performance by escaping deep local minima, and does so even in the presence of other, randomization-based, search enhancements.

Introduction

Greedy Best First Search (GBFS) is a workhorse in automated planning, yet its performance is notoriously unpredictable. While it often finds solutions instantly, it can also become trapped in "bad subtrees" or local minima where heuristic values ($h$-values) are misleading. This leads to a "heavy-tailed" distribution of search effort, where a small fraction of problem instances require exponentially more time to solve than the average. This paper bridges the gap between combinatorial search theory and heuristic state-space planning by quantifying the impact of local minima on search effort and proposing a mitigation strategy.

Quantifying Search Difficulty

To analyze search behavior precisely, the authors introduce two key metrics:

  1. $h$-depth: The difference between the heuristic value at the point where the search escapes a local minimum and the minimum heuristic value encountered within that minimum. This measures the "depth of the hole" the search fell into.
  2. $h$-backtrack: An event where the search expands a node with a higher $h$-value than its predecessor, signaling that the search is struggling to find a path with monotonically decreasing heuristic values.

These concepts were evaluated across six standard benchmark domains from the International Planning Competition (IPC): NoMystery, Rovers, TPP, Maintenance, Parking, and Freecell.

The Heavy-Tailed Phenomenon

The unpredictability of GBFS is characterized by heavy-tailed runtime distributions. By manipulating the "constrainedness" of benchmark problems (e.g., resource availability), the authors observed how these distributions shift. In relaxed problems, the probability of hitting a deep local minimum is low, but when it happens, the search effort explodes, creating a "fat tail" in the performance data.

Survival distribution of search effort across different problem constrainedness levels (C values).

The "Deepest Hole" Rule

A central finding of this research is the nearly perfect exponential correlation between the $h$-depth of the single deepest local minimum encountered and the total search effort. Across various domains, Pearson correlation coefficients between $\log(\text{search effort})$ and max $h$-depth ranged from 0.73 to 0.98. This suggests that the depth of the deepest local minimum is the primary predictor of search complexity.

Correlation between local minima depth (h-depth) and search effort metrics (expanded nodes and backtracks) for both random instances and randomized search.

Randomized Restarting GBFS (RR-GBFS)

Drawing inspiration from SAT solvers, the authors propose RR-GBFS. This variant uses a randomized search and monitors the number of $h$-backtracks. If the search exceeds a specific cutoff of backtracks without finding a solution, it restarts with a new random seed and an increased cutoff following a geometric progression (e.g., 16, 24, 36, ...).

RR-GBFS effectively "chops off" the heavy tail of the runtime distribution. In the NoMystery domain, it solved difficult instances in orders of magnitude less time than standard GBFS. Furthermore, RR-GBFS remains effective even when combined with other randomization enhancements like $\epsilon$-GBFS, suggesting that restarts provide a unique benefit—escaping deep holes—that simple local exploration does not.

Conclusion

While RR-GBFS significantly improves performance, it can underperform in highly constrained environments where deep local minima are unavoidable on almost every path to the goal. In such cases, restarting may lead the agent back into another hole, wasting previous effort. Future work will investigate more sophisticated restart policies and address "plateaus" (regions of constant $h$-values), which remain another major source of GBFS inefficiency.

Summary updated

Abstract

Problem difficulty for greedy best first search (GBFS) is not entirely understood, though existing work points to deep local minima and poor correlation between the h-values and the distance to goal as factors that have significant negative effect on the search effort. In this work, we show that there is a very strong exponential correlation between the depth of the single deepest local minima encountered in a search and the overall search effort. Furthermore, we find that the distribution of local minima depth changes dramatically based on the constrainedness of problems, suggesting an explanation for the previously observed heavy-tailed behavior in GBFS. In combinatorial search, a similar result led to the use of randomized restarts to escape deep subtrees with no solution and corresponding significant speed-ups. We adapt this method and propose a randomized restarting GBFS variant that improves GBFS performance by escaping deep local minima, and does so even in the presence of other, randomization-based, search enhancements.
BibTeX
@inproceedings{cohen2018local,
  author = {Eldan Cohen and J. Christopher Beck},
  title = {{Local Minima, Heavy Tails, and Search Effort for GBFS}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2018},
  url = {https://openreview.net/forum?id=ByZuvQGdWB},
}
Figure