Given a search trace, every subpath of it can be recorded as a macro. Obviously, there are too many subpaths, so we need to employ a filter in order to acquire a set of macros with high utility. The macros should be useful, i.e., they should save the system significant search resources. . There should be as few macros as possible.
Redundant macros increase the branching factor of the search graph without associated benefits. .
The main reason is that applying a long sequence of basic operators to a state is likely to encounter an illegal state. Whenever not in a local minimum, the search procedure can use the heuristic function, so macros that do not start in a local minimum are not necessary. The macros acquired by this filtering method are useful since they enable the search procedure to continue from a local minimum. These macros are also the shortest that satisfy that condition. Let denote the state resulting from the application of the sequence to the initial state.