💻 computer science

Learning Lifted Action Models from Traces with Minimal Information About Actions and States

本文提出了从包含动作和状态部分信息的轨迹中学习 STRIPS+ 动作域的算法及完备性结果，通过考虑从无状态可观测性到特定状态谓词的全局或局部可观测性的各种场景，解决了先前的局限性。

原作者： Jonas Gösgens, Niklas Jansen, Hector Geffner

发布于 2026-05-19

📖 1 分钟阅读☕ 轻松阅读

原作者： Jonas Gösgens, Niklas Jansen, Hector Geffner

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下，你正在试图搞懂一款复杂棋盘游戏（如国际象棋或滑块拼图）的规则，但你面临一个非常奇怪的问题：你看不见棋盘。

你只能看到玩家做出的动作。你看到某个棋子从"A"移动到"B"，或者玩家拿起一个令牌。但你不知道哪个棋子移动了，它从哪里开始，或者移动之前或之后棋盘是什么样子的。你正试图仅通过观察一系列动作来逆向工程出游戏的规则手册。

这正是论文**《从信息最少化的轨迹中学习提升动作模型》**所解决的核心挑战。

以下是作者所做工作的分解，使用了简单的类比。

问题：“信息过多”的陷阱

过去，计算机科学家曾尝试教 AI 学习这些规则。他们主要有两种方法，但都存在缺陷：

“全棋盘”方法：AI 被提供整个棋盘状态（每个棋子的位置）以及移动动作。
- 缺陷：在现实世界中，我们很少能看到整个棋盘。此外，规则往往要求过多的细节。例如，要在拼图中移动一个滑块，旧规则要求你指定滑块的当前位置、新位置以及空位。但要决定移动，你实际上只需要知道“向左移动”。这些额外细节对决策者来说只是噪音。
“仅动作”方法：AI 仅被提供动作列表（例如，“向左移动”、“拿起”）。
- 缺陷：如果没有看到棋盘，AI 就无法弄清楚它在移动什么。它不知道“向左移动”是指移动机器人、汽车还是箱子。

解决方案：一种新语言（STRIPS+）

作者引入了一种名为**STRIPS+**的中间方案。你可以将其视为一种更聪明的规则书写方式。

在旧方式（STRIPS）中，规则看起来像一张严格的表格：

Move(机器人，当前单元格，下一个单元格)

在新方式（STRIPS+）中，规则更像是一个谜语：

Move()

这条规则的意思是：“如果某个单元格中有一个机器人，且右侧有一个单元格，你就可以移动。”计算机必须找出哪个机器人和哪些单元格符合该描述。这就像侦探破案，嫌疑人仅被描述为“戴红帽子的人”，而不是被指名道姓为“约翰·史密斯”。

新算法：SIFT+ 和 SYNTH+

这篇论文提出了两名新的“侦探”（算法），以便在信息缺失时解开这个谜团。

1. SIFT+（“仅动作”侦探）

它做什么：它仅通过观察动作列表来学习规则，完全看不到棋盘。
它如何工作：它使用了一种称为**“互斥特征”**的技巧。
- 类比：想象你看到一名玩家拿起一个杯子。你没看到杯子，但你知道一名玩家一次只能拿一个杯子。如果玩家拿起了一个杯子，他们一定放下了之前拿着的那个。
- SIFT+ 寻找这些“互斥”模式。它意识到：“啊，每当这个动作发生时，被持有的对象一定具有某种状态。”它发明新的“谓词”（如 is_holding 持有）来填补缺失的空白。
结果：即使动作名称被剥离了几乎所有细节，它也能学会完整的规则手册。

2. SYNTH+（“部分视图”侦探）

它做什么：当能看到棋盘的部分而非全部时，它进行学习。
它如何工作：它将新 STRIPS+ 语言的“解谜”能力与 SIFT+ 的“发明”技能相结合。
- 类比：想象你在观察一名送货司机。你能看到司机的位置（“完全可观测”部分），但你看不到卡车里的包裹。然而，你知道司机一次只能携带一个包裹。
- SYNTH+ 利用可见的位置来推断不可见的包裹。它会问：“如果司机在门口，且刚刚‘放下’了某物，那么他们手中一定拿着什么？”
转折：论文引入了**“局部可观测性”**。这意味着你不需要看到整个棋盘。你只需要看到与当前动作相关的部分。
- 示例：如果机器人向“左”移动，你只需要看到它左侧的单元格。你不需要看到地图另一侧的单元格。这使得学习变得更加现实。

