The Role of Macros in Tractable Planning

Abstract

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.

References in corpus (2)

• Structure and Complexity in Planning with Unary Operators
• Planning over Chain Causal Graphs for Variables with Domains of Size 5 Is NP-Hard

Cited by in corpus (6)

• Analyzing Search Topology Without Running Any Search: On the Connection Between Causal Graphs and h+
• Compositional Planning Using Optimal Option Models
• Algorithms and Limits for Compact Plan Representations
• Generalized Planning With Procedural Domain Control Knowledge
• Learning Macro-actions for State-Space Planning
• Mining useful Macro-actions in Planning