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."
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.
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