Abstract

This paper describes an automated approach to generating abstractions for the Tower of Hanoi and analyzes the use of these abstractions for problem solving. The analysis shows that the learned abstractions produce an exponential reduction in the size of the search space. Since few problem solvers actually explore the entire search space, the paper also presents an empirical analysis of the speedup provided by abstraction when a heuristic search is employed. The empirical analysis shows that the benefit of abstraction is largely determined by the portion of the base-level search space explored. Thus, using breadth-first search, which searches the entire space, abstraction provides an exponential reduction in search. However, using a depth-first search, the search reduction is smaller and depends on the amount of backtracking required to solve the problem.

Date

September 22, 1990

Authors

Craig A Knoblock

Journal

Working Notes of AAAI-90 Workshop on Automatic Generation of Approximations and Abstractions

Issue

4976

Pages

1-11

Publisher

Citeseer