On the completeness of pruning techniques for planning with conditional effects

DOI10.1155/2013/398245MaRDI QIDQ473577zbMATH OpenOpenAlexWikidataFDO

Authors Dunbo Cai, Sheng Xu, Tongzhou Zhao, Yanduo Zhang

Publication date 24 November 2014

Published in Mathematical Problems in Engineering (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1155/2013/398245

Mathematics Subject Classification ID

Search theory (90B40) Approximation methods and heuristics in mathematical programming (90C59)

Review text

Summary: 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.

Recommendations

• scientific article; zbMATH DE number 1560491
• Planning graph heuristics for belief space search
• Improving delete relaxation heuristics through explicitly represented conjunctions
• Optimal planning in the presence of conditional effects: extending LM-cut with context splitting
• Planning as heuristic search

Cites work

• Approximation of action theories and its application to conformant planning
• Conformant planning via heuristic forward search: A new approach
• Fast planning through planning graph analysis
• scientific article; zbMATH DE number 5885070 (Why is no real title available?)
• scientific article; zbMATH DE number 2038901 (Why is no real title available?)
• Planning as constraint satisfaction: Solving the planning graph by compiling it into CSP
• Planning as heuristic search
• Planning as satisfiability: heuristics
• Temporal planning using subgoal partitioning and resolution in SGPlan
• The fast downward planning system
• The FF planning system: Fast plan generation through heuristic search
• Theory and Applications of Satisfiability Testing
• Using regression-match graphs to control search in planning

Cited in

(3)

• Tunneling and decomposition-based state reduction for optimal planning
• scientific article; zbMATH DE number 6519681 (Why is no real title available?)
• More than a name? on implications of preconditions and effects of compound HTN planning tasks

Describes a project that uses

Uses Software

• MiniSat
• Graphplan

This page was built for publication: On the completeness of pruning techniques for planning with conditional effects

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q473577)