# Planning with Uncertainty: Symmetries, Policy Inference, and Solution Compression

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 5 of its 37 references that are in the map.
- First posted on arXiv 28 Mar 2024.

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

- [Qualitative Numeric Planning: Reductions and Complexity](https://mlsanity.com/paper/1912.04816/) (2019)
- [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)
- [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 is at the core of artificial intelligence planning with uncertainty. It models uncertainty through actions with non-deterministic effects. In this work, we present a collection of techniques that establish explicit best-first policy-space search as a method competitive with the state of the art for solving FOND planning tasks. We study how to define equivalence relations between policies, allowing part of the search space to be pruned. We show it is possible to use group theory techniques to effectively compute canonical symmetries between states. We also present two contributions that go beyond just policy-space search: we present a procedure that infers in polynomial time a solution policy function given just the specification of its domain set, and an integer-programming formulation procedure that, given a solution policy defined over complete states, yields a set of resource-efficient models that are capable of finding a partial-state policy that represents it unambiguously with the fewest partial states possible.