Using Macros at Run-Time

The purpose of learned macros is to speed up search in new problem instances. A classical search algorithm expands a node by considering low-level actions that can be applied to the current state. We add successor states that can be reached by applying the whole sequence of actions in a macro. We order these macro successors before the regular successors of a state. Macros affects neither the completeness nor the correctness of the original algorithm. The completeness of an original search algorithm is preserved since SOL-EP removes no regular successors of a state. Correctness is guaranteed by the following way of applying a macro to a state. Given a state $s_0$ and a sequence of actions $m=a_1a_2...a_k$ ($k = 2$ in the competition system), we say that $m$ is applicable to $s_0$ if $a_i$ can be applied to $s_{i-1}$, $i = 1,...,k$, where $s_i = \gamma(s_{i-1},a_i)$ and $\gamma(s,a)$ is the state obtained by applying $a$ to $s$.

When a given state is expanded at runtime, many instantiations of a macro could be applicable but only a few would actually be shortcuts towards a goal state. If all instantiations are considered, the branching factor can significantly increase and the induced overhead can be larger than the potential savings achieved by the useful instantiations. Therefore, the challenge is to select for state expansion only a small number of good macro instantiations. To determine what a ``good'' instantiation of a macro is, we use a heuristic method called helpful macro pruning. Helpful macro pruning is based on the relaxed graphplan computation that FF [12] performs for each evaluated state $s$. Given a state $s$, FF solves a relaxed problem, where the initial state is the currently evaluated state, the goal conditions are the same as in the real problem, and the actions are relaxed by ignoring their delete effects. This computation produces a relaxed plan $RP(s)$. In FF, the relaxed plan is used to heuristically evaluate problem states and prune low-level actions in the search space (helpful action pruning).

In addition, we use the relaxed plan to prune the set of macro-instantiations that will be used for node expansion. Since actions from the relaxed plan are often useful in the real world, we request that a selected macro and the relaxed plan match i.e., each action of the macro is part of the relaxed plan.