On Sample-Efficient Generalized Planning via Learned Transition Models

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

这篇论文讲述了一个关于**“如何教 AI 像人类一样学会‘举一反三’，而不是死记硬背”**的故事。

为了让你更容易理解，我们可以把“规划（Planning）”想象成**“教机器人下棋”或者“教机器人做家务”**。

1. 以前的做法：死记硬背的“鹦鹉学舌”

以前的 AI 规划方法（比如 PlanGPT、Plansformer），就像是一个只会背答案的学霸。

怎么学的？ 给它看几千道“把积木从 A 搬到 B"的题目和标准答案（动作序列）。
怎么用的？ 当它遇到新题目时，它试图回忆以前背过的答案，然后直接输出：“第一步拿积木，第二步放积木……"
问题在哪？
- 记不住长流程： 如果题目变长了（比如要把 100 个积木搬完），它背到后面就乱了，因为它是靠“猜”下一个动作，而不是真的理解积木是怎么移动的。这就叫**“状态漂移”**（State Drift），就像你背课文背到一半忘了上一句，后面全编错了。
- 换个场景就懵： 如果以前练的是搬 4 个积木，现在让它搬 100 个，它完全不会，因为它只是死记硬背了“搬 4 个”的模式，没学会“搬积木”的物理规律。

2. 这篇论文的新方法：学会“物理规律”的“老司机”

作者们提出了一种新方法，叫**“基于状态中心的通用规划”。我们可以把它想象成教一个“老司机”**。

核心思想： 不要直接教它“下一步踩油门还是刹车”（预测动作），而是教它**“踩了油门后，车会开到哪里”**（预测状态变化）。
具体做法：
1. 看世界： 给 AI 一个“世界模型”。它不直接输出动作，而是先预测：“如果我做了这个动作，世界会变成什么样？”（比如：积木 A 会从桌子上掉下来，变成在手里）。
2. 模拟推演： AI 在脑子里先“跑”一遍：如果状态变成这样，下一步该做什么？它通过不断预测“下一个世界状态”，把整个计划串起来。
3. 最后确认： 当 AI 预测出“下一个世界状态”后，它会回头去查一下规则书（符号逻辑），确认哪个动作能导致这个状态。这就保证了它的每一步都是合法的。

3. 两个关键创新点（让 AI 变聪明的秘诀）

秘诀一：用“关系图”代替“固定表格” (Size-Invariant Representations)

旧方法（固定表格）： 就像给每个房间分配固定的“床位”。如果只有 4 个积木，就开 4 张床；如果有 100 个积木，旧方法就崩溃了，因为它没那么多床位。
新方法（关系图/WL 编码）： 就像**“乐高说明书”。不管你有 4 块积木还是 100 块，说明书只关心“积木 A 在积木 B 上面”这种关系**，而不关心具体有多少块。
- 比喻： 以前是数人头（人多了就乱），现在是数“谁和谁手拉手”（关系不变，人数变多也不影响理解）。这让 AI 能轻松处理以前没见过的、规模更大的问题。

秘诀二：只学“变化” (Residual Modeling)

旧方法： 每次都要重新描述整个世界的样子（比如：积木 A 在桌上，积木 B 在地上……）。这太啰嗦了，而且容易出错。
新方法： 只告诉 AI**“哪里变了”**。
- 比喻： 就像你发朋友圈，不需要把家里所有东西都拍一遍，只需要拍**“新买的咖啡”**。因为大部分东西（墙壁、地板）都没变。
- 这种方法让 AI 学得非常快，而且只需要很少的数据（样本效率极高）。

4. 实验结果：小模型也能打大模型

作者们做了很多实验，对比了他们的“老司机”方法和以前的“学霸”方法：

数据量： 以前的“学霸”需要几百万个参数和海量数据才能学会；他们的“老司机”只需要100 万个参数（甚至更少），就像用小脑瓜解决了大问题。
泛化能力： 在以前没见过的、规模更大的问题上（比如从搬 4 个积木变成搬 17 个积木），他们的“老司机”方法成功率更高，而“学霸”们直接挂了（成功率 0）。
例外情况： 只有在非常复杂、像“物流调度”这种需要多层级配合的领域，目前的方法还有点吃力，但这已经比以前的方法进步巨大了。

总结

这篇论文的核心贡献是：与其让 AI 死记硬背“怎么做”，不如让它理解“世界是怎么变的”。

