Compiling uncertainty away in conformant planning problems with bounded width
From MaRDI portal
Abstract: Conformant planning is the problem of finding a sequence of actions for achieving a goal in the presence of uncertainty in the initial state or action effects. The problem has been approached as a path-finding problem in belief space where good belief representations and heuristics are critical for scaling up. In this work, a different formulation is introduced for conformant problems with deterministic actions where they are automatically converted into classical ones and solved by an off-the-shelf classical planner. The translation maps literals L and sets of assumptions t about the initial situation, into new literals KL/t that represent that L must be true if t is initially true. We lay out a general translation scheme that is sound and establish the conditions under which the translation is also complete. We show that the complexity of the complete translation is exponential in a parameter of the problem called the conformant width, which for most benchmarks is bounded. The planner based on this translation exhibits good performance in comparison with existing planners, and is the basis for T0, the best performing planner in the Conformant Track of the 2006 International Planning Competition.
Recommendations
- Compiling uncertainty away in non-deterministic conformant planning
- Conformant planning via heuristic forward search: A new approach
- Conformant planning via symbolic model checking and heuristic search
- scientific article; zbMATH DE number 1560498
- More for free: a dynamic epistemic framework for conformant planning over transition systems
Cited in
(25)- Resolving distributed knowledge
- Strong temporal planning with uncontrollable durations
- Efficient multi-agent epistemic planning: teaching planners about nested belief
- Computing programs for generalized planning using a classical planner
- Conformant planning as a case study of incremental QBF solving
- Conformant planning via heuristic forward search: A new approach
- Domain-independent planning for services in uncertain and dynamic environments
- Belief tracking for planning with sensing: width, complexity and approximations
- Compiling uncertainty away in non-deterministic conformant planning
- A translation based approach to probabilistic conformant planning
- Online belief tracking using regression for contingent planning
- Width and serialization of classical planning problems
- scientific article; zbMATH DE number 1560498 (Why is no real title available?)
- Planning with Incomplete Information in Quantified Answer Set Programming
- Using machine learning for decreasing state uncertainty in planning
- Approximation of action theories and its application to conformant planning
- A Practical Approach to Discretised PDDL+ Problems by Translation to Numeric Planning
- Generalized planning as heuristic search: a new planning search-space that leverages pointers over objects
- A knowledge compilation perspective on queries and transformations for belief tracking
- Symbolic search for cost-optimal planning with expressive model extensions
- Answer set planning: a survey
- CPCES: a planning framework to solve conformant planning problems through a counterexample guided refinement
- Conformant planning via symbolic model checking and heuristic search
- A generic approach to planning in the presence of incomplete information: theory and implementation
- Conformant plans and beyond: principles and complexity
This page was built for publication: Compiling uncertainty away in conformant planning problems with bounded width
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3651474)
