Learning Problem Classes by Means of Experimentation and Generalization

Agustin A. ArayaAAAI 1984

Abstract

This paper introduces DARWIN, a system designed to improve the efficiency of physics problem-solving through empirical learning. By performing "mental experiments"—systematically perturbing problem parameters—DARWIN identifies general problem classes that allow for simplified solution methods. This approach bridges the gap between slow, general-purpose solvers and fast, specialized heuristics, demonstrating how an AI can transition from a novice to an expert-like state through practice.

Introduction: Overcoming the Brittleness of Expert Systems

In the early 1980s, expert systems were often criticized for their "brittleness." While capable of solving complex tasks, they lacked the flexibility and optimization skills of human experts. Specifically, these systems struggled to recognize unnecessarily complex solutions, failed to explore problem variations to find better heuristics, and lacked the memory to avoid re-solving identical problems from scratch.

DARWIN addresses these gaps by focusing on the transition from a general method—one that is robust but computationally expensive—to a specialized method that is simple and fast but limited in scope. The core challenge lies in defining the "problem class": the precise boundaries within which a simplified shortcut remains valid. By automating this discovery process, DARWIN allows a system to "learn" its way out of inefficiency.

The DARWIN Architecture and Learning Cycle

The system consists of two primary components: a Problem Solver (PS) and a Learning Agent (LA). Their interaction follows a rigorous three-stage cycle designed to identify and codify shortcuts:

  1. Detection: The LA monitors the PS during problem-solving. If a solution reveals that certain variables or equations were redundant (e.g., terms canceling out or variables that never entered the final calculation), the LA flags the problem as a potential "simplified case."
  2. Experimentation & Generalization: This is the core innovation. To map the boundaries of the simplified case, the system generates variations of the original problem.
  3. T-vars (True variations): Changes to the problem where the shortcut is expected to hold (e.g., changing the absolute length of a lever while keeping forces symmetrical).
  4. F-vars (False variations): Changes intended to break the shortcut (e.g., moving one force so the symmetry is lost).
  5. Mutual Support Principle (MSP): A heuristic that prunes the problem class description by assuming that the final rule should be a conjunction of predicates that collectively reject negative instances.
  6. Method Derivation: Once the class is defined (e.g., "horizontal levers with symmetrical forces"), DARWIN constructs a specialized, stripped-down solver and adds it to its permanent toolkit.
Figure 1: The initial physics problem involving a lever with symmetrical forces and supports.

Empirical Learning via Perturbation

Unlike contemporary systems that relied on deductive reasoning from first principles (such as Explanation-Based Learning), DARWIN is fundamentally empirical. It treats the problem domain as a laboratory, using active learning to create its own training data. By perturbing attributes such as angles, positions, and magnitudes, the system discovers which features are essential to the simplified solution.

Figure 4: A variation of the initial problem where force angles are perturbed to test the boundaries of the simplified solution class.

To manage the vast search space of possible variations, DARWIN employs a Predicate Hierarchy. It evaluates spatial relations first, followed by relations between attributes (e.g., "equal magnitude"), and finally specific numerical values. This structured search allows the system to find the most general possible description for a problem class without exhaustive testing of every possible parameter combination.

Results and Computational Performance

The system was tested in the domain of elementary physics, specifically interacting rigid bodies in equilibrium. In a landmark example, DARWIN successfully generalized from a specific problem involving a 15ft lever with two 120lb forces to a universal rule for any horizontal lever with symmetrical forces and pivots.

This learning process was computationally intensive for its time. Generalizing the lever rule required generating and classifying approximately 300 variations. While solving a single problem took 9 seconds, the one-time "study" cost for a new class was roughly 45 minutes (2,700 seconds). However, this investment yielded a permanent speedup for all future problems within that class, effectively transforming the system from a slow generalist into a fast specialist for that specific problem type.

Limitations and Future Directions

Despite its success, DARWIN faces several challenges that highlight the difficulties of autonomous learning:

  • Vocabulary Constraints: The system's ability to generalize is strictly limited by its predefined set of predicates. If a shortcut depends on a concept the system cannot describe, it will fail to form a correct generalization.
  • Well-Formedness: While physics allows for relatively easy generation of "legal" variations, other domains might require complex rules to ensure that perturbed problems remain valid and physically possible.
  • Scaling: As the system takes on more learning tasks, its internal complexity grows. Future work would need to address how to manage a massive library of specialized methods without introducing new inefficiencies in method selection.

Conclusion

DARWIN demonstrates a powerful approach to learning through experimentation. By bridging empirical observation with heuristic generalization, it provides a blueprint for how AI systems can autonomously optimize their performance through practice, moving beyond the brittleness of early expert systems toward a more flexible, expert-like capability.

Summary updated

BibTeX
@inproceedings{araya1984learning,
  author = {Agustin A. Araya},
  title = {{Learning Problem Classes by Means of Experimentation and Generalization}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1984},
}
Figure