# Flexible FOND Planning with Explicit Fairness Assumptions

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 44 references that are in the map.
- First posted on arXiv 15 Mar 2021.

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

- [Multi-shot ASP solving with clingo](https://mlsanity.com/paper/1705.09811/) (2017)
- [Learning Features and Abstract Actions for Computing Generalized Plans](https://mlsanity.com/paper/1811.07231/) (2018)
- [Qualitative Numeric Planning: Reductions and Complexity](https://mlsanity.com/paper/1912.04816/) (2019)
- [Generalized Planning: Non-Deterministic Abstractions and Trajectory Constraints](https://mlsanity.com/paper/1909.12135/) (2019)
- [A Symbolic SAT-based Algorithm for Almost-sure Reachability with Small Strategies in POMDPs](https://mlsanity.com/paper/1511.08456/) (2015)
- [Practical Synthesis of Reactive Systems from LTL Specifications via Parity Games](https://mlsanity.com/paper/1903.12576/) (2019)
- [Stochastic Fairness and Language-Theoretic Fairness in Planning on Nondeterministic Domains](https://mlsanity.com/paper/1912.11203/) (2019)
- [Multi-tier Automated Planning for Adaptive Behavior (Extended Version)](https://mlsanity.com/paper/2002.12445/) (2020)

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

- [Non-Deterministic Planning for Hyperproperty Verification](https://mlsanity.com/paper/2405.13488/) (2024)
- [Stochastic Perturbations of Tabular Features for Non-Deterministic Inference with Automunge](https://mlsanity.com/paper/2202.09248/) (2022)
- [Iterative Depth-First Search for Fully Observable Non-Deterministic Planning](https://mlsanity.com/paper/2204.04322/) (2022)
- [Fairness in Multi-Agent Planning](https://mlsanity.com/paper/2212.00506/) (2022)
- [An Automatic Sound and Complete Abstraction Method for Generalized Planning with Baggable Types](https://mlsanity.com/paper/2501.15249/) (2025)
- [Planning with Uncertainty: Symmetries, Policy Inference, and Solution Compression](https://mlsanity.com/paper/2403.19883/) (2024)

## Abstract (arXiv)

We consider the problem of reaching a propositional goal condition in fully-observable non-deterministic (FOND) planning under a general class of fairness assumptions that are given explicitly. The fairness assumptions are of the form A/B and say that state trajectories that contain infinite occurrences of an action a from A in a state s and finite occurrence of actions from B, must also contain infinite occurrences of action a in s followed by each one of its possible outcomes. The infinite trajectories that violate this condition are deemed as unfair, and the solutions are policies for which all the fair trajectories reach a goal state. We show that strong and strong-cyclic FOND planning, as well as QNP planning, a planning model introduced recently for generalized planning, are all special cases of FOND planning with fairness assumptions of this form which can also be combined. FOND+ planning, as this form of planning is called, combines the syntax of FOND planning with some of the versatility of LTL for expressing fairness constraints. A new planner is implemented by reducing FOND+ planning to answer set programs, and the performance of the planner is evaluated in comparison with FOND and QNP planners, and LTL synthesis tools.