Strategies for Learning Search Control Rules: An Explanation-based Approach

Steven Minton, Jaime G. Carbonell

Abstract

This paper describes an approach to Explanation-Based Learning (EBL) that enables autonomous systems to acquire search control rules from a variety of problem-solving experiences, including successes, failures, and goal interactions. Implemented in the PRODIGY system, the method utilizes a top-down technique called Explanation-based Specialization (EBS). By reasoning about its own search architecture and domain theory, PRODIGY generates efficient rules that prune search spaces and avoid redundant or incorrect moves. The research highlights the significance of learning from failure and addresses the "utility problem" by monitoring the cost-effectiveness of learned rules.

Introduction

In the field of automated problem solving, early learning systems often focused on creating "macro-operators" — sequences of actions that represent successful solution paths. While effective for repetitive tasks, this approach lacks the depth required for complex reasoning. Steven Minton and Jaime Carbonell argue that intelligent systems must understand why certain paths fail or why goals conflict. This paper introduces a unified framework for learning search control rules through explanation, allowing a system to guide its future searches more intelligently.

Methodology: Explanation-based Specialization (EBS)

The core of the PRODIGY system is the Explanation-based Specialization (EBS) algorithm. Unlike traditional bottom-up EBL, which generalizes specific ground-level proofs, EBS operates top-down:

  1. Proof Schemas: The system utilizes high-level templates describing general search phenomena, such as "Operator Fails" or "Goal Interaction."
  2. Theory of the Solver: PRODIGY maintains a meta-level theory of its own search algorithm. This allows it to explain internal decision-making, such as why a specific subgoal was prioritized or why a node was abandoned.
  3. Domain Theory: The system relies on a formal description of the environment. In the classic Blocks World domain, this includes operators like PICKUP, STACK, and UNSTACK.
STRIPS-style operators for the Blocks World domain.

By specializing abstract schemas using specific problem-solving traces, EBS identifies the "weakest sufficient conditions" for a control rule, ensuring the resulting rules are as general as possible.

Learning from Failure and Search Control

A pivotal insight of this work is that failure is often a more potent teacher than success. When the system encounters a dead end or a cycle, it generates an explanation for the failure. This explanation is then transformed into a "rejection rule" that prevents the system from making similar mistakes in the future.

A search tree in PRODIGY illustrating subgoals, failures, and the eventual success path.

As shown in the search tree above, PRODIGY tracks subgoals and identifies failures (e.g., goal-stack cycles). For instance, if the system attempts to pick up a block that is already supporting another, it learns a rule to reject that operator until the top block is removed. This meta-reasoning turns abstract search failures into concrete logic.

The Utility Problem

A common pitfall in learning systems is the "utility problem": as more rules are added, the time spent checking if a rule applies (matching cost) can exceed the time saved by pruning the search. PRODIGY addresses this by actively monitoring the utility of each learned rule. It retains only those rules that demonstrate a net positive impact on problem-solving efficiency over time.

Key Results and Generalization

The authors demonstrated PRODIGY's effectiveness in the Blocks World and more complex domains like machine shop scheduling. Key achievements include:

  • Pruning Goal-Stack Cycles: The system learns to detect and avoid states that lead back to previous subgoals.
  • Goal Interaction Analysis: PRODIGY discovers optimal stacking strategies (e.g., building from the bottom up) by explaining why certain goal orderings cause interference.
  • Effective Generalization: Rules learned from specific instances are correctly generalized to apply to any objects in similar configurations.

Conclusion

The EBS approach in PRODIGY represents a significant advancement in explanation-based learning. By treating the search process itself as a domain for study and emphasizing learning from failure, the system acquires robust control knowledge. Future work aims to relax the requirement for a perfect domain theory and explore the complex interactions within large sets of learned rules.

Summary updated

BibTeX
@inproceedings{minton1987strategies,
  author = {Steven Minton and Jaime G. Carbonell},
  title = {{Strategies for Learning Search Control Rules: An Explanation-based Approach}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1987},
}
Figure