Technical Report CIS9608

Title: Utilization Filtering of Macros Based on Goal Similarity
Authors: Uri Keidar, Shaul Markovitch and Erez Webman
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 {\em utilization filtering}. Instead of being selective when the macro is {\em acquired}, the learner is selective when the macro is {\em 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.
CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the CIS technical reports of 1996
To the main CS technical reports page

Computer science department, Technion