Abstract

Hierarchical planning is widely acknowledged as an effective technique for reducing search, but the properties that make the technique effective are not well understood. This paper formally defines hierarchical planning, shows that the technique can reduce an exponential search space to a linear one, and identifies the assumptions under which this analysis holds. Since these assumptions would be difficult to guarantee in general, the paper identifies the monotonicity property, a heuristic for evaluating abstraction spaces. Lastly, the paper presents an algorithm for producing abstractions with this property and then describes how the algorithm completely automates a reformulation of the Tower of Hanoi puzzle, which reduces the search space of the puzzle from exponential to linear.
* The author is supported by an Air Force Laboratory Graduate Fellowship through the Human Resources Laboratory at Brooks AFB …

Date

September 22, 1990

Authors

Craig A Knoblock

Book

Change of Representation and Inductive Bias

Pages

81-104

Publisher

Springer US