# PRP Rebooted: Advancing the State of the Art in FOND Planning

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 3 of its 28 references that are in the map.
- First posted on arXiv 18 Dec 2023.

## Builds on (most cited first, 3 of 3)

- [Planning for Goal-Oriented Dialogue Systems](https://mlsanity.com/paper/1910.08137/) (2019)
- [Compact Policies for Fully-Observable Non-Deterministic Planning as SAT](https://mlsanity.com/paper/1806.09455/) (2018)
- [Iterative Depth-First Search for Fully Observable Non-Deterministic Planning](https://mlsanity.com/paper/2204.04322/) (2022)

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

- [Learning Generalized Policies for Fully Observable Non-Deterministic Planning Domains](https://mlsanity.com/paper/2404.02499/) (2024)
- [Planning with Uncertainty: Symmetries, Policy Inference, and Solution Compression](https://mlsanity.com/paper/2403.19883/) (2024)
- [BPMN to PDDL: Translating Business Workflows for AI Planning](https://mlsanity.com/paper/2511.18171/) (2025)
- [Learning Bilevel Policies over Symbolic World Models for Long-Horizon Planning](https://mlsanity.com/paper/2605.15975/) (2026)

## Abstract (arXiv)

Fully Observable Non-Deterministic (FOND) planning is a variant of classical symbolic planning in which actions are nondeterministic, with an action's outcome known only upon execution. It is a popular planning paradigm with applications ranging from robot planning to dialogue-agent design and reactive synthesis. Over the last 20 years, a number of approaches to FOND planning have emerged. In this work, we establish a new state of the art, following in the footsteps of some of the most powerful FOND planners to date. Our planner, PR2, decisively outperforms the four leading FOND planners, at times by a large margin, in 17 of 18 domains that represent a comprehensive benchmark suite. Ablation studies demonstrate the impact of various techniques we introduce, with the largest improvement coming from our novel FOND-aware heuristic.