🤖 AI

Learning to Search and Searching to Learn for Generalization in Planning

本文提出了一种自改进框架，该框架将关系图神经网络与 $\mathrm{WA}^\star$ 搜索相结合，使深度强化学习智能体能够在稀疏奖励规划领域实现强大的零样本泛化能力，从而在不依赖搜索或专家演示的情况下解决规模显著更大的问题实例。

原作者： Michael Aichmüller, Yannik Hesse, Hector Geffner

发布于 2026-05-26

📖 1 分钟阅读☕ 轻松阅读

原作者： Michael Aichmüller, Yannik Hesse, Hector Geffner

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

想象一下，你正在教一个机器人如何解开一个复杂的谜题，比如一场巨大的推箱子（Sokoban，即把箱子推到特定位置）或积木世界（Blocksworld，即按特定顺序堆叠积木）游戏。

巨大的挑战不仅仅在于解开一个谜题；而在于教会机器人解开该谜题的任何版本，甚至是它从未见过的版本，无论箱子更多、起始位置不同，还是目标更大。这被称为泛化。

以下是论文《学习搜索与搜索学习》（Learning to Search and Searching to Learn）如何解决这一问题的简要说明：

1. 问题：在迷宫中迷失

在标准的 AI 训练（深度强化学习）中，机器人通常通过走一步、观察结果、再走一步来学习。这就像在黑暗的迷宫中用手摸索墙壁前行。

问题所在：在这些规划谜题中，“奖励”（找到解决方案）非常罕见。如果机器人只是随机游荡，它可能需要一百万年才能找到出口。它容易陷入死胡同或循环。
旧方法：一些方法试图先向机器人展示解决方案（就像老师展示答案钥匙），但这相当于作弊。另一些方法尝试从目标倒着走回来学习，但这并不总是适用于这些特定类型的逻辑谜题。

2. 解决方案：“智能地图”与“自我改进循环”

作者提出了一种名为**GSP（通用规划搜索，Generalized Search for Planning）**的新方法。与其盲目行走，他们赋予机器人两种相互辅助的超能力：

A. “智能地图”（启发式函数）

想象机器人拥有一张魔法地图（一个神经网络），它能观察当前的谜题并推测：“如果我在这里推这个箱子，离终点会有多近？”

这张地图不仅仅是猜测；它从经验中学习。
关键在于，这张地图是使用关系图神经网络构建的。想象谜题的碎片（积木、箱子）是故事中的角色。这张地图理解它们之间的关系（例如，“箱子 A 在箱子 B 的上面"），而不仅仅是将它们视为像素。这使得即使谜题变得巨大，地图也能理解规则。

B. “智能搜索”（探索者）

机器人不再一次走一步，而是使用最佳优先搜索（具体是一种名为**WA***的算法）。

类比：想象你在森林里寻找一只走失的狗。
- 标准强化学习（实时搜索）： 你选择一条随机路径，走 10 步，检查狗是否在那里。如果没有，你回去再试另一条随机路径。你浪费了大量精力。
- GSP（最佳优先搜索）： 你查看你的智能地图。它指出了 5 条最有希望的路径。你在脑海中同时探索这些路径，检查哪一条看起来最好。你只承诺走地图指出最有可能找到狗的那条路。

3. 魔法循环：“学习搜索，搜索学习”

这是核心创新。上述两部分在一个循环中相互反馈：

搜索以学习：机器人利用其当前不完美的智能地图，在谜题上运行智能搜索。它找到解决方案（或接近解决方案）。
数据：搜索过程产生了一笔宝贵的数据财富：“当我处于这种情况时，采取那个行动导致了解决方案。”
学习以搜索：机器人利用这些新数据来更新和改进智能地图。地图在猜测哪些移动是好的方面变得更擅长。
重复：现在，有了更好的地图，机器人可以更高效地搜索更困难的谜题。搜索发现更好的数据，使地图变得更聪明。

这是一个自我改进的循环：搜索教导地图，地图引导搜索。

