Utilization Filtering of Macros Based on Goal Similarity

Uri Keidar, Shaul Markovitch and Erez Webman. Utilization Filtering of Macros Based on Goal Similarity. Technical Report CIS9608, Technion, 1996.

Abstract

Deductive learners acquire knowledge that is implicitly available to improve the performance of the problem solver. One of the most known form of deductive learning is the acquisition of macro operators. Macro-operators carry cost as well as benefits. When the costs outweigh the benefits, we face the utility problem. The vast number of macros available to the learner forces it to be selective to avoid the utility problem. The most common approach to selective macro-learning is using acquisition filters. Such filters try to estimate the utility of a macro before inserting it into the macro knowledge base. One problem with this approach is that the utility of a macro strongly depends on the problem being solved. In this work we suggest an alternative approach called utilization filtering. Instead of being selective when the macro is acquired, the learner is selective when the macro is utilized. We propose to use similarity-based filtering. A macro is considered as potentially useful for a particular problem if it proved to be useful for similar problems. Without further knowledge about the states in the search space, we suggest to use the heuristic function to determine similarity between states. Initial testing of this approach in the grid domain showed that indeed it is beneficial to delay selectivity to the utilization stage.

Keywords: Selective Learning, Speedup Learning, Macro Learning

Secondary Keywords:

Online version:

Bibtex entry:

 @techreport{Keidar:1996:UFM,
  Author = {Uri Keidar and Shaul Markovitch and Erez Webman},
  Title = {Utilization Filtering of Macros Based on Goal Similarity},
  Year = {1996},
  Number = {CIS9608},
  Type = {Technical Report},
  Institution = {Technion},
  Url = {http://www.cs.technion.ac.il/~shaulm/papers/pdf/Keidar-Markovitch-Webman-CIS9608.pdf},
  Keywords = {Selective Learning, Speedup Learning, Macro Learning},
  Secondary-keywords = {Selective Utilization, Heuristic Search, Deductive Learning},
  Abstract = {
    Deductive learners acquire knowledge that is implicitly available
    to improve the performance of the problem solver. One of the most
    known form of deductive learning is the acquisition of macro
    operators. Macro-operators carry cost as well as benefits. When
    the costs outweigh the benefits, we face the utility problem. The
    vast number of macros available to the learner forces it to be
    selective to avoid the utility problem. The most common approach
    to selective macro-learning is using acquisition filters. Such
    filters try to estimate the utility of a macro before inserting it
    into the macro knowledge base. One problem with this approach is
    that the utility of a macro strongly depends on the problem being
    solved. In this work we suggest an alternative approach called
    utilization filtering. Instead of being selective when the macro
    is acquired, the learner is selective when the macro is utilized.
    We propose to use similarity-based filtering. A macro is
    considered as potentially useful for a particular problem if it
    proved to be useful for similar problems. Without further
    knowledge about the states in the search space, we suggest to use
    the heuristic function to determine similarity between states.
    Initial testing of this approach in the grid domain showed that
    indeed it is beneficial to delay selectivity to the utilization
    stage.
  }

  }