A heuristic approach to the discovery of macro-operators
A heuristic approach to the discovery of macro-operators
复制标题
发现宏观算子的启发式方法
DOI：
10.1007/bf00116836
复制
发表时间：
2004
期刊：
影响因子：
--
通讯作者：
G. Iba
中科院分区：
文献类型：
--
作者：
G. Iba
本文描述了一种在解决问题时发现有用的宏运算符（宏）的启发式方法。该方法已在 Macclearn 程序中实现，该程序由三部分组成：宏提议器、静态过滤器和动态过滤器。学习发生在解决问题的过程中，因此在单个问题试验的过程中性能无法得到证实。原始运算符和宏都在统一的表示框架内表示，该表示框架在组合下封闭。这意味着新的宏可以根据其他宏来定义，从而形成定义层次结构。该表示还支持将宏转移到相关问题。Maclearnis 嵌入在执行最佳优先搜索的支持系统中。宏观学习实验针对两类问题进行：钉子接龙（广义的“Hi-Q 谜题”）和瓷砖滑动（广义的“十五谜题”）。结果表明，Macclearn 的过滤启发式方法都提高了搜索性能，有时甚至是显着提高。当系统接受更简单的训练问题的练习时，它学会了一组宏，从而成功解决了几个更难的问题。
This paper describes a heuristic approach to the discovery of useful macro-operators (macros) in problem solving. The approach has been implemented in a program,Maclearn, that has three parts: macro-proposer, static filter, and dynamic filter. Learning occurs during problem solving, so that performance unproves in the course of a single problem trial. Primitive operators and macros are both represented within a uniform representational framework that is closed under composition. This means that new macros can be defined in terms of others, which leads to a definitional hierarchy. The representation also supports the transfer of macros to related problems.Maclearnis embedded in a supporting system that carries out best-first search. Experiments in macro learning were conducted for two classes of problems: peg solitaire (generalized “Hi-Q puzzle”), and tile sliding (generalized “Fiteen puzzle”). The results indicate thatMaclearn's filtering heuristics all improve search performance, sometimes dramatically. When the system was given practice on simpler training problems, it learned a set of macros that led to successful solutions of several much harder problems.