Transforming and Encoding FTS for SAT Solving: What Helps, What Hurts (Extended Version)

Computer Science > Artificial Intelligence [Submitted on 28 May 2026] Transforming and Encoding FTS for SAT Solving: What Helps, What Hurts (Extended Version) João Filipe, Álvaro Torralba, Gregor Behnke Factored tasks are a classical planning representation that extends SAS+ with limited forms of disjunctive preconditions, conditional effects, and angelic nondeterminism. This allows for a more compact representation of tasks than traditional formalisms such as STRIPS or SAS+, and supports a wide range of task transformations. However, existing planning approaches for factored tasks have been limited to heuristic search methods. In this work, we investigate how to encode factored tasks in SAT. We propose several ways to encode the tasks, focusing on different strategies for translating the factored transition relation into propositional logic. We also analyze how to exploit parallelism at various levels in this setting and study the impact of common task transformations on the performance of SAT-based planners. Subjects: Artificial Intelligence (cs.AI) Cite as: arXiv:2605.30563 [cs.AI]   (or arXiv:2605.30563v1 [cs.AI] for this version)   https://doi.org/10.48550/arXiv.2605.30563 Focus to learn more Submission history From: Gregor Behnke [view email] [v1] Thu, 28 May 2026 20:50:52 UTC (662 KB) Access Paper: view license Current browse context: cs.AI < prev   |   next > new | recent | 2026-05 Change to browse by: cs References & Citations NASA ADS Google Scholar Semantic Scholar Export BibTeX Citation Bookmark Bibliographic Tools Bibliographic and Citation Tools Bibliographic Explorer Toggle Bibliographic Explorer (What is the Explorer?) Connected Papers Toggle Connected Papers (What is Connected Papers?) Litmaps Toggle Litmaps (What is Litmaps?) scite.ai Toggle scite Smart Citations (What are Smart Citations?) Code, Data, Media Demos Related Papers About arXivLabs Which authors of this paper are endorsers? | Disable MathJax (What is MathJax?)