next up previous
Next: Macro Ranking and Filtering Up: Creating Macro-Operators Previous: Creating Macro-Operators


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.
\begin{figure}\begin{center}\par
\begin{tabbing}
\par
\hspace{0.0em} \= {\bf v...
... = A(m) \cup \{a\}$; \\
\> \> \} \\
\}
\end{tabbing}
\end{center}\end{figure}

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:

Figure 9: Operator TAKE-IMAGE and macro-operator TAKE-IMAGE--TAKE-IMAGE in Rovers. This macro is rejected by the locality rule.
\begin{figure}\begin{center}\par
\begin{tabbing}
\par
(:action TAKE-IMAGE \\
...
...m) (not (calibrated ?i1 ?r1))) \\
)
\par
\end{tabbing}
\end{center}\end{figure}

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.
\includegraphics[width=.4\linewidth]{localstaticprecs.eps}


next up previous
Next: Macro Ranking and Filtering Up: Creating Macro-Operators Previous: Creating Macro-Operators
Adi Botea 2005-08-01