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

arXiv Poster Code


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.


Is this published?

Yes! It appears in AAAI 2024. You can find the proceedings here.

Why is there no GitHub repo?

A great question. Technically one exists, but it is in the process of a complete restructuring to make integration with the FastDownward system more modular. This will mean that the PR2 planner will no longer be “frozen in time” with respect to FastDownward. The original PRP planner relied on a verion from around 2010, while PR2 currently builds on top of a version around 2017. The restructured code will mirror the latest version of FastDownward, and hopefully continue to do so.

So what should I compare against?

The code link above is the version that was used to generate the results for the publication. This should be viewed as the canonical asset for comparison. A thorough analysis of the performance difference between the PR2 code above and the restructured project will be released along with the repository. At this point, it is too early to tell if there will be much (if any) difference in performance, and if so, in which direction.

What about the PRP variants like POPRP, MAPRP, and so on?

Conditional effects are handled by PR2 (thus capturing CondPRP), but POPRP, PRPRP, and MAPRP are not. We have near-term plans to add the support of axioms, after which point POPRP will make a triumphant return as POPR2!


Prof. Sheila A. McIlraith

Prof. J. Christopher Beck