通过让 AI 学习物理世界的变化规律（状态预测），而不是死记动作序列，我们就能用更小、更省数据的模型，解决更大、更复杂的问题。这就好比教孩子骑自行车，不是让他背“左脚蹬、右脚蹬”的口令，而是让他理解“怎么保持平衡”，这样他以后骑任何自行车（无论大小）都能学会。

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

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

核心问题：
广义规划（Generalized Planning, GP）旨在构建能够解决同一领域内一系列规划问题的通用策略。传统的 GP 方法通常依赖符号抽象和显式的状态转移推理。然而，近年来基于 Transformer 的规划器（如 PlanGPT, Plansformer）倾向于将 GP 视为直接的动作序列预测问题（Action-centric），即直接根据问题描述生成动作序列 $p(\pi | \Pi)$ 。

现有方法的局限性：

状态漂移（State Drift）： 在长视野（long-horizon）任务中，由于缺乏对世界状态演变的显式建模，基于动作序列的模型容易累积误差，导致生成的计划偏离真实状态。
样本效率低： 这些 Transformer 模型通常需要巨大的数据集和参数量（数千万到数亿参数）才能取得良好效果。
分布外（OOD）泛化能力差： 当测试实例的规模（对象数量）显著大于训练集时，直接预测动作的方法往往失效，因为它们难以捕捉状态随对象数量变化的不变性。

本文目标：
提出一种**以状态为中心（State-centric）的广义规划方法，通过显式学习状态转移模型（Transition Model），实现样本高效（Sample-Efficient）且具备规模不变性（Size-Invariant）**的泛化能力。

2. 方法论 (Methodology)

本文提出了一种神经 - 符号混合的规划流水线，核心思想是学习状态转移函数而非直接学习策略。

2.1 核心范式：以状态为中心的规划

不同于直接预测下一个动作 $a_t$ ，模型学习预测下一个状态 $s_{t+1}$ 。

输入： 当前状态 $s_t$ 和目标 $g$ （或问题描述 $\Pi$ ）。
输出： 预测的下一个状态 $\hat{s}_{t+1}$ 。
执行机制： 通过神经模型预测状态轨迹，然后利用符号搜索在合法算子集合中查找与预测状态最匹配的动作。

2.2 规模不变的状态表示 (Size-Invariant State Representation)

为了解决状态描述随对象数量增加而变化的问题，论文采用了 Weisfeiler-Leman (WL) 图嵌入。

构建实例学习图 (ILG)： 将状态 $s$ 和目标 $g$ 编码为关系图，节点代表对象和谓词，边代表关系。
WL 颜色细化： 对图进行 $k$ 次颜色迭代细化，统计最终的颜色直方图。
优势： 生成的嵌入向量 $\phi(s, g)$ 维度固定，仅取决于领域结构，与对象数量 $|O|$ 无关。这赋予了模型置换不变性和规模不变性，使其能够从小规模训练集泛化到大规模测试集。
对比基线： 论文还对比了固定大小的因子化编码（FSF），发现其无法处理超出训练对象数量的情况。

2.3 过渡模型学习 (Transition-Model Learning)

模型在嵌入空间中预测状态更新。

残差建模 (Residual Formulation)： 考虑到 STRIPS 风格的规划中，大多数谓词在一步操作中保持不变（Frame Axioms），模型不直接预测 $\phi(s_{t+1})$ ，而是预测残差向量 $\Delta_t$ ：
$\hat{\phi}(s_{t+1}) = \phi(s_t) + f_\theta(\phi(s_t), \phi(g))$
其中 $f_\theta$ 预测状态变化的增量。这种设计显著提高了非参数模型的样本效率。
模型架构：
- 参数化模型： 双层 LSTM（测试序列记忆是否必要）。
- 非参数化模型： XGBoost（树回归器，测试局部近似是否足够）。

2.4 神经 - 符号解码 (Neuro-Symbolic Plan Decoding)

在推理阶段，为了保证符号有效性，采用以下流程（见算法 1）：

神经预测： 给定当前符号状态 $s_t$ ，计算嵌入 $\phi(s_t)$ ，通过模型预测目标嵌入 $v_t$ 。
符号枚举： 利用领域算子枚举所有合法的符号后继状态集合 $Succ(s_t) = \{ \gamma(s_t, a) \mid a \in A \}$ 。
最近邻匹配： 在 $Succ(s_t)$ 中寻找嵌入距离 $v_t$ 最近的符号状态 $s_{t+1}$ 。
动作恢复： 确定导致该状态转移的唯一动作 $a_t$ 。
迭代： 重复直到满足目标 $g$ 。