“依赖图”（路线图）

为了确保这些侦探不会陷入死循环，作者创建了一张名为依赖图的地图。

你可以将其视为流程图。要学习“规则 A"，你可能需要知道“事实 B"。要学习“事实 B"，你可能需要“规则 C"。
论文证明，只要这个流程图没有循环回路（即 A 需要 B，B 需要 C，而 C 又需要 A），算法就能从你能看到的事物开始，逐步向后推导到看不到的事物，从而一步步学会规则。

结果：它奏效了吗？

作者在经典谜题上测试了这些侦探，包括Blocksworld（堆叠积木）、Delivery（运送包裹）和Sokoban（推箱子）。

测试：他们向算法输入了轨迹，其中 50% 到 90% 的信息被隐藏。
结果：
- SIFT+ 成功仅从动作列表中学习了规则，仅通过观察模式就恢复了缺失的细节（如“哪个积木在顶部”）。
- SYNTH+ 即使在“棋盘”大部分被隐藏的情况下也学会了规则，只要关键部分（如智能体的位置）是可见的。
- 在几乎每一项测试中，算法都达到了100% 的准确率，正确重建了隐藏的规则手册。

总结

这篇论文是关于教计算机在获得极少信息的情况下学习“游戏规则”。

旧方法：“这是棋盘，这是移动。学习规则。”（需要太多信息）。
新方法：“这是一份移动列表。你可以看到玩家的位置，但看不到物体。找出规则。”
突破：通过使用更聪明的语言（STRIPS+）和一种基于必须为真的事实来“发明”缺失事实的巧妙方法（互斥特征），AI 可以填补空白，并在不需要完全观察世界的情况下学习领域的完整逻辑。

论文声称，这是迈向让 AI 能够从自然的、不完美的观察中学习的重要一步，类似于人类通过观察他人来学习，而不是需要一份完美且数据丰富的手册。

技术摘要：从信息最小化的轨迹中学习提升的动作模型

问题陈述

近期研究表明，可以从单纯的动作轨迹中高效地学习提升的 STRIPS 模型（SIFT 算法），并且可以从完全可观测的状态 - 动作轨迹中学习 STRIPS+ 模型（允许隐式动作参数）（SYNTH 算法）。然而，这些方法面临实际限制：

SIFT 需要完整的 STRIPS 动作轨迹，其中参数是显式的，这通常包含动作选择所不需要的多余参数（例如，在滑动方块谜题中，即使动作是“向左移动”，也必须显式传递方块的当前位置）。
SYNTH 假设所有状态谓词都是完全可观测的，这对于在部分可观测环境中运行的智能体来说是不现实的。

本文解决了从动作参数和状态信息均部分可观测的轨迹中学习 STRIPS+ 动作域的问题。具体而言，作者研究了当轨迹携带最小信息时（即某些动作参数被省略，状态谓词要么完全不可观测、要么完全可观测、要么仅局部可观测——仅对与当前状态相关的对象可观测），在何种条件下可以学习到等价的域。

方法论

提出的解决方案 SYNTH+ 是一个统一算法，扩展并结合了 SIFT 和 SYNTH 的能力。它在扩展轨迹（动作序列和部分状态观测）上运行，并依赖于两个核心机制：

1. 互斥特征（SIFT 的扩展）

为了在不具备状态可观测性的情况下处理缺失的动作参数，作者引入了互斥特征。

