Fast Planning with Iterative Macros

Adi Botea, Martin Müller, Jonathan Schaeffer

Research on macro-operators has a long history in planning and other search applications. There has been a revival of interest in this topic, leading to systems that successfully combine macro-operators with current state-of-the-art planning approaches based on heuristic search. However, research is still necessary to make macros become a standard, widely-used enhancement of search algorithms. This article introduces sequences of macro-actions, called iterative macros. Iterative macros exhibit both the potential advantages (e.g., travel fast towards goal) and the potential limitations (e.g., utility problem) of classical macros, only on a much larger scale. A family of techniques are introduced to balance this trade-off in favor of faster planning. Experiments on a collection of planning benchmarks show that, when compared to low-level search and even to search with classical macro-operators, iterative macros can achieve an impressive speed-up in search.