Genetically evolved macro-actions in AI planning problems
Genetically evolved macro-actions in AI planning problems
复制标题
人工智能规划问题中基因进化的宏观行动
DOI：
--
复制
发表时间：
2005
期刊：
影响因子：
--
通讯作者：
M. Fox
中科院分区：
文献类型：
--
作者：
M. Newton;J. Levine;M. Fox
尽管最近在规划方面取得了进展，但对于当前的规划者来说，许多复杂的领域，甚至是具有大问题的简单领域，仍然是困难和具有挑战性的。宏观动作被定义为一次应用的一组动作，它可以跳到搜索树中深度较小的地方到达目标，因此在给定时间限制内无法解决的问题可能会变得可解。像Macro-FF和Marvin这样的FF风格规划者在宏观行动方面表现出了一些改进。但它们都不知何故需要关于域和搜索算法的知识，因为Macro-FF使用静态事实，而Marvin使用平台转义序列来生成宏动作。在没有关于域或规划算法的任何重要结构知识的情况下，没有已知的方法能够学习好的宏。遗传算法是一种自动学习方法，它只需要一种方法来播种初始种群，定义种群上的遗传算子，以及一种在种群中评估个体的方法，而不需要关于问题域和搜索算法的结构性知识。遗传算法在学习某一领域的控制知识方面有很好的效果，在生成计划方面也取得了一些成功，但还没有尝试过进化宏观行动。本文介绍了应用遗传算法学习规划问题中的宏观动作的初步结果。
Despite recent progress in planning, many complex domains and even simple domains with large problems remain hard and challenging for current planners. A macro-action, defined as a group of actions applied at one time, can make jumps to reach a goal at less depth in the search tree and thus problems, not solvable within a given time limit, might become solvable. FF Style planners like Macro-FF and MARVIN showed some improvement with macro-actions. But both of them somehow need knowledge about the domains and the search algorithms as Macro-FF uses static facts and MARVIN uses plateau escaping sequences to generate macroactions. There is no known method capable of learning good macros without any significant structural knowledge about the domains or the planning algorithms. Genetic algorithms are automatic learning methods that require just a method to seed the initial population, definitions of the genetic operators on the populations, and a method to evaluate individuals across the populations but no structural knowledge about the problem domains and the search algorithms. Genetic algorithms have promising results in learning control knowledge for a domain and some success in generating plans but have not yet been tried to evolve macro-actions. This paper presents initial results of applying a genetic algorithm to learn macro-actions in planning problems.