next up previous
Next: Using Macros from Solutions Up: Creating Macro-Operators Previous: Macro Generation


Macro Ranking and Filtering

The goal of ranking and filtering is to reduce the number of macros and use only the most efficient ones for solving problems. The overhead of poor macros can outweight their benefit. This is known under the name of the utility problem [24]. In CA-ED, adding more operators to a domain increases the preprocessing costs and the cost per node in the planner's search.

We used a simple but efficient and practical approach to dynamic macro filtering to select a small set of macro operators. We count how often a macro operator is instantiated as an action in the problem solutions found by the planner. The more often a macro has been used in the past, the greater the chance that the macro will be useful in the future.

For ranking, each macro operator is assigned a weight that estimates its efficiency. All weights are initialized to 0. Each time a macro is present in a plan, its weight is increased by the number of occurrences of the macro in the plan (occurrence points), plus 10 bonus points. No effort was spent on tuning parameters such as the bonus. For common macros that are part of all solutions of training problems, any bonus value $v \geq 0$ will produce the same ranking among these common macros. No matter what the value $v$ is, each common macro will receive $v \times T$ bonus points, where $T$ is the number of training problems. Hence the occurrence points decide the relative ranking of common macros.

We use the simplest problems in a domain for training. For these simple problems, we use all macro operators, giving each macro a chance to participate in a solution plan and increase its weight. After the training phase, the best macro operators are selected to become part of the enhanced domain definition. In experiments, 2 macros, each containing two steps, were added as new operators to the initial sets of 9 operators in Rovers, and 5 operators in Depots and Satellite. In these domains, such a small amount of extra-information was observed to be a good tradeoff between the benefits and the additional pre-processing and run-time costs. In more difficult domains, possibly with larger initial sets of operators, using more macros would probably be beneficial.


next up previous
Next: Using Macros from Solutions Up: Creating Macro-Operators Previous: Macro Generation
Adi Botea 2005-08-01