Qualitative numeric planning: reductions and complexity
From MaRDI portal
Abstract: Qualitative numerical planning is classical planning extended with non-negative real variables that can be increased or decreased "qualitatively", i.e., by positive indeterminate amounts. While deterministic planning with numerical variables is undecidable in general, qualitative numerical planning is decidable and provides a convenient abstract model for generalized planning. The solutions to qualitative numerical problems (QNPs) were shown to correspond to the strong cyclic solutions of an associated fully observable non-deterministic (FOND) problem that terminate. This leads to a generate-and-test algorithm for solving QNPs where solutions to a FOND problem are generated one by one and tested for termination. The computational shortcomings of this approach for solving QNPs, however, are that it is not simple to amend FOND planners to generate all solutions, and that the number of solutions to check can be doubly exponential in the number of variables. In this work we address these limitations while providing additional insights on QNPs. More precisely, we introduce two polynomial-time reductions, one from QNPs to FOND problems and the other from FOND problems to QNPs both of which do not involve termination tests. A result of these reductions is that QNPs are shown to have the same expressive power and the same complexity as FOND problems.
Recommendations
- Fast strong planning for fully observable nondeterministic planning problems
- An approach to efficient planning with numerical fluents and multi-criteria plan quality
- The complexity of planning problems with simple causal graphs
- The computational complexity of propositional STRIPS planning
- scientific article; zbMATH DE number 1216123
Cites work
- A Concise Introduction to Models and Methods for Automated Planning
- A new representation and associated algorithms for generalized planning
- Approximate policy iteration with a policy language bias: solving relational Markov decision processes
- Depth-First Search and Linear Graph Algorithms
- scientific article; zbMATH DE number 5595162 (Why is no real title available?)
- scientific article; zbMATH DE number 4124989 (Why is no real title available?)
- scientific article; zbMATH DE number 1216123 (Why is no real title available?)
- scientific article; zbMATH DE number 1467489 (Why is no real title available?)
- scientific article; zbMATH DE number 783783 (Why is no real title available?)
- scientific article; zbMATH DE number 2201583 (Why is no real title available?)
- Learning action strategies for planning domains
- Learning generalized policies from planning examples using concept languages
- Practical solution techniques for first-order MDPs
- STRIPS: A new approach to the application of theorem proving to problem solving
- Theory and Applications of Satisfiability Testing
- Weak, strong, and strong cyclic planning via symbolic model checking
Cited in
(5)- An approach to efficient planning with numerical fluents and multi-criteria plan quality
- Flexible FOND Planning with Explicit Fairness Assumptions
- Hierarchical decompositions and termination analysis for generalized planning
- Generalized planning as heuristic search: a new planning search-space that leverages pointers over objects
- Planning with uncertainty: symmetries, policy inference, and solution compression
This page was built for publication: Qualitative numeric planning: reductions and complexity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5139597)
