Report Number: CS-TR-96-1569
Institution: Stanford University, Department of Computer Science
Title: Using Automatic Abstraction for Problem-Solving and Learning
Author: Unruh, Amy
Date: April 1996
Abstract: Abstraction is a powerful tool for controlling search combinatorics. This research presents a framework for automatic abstraction planning, and a family of associated abstraction methods, called SPATULA. The framework provides a structure within which different parameterized methods for automatic abstraction can be instantiated to generate abstraction planning behavior, and provides an integrated environment for abstract problem-solving and learning. A core idea underlying the abstraction techniques is that abstraction can arise as an obviation response to impasses in planning. Abstraction is performed at problem-solving time with respect to impasses in the current problem context, and thus the planner generates abstractions in response to specific situations. This approach is used to reduce the cost of lookahead evaluation searches, by performing abstract search in problem spaces which are automatically abstracted from the ground spaces during search. New search control rules are learned during abstract search; they constitute an abstract plan used in future situations, and produce an emergent multi-level abstraction behavior. The abstraction method has been implemented and evaluated. It has been shown to: reduce planning time, while still yielding good solutions; reduce learning time; and increase the effectiveness of learned rules by enabling them to transfer more widely.
http://i.stanford.edu/pub/cstr/reports/cs/tr/96/1569/CS-TR-96-1569.pdf