PRP Rebooted: Advancing the State of the Art in FOND Planning
This work advances the state of the art in FOND planning, which is used in applications like robot planning and dialogue-agent design, though it appears incremental as it builds on existing powerful planners.
The authors tackled the problem of Fully Observable Non-Deterministic (FOND) planning by developing a new planner, PR2, which decisively outperforms four leading planners in 17 out of 18 domains, often by a large margin.
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.