# Compiling Uncertainty Away in Conformant Planning Problems with Bounded Width

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Jan 2014.

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

- [Answer Set Planning: A Survey](https://mlsanity.com/paper/2202.05793/) (2022)
- [Planning with Incomplete Information in Quantified Answer Set Programming](https://mlsanity.com/paper/2108.06405/) (2021)
- [Efficient Multi-agent Epistemic Planning: Teaching Planners About Nested Belief](https://mlsanity.com/paper/2110.02480/) (2021)
- [Egocentric Planning for Scalable Embodied Task Achievement](https://mlsanity.com/paper/2306.01295/) (2023)
- [Generalized Planning as Heuristic Search: A new planning search-space that leverages pointers over objects](https://mlsanity.com/paper/2301.11087/) (2023)
- [Planning for Proactive Assistance in Environments with Partial Observability](https://mlsanity.com/paper/2105.00525/) (2021)
- [Reformulation Techniques for Automated Planning: A Systematic Review](https://mlsanity.com/paper/2301.10079/) (2023)
- [Planning with Dynamically Changing Domains](https://mlsanity.com/paper/2508.02697/) (2025)
- [Planning in the LLM Era: Building for Reliability and Efficiency](https://mlsanity.com/paper/2605.21902/) (2026)
- [Make Planning Research Rigorous Again!](https://mlsanity.com/paper/2505.21674/) (2025)
- [Bridging Learned Visual Perception and Symbolic Belief-Space Planning](https://mlsanity.com/paper/2609.16884/) (2026)

## Abstract (arXiv)

Conformant planning is the problem of finding a sequence of actions for achieving a goal in the presence of uncertainty in the initial state or action effects. The problem has been approached as a path-finding problem in belief space where good belief representations and heuristics are critical for scaling up. In this work, a different formulation is introduced for conformant problems with deterministic actions where they are automatically converted into classical ones and solved by an off-the-shelf classical planner. The translation maps literals L and sets of assumptions t about the initial situation, into new literals KL/t that represent that L must be true if t is initially true. We lay out a general translation scheme that is sound and establish the conditions under which the translation is also complete. We show that the complexity of the complete translation is exponential in a parameter of the problem called the conformant width, which for most benchmarks is bounded. The planner based on this translation exhibits good performance in comparison with existing planners, and is the basis for T0, the best performing planner in the Conformant Track of the 2006 International Planning Competition.