概念：一个互斥特征 $f = \langle k, A, D \rangle$ 表示一个 $k$ 元谓词，其中第 $k$ 个参数由前 $k-1$ 个参数隐式确定。
机制：与标准特征（其添加模式和删除模式具有相同的元数）不同，互斥特征允许删除模式具有 $k-1$ 元。这捕捉了这样的约束：一个动作（例如 drop()）基于当前持有的对象删除一个谓词（例如 holding(o)），而无需在动作轨迹中显式命名该对象。
一致性：如果在整个轨迹图中，每个基原子 $f(o)$ 都获得单一的真值，并且对于同一状态中的任意两个真原子 $f(o)$ 和 $f(o')$ ，如果最后一个参数不同（ $o_k \neq o'_k$ ），则至少有一个 preceding 参数也必须不同（对于某个 $i < k$ ， $o_i \neq o'_i$ ），则该互斥特征是一致的。

2. 查询合成与集成（SYNTH 的扩展）

SYNTH+ 在一个迭代循环中将谓词的“发明”（通过 SIFT）与隐式参数的推断（通过 SYNTH）集成起来：

输入：标记的扩展轨迹图以及一组完全可观测的谓词 $P_\omega$ 。
迭代：
- SIFT+ 步骤：利用显式参数和当前已知的隐式参数上的动作模式，发明新的互斥特征和普通特征。这些特征代表新谓词及其效果。
- SYNTH 步骤：利用新发明的谓词（以及任何可观测谓词）来定义查询（子查询 $Q_i$ ），将隐式变量 ( $z_i$ ) 绑定到状态中的唯一对象。
- 更新：使用新的隐式参数及其定义查询更新图。
终止：该过程持续进行，直到达到不动点或超过最大深度界限 ( $d_{max}$ )。

3. 局部可观测性

该框架被扩展为 LOCAL SYNTH+，以处理局部可观测性。在这种设定下，谓词仅对“局部”对象（即作为当前动作参数出现的对象）可观测。该算法修改了一致性测试过程（TEST*），在测试前提条件时假设非局部原子为假，确保状态的未观测部分不会使隐式参数的学习失效。

主要贡献

SYNTH+ 算法：一种通用算法，用于从动作和状态均部分可观测的轨迹中学习 STRIPS+ 域。它将 SIFT 的谓词发明与 SYNTH 的隐式参数解析统一起来。
互斥特征：一种新颖的形式化方法，允许学习最后一个参数功能依赖于其他参数的谓词，从而能够在没有完整状态观测的情况下恢复被省略的动作参数。
完备性结果：建立了算法完备的理论条件：
- SIFT+（无状态可观测性）：要求隐藏的 STRIPS+ 域是良构的、强连通的，并且在其依赖图（其中节点为谓词和隐式变量）中是无环的。
- SYNTH+（部分状态可观测性）：要求限制在非可观测谓词上的依赖图是无环的。
- LOCAL SYNTH+：在局部可观测性下被证明是完备的，前提是涉及仅隐式参数的前提条件中的关键谓词是完全可观测的，且其他谓词是局部可观测的。
泛化性：这项工作证明 SIFT 和 SYNTH 是 SYNTH+ 的特例（分别对应 $P_\omega = \emptyset$ 和 $P_\omega = P$ ）。

实验结果

作者在一系列标准规划域（例如 Blocks、Delivery、Grid、Sokoban、Logistics）上评估了 SIFT+ 和 SYNTH+，使用了从隐藏 STRIPS+ 模型生成的扩展轨迹。

SIFT+ 性能：在所有测试域中，仅从动作轨迹成功学习了正确的域（100% 验证率），平均恢复了轨迹中被省略的 55% 的动作参数。
SYNTH+ 性能：使用比 SYNTH 少得多的可观测谓词学习了正确的域。
- 在 Delivery 中，SYNTH+ 仅通过观测智能体的位置 (at(x)) 和静态邻接关系就学会了该域，而 SYNTH 需要所有流谓词。
- 在 Sokoban 和 Logistics 中，SYNTH+ 仅通过观测静态谓词就学会了域，而在这种场景下 SYNTH 和 SIFT+ 均无法成功。
效率：算法在标准硬件上运行高效（从几秒到几分钟），可扩展至包含数千个轨迹步骤的域。

意义与主张

本文主张 SYNTH+ 提供了一种实用的、提升的替代方案，用于基于模型的强化学习，因为它能够从“自然”轨迹中学习动态模型。这些轨迹所需的信息极少：

它们不需要列出形式化 STRIPS 编码所需的每个参数（例如，被拆垛的方块的当前位置）。
它们不需要完全的状态可观测性；特定谓词的部分或局部可观测性已足够。

作者强调，他们的方法弥合了理论模型学习（通常假设完全可观测性）与实际应用（智能体感知有限）之间的差距。通过刻画学习可行的确切条件（依赖图的无环性），这项工作为部分可观测环境下的提升动作模型学习确立了严格的范围。结果表明，复杂的域可以从仅传达选择动作所需信息的轨迹中重建，而无需完整的状态描述。