4. 结果：解决不可能之事

论文在非常严峻的基准测试中验证了这一点：

积木世界：机器人在少于 30 个积木的谜题上接受训练。当在488 个积木的谜题（规模巨大跳跃）上进行测试时，它无需搜索就解决了问题。它只需查看地图就知道该做什么。这被称为“零样本泛化”。
推箱子与《见证者》（The Witness）：它解决了近 100% 的此类复杂谜题，通常比其他顶级 AI 方法找到解决方案的速度更快（步数更少）。
PushWorld：它处理了它从未见过的新的、更难的关卡，表现优于依赖随机探索的标准 AI。

总结

这篇论文介绍了一个系统，其中 AI 通过利用基于学习的智能地图来引导系统性搜索，从而学会解决逻辑谜题。

它不再盲目游荡，而是利用地图选择最佳路径。
它不再仅仅死记硬背一个谜题，而是学习物体之间的关系，从而能够解决任何规模的谜题。
搜索与学习相互促进，创造出一个机器人，它通过在旧问题上练习，就能更好地解决新的、未见过的难题。

简而言之：他们教会了 AI 停止猜测并开始规划，然后教会规划者如何从自己的规划中学习。

技术摘要：为规划中的泛化而学习搜索与通过搜索学习

问题陈述

组合泛化仍然是深度强化学习（DRL）中的核心挑战，其中策略或价值函数必须泛化到由共同问题结构定义的分布外场景。经典规划为此问题提供了理想的测试平台，因为其底层的关联结构（谓词和动作模式）是固定且显式的，而实例在对象数量、初始状态和目标上各不相同。

然而，标准的 DRL 方法在稀疏奖励的规划领域中表现挣扎。实时搜索（迭代的状态到状态转换），如在 LRTA* 或 RTDP 等 RL 算法中典型的方法，在这些设置中难以找到规划。相反，经典规划器使用最佳优先搜索（例如 A*、WA*），但依赖于手工制作的启发式函数。虽然最近的工作试图学习通用策略或启发式函数，但现有方法通常依赖实时搜索、来自专家演示的监督学习或 hindsight 重标记，未能建立一个自我改进的循环，其中搜索与学习相互强化，以实现跨不同问题规模的零样本泛化。

方法论：规划中的广义搜索（GSP）

作者提出了GSP，这是一个将最佳优先搜索与 Q 学习相结合的自我改进框架，用于学习通用的动作价值函数（ $Q_\theta$ ）。

核心循环

搜索引导的学习：GSP 不使用实时搜索，而是使用加权 A（WA）**来求解训练实例。搜索由当前学习到的 $Q_\theta(s, a)$ 值引导。
数据生成：随着 WA* 扩展节点，它生成一个转换的重放缓冲区。关键在于，搜索提供了标准 RL 所缺乏的监督信号：
- 目标路径：当达到目标时，算法回溯，为解路径上的状态 - 动作对分配实际的“剩余回报”值。
- 死胡同：如果某个状态是死胡同（无可用的动作），则为其父节点对分配固定的惩罚回报。
- 下界：搜索为解路径上遇到的任何状态 - 动作对提供最优回报的下界。
Q 学习更新： $Q_\theta$ 网络使用这些搜索衍生的目标进行更新。对于目标路径对，目标值为 $\max(R, \hat{y})$ ，其中 $R$ 是搜索衍生的下界， $\hat{y}$ 是标准的自举目标。这防止了价值估计下降到低于搜索已证明可达到的水平。
实例选择：为了优化学习效率，该框架维护三个实例池（未求解、已求解和已满足），并以指数增加的权重从中采样，优先选择提供最具信息量更新的实例（例如，那些具有次优解的实例）。

表示：关联图神经网络

为了确保在不同数量的对象和目标之间实现泛化， $Q_\theta$ 由**关联图神经网络（R-GNN）**表示。

