On the Completeness of Pruning Techniques for Planning with Conditional Effects
Joint Authors
Cai, Dunbo
Xu, Sheng
Zhao, Tongzhou
Zhang, Yanduo
Source
Mathematical Problems in Engineering
Issue
Vol. 2013, Issue 2013 (31 Dec. 2013), pp.1-6, 6 p.
Publisher
Hindawi Publishing Corporation
Publication Date
2013-08-18
Country of Publication
Egypt
No. of Pages
6
Main Subjects
Abstract EN
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.
American Psychological Association (APA)
Cai, Dunbo& Xu, Sheng& Zhao, Tongzhou& Zhang, Yanduo. 2013. On the Completeness of Pruning Techniques for Planning with Conditional Effects. Mathematical Problems in Engineering،Vol. 2013, no. 2013, pp.1-6.
https://search.emarefa.net/detail/BIM-1009243
Modern Language Association (MLA)
Cai, Dunbo…[et al.]. On the Completeness of Pruning Techniques for Planning with Conditional Effects. Mathematical Problems in Engineering No. 2013 (2013), pp.1-6.
https://search.emarefa.net/detail/BIM-1009243
American Medical Association (AMA)
Cai, Dunbo& Xu, Sheng& Zhao, Tongzhou& Zhang, Yanduo. On the Completeness of Pruning Techniques for Planning with Conditional Effects. Mathematical Problems in Engineering. 2013. Vol. 2013, no. 2013, pp.1-6.
https://search.emarefa.net/detail/BIM-1009243
Data Type
Journal Articles
Language
English
Notes
Includes bibliographical references
Record ID
BIM-1009243