Mapping Explanation-Based Generalization onto Soar

Paul S. Rosenbloom, John E. LairdAAAI 1986

Introduction

In the mid-1980s, classical AI research saw the emergence of two influential paradigms: Explanation-Based Generalization (EBG) and the Soar cognitive architecture. EBG provided a formal method for learning general rules from single examples by "explaining" them through a pre-existing domain theory. Meanwhile, Soar was developed as a "General Cognitive Architecture" designed to solve diverse problems and learn through a process called chunking. This paper establishes a crucial link between these two fields, demonstrating that Soar’s chunking mechanism is a functional implementation of EBG.

Structural Mapping

The core contribution of the paper is a structural mapping between the four pillars of EBG and the components of the Soar architecture. This mapping proves that Soar provides a uniform and computationally efficient environment for performing EBG.

Table 1: Mapping of EBG components to Soar architectural elements.

As illustrated in Table 1, the Goal Concept in EBG is represented by a Goal in Soar. The Training Example corresponds to the Pre-goal Situation—the state of the world before a problem-solving impasse occurs. The Domain Theory is embodied by the Problem Space (the set of operators and productions), and the Operationality Criterion is naturally defined as Pre-goal Predicates—any information already present in working memory before the subgoal was created.

The Learning Mechanism: Backtracing

Soar’s learning is driven by backtracing. When the system encounters an impasse, it creates a subgoal. Once resolved, Soar "backtraces" through the productions that led to the result, identifying only the essential features of the initial state. It then creates a "chunk"—a new production rule—that generalizes this logic for future use.

A key technical advantage of Soar’s approach is its use of instantiated regression. While standard EBG often requires expensive symbolic unification to regress general variables, Soar regresses specific instances and variablizes the result at the end. This method is significantly more efficient, though it requires careful representation to avoid creating rules that are too specific.

Case Studies: Symbolic Integration and Safe-to-Stack

The authors validated their mapping using classic AI benchmark tasks. In the Safe-to-Stack problem, the system learns the conditions under which it is safe to stack objects based on properties like weight and fragility. In the Symbolic Integration task, Soar learns search-control rules, such as determining when to move a coefficient outside an integral.

Figure 1: A trace of the symbolic integration task in Soar, illustrating the stages of operator selection and evaluation.

Figure 1 shows the process of operator selection and evaluation during symbolic integration. By observing successful solution paths, Soar generates chunks that act as search-control rules, allowing the system to bypass future impasses in similar mathematical contexts.

Key Insights and Conclusion

The unification of EBG and Soar offers several significant insights:

  • Uniformity of Learning: In Soar, learning a "concept" (e.g., what defines a chair) and learning "search control" (e.g., which move to make next) use the exact same underlying mechanism.
  • Dynamic Operationality: Unlike EBG, where operationality is often a fixed global decision, in Soar it is contextual—anything known before the current impasse is considered operational.
  • Architectural Integration: Soar can naturally navigate type hierarchies during learning without needing specialized modules.

While challenges such as handling imperfect domain theories and integrating similarity-based learning remain, this work successfully demonstrates that a general cognitive architecture can provide a robust, efficient foundation for formal analytical learning.

Summary updated

BibTeX
@inproceedings{rosenbloom1986mapping,
  author = {Paul S. Rosenbloom and John E. Laird},
  title = {{Mapping Explanation-Based Generalization onto Soar}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1986},
}
Figure