Abstraction in Problem

A b s t r a c t i o n i n P r o b l e m Solving and Learning*

Amy Unruh Computer Science Dept. Stanford University 701 Welch Rd., Bldg. C Palo A l t o , CA 94304 Abstract

Abstraction has proven to be a powerful tool for controlling the combinatorics of a problemsolving search. It is also of critical importance for learning systems. In this article we present, and evaluate experimentally, a general abstraction m e t h o d — impasse-driven abstraction which is able to provide necessary assistance to b o t h problem solving and learning. It reduces the amount of t i m e required to solve problems, and the t i m e required to learn new rules. In a d d i t i o n , it results in the acquisition of rules t h a t are more general than would have otherwise been learned.

P a u l S. R o s e n b l o o m Information Sciences Institute University of Southern California 4676 Admiralty Way Marina del Rey, CA 90292

The four key requirements such a technique should satisfy are: 1. Apply in any domain. 2. Reduce problem solving time. 3. Reduce learning time (therefore help in intractable domains). 4. Increase the transfer of learned rules. The first requirement implies that the technique must be a general weak method that is applicable to domains without additional domain-specific knowledge about how to perform the abstraction. Most problem solvers that utilize abstractions do so only when the appropriate abstractions have been prespecified for them. The second requirement implies that, on average, the time to solve problems w i t h abstraction should be less than the t i m e without. Implicit in this requirement is also that this should be true even if only one problem is being solved; that is, abstraction should help immediately, on the first problem seen in the domain. The t h i r d requirement i m plies that abstraction should be integral to the rule creation process. If the problem-solving time necessary to learn a rule is to be reduced, an approach that simply abstracts...