When both Grounding and not Grounding are Bad -- A Partially Grounded Encoding of Planning into SAT (Extended Version)

Each language version is independently generated for its own context, not a direct translation.

这篇论文讲的是如何让计算机更聪明、更高效地做“规划”（比如机器人怎么移动、物流怎么送货）。

为了让你轻松理解，我们可以把“规划”想象成给一个巨大的迷宫找出口，或者给一个复杂的乐高任务写说明书。

1. 核心难题：太具体 vs. 太抽象

在计算机规划的世界里，有两种处理问题的方法，就像两种不同的“地图”：

完全“落地”的方法（Grounding）：
想象你要指挥一个机器人去送货。传统的做法是，把每一个具体的包裹（包裹 A、包裹 B...）和每一个具体的地点（北京、上海、广州...）都列出来，生成一份超级详细的清单。
- 优点： 计算机看得很清楚，每一步都知道具体该动哪个包裹。
- 缺点： 如果包裹有 1000 个，地点有 1000 个，这份清单就会变得像宇宙一样大，计算机根本算不过来，内存直接爆炸。这就叫“指数级爆炸”。
完全“悬浮”的方法（Lifting）：
另一种做法是，计算机只记规则，不记具体名字。比如它只记：“如果有车，就可以把包裹从 A 运到 B"。它不关心车是红色的还是蓝色的，也不关心 A 是北京还是纽约。
- 优点： 清单非常短，很省内存。
- 缺点： 以前有一种叫 LiSAT 的顶尖方法，虽然用了这种“悬浮”规则，但在计算长任务（比如要运 100 步）时，它需要把每一步和之前的每一步都“手拉手”连起来检查。这就像每走一步都要回头和之前所有的步骤握手，导致计算量随着步数平方级增长（走 10 步要 100 次检查，走 100 步要 10000 次检查）。

这篇论文的痛点是： 完全落地太慢（清单太大），完全悬浮（LiSAT）在长任务中又太慢（握手太多）。

2. 作者的解决方案：半落地、半悬浮（Partial Grounding）

作者想出了一个“中间路线”：动作保持“悬浮”（不记具体名字），但状态“半落地”（记具体关系）。

他们用了三个聪明的技巧，就像给计算机装上了**“智能分类器”**：

技巧一：把动作抽象化（动作不落地）

就像你写菜谱时，只写“炒一个鸡蛋”，而不需要写“炒那个编号 007 的鸡蛋”。计算机依然用通用的规则来指挥动作，这样动作的清单就很短。

技巧二：利用“互斥组”（Mutex Groups）来压缩状态

这是最精彩的部分。作者发现，很多事实是互斥的。

比喻： 想象一个包裹。它要么在“车上”，要么在“仓库里”，要么在“家里”。它不可能同时在这三个地方。这三个状态就像是一个**“互斥组”**。
传统做法： 计算机要分别记录“在车上=真/假”、“在仓库=真/假”、“在家=真/假”。
作者的做法： 既然它们互斥，计算机只需要记一个变量：“它现在在哪个位置？”（比如用数字 1 代表车，2 代表仓库）。
- 这就好比以前你要给 1000 个开关分别记录状态（1000 个变量），现在你只需要一个**“旋钮”**，转到哪个数字就代表哪个状态（只需要 $\log_2(1000)$ 个变量，大概 10 个）。
- 这种方法叫**“部分落地”**：动作是通用的，但状态通过这种“旋钮”被压缩了。

技巧三：线性增长 vs. 平方增长

LiSAT（旧方法）： 就像每走一步都要和之前的所有步骤握手。步数越多，握手次数呈平方级爆炸（ $N^2$ ）。
新方法： 因为用了“旋钮”压缩状态，每一步只需要检查当前的状态，不需要回头和所有历史握手。步数增加，工作量只是线性增加（ $N$ $N$ ）。
- 比喻： 以前是“全员大合唱”，人越多声音越乱；现在是“接力赛”，每个人只和下一棒交接，人再多也能跑得飞快。

3. 实验结果：真的管用吗？

作者在 9 个不同的“迷宫”（规划领域，如物流、机器人、管道运输等）里测试了他们的算法。

