On the Completeness of Pruning Techniques for Planning with Conditional Effects
On the Completeness of Pruning Techniques for Planning with Conditional Effects
复制标题
论具有条件效应的规划修剪技术的完备性
DOI：
10.1155/2013/398245
复制
发表时间：
2013-08
影响因子：
--
通讯作者：
uo
中科院分区：
文献类型：
--
作者：
Cai Dunbo;Xu Sheng;Zhao Tongzhou;Zhang Y;uo
剪枝技术和算法是启发式搜索规划的两个关键。其中，有帮助的行为剪枝策略和基于松弛计划的规划方法是两种具有代表性的方法，至今仍是规划师们研究的热点。在这里，我们提出了新的分析HAP的属性。具体来说，我们展示了新的原因，HAP可能会导致搜索过程的不完整性。我们证明，在一般情况下，HAP是不完整的规划与条件的影响，如果因子化的行动扩展。为了保持完整性，我们提出了一个修剪策略，是基于相关性分析和对抗。我们将表明，相关性分析和对抗都是必要的。我们称之为对抗和目标相关动作修剪（CGRAP）策略。然而，CGRAP在计算上难以精确计算。因此，我们建议从文献中实际近似。
Pruning techniques and heuristics are two keys to the heuristic search-based planning. The helpful actions pruning (HAP) strategy and relaxed-plan-based heuristics are two representatives among those methods and are still popular in the state-of-the-art planners. Here, we present new analyses on the properties of HAP. Specifically, we show new reasons for which HAP can cause incompleteness of a search procedure. We prove that, in general, HAP is incomplete for planning with conditional effects if factored expansions of actions are used. To preserve completeness, we propose a pruning strategy that is based on relevance analysis and confrontation. We will show that both relevance analysis and confrontation are necessary. We call it the confrontation and goal relevant actions pruning (CGRAP) strategy. However, CGRAP is computationally hard to be exactly computed. Therefore, we suggest practical approximations from the literature.
登录
查看更多内容
DOI：
10.1007/3-540-63912-8_88
发表时间：
1997-09
期刊：
--
影响因子：
--
作者：
B. Gazen;Craig A. Knoblock
通讯作者：
B. Gazen;Craig A. Knoblock
影响因子：
14.4
作者：
Bonet, B;Geffner, H
通讯作者：
Geffner, H
DOI：
10.1016/j.artint.2012.08.001
发表时间：
2012-12
期刊：
Artif. Intell.
影响因子：
--
作者：
J. Rintanen
通讯作者：
J. Rintanen
DOI：
--
发表时间：
1998-07
期刊：
--
影响因子：
--
作者：
Corin R. Anderson;David E. Smith;Daniel S. Weld
通讯作者：
Corin R. Anderson;David E. Smith;Daniel S. Weld
DOI：
10.1016/j.artint.2010.04.007
发表时间：
2005-09
期刊：
--
影响因子：
--
作者：
Tran Cao Son;P. Tu;M. Gelfond;A. Morales
通讯作者：
Tran Cao Son;P. Tu;M. Gelfond;A. Morales