next up previous
Next: Generating Macros Up: Using Macros from Solutions Previous: Using Macros from Solutions


SOL-EP was designed with the goal of eliminating the main limitations of CA-ED. Specifically, we wanted to extend the applicability of CA-ED to larger classes of domains. Since CA-ED generates macros based on component abstraction, its applicability is limited to domains with static predicates in their definition. SOL-EP generates macros from solutions of sample problems, with no restrictions caused by the nature of a domain's predicates.

Furthermore, CA-ED is limited to relatively simple subsets of PDDL such as STRIPS. Since CA-ED adds macros as new operators to the original domain, complete definitions of macros, including precondition and effect formulas, are required. These formulas are easy to obtain in STRIPS, as shown in Figures 7 and 8. However, adding macros to an ADL domain file becomes unfeasible in practice for two main reasons. First, the precondition and effect formulas of a macro are hard to infer from the formulas of contained operators. Second, even if the previous issue is solved and a macro with complete definition is added to a domain, the costs for pre-instantiating it into ground macro-actions can be large.

Figure 11: Operator MOVE in ADL Airport.
\hspace{0.0em} \= (:acti... ?a ?d2)) \\
\> \quad \= ) \\

To illustrate how challenging the formula inference is in ADL, consider the example in Figure 11, which shows operator MOVE from the ADL Airport domain used in IPC-4. The preconditions and the effects of this operator are quite complex formulas that include quantifiers, implications and conditional effects. Assume we want to compose a macro that applies two MOVE actions in a row with a given parameter mapping. To achieve a complete definition of macro MOVE MOVE, its precondition and effect formulas would have to be automatically composed by analyzing how the preconditions and effects of the two contained operators interact. We could not find a straight-forward way to generate a macro's formulas, so we decided to move towards an alternative solution that is presented later in this subsection.

Even if the above issue is solved and macros can be added as new domain operators, pre-instantiating a macro into ground actions can be costly. Many top-level planners, including FF, pre-instantiate the domain operators into all possible ground actions that might be applied in the problem instance at hand. The cost of instantiating one operator is exponential in the total number of parameters and quantifier variables. Macros tend to have larger numbers of parameters and quantifiers and therefore their instantiation can significantly increase the total preprocessing costs. ADL Airport is a good illustration of how important this effect can be. As shown in Section 5.2, the preprocessing is so costly as compared to the main search that it dominates the total cost of solving a problem in this domain. Further increasing the preprocessing costs with new operators is not desirable in such domains.

Our solution for ADL macros is to represent a SOL-EP macro as a list of atomic actions. Precondition and effect formulas are not explicitly provided. Rather, they are determined at run-time, when a macro is dynamically instantiated by applying its action sequence.

The benchmarks used in IPC-4 emphasize the need to address the issues described above. Many competition domains were provided in both STRIPS and ADL formulations. The ``main'' definition was in ADL and, for planners that could not take ADL domains as input, STRIPS compilations of each ADL domain were provided. We could only run our system on ADL domains. The reason is that in STRIPS compilations of ADL domains, a distinct domain file was generated for each problem instance. However, our learning approach requires several training problems for each domain.

next up previous
Next: Generating Macros Up: Using Macros from Solutions Previous: Using Macros from Solutions
Adi Botea 2005-08-01