Integrating Abstraction and Explanation-Based Learning in PRODIGY

Craig A. Knoblock, Steven Minton, Oren EtzioniAAAI 1991

Introduction

In the field of automated planning, researchers have long sought methods to improve the efficiency of search-based systems. Two prominent techniques emerged in the early 1990s: Abstraction, which simplifies a problem by removing details, and Explanation-Based Learning (EBL), which derives general search-control rules from specific problem-solving experiences. While both were designed to speed up planning, they often faced the "utility problem"—where the overhead of managing abstractions or matching complex learned rules outweighed the performance gains.

This paper presents a synergistic integration of these two approaches within the PRODIGY architecture. By using abstraction to decompose complex problems into simpler sub-problems, the system can learn more general and efficient search-control rules that would be difficult or impossible to acquire in the original, more detailed problem space.

The Challenge: Gaps in Individual Approaches

The authors identify significant limitations when using these techniques in isolation:

  1. Abstraction alone (via the ALPINE module): While ALPINE can automatically generate a hierarchy of problem spaces, it provides no guidance on how to navigate within each abstract space. The planner may still engage in exhaustive search at any given level.
  2. EBL alone: Standard EBL struggles with complex problems characterized by long solution traces or high "goal interference" (where achieving one goal necessitates undoing another). In such environments, EBL either fails to find a general explanation or produces rules that are too specific and computationally expensive to match.

Methodology: Integrating ALPINE and EBL

The researchers integrated two specific modules within the PRODIGY architecture:

  • ALPINE: This module generates an abstraction hierarchy based on the property of ordered monotonicity. This ensures that once a goal is satisfied at a high level of abstraction, it remains satisfied as the planner adds details at lower levels.
  • EBL: This module analyzes successful and failed planning traces to create "if-then" search control rules.

The Integration Strategy: Instead of applying EBL to the entire problem trace, the system runs EBL on the individual sub-problems defined by the abstraction hierarchy. Crucially, the resulting rules are indexed to the specific abstraction level where they were learned. This prevents the "match cost" explosion by ensuring the planner only considers rules relevant to its current level of detail.

Case Study: The Tower of Hanoi

The Tower of Hanoi serves as a primary example of how abstraction facilitates learning. In the full problem space, every move involves significant goal interference, making it difficult for EBL to extract a clean logic.

The state space of the 3-disk Tower of Hanoi problem, illustrating the complexity of transitions between initial and goal states.

By applying abstraction, the problem is broken down. At the highest level, the system might only consider the largest disk. Within this simplified space, the path to the goal is interference-free, allowing EBL to learn the fundamental recursive logic of the puzzle. When combined, abstraction and EBL completely eliminate search for this domain, allowing the system to solve the puzzle optimally and deterministically.

Experimental Results

The approach was further validated in a complex Machine-Shop Scheduling domain involving various parts, machines, and temporal constraints. The researchers tested four configurations: the base PRODIGY system, PRODIGY with ALPINE, PRODIGY with EBL, and the fully integrated system.

Performance comparison in the machine-shop domain, showing the total CPU time required as a function of the time bound per problem.

As shown in the performance data, the integrated system (Prodigy + Alpine + EBL) significantly outperformed all other configurations. While EBL alone and Abstraction alone provided some benefits, their combination yielded a non-linear improvement in robustness. The integrated system was able to solve a much higher percentage of problems within the given time bounds, demonstrating that the rules learned in abstract spaces are both more general and less expensive to compute.

Conclusion and Future Work

The integration of abstraction and EBL addresses the utility problem by simplifying the "theory" from which EBL learns and reducing the match cost of the resulting rules. By isolating sub-problems, abstraction allows EBL to overcome goal interference and learn more powerful control knowledge.

Future research directions include addressing "information hiding," where the cause of a planning failure might be located in a level of detail currently ignored by the abstraction. Developing EBL techniques that can explain failures bridging multiple levels of the hierarchy remains a key challenge for further enhancing the robustness of integrated planning systems.

Summary updated

BibTeX
@inproceedings{knoblock1991integrating,
  author = {Craig A. Knoblock and Steven Minton and Oren Etzioni},
  title = {{Integrating Abstraction and Explanation-Based Learning in PRODIGY}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1991},
}
Figure