Solving QNP and FOND+ with Generating, Testing and Forbidding

Zheyuan Shi, Hao Dong, Yongmei LiuIJCAI 2025 · DOI

Introduction

Automated planning aims to find a policy—a set of rules—that guides an agent to a goal state. However, real-world scenarios often involve complexities like non-determinism and numerical variables. Non-deterministic actions (FOND) have multiple possible outcomes, while Qualitative Numerical Planning (QNP) involves numerical variables that change by arbitrary amounts. FOND+ generalizes both by incorporating fairness assumptions: if an action is attempted infinitely often, every possible outcome will eventually occur.

Existing solvers for these problems often struggle with scalability. Logic-based approaches like Answer Set Programming (ASP) can lead to memory explosions, while others lack effective heuristics. This paper, presented at IJCAI-25, introduces the Generate-Test-and-Forbid (GTF) framework, a novel iterative approach that significantly improves scalability and coverage.

The GTF Framework

The core contribution is the GTF framework, which decomposes the planning problem into an iterative three-step cycle:

  1. Generate: The framework uses an adapted version of the PRP solver to find a "strong cyclic" solution—a policy where the goal is reachable from every state under standard fairness.
  2. Test: A new algorithm, SIEVE, verifies if the generated policy satisfies the specific fairness constraints of the FOND+ or QNP problem. SIEVE works by iteratively "peeling away" edges of the policy's transition graph; if the graph can be reduced to an acyclic state, the policy is valid.
  3. Forbid: If the policy fails the test, the framework identifies "bad" state-action pairs and adds them to a list of Forbidden Steps (FSteps). The generator then restarts, avoiding these forbidden steps.

To enhance efficiency, the authors implemented optimizations such as identifying "Key Steps" that must be in a solution and "Vital Fsaps" that are guaranteed to violate fairness. They also introduced heuristics like 3FF and 3FN to prioritize which steps to forbid.

Experimental Evaluation

The researchers evaluated GTF on standard benchmarks (e.g., Nests, Gripper, Logistics) and new, more complex domains like BlocksColumns and HallsFloors.

Coverage vs. Time for QNP and FOND+ domains.

As shown in the performance plots, the GTF variants (GTF-3FF, GTF-3FN, GTF-BFF) consistently outperform existing methods in both coverage and speed. In the QNP setting, the GTF-3FN variant achieved a remarkable 94% coverage, a significant leap over the previous state-of-the-art DSET (58%) and FOND-ASP (31%).

Key Results and Insights

The experimental results highlight the framework's superior scalability. In large-scale domains like ZenotravelAbs, which features over 10 million reachable states, GTF solvers were often the only ones to find solutions within the 30-minute time limit.

Detailed performance comparison on QNP domains.

The table above details the performance across various QNP domains. The GTF approach's success stems from its incremental refinement: instead of solving the entire problem at once, it learns from failed policies by pruning the search space through the "Forbid" mechanism. Furthermore, SIEVE* provides a unified verification method for a broad class of fairness-based planning problems.

Conclusion

The GTF framework represents a major advancement in solving complex planning problems involving non-determinism and numerical variables. By leveraging existing FOND solvers and introducing an iterative refinement process with the SIEVE* test, the authors have created a highly scalable and effective planning tool. Future work will focus on improving heuristics for domains where the search space of candidate policies remains exceptionally large.

Summary updated

BibTeX
@inproceedings{shi2025solving,
  author = {Zheyuan Shi and Hao Dong and Yongmei Liu},
  title = {{Solving QNP and FOND+ with Generating, Testing and Forbidding}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2025},
  doi = {10.24963/ijcai.2025/961},
}
Figure