Research map / Multi-agent systems and games / Human-AI and goal-conditioned
PRP Rebooted: Advancing the State of the Art in FOND Planning
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Introduces PR2, a FOND planner that extends PRP with a controller/reachable representation, fixed-point regression, deadend poisoning, object sampling, and an FSAP-aware FF heuristic, outperforming MyND, FONDSAT, PRP, and Paladinus on 800 benchmark problems.
Problem
Fully observable non-deterministic (FOND) planning requires computing strong cyclic plans; existing planners have limited coverage and solution quality across benchmark domains.
Approach
Combines a compact controller graph of regressed SolStep nodes (inspired by GRENDEL/FONDSAT) with PRP-style replanning over an all-outcomes determinization, adds fixed-point regression, deadend poisoning, object-removal sampling, and a heuristic that penalizes potentially forbidden actions in FF.
Key results
- PR2 reaches a total normalized coverage of 17.75 out of 800 problems, versus 13.65 for PRP, 11.34 for Paladinus, 10.33 for MyND, and 8.23 for FONDSAT.
- PR2 is at least as good as every other planner in virtually all domains, with PRP ahead only on blockworlds-new and four forest-new instances.
- Ablation: disabling the FSAP-aware heuristic drops coverage by 2.839, the largest effect among the ablated features.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use PR2 instead of PRP | FOND planners · 18-domain benchmark suite | normalized coverage: 13.65 -> 17.75 | Helped |
| use PR2 instead of Paladinus | FOND planners · 18-domain benchmark suite | normalized coverage: 11.34 -> 17.75 | Helped |
| use PR2 instead of MyND | FOND planners · 18-domain benchmark suite | normalized coverage: 10.33 -> 17.75 | Helped |
| use PR2 instead of FONDSAT | FOND planners · 18-domain benchmark suite | normalized coverage: 8.23 -> 17.75 | Helped |
| add object sampling (ablation) | PR2 · 18-domain benchmark suite | normalized coverage: 17.74 -> 16.99 (drop -0.743 when disabled) | Helped |
| add poisoning (ablation) | PR2 · 18-domain benchmark suite | normalized coverage: 17.74 -> 16.99 (drop -0.743 when disabled) | Helped |
| add the FSAP-aware heuristic penalty (ablation) | PR2 · 18-domain benchmark suite | normalized coverage: 17.74 -> 14.90 (drop -2.839 when disabled) | Helped |
| add full strong-cyclic marking (ablation) | PR2 · 18-domain benchmark suite | normalized coverage: 17.74 -> 16.98 (drop -0.757 when disabled) | Helped |
| force 1-safe plans (ablation) | PR2 · 18-domain benchmark suite | normalized coverage: 17.74 -> 16.16 (drop -1.570 when disabled) | Helped |
Surprising findings
- PRP produces smaller solutions as problem size grows, despite PR2 outperforming it in size on most problems.
- A bug in PRP caused it to incorrectly declare the simplest doors problems unsolvable.
Limitations
- PR2 runs out of memory on the largest blockworlds-new instance where PRP barely succeeds.
- Removing the FSAP-aware heuristic greatly reduces performance on triangle tireworld, islands, and miner.
- Object sampling is a sound-but-incomplete preprocessing step and the heuristic is inadmissible.
Experimental setup
Datasets: FOND benchmark domains (18 domains, 800 problems)
Benchmarks: FOND benchmark suite of 18 domains (800 problems)
Metrics: normalized coverage solve time solution size
Baselines: MyND FONDSAT PRP Paladinus
Builds on: PRP Fast Downward FONDSAT GRENDEL NDP
Closest papers by meaning
- Symbolic Numeric Planning with Patterns (AAAI 2024 · similarity 0.83)
- Towards Practical Classical Planning Compilations of Numeric Planning (AAAI 2025 · similarity 0.83)
- Learning Planning Domains from Non-redundant Fully-Observed Traces: Theoretical Foundations and Complexity Analysis (AAAI 2024 · similarity 0.83)
- PO-PDDL: Learning Symbolic POMDPs from Visual Demonstrations for Robot Planning Under Uncertainty (NeurIPS 2026 · similarity 0.83)
- Towards Epistemic-Doxastic Planning with Observation and Revision (AAAI 2024 · similarity 0.83)
- Hierarchical Planning for Complex Tasks with Knowledge Graph-RAG and Symbolic Verification (ICML 2025 · similarity 0.83)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.