How Long Will It Take?

Ron Musick, Stuart RussellAAAI 1992

Abstract: Predicting the average-case performance of search algorithms in vast state spaces is a fundamental problem in AI. This paper introduces a framework that maps high-dimensional state spaces into compact, one-dimensional Markov chains based on the distance to a goal. This simplification reduces the computational complexity of estimating search time from exponential to linear. The resulting models identify a critical "easy zone" around goals, providing a mathematical explanation for the effectiveness of greedy initializers and the observed phase transitions in problem difficulty.

Introduction

In the early 1990s, AI research primarily focused on the completeness and worst-case complexity of search algorithms. However, practical applications require an understanding of average-case performance. For complex problems like the 50-queens puzzle, the state space of $50^{50}$ configurations makes direct calculation of expected search time impossible. Musick and Russell (1992) proposed a method to simplify this complexity by abstracting state spaces into solvable mathematical models.

Methodology: Abstracting the State Space

The authors' core innovation is a mapping from a generic state space to an abstract Markov model. Instead of tracking every unique state, they group states by their syntactic "distance" ($i$) from the goal—for instance, the number of violated constraints in a scheduling problem.

By modeling the search as a process that moves between these distance-based states (closer, further, or remaining at the same distance), the authors transform a massive system of equations into a tridiagonal matrix. Solving for the expected number of steps ($NS$) becomes an $O(n)$ process, where $n$ is the number of features, rather than an exponential one. For certain cases, they even derive closed-form solutions that allow for instantaneous calculation of search time.

The "Easy Zone" and Phase Transitions

A key insight from this model is the existence of an "easy zone"—a specific radius around a goal where solutions are found almost instantly. If an algorithm's probability of moving toward the goal increases as it nears the target, there is a clear "radius of success."

Figure 3: The expected number of steps as a function of distance, illustrating the exponential explosion of search time once the "easy zone" is exited.

As shown in Figure 3, search time remains trivial within a certain distance but "explodes" exponentially once a boundary is crossed. This phenomenon explains why "greedy" initializers are so effective: if a preprocessor can place the search within this easy zone, the heuristic repair will finish the task rapidly.

Empirical Validation

The model was validated across several domains, including 3-coloring problems, random constraint satisfaction problems (CSPs), and the 8-puzzle. Despite the abstraction technically breaking the Markov property by losing specific state information, empirical tests showed the model remained highly accurate.

Figure 4: Comparison of theoretical predictions (solid line) with the mean of 100 actual runs (data points with error bars) for the 8-puzzle.

In Figure 4, the theoretical curve for expected steps closely matches the empirical results from 8-puzzle runs. This demonstrates the model's robustness and its ability to capture the "sharp transition" between easy and hard problem instances, a phenomenon observed empirically in the field at the time.

Conclusion

Musick and Russell's framework provides a powerful tool for predicting search performance without exhaustive simulation. By reducing the complexity of estimation to $O(n)$, it opens doors for metareasoning—allowing systems to dynamically allocate computational resources between preprocessing and search based on the predicted difficulty of a problem.

Summary updated

BibTeX
@inproceedings{musick1992how,
  author = {Ron Musick and Stuart Russell},
  title = {{How Long Will It Take?}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1992},
}
Figure