💻 computer science

Efficient Lookahead Encoding and Abstracted Width for Learning General Policies in Classical Planning

本文提出了一种高效的全局编码与抽象IW(1)方法，该方法利用关系图神经网络克服广义规划中的可扩展性与表达性局限，在IPC 2023基准测试中超越包括经典规划器LAMA在内的先前方法，实现了最先进的性能。

原作者： Michael Aichmüller, Simon Ståhlberg, Martin Funkquist, Hector Geffner

发布于 2026-05-19

📖 1 分钟阅读☕ 轻松阅读

原作者： Michael Aichmüller, Simon Ståhlberg, Martin Funkquist, Hector Geffner

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

想象一下，你正在教一个机器人解决一个巨大且不断变化的迷宫。这个迷宫每次你玩的时候都会改变：有时有 10 个房间，有时有 10,000 个。目标是教会机器人掌握一本单一的“规则手册”（即策略），使其能够适用于迷宫的任何版本，无论其规模变得多大。

本文提出了一种教导该机器人的新方法，解决了以往方法所面临的两大主要障碍：内存过载和思考缓慢。

以下是他们解决方案的分解，使用了简单的类比：

1. 问题所在：“巴别图书馆”

过去，当机器人试图规划下一步行动时，它会逐一查看每一个可能的未来步骤。

旧方法：想象你身处一个拥有一百万本书的图书馆。为了决定下一本读哪本书，你必须走到每一本书前，阅读第一页，记下笔记，然后再走回去。如果你有 1,000 本书，那就需要走 1,000 趟；如果你有 100 万本书，你永远无法完成。
局限性：随着“迷宫”（即规划问题）变大，“书籍”（即可能的移动）的数量会呈爆炸式增长。以往的 AI 方法会耗尽计算机内存，或者思考时间过长，尤其是当对象数量（如方块或汽车）达到近期竞赛中常见的数千个时。

2. 第一项创新：“增量快照”（聚合增量编码）

作者们意识到，他们不需要每次都重读整本图书馆。他们只需要知道什么发生了变化。

类比：与其每次移动一本书时都拍摄整个图书馆的照片，不如只贴一张小小的“便利贴”，上面写着：“书 A 从第 1 层书架移到了第 2 层书架。”
工作原理：这种新方法称为聚合增量（AD），它将机器人的规划树视为一张单一的、相互连接的地图。它不再将每一个未来状态作为单独的、沉重的图像进行处理，而是仅编码当前状态与下一个状态之间的差异（即“增量”）。
结果：机器人可以一眼（即一次“前向传播”）审视整个可能性地图，而不是逐一检查。这将所需的内存减少了 10 倍以上，使机器人能够处理以前会导致计算机崩溃的庞大问题。

3. 第二项创新：“模糊镜头”（抽象宽度）

即使有了新的内存技巧，机器人仍然需要检查某个特定移动是否是“新”的或“新颖”的。在一个拥有数千个对象的世界里，检查每一个具体的细节非常缓慢。

类比：想象你在停车场寻找一辆特定的红色汽车。
- 旧方法：你逐一检查每辆车：“这是红色的福特吗？这是红色的丰田吗？这是红色的本田吗？”
- 新方法（抽象 IW）：你戴上了一副“模糊镜头”。你不再检查具体的车型。相反，你只问：“这里有红色汽车吗？”你将所有红色汽车视为同一种“类型”的对象。
工作原理：他们引入了抽象 IW（AIW）。在检查一个移动是否为新时，AI 会忽略对象的具体身份（如“方块 #452"），而只关注它们的通用类型（如“方块”）。
结果：这将一个随对象数量呈指数级增长的搜索，转变为一个呈线性增长的搜索。这就像检查 100 种汽车类型的列表，而不是 10,000 辆单独的汽车。这要快得多，但它仍然能找到解决谜题所需的“子目标”。

4. 成果：超级规划器

通过结合“便利贴”内存技巧与“模糊镜头”思维方式，作者们创造了一个规划器，它能够：

扩展规模：它可以解决包含数百个对象的问题（例如一个由 488 个方块组成的塔），而这些问题曾让以往的 AI 束手无策。
超越最佳：在 2023 年国际规划竞赛（AI 规划器的主要测试）中，他们的方法击败了之前的冠军，包括一个非常强大的经典规划器 LAMA。
处理高难谜题：它解决了复杂的领域（如“卫星”和“漫游车”），这些领域所需的逻辑比大多数 AI 模型通常能处理的要高级得多。

总结

这篇论文是关于教导 AI 停止试图记忆一个巨大且变化世界中的每一个单一细节。相反，它教导 AI：

只记住变化的部分（节省海量内存）。
将相似事物归为一类（通过忽略不必要的细节来加快思考速度）。

其结果是一种通用的策略，能够高效地导航巨大而复杂的迷宫，解决以前计算机无法处理的庞大问题。

技术摘要：高效前瞻编码与抽象宽度用于经典规划中的通用策略学习

问题陈述

通用规划旨在学习能够在单一领域内的大规模规划实例集合中泛化的策略，这些实例仅在初始状态、目标和对象数量上有所不同。虽然近期使用图神经网络（GNN）的方法显示出前景，但在应用于大规模实例（如 2023 年国际规划竞赛 IPC 2023 中的实例）时，它们面临显著的可扩展性和表达力限制。

具体而言，以往关于迭代宽度（IW）策略的工作利用 IW(1) 前瞻搜索来定义跨越多个转换的“跳跃”，从而简化问题结构。然而，现有实现存在两个主要瓶颈：