在“找最短路径”的任务中（Optimal Planning）：
他们的算法在 9 个领域里有 5 个打败了目前的冠军（LiSAT）。特别是在那些“包裹多、地点多”的复杂领域（如物流、管道），优势非常明显。
在“随便找个路就行”的任务中（Satisficing Planning）：
虽然还没完全超越所有对手，但表现非常强劲，而且能解决一些其他方法解决不了的难题。
公式大小：
随着任务变长，他们的算法生成的“说明书”（公式）大小是直线上升的，而旧方法是曲线飙升的。这意味着任务越长，新方法的相对优势越大。

4. 总结：这就像什么？

如果把规划问题比作组织一场大型婚礼：

完全落地： 给每个宾客发一张专属的座位表，列出 1000 个人的名字和具体座位。太厚了，翻都翻不过来。
完全悬浮（旧方法）： 只写规则“新郎新娘要交换戒指”。但为了确认戒指没被偷，每交换一次，都要把之前 100 次交换的记录都拿出来核对一遍，累死人。
新方法（本文）：
1. 动作规则保持简单（“交换戒指”）。
2. 把宾客分组（“互斥组”）：比如“新郎”、“新娘”、“伴郎”、“伴娘”。你只需要一个**“当前状态旋钮”**，显示“戒指现在在谁手里”。
3. 因为状态被压缩了，而且不需要回头核对所有历史，所以婚礼流程再长，组织者也不会累垮。

一句话总结：
这篇论文发明了一种**“聪明压缩法”，让计算机在处理复杂规划任务时，既能保持规则的简洁，又能避免状态爆炸，特别是在长任务**中，它比以前的冠军方法跑得更快、更稳。

Each language version is independently generated for its own context, not a direct translation.

这是一份关于论文《When both Grounding and not Grounding are Bad – A Partially Grounded Encoding of Planning into SAT》（当完全接地和完全提升都不好时——一种部分接地的规划到 SAT 编码）的详细技术总结。

1. 研究背景与问题 (Problem)

经典规划的挑战：经典规划问题通常使用提升的（lifted）一阶逻辑表示，具有紧凑性和通用性。然而，大多数规划器为了简化推理，会将这些表示“接地”（grounding），即实例化为所有具体的对象组合。在对象数量多或谓词 arity（参数个数）高时，这会导致状态空间呈指数级爆炸。
现有方法的局限性：
- 完全接地（Fully Grounded）：虽然推理简单，但在大规模问题上可扩展性差。
- 完全提升（Fully Lifted）：如 LiSAT（State-of-the-art），直接在提升层面操作以避免接地爆炸。LiSAT 使用因果链接（causal links）来确保前提条件被满足且效果未被破坏，而不显式跟踪状态。
- LiSAT 的缺陷：LiSAT 的公式大小随规划长度 $\ell$ 呈**二次方（quadratic）**增长。这是因为每个前提条件必须与之前任意时间步的潜在达成者建立链接。这限制了其在需要长规划的问题上的性能。此外，LiSAT 难以利用如互斥组（Mutex Groups）等问题的内在结构。
核心问题：如何在保持动作提升（compactness）的同时，避免状态描述的完全接地爆炸，并解决现有提升 SAT 编码随规划长度二次方增长的问题？

2. 方法论 (Methodology)

作者提出了一种**部分接地（Partially Grounded）**的中间路线，引入了三种新的 SAT 编码方案。其核心思想是：动作保持完全提升，而状态描述（谓词）进行部分接地。

2.1 核心组件

动作编码：沿用 LiSAT 的“统一参数”（Unified Arguments）机制，保持动作完全提升，不随对象数量增加而爆炸。
状态编码：
1. 完全接地基线：将所有谓词实例化为事实。作为对比基准，但性能不佳。
2. 部分接地（利用 PLMGs）：利用部分提升互斥组（Partially Lifted Mutex Groups, PLMGs）。
  - PLMGs：基于 Helmert (2009) 和 Fišer (2020) 的方法，识别出在任意可达状态下，一组事实中至多（或恰好）有一个为真。
  - 编码策略：对于属于 PLMG 的谓词，不显式编码所有事实，而是使用**计数变量（counted variables）**来隐式表示当前哪个事实为真。
  - 未覆盖事实：对于不属于任何 PLMG 的谓词（或未被选中的部分），仍进行完全接地编码。
线性扩展机制：
- 通过显式跟踪状态（State Tracking），消除了对因果链接（causal links）的需求。
- 状态转移函数 $\tau(t, t+1)$ 的大小仅取决于问题规模 $|\Pi|$ ，与规划长度 $\ell$ 无关。
- 因此，整体公式大小 $F$ 随规划长度 $\ell$ 呈**线性（linear）**增长，解决了 LiSAT 的二次方瓶颈。

