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

转换与编码 FTS 以用于 SAT 求解：哪些有益，哪些有害（扩展版）

Abstract: 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.

摘要： 因子化任务（Factored tasks）是一种经典的规划表示法，它在 SAS+ 的基础上扩展了有限形式的析取前提、条件效应和天使非确定性（angelic nondeterminism）。与 STRIPS 或 SAS+ 等传统形式化方法相比，这种表示法能够更紧凑地描述任务，并支持多种任务转换。

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.

然而，现有的因子化任务规划方法仅限于启发式搜索方法。在这项工作中，我们研究了如何将因子化任务编码为 SAT 问题。我们提出了几种编码任务的方法，重点探讨了将因子化转换关系转化为命题逻辑的不同策略。我们还分析了在此设置下如何利用不同层级的并行性，并研究了常见任务转换对基于 SAT 的规划器性能的影响。