计算低效：单独评估每个后继状态会导致共享状态描述的重复编码，随着对象和原子数量的增加，内存和计算成本扩展性差。
表达力与扩展限制：标准 IW(1) 新颖性检查随地面原子数量线性扩展。在拥有数千个对象的领域中，地面原子数量呈多项式增长，使得前瞻搜索效率低下。此外，仅限于直接后继的模型往往缺乏推导复杂领域（例如需要超越 C2 片段逻辑的领域）所需特征的表达力。

方法论

本文提出了一种统一方法，结合了两项关键创新：用于关系图神经网络（R-GNN）的新型聚合 - 差分（AD）编码，以及用于前瞻搜索的抽象 IW(1)（AIW(1)）。

1. 聚合 - 差分（AD）编码

作者引入了一种整体编码，将整个前瞻树表示为单个关系图，而不是独立处理当前状态 $s$ 和每个后继状态 $s'$ 。

联合表示：根状态 $s$ 通过其关系集隐式编码。后继状态不是通过其完整状态描述表示，而是通过状态对象节点（ $o_{s'}$ ）表示，这些节点仅编码相对于根状态的差异（添加和删除的谓词）。
树结构：编码包含显式原子，表示后继状态之间的转换以及深度节点以捕获搜索深度。这使得 R-GNN 能够直接在后继节点之间交换信息，并在单次前向传递中计算所有状态的嵌入。
效率：这种方法避免了重新编码共享状态描述，在测试场景中减少了超过一个数量级的内存使用（VRAM 从 >24GB 降至 <4GB），并能够同时评估所有转换。

2. 抽象 IW(1)（AIW(1)）

为了解决新颖性检查的扩展瓶颈，作者提出了一种 IW(1) 的松弛变体，在新颖性测试期间对状态原子进行抽象。

关系抽象：AIW(1) 不测试完全实例化的原子，而是迭代地将 $n$ 元原子的所有参数（除一个外）替换为其最具体类型（例如，将对象 $o$ 替换为 $type(o)$）。如果原子的任何抽象形式是新颖的，则该原子被视为新颖。
复杂度转移：这一修改将新颖性搜索的最坏情况复杂度从与地面原子数量线性相关，转变为与对象数量线性相关。
目标保持：目标中提到的原子不被抽象，以确保目标检测保持精确。
优势：这使得前瞻能够扩展到拥有数千个对象的实例，同时仍能捕捉有意义的子目标结构，并简化学习代理的成本结构。

训练过程

R-GNN 使用带有 hindsight Experience Replay (HER) 提升变体的深度 Q 学习进行训练。奖励定义为每步 -1，使得 Q 值代表到达目标的负期望转换次数。引入了一种辅助排序损失，以在前瞻树中强制深度顺序，确保代理学会避免因跳跃过远而导致的死胡同（例如在 Spanner 领域中）。

主要贡献

聚合 - 差分（AD）编码：一种用于 R-GNN 的新型输入编码，通过状态差异联合表示整个前瞻树。这使得所有后继状态的单次传递评估成为可能，大幅减少了内存占用和训练时间。
抽象 IW(1)（AIW(1)）：一种可扩展的前瞻机制，通过利用基于类型的抽象，将新颖性搜索的复杂度从原子的多项式级降低为对象的线性级。
最先进性能：AIW 和 AD 的结合在 IPC 2023 学习赛道及其他领域实现了新的性能基准，超越了以往的学习策略和 LAMA 等强大的经典规划器。

实验结果

作者在 IPC 2023 基准（10 个领域的 900 个实例）和扩展领域集（包括 Grid 和 Logistics）上评估了他们的方法。

IPC 2023 性能：AIW–AD 方法实现了 74% 的总覆盖率（900 个实例中的 668 个），显著优于：
- IW–AD（59%）：证明了抽象的价值。
- AIW–Ext（51%）和 IW–Ext（51%）：证明了 AD 编码的价值。
- LAMA（65%）：强大的经典基线。
- Flat AA（58%）：没有前瞻的扁平策略。
领域特异性：
- Satellite：AIW–AD 解决了 98% 的实例，完全解决了其他学习方法难以处理的该领域。
- Rovers & Childsnack：观察到显著改进，尽管 Childsnack 中的困难实例由于巨大的分支因子（数百万个动作）仍然具有挑战性。
- Sokoban & Floortile：性能保持低位，这与这些 PSPACE 完全或结构复杂的领域对于无搜索策略的已知难度一致。
可扩展性：该方法成功处理了多达 488 个块（Blocksworld）和超过 290,000 个原子（Rovers）的实例，而之前的 IW 策略公式由于内存限制在这些情况下失败。
表达力：该方法成功泛化到需要超越 C2 逻辑片段特征的领域（例如 Satellite、Rovers、Grid、Logistics），表明前瞻机制减轻了神经架构的表达负担。

意义与主张

本文主张，基于宽度的高效前瞻是扩展通用规划的关键推动因素。这项工作的意义主要体现在两个方面：

可扩展性：通过将前瞻搜索的复杂度与地面原子数量解耦（通过 AIW），并将神经编码的复杂度与转换数量解耦（通过 AD），该方法使得为以前对学习方法而言不可处理的巨大规划实例学习策略成为可能。
降低表达力要求：前瞻机制简化了学习代理的问题结构。通过“跳跃”过一系列原始决策，策略只需学习高层决策。这使得表达力有限的模型（标准 R-GNN）能够解决原本需要超越 C2 逻辑片段的复杂特征的领域。

作者得出结论，他们的方法代表了通用规划的新最先进水平，证明了将原则性搜索（前瞻）与高效神经编码相结合，可以使学习策略在保持跨多样和复杂领域的高性能的同时有效扩展。