SteppingStone: An Empirical and Analytical Evaluation

David Ruby, Dennis F. KiblerAAAI 1991

Introduction

In classical artificial intelligence, complex tasks are often decomposed into a set of ordered subgoals. However, a significant challenge arises when these subgoals interact: progress toward one goal may necessitate temporarily undoing a previously satisfied one. This phenomenon, known as an "impasse," typically forces a choice between two suboptimal search strategies. Constrained solvers are efficient but fail at impasses because they strictly protect solved subgoals. Conversely, unconstrained solvers can bypass impasses through brute-force search but suffer from exponential computational costs, making them impractical for large-scale problems.

SteppingStone is a learning architecture designed to resolve this tension. By identifying recurring impasses and memorizing the localized solutions as "stepping stones," the system enables a fast, constrained solver to navigate complex state spaces that would otherwise require exhaustive search.

System Architecture

The SteppingStone architecture consists of five primary components that coordinate to solve problems and learn from failures.

The SteppingStone system architecture, illustrating the interaction between constrained search, unconstrained search, and the learning/memory components.
  1. Goal Ordering: This component uses a domain-independent "openness" heuristic to sequence subgoals, aiming to minimize potential interactions.
  2. Constrained Search: An efficient incremental hill-climbing algorithm that attempts to solve subgoals sequentially while protecting those already achieved.
  3. Unconstrained Search: When the constrained search reaches an impasse, this component is activated. It relaxes subgoal protections to find a localized brute-force solution.
  4. Learning: This module analyzes the solution path provided by the unconstrained search, generalizing the sequence of moves into a series of partial state descriptions, or "stepping stones."
  5. Memory: Stores these generalized sequences. When a similar impasse is encountered in the future, the system retrieves the relevant stepping stones to guide the constrained search.

Learning and Generalization

A key innovation of SteppingStone is its focus on sequences of states rather than fixed sequences of moves (macro-operators). Traditional macro-operators are rigid; they specify exactly which actions to take. In contrast, a stepping stone defines a target intermediate state. This allows the system to remain flexible, as the constrained solver only needs to reach the next "stone" using any available valid moves.

Comparison between raw states leading to improvement and generalized stepping stones in the logic synthesis domain.

Furthermore, SteppingStone employs "variablization" to generalize its learned knowledge. By using partial state descriptions, a strategy learned in one part of the problem space can be applied to isomorphic situations elsewhere, significantly increasing the utility of each learned sequence.

Experimental Evaluation

The system was evaluated on two benchmarks: the classic 8-puzzle and logic synthesis for VLSI design. The latter served as the primary experimental domain, where the goal was to map Boolean equations to a specific library of technology components (e.g., NAND, NOR, inverters).

Performance in Logic Synthesis

The results demonstrated a dramatic reduction in search complexity. After learning only 34 subgoal sequences from small training problems (2-5 inputs), SteppingStone was able to solve 30-input problems by expanding an average of only 2,841 nodes. In contrast, a standard brute-force approach failed to find solutions even after 500,000 node expansions.

Beyond efficiency, the quality of the solutions was high. In optimizing for "critical path delay," SteppingStone's performance was comparable to MisII, a state-of-the-art specialized tool for logic synthesis.

Analytical Validation

The authors developed a mathematical model to explain these gains. They found that the memory of stepping stones effectively replaces an exponential search factor ($b^l$) with a linear factor ($1/s * l * b$). This transformation confirms that the system's performance is not merely a result of heuristic tuning but a fundamental reduction in the effective search space.

Conclusion

SteppingStone successfully demonstrates how a system can learn from expensive, localized failures to achieve global efficiency. By bridging the gap between constrained and unconstrained search, it provides a scalable framework for complex optimization tasks. While the current implementation showed some limitations in optimizing for circuit area, the system's ability to achieve exponential speedups in logic synthesis marks a significant advancement in learning-based problem solving.

Summary updated

BibTeX
@inproceedings{ruby1991steppingstone,
  author = {David Ruby and Dennis F. Kibler},
  title = {{SteppingStone: An Empirical and Analytical Evaluation}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1991},
}
Figure