Macro Generation

For an abstract type $at$, macros are generated by performing a forward search in the space of macro operators. Macros perform local processing within a component of type $at$, according to the locality rule detailed below.

Figure 8: Adding operators to a macro.

The root state of the search represents an empty macro (i.e., empty sets of operators, variables, preconditions, and effects). Each search step appends an operator to the current macro, and fixes the variable mapping between the new operator and the macro. Adding a new operator $o$ to a macro $m$ modifies $P(m)$, $A(m)$, and $D(m)$ as shown in Figure 8. Even if not explicitely shown in the figure, the variable mapping $vm$ in the procedure is used to check the identity between operator's predicates and macro's predicates (e.g., in $p \notin A(m) \cup P(m)$). Two predicates are considered identical if they have the same name and the same set of parameters. The variable mapping $vm$ tells what variables (parameters) are common in both the macro and the new operator.

The search is selective: it includes a set of rules for pruning the search tree and for validating a built macro operator. Validated macros are goal states in this search space. The search enumerates all valid macro operators. The following pruning rules are used for static filtering:

• The negated precondition rule prunes operators with a precondition that matches one of the current delete effects of the macro operator. This rule avoids building incorrect macros where a predicate should be both true and false.
• The repetition rule prunes operators that generate cycles. A macro containing a cycle is either useless, producing an empty effect set, or it can be written in a shorter form by eliminating the cycle. A cycle in a macro is detected when the effects of the first $k_1$ operators are the same as for the first $k_2$ operators, with $k_1 < k_2$. In particular, if $k_1 = 0$ then the first $k_2$ operators have no effect.
• The chaining rule requires that for consecutive operators $o_1$ and $o_2$ in a macro, the preconditions of $o_2$ must include at least one positive effect of $o_1$. This rule is motivated by the idea that the action sequence of a macro should have a coherent meaning.
• We limit the size of a macro by imposing a maximal length and a maximal number of preconditions. Similar constraints could be added for the number of variables or effects, but we found this unnecessary. Limiting the number of preconditions indirectly limits the number of variables and effects. Large macros are generally undesirable, as they can significantly increase the preprocessing costs and the cost per node in the planner's search.
• The locality rule is meant to prune macros that change two or more abstract components at the same time. All local static preconditions of an acceptable macro are part of the same abstract component. Given an abstract type $at$ and a macro $m$, let the local static preconditions be the static predicates that are part of both $m$'s preconditions and $at$'s edges. Local static preconditions and their parameters in $m$'s definition define a graph structure (different variable bindings for the operators that compose $m$ can create different graph structures). To implement the idea of locality we require that this graph is isomorphic with a subgraph of $at$.

Figure 9: Operator TAKE-IMAGE and macro-operator TAKE-IMAGE--TAKE-IMAGE in Rovers. This macro is rejected by the locality rule.

As an example of the locality rule, consider the Rovers abstract type $at$ in Figure 5 and the macro $m$ TAKE-IMAGE--TAKE-IMAGE shown in Figure 9 (this figure also shows the definition of the TAKE-IMAGE operator). Intuitively, $m$ involves two components, since two distinct cameras and two distinct rovers are part of the macro's variables. We show that this macro is rejected by the locality rule. The graph corresponding to the local static preconditions of $m$ and $at$ is shown in Figure 10. Obviously, this is not a subgraph of $at$'s graph shown in Figure 5, so $m$ is rejected.

Figure 10: Local static preconditions of macro TAKE-IMAGE--TAKE-IMAGE with respect to the abstract type in Figure 5. As the picture shows, these correspond to a graph with 4 nodes and 2 edges.