Iterative Depth-First Search for Fully Observable Non-Deterministic Planning
This work addresses the challenge of handling non-determinism and task size in FOND planning, which is important for AI planning under uncertainty, though it appears incremental as it builds on existing techniques.
The paper tackles the problem of Fully Observable Non-Deterministic (FOND) planning by developing an iterative depth-first search algorithm that produces strong cyclic policies, showing robust performance across various FOND domains in comparisons with existing planners.
Fully Observable Non-Deterministic (FOND) planning models uncertainty through actions with non-deterministic effects. Existing FOND planning algorithms are effective and employ a wide range of techniques. However, most of the existing algorithms are not robust for dealing with both non-determinism and task size. In this paper, we develop a novel iterative depth-first search algorithm that solves FOND planning tasks and produces strong cyclic policies. Our algorithm is explicitly designed for FOND planning, addressing more directly the non-deterministic aspect of FOND planning, and it also exploits the benefits of heuristic functions to make the algorithm more effective during the iterative searching process. We compare our proposed algorithm to well-known FOND planners, and show that it has robust performance over several distinct types of FOND domains considering different metrics.