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

TL;DR

This paper introduces PRODIGY, a system that learns to improve its problem-solving efficiency by explaining not just successes, but also failures and goal interactions. By analyzing why certain choices were made and their consequences, PRODIGY generates specialized control rules that guide future searches more effectively, going beyond traditional explanation-based learning (EBL) that focuses solely on successful solutions.

What Problem Does This Paper Address?

Traditional explanation-based learning (EBL) systems primarily learn by analyzing successful problem-solving traces. They explain why a particular solution worked and generalize this knowledge into control rules to speed up future problem-solving. However, this approach is limited because it ignores the vast amount of information available in problem-solving failures and the complex interactions between different goals. The challenge is to leverage these other phenomena to build more robust and efficient problem solvers. The authors argue that learning from failures and goal interactions can provide crucial insights that learning from successes alone misses, especially in complex domains where initial formalizations might be suboptimal.

Methods

The core of PRODIGY's learning capability lies in its Explanation-based Specialization (EBS) algorithm. Unlike generalization-based EBL, EBS works top-down, specializing a high-level target concept using a training example and a domain theory.

Here's how it works:

  • Target Concepts: PRODIGY defines four meta-level "target concepts" that represent different learning opportunities:
  • SUCCEEDS: A control choice leads to a solution.
  • FAILS: A control choice leads to no solution.
  • SOLE-ALTERNATIVE: A choice is the only viable option among alternatives.
  • GOAL-INTERACTION: A choice leads to a situation where a goal must be re-achieved or conflicts with another goal.
  • Explanation-Based Specialization (EBS): When a target concept is identified (e.g., an operator failed), EBS constructs an explanation by specializing proof schemas. This process involves recursively breaking down the target concept using domain and architecture-level axioms until primitive concepts are reached. The result is a generalized description of the weakest conditions under which the phenomenon occurred.
  • Control Rule Generation: The specialized descriptions are then used to generate search control rules. These rules can be of different types:
  • Preference rules: To order candidate goals or operators.
  • Rejection rules: To discard unsuitable choices.
  • Selection rules: To pick the best candidate.
  • Utility Estimation: Learned rules are assigned a utility estimate based on their cumulative cost of matching versus their savings in search time. Only rules that prove useful are retained.

The paper highlights that EBS is particularly suited for learning from a problem solver's own performance traces, as it doesn't require a pre-existing ground-level explanation.

Datasets

Not discussed in the paper. The examples are drawn from the "blocks world" domain, a standard AI benchmark for planning and problem-solving.

Key Insights and Ideas

  • Learning from Failure is Crucial: The paper strongly advocates for learning from failures. Explaining why a choice failed can lead to more powerful and general control rules than solely learning from successes. For instance, identifying that PICKUP failed because an object wasn't on the table provides a direct reason to reject it in similar situations.
  • Goal Interactions as a Learning Opportunity: PRODIGY explicitly models and learns from goal interactions (e.g., when achieving one goal negates a prerequisite for another). This allows it to learn preference rules that guide the order of goal achievement to avoid such conflicts, or to manage them more efficiently.
  • EBS: A Top-Down Specialization Approach: EBS is presented as a novel approach that differs from traditional generalization-based EBL. By starting with a high-level concept and specializing it, EBS can directly generate explanations for failures and interactions without needing to construct a full, instantiated proof first.
  • Declarative and Extensible Framework: The use of declarative target concepts and domain theories makes PRODIGY's learning system extensible. New optimization strategies can be incorporated by adding new target concepts and their associated proof schemas.
  • Utility-Driven Rule Retention: The system doesn't just learn rules; it actively evaluates their usefulness, ensuring that the knowledge base remains efficient and relevant.

Key Results

The paper demonstrates PRODIGY's ability to learn effective search control rules through examples in the blocks world.

  • Learning from Success: The paper shows how learning from a successful UNSTACK operation can lead to a rule that selects UNSTACK when an object needs to be picked up and is not on the table.
  • Learning from Failure: It illustrates how learning from the failure of PICKUP leads to a rejection rule, preventing wasted search.
  • Learning from Goal Interactions: The example of stacking blocks demonstrates how PRODIGY learns a preference rule to build stacks from the bottom up, avoiding prerequisite violations.

While specific quantitative speedup figures are not the primary focus, the qualitative examples strongly suggest that the learned control rules significantly improve search efficiency by pruning suboptimal branches of the search tree.

Limitations and Future Work

  • Domain Formalization: The paper acknowledges that the utility of optimization techniques, including those in PRODIGY, depends heavily on the task domain and its formalization. Suboptimal formalizations can still pose challenges.
  • Experimentation Module: The "learning-by-experimentation" module, designed for refining domain knowledge, was under development at the time of writing.
  • Inductive Proofs: The paper briefly mentions the possibility of formulating inductive proofs for more general learning, which was not fully explored.
  • Extensibility: While the framework is designed to be extensible, the paper focuses on four specific target concepts. Future work would involve exploring and implementing additional target concepts and optimization strategies.
  • Utility Estimation: The paper mentions utility estimation but doesn't delve into its specifics, noting it as a topic for further discussion.

Summary updated

BibTeX
@inproceedings{1987strategies,
  title = {{Strategies for Learning Search Control Rules: An Explanation-based Approach}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1987},
}
Figure