这一机制确保了每一步生成的动作在符号层面都是合法的，并纠正了神经预测的误差。

3. 实验设置 (Experimental Setup)

数据集： 4 个 IPC 基准领域：Blocksworld（积木世界）, Gripper（机械手）, Logistics（物流）, VisitAll（访问所有）。
数据划分： 按对象数量划分训练集（小）、验证集、插值集（未见配置但大小在范围内）和外推集（Extrapolation，对象数量严格大于训练集）。外推是评估规模不变性的关键。
基线模型：
- Symmetry-Aware Transformers (SymT)
- PlanGPT
- Plansformer
- 符号规划器 Fast Downward (A* + LM-cut) 作为上限参考。
评估指标： 满意解成功率（Satisficing Success Rate），即生成的计划在目标步长内到达目标状态的比例。

4. 主要结果 (Results)

4.1 泛化性能对比

外推能力： 在严格的外推设置下（测试对象数远大于训练集），基于动作序列的 Transformer 模型（Plansformer, PlanGPT）在几乎所有领域中的成功率均为 0.00。SymT 在部分领域有微弱表现，但在 Logistics 领域失败。
本文方法优势： 基于 WL 嵌入和残差过渡模型的方法（特别是 WL-XGB Delta）在 Blocksworld (0.45 vs 0.13) 和 VisitAll (0.87 vs 0.64) 上显著优于 SymT。在 Gripper 领域，LSTM 表现略好，但整体仍具竞争力。
Logistics 领域的挑战： 所有方法（包括符号规划器）在 Logistics 的外推任务中表现不佳（0.00），表明该领域存在深层的层级因果耦合，单步状态预测难以处理。

4.2 规模不变性与表示学习

WL vs FSF： 使用固定槽位编码（FSF）的模型在外推任务中完全失败（0.00），证明了置换不变和规模不变的图嵌入（WL）是泛化的必要条件。
残差建模： 在树模型（XGBoost）中，残差（Delta）预测显著优于直接状态预测（例如 VisitAll 从 0.08 提升至 0.87），验证了利用状态稀疏变化特性的有效性。

4.3 样本与模型效率

参数量对比： 本文使用的模型极其轻量。
- LSTM: ~100 万参数。
- XGBoost: ~11.5 万个树节点。
- 对比基线：SymT (~~25-35M), PlanGPT (~~125M), Plansformer (~220M)。
数据效率： 本文模型在未进行数据增强（如对称性扩展）的小规模训练集上（例如 Blocksworld 仅 9 个实例）训练，却取得了优于经过大规模数据增强训练的 Transformer 模型的外推性能。

5. 关键贡献 (Key Contributions)

新的规划公式： 提出了基于目标条件后继状态预测的广义规划公式，将 GP 转化为过渡模型学习问题，而非动作序列预测。
系统性的表示评估： 系统评估了多种状态表示，证明了WL 图嵌入对于实现规模不变性和样本高效泛化的关键作用。
实证发现： 证明了紧凑的过渡模型（小参数、少数据）结合显式状态演化，在局部因子化领域（Locally Factored Domains）中，其外推性能可以匹配甚至超越依赖大规模参数和数据增强的 Transformer 基线。
神经 - 符号接口： 设计了一种神经 - 符号解码机制，在利用神经网络进行泛化预测的同时，通过符号验证保证每一步的合法性，解决了状态漂移问题。

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

核心结论：
对于广义规划任务，学习领域物理（显式过渡动力学）比单纯扩大模型规模或增加数据量提供了更强的归纳偏置。通过结合规模不变的状态表示和残差过渡建模，可以使用极小的模型实现强大的分布外泛化能力。

局限性：
该方法在具有深层层级因果耦合的复杂领域（如 Logistics）中，单步状态预测仍面临挑战，无法完全替代复杂的符号推理。

未来工作：
未来的研究将致力于扩展该框架，以处理多步或抽象过渡，解决层级依赖问题，同时保持符号验证的鲁棒性。

总结：
这篇论文挑战了当前“大模型直接生成动作”的主流趋势，回归到“学习世界模型”的本质，证明了在结构化规划任务中，小模型 + 显式状态建模 + 符号验证是解决样本效率和泛化问题的更优路径。