The Detection and Exploitation of Symmetry in Planning Problems
The Detection and Exploitation of Symmetry in Planning Problems
复制标题
规划问题中对称性的检测和利用
DOI：
--
复制
发表时间：
1999
期刊：
影响因子：
--
通讯作者：
D. Long
中科院分区：
文献类型：
--
作者：
M. Fox;D. Long
许多规划问题表现出高度的对称性，而现代规划技术还不能成功地利用这些对称性。例如，在夹爪领域，一个机器人必须用两个抓手将球从一个房间转移到另一个房间，这对人类的问题解决者来说是微不足道的，因为这个领域的高度对称性意味着成对的球被运送的顺序与最短运输计划的长度无关。然而，计划者通常会搜索所有可能的订单，导致搜索空间呈指数爆炸式增长。本文描述了一种在显示这些特征的问题的解决中检测和利用对称性的方法。我们已经在Stan中实现了我们的技术，Stan是一个基于Graphplan的计划器，它以多种方式使用状态分析技术来利用域的底层结构。我们在解决具有对称性的问题方面取得了显著的进步。我们提出了一系列结果，并指出了我们目前正在追求的进一步发展。
Many planning problems exhibit a high degree of symmetry that cannot yet be exploited successfully by modern planning technology. For example, problems in the Gripper domain, in which a robot with two grippers must transfer balls from one room to another, are trivial to the human problem-solver because the high degree of symmetry in the domain means that the order in which pairs of balls are transported is irrelevant to the length of the shortest transportation plan. However, planners typically search all possible orderings giving rise to an exponential explosion of the search space. This paper describes a way of detecting and exploiting symmetry in the solution of problems that demonstrate these characteristics. We have implemented our techniques in STAN, a Graphplan-based planner that uses state analysis techniques in a number of ways to exploit the underlying structures of domains. We have achieved a dramatic improvement in performance in solving problems exhibiting symmetry. We present a range of results and indicate the further developments we are now pursuing.