A selective macro-learning algorithm and its application to the N x N sliding-tile puzzle

One of the most common mechanisms used for speeding up problem solvers is m acrolearning. Macros are sequences of basic operators acquired during probl em solving. Macros are used by the problem solver as if they were basic ope rators. The major problem that macro-learning presents is the vast number o f macros that are available for acquisition. Macros increase the branching factor of the search space and can severely degrade problem-solving efficie ncy. To make macro learning useful, a program must be selective in acquirin g and utilizing macros. This paper describes a general method for selective acquisition of macros. Solvable training problems are generated in increas ing order of difficulty. The only macros acquired are those that take the p roblem solver out of a local minimum to a better state. The utility of the method is demonstrated in several domains, including the domain of N x N sl iding-tile puzzles. After learning on small puzzles, the system is able to efficiently solve puzzles of any size.