# Generalized Planning: Non-Deterministic Abstractions and Trajectory Constraints

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Sep 2019.

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

- [Flexible FOND Planning with Explicit Fairness Assumptions](https://mlsanity.com/paper/2103.08391/) (2021)
- [Hierarchical Decomposition and Analysis for Generalized Planning](https://mlsanity.com/paper/2212.02823/) (2022)
- [Learning General Policies with Policy Gradient Methods](https://mlsanity.com/paper/2512.19366/) (2025)
- [Abstraction of Nondeterministic Situation Calculus Action Theories -- Extended Version](https://mlsanity.com/paper/2305.14222/) (2023)
- [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)
- [Learning and Reusing Policy Decompositions for Hierarchical Generalized Planning with LLM Agents](https://mlsanity.com/paper/2605.06957/) (2026)
- [Planning with Uncertainty: Symmetries, Policy Inference, and Solution Compression](https://mlsanity.com/paper/2403.19883/) (2024)

## Abstract (arXiv)

We study the characterization and computation of general policies for families of problems that share a structure characterized by a common reduction into a single abstract problem. Policies μ that solve the abstract problem P have been shown to solve all problems Q that reduce to P provided that μ terminates in Q. In this work, we shed light on why this termination condition is needed and how it can be removed. The key observation is that the abstract problem P captures the common structure among the concrete problems Q that is local (Markovian) but misses common structure that is global. We show how such global structure can be captured by means of trajectory constraints that in many cases can be expressed as LTL formulas, thus reducing generalized planning to LTL synthesis. Moreover, for a broad class of problems that involve integer variables that can be increased or decreased, trajectory constraints can be compiled away, reducing generalized planning to fully observable non-deterministic planning.