Flexible Strategy Learning: Analogical Replay of Problem Solving Episodes

Manuela M. VelosoAAAI 1994 · OpenReview

Abstract

This paper describes the integration of analogical reasoning into general problem solving as a method of learning at the strategy level to solve problems more effectively. Learning occurs by the generation and replay of annotated derivational traces of problem solving episodes. The problem solver is extended with the ability to examine its decision cycle and accumulate knowledge from the chains of successes and failures encountered during its search experience. Instead of investing substantial effort deriving general rules of behavior to apply to individual decisions, the analogical reasoner compiles complete problem solving cases that are used to guide future similar situations. Learned knowledge is flexibly applied to new problem solving situations even if only a partial match exists among problems. We relate this work with other alternative strategy learning methods, and also with plan reuse. We demonstrate the effectiveness of the analogical replay strategy by providing empirical results on the performance of a fully implemented system, PRODIGY/ANALOGY, accumulating and reusing a large case library in a complex problem solving domain.

Introduction

Automated problem solvers often face a significant efficiency hurdle: the "reinvention of the wheel." When presented with a new task, traditional planners frequently explore vast search spaces from scratch, often repeating mistakes made in previous, similar episodes. While methods like macro-operators, control rules, and transformational analogy have been proposed to mitigate this, they often suffer from rigidity, high computational costs for rule derivation, or difficulty in adapting to structural changes in problems.

This paper introduces PRODIGY/ANALOGY, a system that addresses these challenges through strategic learning. By "remembering" the reasoning process behind past successes and failures, the system can solve new, complex problems more efficiently by replaying and merging multiple past experiences.

Methodology: Derivational Analogy

The core innovation of PRODIGY/ANALOGY is the use of Derivational Analogy. Unlike traditional plan reuse, which focuses on the final solution (the "what"), derivational analogy focuses on the reasoning process (the "why").

  1. Justification-Rich Traces: When the base planner (NOLIMIT) solves a problem, it records a "derivational trace." This trace contains justifications for every choice, including operator selection, variable bindings, and reasons for abandoning failed paths (e.g., detecting goal loops).
  2. Flexible Replay: The replay algorithm validates past justifications against the current state. It can skip irrelevant steps, search for new sub-solutions when needed, and interleave steps from multiple retrieved cases—a process known as case merging.
Derivational trace (b) vs. search tree (a) showing justifications for decisions.

Experimental Evaluation

The system was rigorously tested in a logistics transportation domain. The evaluation involved a library of 1,000 problems of varying complexity, involving the movement of packages between cities using trucks and airplanes. Problems scaled up to 20 goals and over 100 initial state literals. The case library was built incrementally, allowing the system to learn from simpler problems to tackle more complex ones.

Results and Key Insights

The empirical results demonstrate a significant improvement in both solvability and efficiency. As shown in the performance graphs, PRODIGY/ANALOGY dramatically outperformed the base planner.

Performance comparison between PRODIGY/ANALOGY and the base planner (NoLimit) across 1,000 problems.
  • Solvability Horizon: While the base planner (NoLimit) could only solve 458 out of 1,000 problems within a 350-second limit, PRODIGY/ANALOGY successfully solved all 1,000.
  • Speedup: For problems solvable by both, the analogical reasoner provided a 3.6x cumulative speedup, with individual cases showing up to 40x faster performance.
  • Solution Quality: Replaying past cases did not degrade solution quality; 92% of solutions were of equal or shorter length than those found by the base planner.

A key insight is that failures are as instructive as successes. By recording why a path failed, the solver can prune the search tree of a new problem immediately, significantly reducing the branching factor. Furthermore, replaying the derivation is more robust than replaying the solution, allowing for adaptation even in "partial matches."

Conclusion

PRODIGY/ANALOGY demonstrates that integrating analogical reasoning into a general problem solver can lead to substantial gains in efficiency and robustness. By focusing on the justifications behind decisions, the system avoids the "utility problem" common in other learning architectures. Future work will explore more sophisticated strategies for merging multiple cases and further refine the similarity metrics for case retrieval.

Summary updated

Abstract

This paper describes the integration of analogical reasoning into general problem solving as a method of learning at the strategy level to solve problems more effectively. Learning occurs by the generation and replay of annotated derivational traces of problem solving episodes. The problem solver is extended with the ability to examine its decision cycle and accumulate knowledge from the chains of successes and failures encountered during its search experience. Instead of investing substantial effort deriving general rules of behavior to apply to individual decisions, the analogical reasoner compiles complete problem solving cases that are used to guide future similar situations. Learned knowledge is flexibly applied to new problem solving situations even if only a partial match exists among problems. We relate this work with other alternative strategy learning methods, and also with plan reuse. We demonstrate the effectiveness of the analogical replay strategy by providing empirical results on the performance of a fully implemented system, PRODIGY/ANALOGY, accumulating and reusing a large case library in a complex problem solving domain.
BibTeX
@inproceedings{veloso1994flexible,
  author = {Manuela M. Veloso},
  title = {{Flexible Strategy Learning: Analogical Replay of Problem Solving Episodes}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1994},
  url = {https://openreview.net/forum?id=ByZg9RlO-S},
}
Figure