Generalization and Use of Macros

A major factor that determines the utility of macros is the decision regarding where to use them. The major contributor to the utility problem in macro learning is the increased branching factor of the search graph as a result of the added macros. At one extreme, we can avoid generalization and apply a macro only at the same state where it was acquired. This approach will reduce the cost of the added branching factor but will also reduce the benefit of macros since they will be rarely applicable. At the other extreme, we can aim for full generalization and apply a macro at any state as if it were a basic operator. This approach has the potential of significantly increasing the benefit of macros, but it also increases the cost dramatically because every acquired macro increments the branching factor by one. MACLEARN, which uses best-first search, cannot use the second approach because it will make the search prohibitively expensive. Therefore, it uses a domain-specific pattern language and domain-specific abstraction procedures to perform a more restricted generalization of macros. Since in MICRO-HILLARY we tried to avoid domain-specific procedures, we took the second approach of full generalization. Fortunately, the hill-climbing search employed by the problem solver in MICRO-HILLARY does not suffer from the extreme increase in search time as a result of the increase in the branching factor.