  This paper presents several new tractability results for planning based on
macros. We describe an algorithm that optimally solves planning problems in a
class that we call inverted tree reducible, and is provably tractable for
several subclasses of this class. By using macros to store partial plans that
recur frequently in the solution, the algorithm is polynomial in time and space
even for exponentially long plans. We generalize the inverted tree reducible
class in several ways and describe modifications of the algorithm to deal with
these new classes. Theoretical results are validated in experiments.
