Component Abstraction - Enhanced Domain

Figure 1: CA-ED - Integrating component abstraction and macro-operators into a standard planning framework.

The first method produces a small set of macro-operators from the PDDL formulations of a domain and several training problems. The macro-operators are added to the initial domain formulation, resulting in an enhanced domain expressed in the same description language. The definitions of the enhanced domain and new problem instances can be given as input to any planner, with no need to implement additional support for macro-operators [6]. We call this approach CA-ED for Component Abstraction - Enhanced Domain.

Figure 1 shows the general architecture of CA-ED. The box Abstraction in the figure includes steps 1 - 3 above. Step 1 uses component abstraction, a technique that exploits permanent relationships between low-level features of a problem. Low-level features (i.e., constant symbols) linked by static facts (i.e., facts that remain true during planning) form a more complex unit called an abstract component.

At step 2, local analysis of abstract components builds macros that can speed up planning. CA-ED generates macros using a forward search process in the space of macro operators. A macro operator is built as an ordered sequence of operators linked through a mapping of the operators' variables. Applying a macro operator is semantically equivalent to applying all contained operators in the given order, respecting the macro's variable mapping and the interactions between preconditions and effects.

At step 3 (filtering), a set of heuristic rules is used to prune the search space and generate only macros that are likely to be useful. Macros are further filtered dynamically, based on their performance in solving training problems, and only the most effective ones are kept for future use.

The best macro operators that this method generates are added as new operators to the initial PDDL domain formulation, enhancing the initial set of operators. Hence, we need complete macro-operator definitions, including precondition and effect formulas. Expressing these formulas starting from the contained operators is easy in STRIPS, but hard in larger PDDL subsets such as ADL, where the preconditions and the effects of the contained operators can interact in complex ways. See Section 3.1 for a detailed explanation. In CA-ED no work is required to implement step 4, since the planner makes no distinction between a macro operator and a normal operator. Once the enhanced domain formulation is available in standard STRIPS, any planner can be used to solve problem instances.

The architecture of CA-ED has two main limitations. First, component abstraction can currently be applied only to domains with static facts in their formulation. Second, adding macros to the original domain definition is limited to STRIPS domains.