# Compact Policies for Fully-Observable Non-Deterministic Planning as SAT

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 Jun 2018.

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

- [PRP Rebooted: Advancing the State of the Art in FOND Planning](https://mlsanity.com/paper/2312.11675/) (2023)
- [Non-Deterministic Planning for Hyperproperty Verification](https://mlsanity.com/paper/2405.13488/) (2024)
- [Iterative Depth-First Search for Fully Observable Non-Deterministic Planning](https://mlsanity.com/paper/2204.04322/) (2022)
- [Learning Generalized Policies for Fully Observable Non-Deterministic Planning Domains](https://mlsanity.com/paper/2404.02499/) (2024)
- [Recognizing LTLf/PLTLf Goals in Fully Observable Non-Deterministic Domain Models](https://mlsanity.com/paper/2103.11692/) (2021)
- [Safe-Planner: A Single-Outcome Replanner for Computing Strong Cyclic Policies in Fully Observable Non-Deterministic Domains](https://mlsanity.com/paper/2109.11471/) (2021)
- [Planning with Uncertainty: Symmetries, Policy Inference, and Solution Compression](https://mlsanity.com/paper/2403.19883/) (2024)
- [FONDANT: Strong and Best-Effort Planning via Antichains](https://mlsanity.com/paper/2609.35160/) (2026)

## Abstract (arXiv)

Fully observable non-deterministic (FOND) planning is becoming increasingly important as an approach for computing proper policies in probabilistic planning, extended temporal plans in LTL planning, and general plans in generalized planning. In this work, we introduce a SAT encoding for FOND planning that is compact and can produce compact strong cyclic policies. Simple variations of the encodings are also introduced for strong planning and for what we call, dual FOND planning, where some non-deterministic actions are assumed to be fair (e.g., probabilistic) and others unfair (e.g., adversarial). The resulting FOND planners are compared empirically with existing planners over existing and new benchmarks. The notion of "probabilistic interesting problems" is also revisited to yield a more comprehensive picture of the strengths and limitations of current FOND planners and the proposed SAT approach.