Home | Publications | CS Home

A Selective Macro-learning Algorithm and its Application to the NxN Sliding-Tile Puzzle

---

Lev Finkelstein and Shaul Markovitch. A Selective Macro-learning Algorithm and its Application to the NxN Sliding-Tile Puzzle. Journal of Artificial Intelligence Research, 8:223-263 1998.

---

Abstract

One of the most common mechanisms used for speeding up problem solvers is macro-learning. Several methods for acquiring macros have been devised. The major problem with these methods is the vast number of macros that are available for learning. 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.

---

Keywords: Speedup Learning, Macro Learning, Selective Learning, Active Learning

---

Secondary Keywords:

---

Online version:

---

Bibtex entry:

 @article{Finkelstein:1998:SML,
  Author = {Lev Finkelstein and Shaul Markovitch},
  Title = {A Selective Macro-learning Algorithm and its Application to the NxN Sliding-Tile Puzzle},
  Year = {1998},
  Journal = {Journal of Artificial Intelligence Research},
  Volume = {8},
  Pages = {223--263},
  Url = {http://www.cs.technion.ac.il/~shaulm/papers/pdf/Finkelstein-Markovitch-jair1998.pdf},
  Keywords = {Speedup Learning, Macro Learning, Selective Learning, Active Learning},
  Secondary-keywords = {Heuristic Search, Deductive Learning, Explanation-Based Learning},
  Abstract = {
    One of the most common mechanisms used for speeding up problem
    solvers is macro-learning. Several methods for acquiring macros
    have been devised. The major problem with these methods is the
    vast number of macros that are available for learning. 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.
  }

  }