Solution - Enhanced Planner

Figure 3: The general architecture of SOL-EP. Enhanced Planner means a planner with capabilities to handle macros.

The second abstraction method presented in this article does not suffer from the above limitations, and is applicable to a larger class of problems. We call this approach SOL-EP, which stands for Solution - Enhanced Planner. SOL-EP extracts macros from solutions of training problems and uses them in a planner enhanced with capabilities to handle macros. The general architecture of this approach is shown in Figure 2. As before, the module Abstraction implements steps 1 - 3. Instead of using static facts and component abstraction as in CA-ED, step 1 in SOL-EP processes the solutions of training problems. To extend applicability from STRIPS to ADL domains, a different macro representation is used as compared to CA-ED. A SOL-EP macro is represented as a sequence of operators and a mapping of the operators' variables rather than a compilation into a single operator with complete definition of its precondition and effects. As shown in Section 3.1, for ADL domains, it is impractical to use macros with complete definition.

For this reason, SOL-EP macros cannot be added to the original domain formulation as new operators anymore. They are distinct input data for the planner, and for step 4 the planner is enhanced with code to handle macro operators. Since SOL-EP is more general, we used this approach in the fourth planning competition IPC-4.

We implemented the ideas presented in this article in MACRO-FF, an adaptive planning system developed on top of FF version 2.3 [12]. FF 2.3 is a state-of-the-art fully automatic planner that uses a heuristic search approach. The solving mechanism of FF has two main phases: preprocessing and search. The preprocessing phase builds data structures needed at search time. All operators are instantiated into ground actions, and all predicates are instantiated into facts. For each action, pointers are stored to all precondition facts, all add-effect facts, and all delete-effect facts. Similarly, for each fact $f$, pointers are stored to all actions where $f$ is a precondition, to all actions where $f$ is an add effect, and to all actions where $f$ is a delete effect. This information is instantly available at run-time, when states are evaluated with the relaxed graphplan heuristic.

MACRO-FF adds the ability to automatically learn and use macro-actions, with the goal of improving search. MACRO-FF also includes engineering enhancements that can reduce space and CPU time requirements that were performance bottlenecks in some of the test problems. The engineering enhancements affect neither the number of expanded nodes nor the quality of found plans.

The contributions of this article include a detailed presentation of MACRO-FF. We present and compare two methods that automatically create and use macro-operators in domain-independent AI planning. Experimental evaluation is focused on several main directions. First, the impact of the engineering enhancements is analyzed. Then we evaluate how SOL-EP macros implemented in the competition system can improve planning. These experiments use as testbeds domains used in IPC-4. Finally, we compare the two abstraction methods on test instances where both techniques are applicable, and evaluate them against planning with no macros.

The rest of the paper is structured as follows: The next two sections describe CA-ED and SOL-EP respectively. Section 4 summarizes the implementation enhancements that we added to FF. We present experimental results and evaluate our methods in Section 5. In Section 6 we briefly review related work and discuss the similarities and differences with our work. The last section contains conclusions and ideas for future work.