Problem Difficulty and the Phase Transition in Heuristic Search

Eldan Cohen, J. Christopher BeckAAAI 2017 · OpenReview

Abstract

In recent years, significant work has identified problem instance characteristics that impact search effort. Phase transitions in solubility have proved useful in studying difficulty for SAT and CSP, where the hardest problems typically occur during rapid transitions. This work performs the first empirical investigation of phase transitions in heuristic search. We establish a rapid transition in solubility within an abstract model and show that for greedy best-first search (GBFS), the hardest instances cluster in this transition region. We also investigate heuristic behavior across the solubility spectrum and demonstrate that these findings carry over to benchmark problems like the Pancake Problem and Towers of Hanoi, with notable exceptions explained in the Sliding Puzzle.

Introduction

In computational fields like Boolean Satisfiability (SAT), "phase transitions" are well-documented. As a problem becomes more constrained, it reaches a critical threshold where it shifts abruptly from being almost always solvable to almost always unsolvable. Crucially, the most computationally demanding instances typically reside at this boundary. While heuristic search is fundamental to AI, this phenomenon remained largely unexplored in the field. This research bridges that gap, investigating whether heuristic search exhibits similar phase transitions and how heuristic strength influences performance across this spectrum.

Methodology

The study utilizes two primary modeling approaches:

  1. Abstract Random Graph Model: State spaces are represented as random directed graphs with $n$ states. A control parameter, $\gamma$ (the ratio of edges to states), is used to vary the "constrainedness" of the problem.
  2. Benchmark Adaptation: To validate findings on real-world problems, the authors developed a technique to "restrict" or "relax" standard benchmarks. By randomly adding or removing valid moves (edges) from the state-space graph, they could shift problems like the Pancake Problem or Grid Navigation across the phase transition.

Search performance was evaluated using Greedy Best-First Search (GBFS). To control heuristic "strength," the authors employed a family of synthetic heuristics ($h_i$) that provide perfect distance information for any state within $i$ steps of the goal.

The core finding is the existence of an "easy-hard-easy" pattern of search difficulty. When the state-space graph is dense (high $\gamma$), many paths to the goal exist, making search easy. Conversely, when the graph is very sparse (low $\gamma$), it is easy to quickly prove no path exists. The "mushy region" between these extremes is where search effort spikes.

Solubility and search effort in the abstract random digraph model.

In the abstract model, the "crossover point" (where 50% of instances are soluble) occurs at $\gamma \approx 1.65$. At this point, GBFS expands approximately 65 times more nodes than in the underconstrained region. The hardest soluble instances occur near the end of the phase transition, where the graph is "stringy," while the hardest insoluble instances occur when a large connected component exists but does not include the goal.

Heuristic Strength and Diminishing Returns

A significant insight involves the impact of heuristic quality. While a strong heuristic (e.g., $h_4$) significantly outperforms a weak one ($h_0$) in "easy" regions, this advantage diminishes at the phase transition. For example, in the Pancake problem, a strong heuristic was 69 times more efficient in easy regions but only 1.75 times better at the hardest point. This suggests that the inherent topological difficulty of the phase transition can overwhelm the benefits of better heuristics.

Phase transition and search effort for a benchmark problem.

Benchmark Results and Topology

The "easy-hard-easy" pattern was confirmed across several benchmarks, including the Pancake Problem, Grid Navigation, and Towers of Hanoi. However, the Sliding Tile Puzzle (8-puzzle) presented a unique case. Its state space is naturally partitioned into two equal-sized components, placing the "original" puzzle naturally at the 50% solubility point. Consequently, the standard 8-puzzle is inherently harder than its relaxed or restricted variants.

Conclusion

This study establishes that heuristic search difficulty is deeply tied to the phase transition in solubility. The findings suggest that researchers should evaluate new heuristics specifically on "phase transition" instances to test their robustness. Future work should extend this analysis to optimal search algorithms like A* and explore predictive models for the crossover point in complex, real-world domains.

Summary updated

Abstract

In the recent years, there has been significant work on the difficulty of heuristic search problems, identifying different problem instance characteristics that can have a significant impact on search effort. Phase transitions in the solubility of random problem instances have proved useful in the study of problem difficulty for other classes of computational problems, notably SAT and CSP, and it has been shown that the hardest problems typically occur during this rapid transition. In this work, we perform the first empirical investigation of the phase transition phenomena for heuristic search. We establish the existence of a rapid transition in the solubility of an abstract model of heuristic search problems and show that, for greedy best first search, the hardest instances are associated with the phase transition region. We then perform a novel investigation of the behavior of heuristics of different strength across the solubility spectrum. Finally, we demonstrate that the behavior of our abstract model carries over to commonly used benchmark problems including the Pancake Problem, Grid Navigation, TopSpin, and the Towers of Hanoi. An interesting deviation is observed and explained in the Sliding Puzzle.
BibTeX
@inproceedings{cohen2017problem,
  author = {Eldan Cohen and J. Christopher Beck},
  title = {{Problem Difficulty and the Phase Transition in Heuristic Search}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2017},
  url = {https://openreview.net/forum?id=HkEPx1bOWB},
}
Figure