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.
- Goal Ordering: This component uses a domain-independent "openness" heuristic to sequence subgoals, aiming to minimize potential interactions.
- Constrained Search: An efficient incremental hill-climbing algorithm that attempts to solve subgoals sequentially while protecting those already achieved.
- Unconstrained Search: When the constrained search reaches an impasse, this component is activated. It relaxes subgoal protections to find a localized brute-force solution.
- 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."
- 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.
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