Extending the Exploitation of Symmetries in Planning
Extending the Exploitation of Symmetries in Planning
复制标题
扩大规划中对称性的利用
DOI：
--
复制
发表时间：
2002
期刊：
影响因子：
--
通讯作者：
D. Long
中科院分区：
文献类型：
--
作者：
M. Fox;D. Long
高度对称的问题会导致冗余的搜索工作，这可能会使看似简单的问题变得棘手。虽然在更广泛的搜索和约束满足社区中已经探索了打破限制的潜在好处（例如，参见（Gent & Smith 2000; Ip & Dill 1996; Crawford et al. 1996）），但在规划中开发这种潜力的兴趣相对较少。Fox和Long在1999年（Fox & Long 1999）对Graphplan框架中的对称性破坏的好处进行了初步探索，取得了令人鼓舞的结果，但没有考虑到识别和利用搜索过程中出现的新对称性的重要性。在本文中，我们扩展的对称性开发的想法（福克斯和龙1999年）中描述的处理新的对称性和报告的结果，从一系列的规划问题。
Highly symmetric problems result in redundant search effort which can render apparently simple problems intractable. Whilst the potential benefits of symmetry-breaking have been explored in the broader search and constraint satisfaction community (see (Gent & Smith 2000; Ip & Dill 1996; Crawford et al. 1996) for examples) there has been relatively little interest in the exploitation of this potential in planning. An initial exploration of the benefits of symmetry-breaking in a Graphplan framework, by Fox and Long in 1999 (Fox & Long 1999) yielded promising results but failed to take into account the importance of identifying and exploiting new symmetries that arise during the search process. In this paper we extend the symmetry exploitation ideas described in (Fox & Long 1999) to handle new symmetries and report results obtained from a range of planning problems.