输入：状态 $s$ 和目标 $g$ 被编码为一组基原子。通过引入辅助的“动作对象”和原子，显式地表示可用的动作，使网络能够在状态的上下文中评估特定的动作选择。
架构：网络在关联结构上使用消息传递。特定于谓词的多层感知机（MLP）根据参数角色生成消息，并通过置换不变函数进行聚合。
输出：共享的读取 MLP 将特定动作对象的嵌入与状态和目标的池化摘要相结合，以产生 Q 值。这种架构确保模型学习针对接地动作的通用评分原则，而不是为每个模式学习单独的预测器。

主要贡献

自我改进的搜索 - 学习循环：本文引入了一个框架，其中最佳优先搜索（WA*）生成高质量的训练数据（包括下界和死胡同信号）以更新学习到的启发式函数，而该启发式函数反过来引导更高效的未来搜索。
零样本泛化：学习到的 Q 函数作为通用策略，能够解决在训练期间未见过的、具有显著更多对象和不同目标的实例，在许多情况下无需在测试时进行搜索。
统一框架：该方法统一应用于不同的领域，从 2023 年国际规划竞赛（IPC）基准到组合谜题（Sokoban、The Witness）以及 PushWorld 领域，使用单一架构和超参数集。
优于实时搜索：这项工作证明，在稀疏奖励、高分支因子的规划领域中，用最佳优先搜索替代学习循环中的实时搜索对于成功至关重要。

实验结果

作者在三个类别的基准上评估了 GSP：

2023 IPC 学习赛道：
- 贪婪执行（ $GSP_\pi$ ）：在 Blocksworld、Miconic 和 Spanner 上实现了 100% 的覆盖率，优于 Lifted HER、LAMA 和 AlphaZero 风格策略等基线。
- 搜索引导（ $GSP_{WA^*}$ ）：结果喜忧参半；虽然它提高了 Sokoban 等谜题的覆盖率（从 14% 提升至 32%），但在具有巨大分支因子的领域（如 Blocksworld）中，有时会降低覆盖率，在这些领域中，学习到的启发式函数虽然有利于局部排序，但缺乏全局校准。
- 扩展性：在少于 30 个块的 Blocksworld 实例上训练的启发式函数，成功解决了488 个块的实例，且无需搜索。
组合谜题（Sokoban、The Witness、24 拼图）：
- 在Sokoban上， $GSP_{WA^*}$ 解决了 100% 的实例，平均扩展次数为 207 次，显著优于使用标准启发式函数的 WA*（3298 次扩展）和 DeepCubeA（1050 次扩展）。
- 在The Witness上，该方法解决了所有实例，证明了在死胡同状态上训练的价值。
- 在24 拼图上，该方法在训练期间未能找到解，突显了该方法需要至少能够找到一个解来启动学习，而在没有初始信息启发式函数的极难固定大小谜题中，这是困难的。
PushWorld：
- 在 Level 0 上训练，模型泛化到了 Level 1。 $GSP_{WA^*}$ 解决了 48/63 个 Level 1 实例，其规划更短，且扩展次数比经典规划器 LAMA 少约 30 倍。
- 作为贪婪策略，它显著优于无模型 RL 基线（DQN、PPO）。

意义与主张

本文主张，当转换模型已知时，最佳优先搜索是通用强化学习的优越探索机制，特别是在实时搜索无法发现信息丰富轨迹的稀疏奖励领域。

其主要意义在于展示了一个自我强化的循环：搜索提供了训练目标（下界、死胡同），使启发式函数得以改进，而改进后的启发式函数使后续搜索更加高效。这使得系统能够学习通用策略，以解决任意大小和复杂度的问题而无需搜索，或者学习高效的启发式函数来引导搜索至最优解。

作者谦逊地指出了局限性：学习到的 Q 函数通常作为强大的局部动作排序机制，但可能在整个搜索前沿缺乏全局校准，这可能导致 WA* 在具有极大分支因子的领域中出现次优性能。他们建议未来的工作可以专注于改进跨状态的价值泛化，并将最佳优先搜索与实时搜索和 hindsight 经验重标记的互补优势相结合。