Accession Number : ADA221571


Title :   Learning to Solve Problems by Searching for Macro-Operators


Corporate Author : CARNEGIE-MELLON UNIV PITTSBURGH PA DEPT OF COMPUTER SCIENCE


Personal Author(s) : Korf, Richard E


Full Text : https://apps.dtic.mil/dtic/tr/fulltext/u2/a221571.pdf


Report Date : Jul 1983


Pagination or Media Count : 145


Abstract : This thesis explores the idea of learning efficient strategies for solving problems by searching for macro-operators. A macro-operator, or macro for short, is simply a sequence of operators chosen from the primitive operators of a problem. The technique is particularly useful for problems with non- serializable subgoals, such as Rubik's Cube, for which other weak methods fail. Both a problem-solving program and a learning program are described in detail. The performance of these programs is analyzed in terms of the number of macros required to solve all problem instances, the length of the resulting solutions (expressed as the number of primitive moves), and the amount of time necessary to learn the macros. In addition, a theory of why the method works, and a characterization of the range of the problems for which its is useful are presented. The theory introduces a new type of problem structure called operator decomposability. Finally, it is concluded that the macro technique is a valuable addition to the class of weak methods, that macro-operators constitute an interesting and important representation of knowledge, and that searching for macros may be a useful general learning paradigm.


Descriptors :   *MACROPROGRAMMING , *PROBLEM SOLVING , THESES , ADDITION , VALUE , LEARNING , LOW STRENGTH , EFFICIENCY , STRATEGY , SEARCHING


Subject Categories : Computer Programming and Software


Distribution Statement : APPROVED FOR PUBLIC RELEASE