Qualitative Numeric Planning: Reductions and Complexity
share
Qualitative numerical planning is classical planning extended with non-negative real variables that can be increased or decreased "qualitatively", i.e., by positive random 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. Qualitative numerical planning, introduced by Srivastava, Zilberstein, Immerman, and Geffner (2011), showed that solutions to qualitative numerical problems (QNPs) correspond to the strong cyclic solutions of an associated fully observable non-deterministic (FOND) problem that terminate. The approach 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, 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 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.
READ FULL TEXT