# SAS+ Planning as Satisfiability

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

## Key facts

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

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

- [LLMs as Planning Formalizers: A Survey for Leveraging Large Language Models to Construct Automated Planning Models](https://mlsanity.com/paper/2503.18971/) (2025)
- [Large Language Models as Planning Domain Generators](https://mlsanity.com/paper/2405.06650/) (2024)
- [When both Grounding and not Grounding are Bad -- A Partially Grounded Encoding of Planning into SAT (Extended Version)](https://mlsanity.com/paper/2603.19429/) (2026)
- [Transforming and Encoding FTS for SAT Solving: What Helps, What Hurts (Extended Version)](https://mlsanity.com/paper/2605.30563/) (2026)

## Abstract (arXiv)

Planning as satisfiability is a principal approach to planning with many eminent advantages. The existing planning as satisfiability techniques usually use encodings compiled from STRIPS. We introduce a novel SAT encoding scheme (SASE) based on the SAS+ formalism. The new scheme exploits the structural information in SAS+, resulting in an encoding that is both more compact and efficient for planning. We prove the correctness of the new encoding by establishing an isomorphism between the solution plans of SASE and that of STRIPS based encodings. We further analyze the transition variables newly introduced in SASE to explain why it accommodates modern SAT solving algorithms and improves performance. We give empirical statistical results to support our analysis. We also develop a number of techniques to further reduce the encoding size of SASE, and conduct experimental studies to show the strength of each individual technique. Finally, we report extensive experimental results to demonstrate significant improvements of SASE over the state-of-the-art STRIPS based encoding schemes in terms of both time and memory efficiency.