# Iterative Depth-First Search for Fully Observable Non-Deterministic Planning

arXiv: https://arxiv.org/abs/2204.04322 · HTML: https://mlsanity.com/paper/2204.04322/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 3 of its 30 references that are in the map.
- First posted on arXiv 8 Apr 2022.

## Builds on (most cited first, 3 of 3)

- [Compact Policies for Fully-Observable Non-Deterministic Planning as SAT](https://mlsanity.com/paper/1806.09455/) (2018)
- [Generalized Planning: Non-Deterministic Abstractions and Trajectory Constraints](https://mlsanity.com/paper/1909.12135/) (2019)
- [Flexible FOND Planning with Explicit Fairness Assumptions](https://mlsanity.com/paper/2103.08391/) (2021)

## Built on by (most cited first, 1 of 1)

- [PRP Rebooted: Advancing the State of the Art in FOND Planning](https://mlsanity.com/paper/2312.11675/) (2023)

## Abstract (arXiv)

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.