Qualitative Numeric Planning: Reductions and Complexity

Qualitative numerical planning is classical planning extended with nonnegative real variables that can be increased or decreased "qualitatively", i.e., by positive r andom amounts. While deterministic planning with numerical variables is undecidable in general, qualit ative numerical planning is decidable and provides a convenient abstract model for generaliz ed planning. Qualitative numerical planning, introduced by Srivastava, Zilberstein, Immerman, an d Geffner (2011), showed that solutions to qualitative numerical problems (QNPs) correspond to t he 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 generat e all solutions, and that the number of solutions to check can be doubly exponential in the nu mber of variables. In this work we address these limitations, while providing additional insights o n 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 th ese reductions is that QNPs are shown to have the same expressive power and the same complex ity as FOND problems.