Qualitative Numeric Planning: Reductions and Complexity
  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.
