Macro-Actions in Planning

A macro-action, as used in planning, is a meta-action built from a sequence of action steps. In forward-chaining planning, applying a macro-action to a state produces a successor corresponding to the application of a series of actions. In this way, the use of macro-actions can be thought of as extending the neighbourhood of successors visible from each state to selectively introduce states which hitherto would only have been visible after the application of several steps. If the additional states introduced are chosen effectively, an increase in planner performance can be realised; whereas if the additional states are chosen poorly, the performance of the planner decreases due to the increased branching factor.

The use of macro-actions in planning has been widely explored. Most techniques use an off-line learning approach to generate and filter macro-actions before using them in search. Early work on macro-actions began with a version of the STRIPS planner--known as ABSTRIPS [Fikes & Nilsson 1971]--which used previous solution plans (and segments thereof) as macro-actions in solving subsequent problems. MORRIS [Minton 1985] later extended this approach by adding some filtering heuristics to prune the generated set of macro-actions. Two distinct types of macro-actions were identified in this approach: S-macros--those that occur frequently during search--and T-macros--those that occur less often but model some weakness in the heuristic. Minton observed that the T-macros, although used less frequently, offered a greater improvement in search performance. The REFLECT system [Dawson & Siklossy 1977] took the alternative approach of forming macro-actions based on preprocessing of the domain. All sound pairwise combinations of actions were considered as macro-actions and filtered through some basic pruning rules. Due to the small size of the domains with which the planner was reasoning, the number of macro-actions remaining following this process was sufficiently small to use in planning.

More recent work on macro-actions includes that on Macro-FF [Botea et al. 2005]. Macro-actions are extracted in two ways: from solution plans; and by the identification of statically connected abstract components. An offline filtering technique is used to prune the list of macro-actions. Another recent approach to macro-action generation [Newton et al. 2005] uses a genetic algorithm to generate a collection of macro-actions, and then filters this collection through an offline filtering technique similar to that used by Macro-FF.