A Selective Macro-learning Algorithm and its Application to the NxN Sliding-Tile Puzzle
<|reference_start|>A Selective Macro-learning Algorithm and its Application to the NxN Sliding-Tile Puzzle: One of the most common mechanisms used for speeding up problem solvers is macro-learning. Macros are sequences of basic operators acquired during problem solving. Macros are used by the problem solver as if they were basic operators. The major problem that macro-learning presents is the vast number of macros that are available for acquisition. Macros increase the branching factor of the search space and can severely degrade problem-solving efficiency. To make macro learning useful, a program must be selective in acquiring and utilizing macros. This paper describes a general method for selective acquisition of macros. Solvable training problems are generated in increasing order of difficulty. The only macros acquired are those that take the problem solver out of a local minimum to a better state. The utility of the method is demonstrated in several domains, including the domain of NxN sliding-tile puzzles. After learning on small puzzles, the system is able to efficiently solve puzzles of any size.<|reference_end|>
@article{finkelstein1998a,
    title={A Selective Macro-learning Algorithm and its Application to the NxN
  Sliding-Tile Puzzle},
    author={L. Finkelstein, S. Markovitch},
    journal={Journal of Artificial Intelligence Research, Vol 8, (1998),
  223-263},
    year={1998},
    archivePrefix={arXiv},
    eprint={cs/9806102},
    primaryClass={cs.AI}
}