On-the-fly Macros

Macros have long been studied in AI planning [9, 18]. Many domain-dependent applications of macros have been exhibited and studied [15, 17, 12]; also, a number of domain-independent methods for learning, inferring, filtering, and applying macros have been the topic of research continuing up to the present [2, 7, 20]. In this paper, we present a domain-independent algorithm that computes macros in a novel way. Our algorithm computes macros "on-the-fly" for a given set of states and does not require previously learned or inferred information, nor does it need any prior domain knowledge. We exhibit the power of our algorithm by using it to define new domain-independent tractable classes of classical planning that strictly extend previously defined such classes [6], and can be proved to include Blocksworld-arm 1 and Towers of Hanoi. We believe that this is notable as theoretically defined, domainindependent tractable classes have generally struggled to incorporate construction-type domains such as these two. We hence give theoretically grounded evidence of the computational value of macros in planning.