Iterative Depth-First Search for FOND Planning

Fully Observable Non-Deterministic (FOND) planning models uncertainty through actions with non-deterministic effects. Ex- isting FOND planning algorithms are effective and employ a wide range of techniques. However, most of the existing algo- rithms 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 ex- ploits the benefits of heuristic functions to make the algorithm more effective during the iterative searching process. We com- pare 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.