2.2 具体编码变体

Fully Grounded：所有谓词接地。
Partially Grounded (One-hot)：使用 PLMGs 编码部分谓词，计数变量使用独热编码（one-hot encoding）。
Partially Grounded (Binary)：同上，但对 PLMG 中的计数变量使用二进制编码（Binary Encoding）。
- 将 $|O|$ 个对象映射为 $\lceil \log_2 |O| \rceil$ 个比特变量。
- 显著减少了变量数量，提高了信息密度，进一步压缩了公式规模。

2.3 优化技术

谓词剪枝（Predicate Pruning）：移除那些既不出现在初始/目标状态，也不作为任何动作前提条件的谓词。这大幅减少了需要显式编码的事实数量。

3. 关键贡献 (Key Contributions)

理论突破：提出了三种新的 SAT 编码，首次实现了在保持动作提升的同时，通过部分接地状态描述，将公式规模从二次方降低到线性。
利用结构信息：创新性地结合了**部分提升互斥组（PLMGs）**与 SAT 编码，利用规划问题的内在互斥结构来压缩状态表示。
二进制编码优化：在部分接地编码中引入二进制表示法，进一步减少了变量数量，提升了处理大规模对象域的能力。
实证优势：在长度最优规划（Length-Optimal Planning）任务中，新编码在多个难接地（hard-to-ground）领域超越了当时的最先进方法 LiSAT。

4. 实验结果 (Results)

实验在标准提升规划基准集上进行，对比了 LiSAT、Powerlifted (PWL)、CPDDL 以及接地规划器（Madagascar, Fast Downward）。

长度最优规划（Optimal Planning）：
- 覆盖率（Coverage）：提出的编码（特别是 Binary + Predicate Pruning）在 9 个基准域中的 5 个上优于 LiSAT。
- 得分（Score）：在长度最优模式下，新编码的得分显著高于 LiSAT 和其他基于搜索的提升规划器（如 PWL, CPDDL）。
- 特定领域表现：在 Logistics, Pipesworld, Rover 等领域，新编码比 LiSAT 多解决了 20% 以上的实例。
- 对比搜索法：在最优模式下，基于 SAT 的方法（包括本文方法和 LiSAT）明显优于基于搜索的提升方法（PWL, CPDDL）。
可满足性规划（Satisficing Planning）：
- 虽然基于搜索的 PWL 在覆盖率上略胜一筹，但本文提出的 SAT 编码在 Blocksworld, Childsnack, Visitall 等特定领域表现优异，显示出与现有搜索方法互补的能力。
公式规模分析：
- 变量数：Binary 编码所需的变量数通常比 LiSAT 少（有时少两个数量级），且随规划长度呈线性增长。
- 子句数：由于 PLMG 语义编码的复杂性，Binary 编码的子句数通常比 LiSAT 多（约 1-2 个数量级），但其线性增长特性使得在长规划中更具优势。
- 扩展性：LiSAT 的变量和子句数随规划长度呈二次方增长，且受实例难度影响大；本文方法则表现出稳定的线性增长。

5. 意义与结论 (Significance & Conclusion)

解决“接地困境”：该论文成功地在“完全接地”和“完全提升”之间找到了一个高效的平衡点。它证明了通过部分接地状态并利用互斥结构，可以克服现有提升 SAT 规划器的扩展性瓶颈。
线性扩展性：将规划到 SAT 的编码复杂度从二次方降低到线性，使得处理长规划序列成为可能，这是 LiSAT 等现有方法难以做到的。
互补性：实验表明，基于 SAT 的规划器（包括本文方法和 LiSAT）与基于搜索的规划器具有正交的能力。SAT 方法擅长解决某些特定结构（如长规划、特定互斥结构）的问题，而搜索方法在其他场景下表现更好。这为构建混合规划器（Portfolio Planners）提供了强有力的组件。
未来方向：作者指出未来工作可探索将动作并行性（Action Parallelism）、负前提条件（Negative Preconditions）和条件效果（Conditional Effects）集成到该框架中。

总结：这篇论文通过引入部分接地状态描述和 PLMGs，提出了一种线性扩展的 SAT 规划编码，在长度最优规划任务中显著超越了当前的最先进方法 LiSAT，为处理大规模和复杂结构的规划问题提供了新的有效途径。