# Qualitative Numeric Planning: Reductions and Complexity

arXiv: https://arxiv.org/abs/1912.04816 · HTML: https://mlsanity.com/paper/1912.04816/

## Key facts

- Cited by 18 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Dec 2019.

## Built on by (most cited first, 18 of 18)

- [Learning Generalized Policies Without Supervision Using GNNs](https://mlsanity.com/paper/2205.06002/) (2022)
- [Generalized Planning as Heuristic Search](https://mlsanity.com/paper/2103.14434/) (2021)
- [Learning Sketches for Decomposing Planning Problems into Subproblems of Bounded Width: Extended Version](https://mlsanity.com/paper/2203.14852/) (2022)
- [Expressing and Exploiting the Common Subgoal Structure of Classical Planning Domains Using Sketches: Extended Version](https://mlsanity.com/paper/2105.04250/) (2021)
- [Learning General Policies from Small Examples Without Supervision](https://mlsanity.com/paper/2101.00692/) (2021)
- [Flexible FOND Planning with Explicit Fairness Assumptions](https://mlsanity.com/paper/2103.08391/) (2021)
- [Generalized Planning as Heuristic Search: A new planning search-space that leverages pointers over objects](https://mlsanity.com/paper/2301.11087/) (2023)
- [General Policies, Subgoal Structure, and Planning Width](https://mlsanity.com/paper/2311.05490/) (2023)
- [Graph Learning for Numeric Planning](https://mlsanity.com/paper/2410.24080/) (2024)
- [Hierarchical Decomposition and Analysis for Generalized Planning](https://mlsanity.com/paper/2212.02823/) (2022)
- [Deep Learning for Generalised Planning with Background Knowledge](https://mlsanity.com/paper/2410.07923/) (2024)
- [Weisfeiler-Leman Features for Planning: A 1,000,000 Sample Size Hyperparameter Study](https://mlsanity.com/paper/2508.18515/) (2025)
- [Automatic Verification of Sound Abstractions for Generalized Planning](https://mlsanity.com/paper/2205.11898/) (2022)
- [Integrating Reinforcement Learning, Action Model Learning, and Numeric Planning for Tackling Complex Tasks](https://mlsanity.com/paper/2502.13006/) (2025)
- [Planning with Dynamically Changing Domains](https://mlsanity.com/paper/2508.02697/) (2025)
- [Multi-Valued Partial Order Plans in Numeric Planning](https://mlsanity.com/paper/2307.14660/) (2023)
- [On Grid Graph Reachability and Puzzle Games](https://mlsanity.com/paper/2310.01378/) (2023)
- [Planning with Uncertainty: Symmetries, Policy Inference, and Solution Compression](https://mlsanity.com/paper/2403.19883/) (2024)

## Abstract (arXiv)

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.