Best-Case and Worst-Case Behavior of Greedy Best-First Search

Manuel Heusner, Thomas Keller, Malte HelmertIJCAI 2018 · DOI

TL;DR

This paper delves into the often-overlooked impact of tie-breaking in Greedy Best-First Search (GBFS), a popular algorithm for finding solutions in state-space search problems. The authors prove that determining the optimal (best-case) or worst-case number of states GBFS expands is NP-complete in general, but surprisingly, becomes tractable for undirected state spaces.

What Problem Does This Paper Address?

While optimal search algorithms like A have been extensively studied, satisficing search algorithms like Greedy Best-First Search (GBFS) remain less understood. GBFS aims to find a* solution, not necessarily the optimal one, by greedily expanding the node with the lowest heuristic value. However, when multiple nodes share the same lowest heuristic value (a tie), the choice of which node to expand next (tie-breaking) can drastically alter GBFS's performance. Anecdotal evidence suggests this impact is significant, but a formal understanding, especially of the best-case (minimum expansions) and worst-case (maximum expansions) scenarios, was lacking. This paper aims to bridge that gap by formally analyzing the complexity of these extreme behaviors and identifying conditions under which they become computationally tractable.

Methods

The authors introduce several key concepts to analyze GBFS behavior:

  • High-Water Marks (hwm): A measure of the highest heuristic value encountered on any path from a state to a goal. This helps partition GBFS runs into "episodes."
  • Progress States: States where the high-water mark of the current episode is lower than the previous one. These act as "reset points" for the search.
  • Benches: Restricted state spaces defined by progress states, simplifying the analysis of GBFS episodes.
  • Craters: Sets of states that are guaranteed to be expanded due to heuristic depressions.
  • Surface Graph: A graph containing only states with heuristic values equal to their high-water marks, relevant for best-case analysis.
  • Bench Transition System: A meta-graph where nodes are benches, used for worst-case analysis.

They then leverage these concepts to:

  • Prove NP-completeness: By reducing known NP-complete problems (VERTEXCOVER and SAT) to decision problems for GBFS best-case and worst-case expansions, they show these problems are NP-complete in the general case.
  • Develop Algorithms: They propose algorithms for computing best-case and worst-case GBFS behavior. These algorithms operate on the surface graph and bench transition system, respectively, offering a more efficient approach than brute-force search.
  • Identify Tractable Cases: They demonstrate that for undirected state spaces (where transitions are bidirectional) and for state spaces that are "overlap-free" (meaning benches or craters don't excessively intersect), the best-case and worst-case GBFS behavior can be computed in polynomial time.

Datasets

The authors performed computational experiments on benchmark tasks from the International Planning Competitions (IPC) from 1998-2014. They used the hFF heuristic and unit cost for these experiments. The benchmark set used for further analysis consisted of 764 instances from 78 domains where GBFS with FIFO tie-breaking found a plan within specific time and memory limits.

Key Insights and Ideas

  • Tie-breaking is Crucial: The paper strongly emphasizes that tie-breaking in GBFS is not a minor detail; it can lead to vastly different numbers of expanded states, especially in the presence of "craters" (heuristic depressions).
  • NP-Completeness for General Cases: The formal proof of NP-completeness for determining best-case and worst-case expansions is a significant theoretical contribution, explaining why finding optimal tie-breaking strategies is hard in general.
  • Undirected State Spaces are Tractable: The discovery that undirected state spaces make best-case and worst-case analysis polynomial is a key finding. This suggests that for certain classes of problems, efficient computation of these bounds is possible.
  • Craters Dramatically Increase Worst-Case: The experimental results highlight that craters significantly widen the gap between best-case and worst-case GBFS performance, making the worst-case much more expensive.
  • GBFS vs. A* in Crater-Free Domains: In crater-free domains, the number of states expanded by worst-case GBFS is often a small fraction of the "possibly expanded states" (states that could be expanded by any tie-breaking strategy). This explains why GBFS can be a good choice for satisficing planning in such scenarios, as its worst-case is still relatively contained.

Key Results

  • NP-Completeness: GBFSBESTCASE and GBFSWORSTCASE problems are proven to be NP-complete.
  • Polynomial Time Tractability: GBFSWORSTCASE is polynomial for overlap-free state spaces with respect to benches. GBFSWORSTCASE and GBFSBESTCASE are polynomial for undirected state spaces. GBFSBESTCASE is polynomial for state spaces that are overlap-free with respect to craters and benches.
  • Experimental Findings:
    • GBFS with worst-case tie-breaking expands approximately 10-100 times more states than GBFS with best-case tie-breaking.
  • Standard tie-breaking strategies (FIFO, LIFO, random) are not significantly better than each other and are considerably worse than the best-case, especially in the presence of craters.
  • In state spaces with craters, the number of states expanded by worst-case GBFS is similar to the number of possibly expanded states.
  • In crater-free state spaces, worst-case GBFS expands less than 1% of the possibly expanded states.

Limitations and Future Work

  • Computational Cost: While polynomial algorithms exist for specific cases, the general algorithms for computing best- and worst-case tie-breaking are still exponential in the worst case. The authors note that their implementation works for only about a third of the instances solvable by GBFS, indicating room for improvement in graph computation.
  • Designing Better Tie-Breaking: A significant future direction is to use the insights gained to design new tie-breaking strategies for GBFS that perform closer to the best-case, even in the presence of craters.
  • Heuristic Comparison: The authors plan to use their framework to compare different heuristics for GBFS, similar to how admissible heuristics are compared for A*.
  • Implicit State Spaces: The current NP-completeness proofs assume explicit state space representations. The complexity for implicitly defined state spaces (where states are generated on the fly) is not directly addressed.

Summary updated

BibTeX
@inproceedings{heusner2018best,
  author = {Manuel Heusner and Thomas Keller and Malte Helmert},
  title = {{Best-Case and Worst-Case Behavior of Greedy Best-First Search}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2018},
  doi = {10.24963/ijcai.2018/203},
}

Loading related content...

Figure