The Role of Macros in Tractable Planning
This work addresses planning efficiency for AI systems, but it appears incremental as it generalizes existing classes and modifies algorithms.
The paper tackles the problem of planning by introducing an algorithm that optimally solves planning problems in the inverted tree reducible class, achieving polynomial time and space complexity even for exponentially long plans through the use of macros.
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.