Improved Non-Deterministic Planning by Exploiting State Relevance

Vol. 22 (2012): Twenty-Second International Conference on Automated Planning and Scheduling

Volume

Vol. 22 (2012): Twenty-Second International Conference on Automated Planning and Scheduling

Full Technical Papers

We address the problem of computing a policy for fully observable non-deterministic (FOND) planning problems. By focusing on the relevant aspects of the state of the world, we introduce a series of improvements to the previous state of the art and extend the applicability of our planner, PRP, to work in an online setting. The use of state relevance allows our policy to be exponentially more succinct in representing a solution to a FOND problem for some domains. Through the introduction of new techniques for avoiding deadends and determining sufficient validity conditions, PRP has the potential to compute a policy up to several orders of magnitude faster than previous approaches. We also find dramatic improvements over the state of the art in online replanning when we treat suitable probabilistic domains as FOND domains.

10.1609/icaps.v22i1.13520