🤖 machine learning

Test-Time Graph Search for Goal-Conditioned Reinforcement Learning

本文介绍了测试时图搜索（TTGS），这是一种轻量级且无需训练的规划封装方法，它利用现有离线目标条件强化学习策略固有的几何结构，在无需额外监督或参数更新的情况下，显著提升长程任务的成功率。

原作者： Evgenii Opryshko, Junwei Quan, Claas Voelcker, Yilun Du, Igor Gilitschenski

发布于 2026-05-26✓ Author reviewed ⓘ

📖 1 分钟阅读☕ 轻松阅读

CC BY 4.0

原作者： Evgenii Opryshko, Junwei Quan, Claas Voelcker, Yilun Du, Igor Gilitschenski

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

想象一下，你训练了一个非常聪明的机器人来穿越迷宫。你已经向它展示了成千上万条不同的路径，它学会了当起点和终点相距较近时如何从 A 点移动到 B 点。然而，当你要求它从迷宫的一侧穿越到另一侧时，它却感到困惑。它试图一步跨越巨大距离，却偏离目标、被困在角落，或耗尽时间。这是机器人学和人工智能中的一个常见问题：短期规划行之有效，但长期规划往往失败。

本文介绍了一种巧妙的“即插即用”解决方案，称为测试时图搜索（TTGS）。它无需重新训练机器人或教它新技能，而是在机器人开始移动之前，直接为其提供一张“地图”和一个“向导”。

以下是其工作原理，使用简单的类比说明：

1. 问题：“巨跃”陷阱

将训练好的机器人想象成一位对接下来 10 步内的地形了如指掌的徒步者。如果你让他们走 100 步到达一棵特定的树，他们可能会试图全程冲刺。由于他们无法清晰地看到那么远的地方，可能会绊倒在石头上或走进死胡同。用论文中的术语来说，机器人的“价值函数”（即其对某个动作好坏的内部猜测）在长距离上会变得嘈杂且不可靠。

2. 解决方案：“接力赛”策略

TTGS 不是让机器人一次性跑完整个马拉松，而是将旅程分解为一系列短小、可控的冲刺。它将机器人的旅程变成了一场接力赛。

地图（图结构）： 系统查看机器人已经完成的庞大练习运行库（离线数据集）。它从这些旧运行中提取关键“路点”，并将它们像地图上的点一样连接起来。
向导（最短路径）： 当你给机器人设定一个新目标时，系统使用经典数学算法（Dijkstra 算法）来寻找起点和终点之间的最短、最安全路径，且仅使用来自旧练习运行的那些点。
交接（子目标）： 机器人暂时不关注最终目的地，它只查看地图上的下一个“路点”。一旦到达该点，它会收到新指令，前往下一个路点。如此循环，直到抵达目标。

3. 秘诀：“软惩罚”

这里有一个陷阱：有时“地图”可能会建议一条看似捷径但实际上危险的路径（例如一座看起来坚固实则断裂的桥）。论文作者注意到，机器人内部对距离的“猜测”可能是错误的。

为了解决这个问题，他们添加了一个软惩罚。想象地图有一条规则：“如果某条路径看起来太长或太危险，我们不会删除它，而是对其征收巨额‘税’。”机器人的规划器仍然能看到这条危险路径，但它会更倾向于选择一条稍长但更安全、由可靠小步组成的路线。这防止了机器人尝试跨越它实际上无法跨越的鸿沟，同时保持了地图的连通性。

4. 为何它与众不同

无需重新训练： 你无需教机器人任何新东西。只需将你已构建的机器人配上这个“地图包装”，它就能立即表现得更好。
适用于“冻结”策略： 机器人的“大脑”是“冻结”的（在测试期间无法学习新事物），但这种方法能帮助它更有效地利用已有的知识。
懂得何时停止： 如果地图没有足够的“路点”来弥合起点和目标之间的差距（就像试图在没有踏脚石的情况下跨越峡谷），该系统足够智能，会说出“我无法安全地规划此路径”，然后让机器人自行尽力尝试。它不会强行执行糟糕的规划。

结果

研究人员在名为OGBench的基准测试中测试了该方法，该测试包含针对蚂蚁和人形机器人等复杂迷宫。

之前： 在最难的迷宫中，机器人经常完全失败（成功率为 0%）。
之后： 使用 TTGS 后，在许多情况下成功率跃升至**90%**以上。
对比： 这种性能匹配甚至超越了那些需要额外训练、昂贵计算机模型或在线练习的更复杂方法，而规划时间不到一秒。

总结

可以将 TTGS 想象成给一位技艺娴熟但目光短浅的徒步者配备了一个GPS，该 GPS 仅基于其他徒步者此前成功走过的路线，向他们显示接下来的几步安全路径。它将一段令人恐惧的长途旅程转化为一系列轻松、自信的短步，使机器人能够解决此前无法触及的问题。

技术摘要：面向目标条件强化学习的测试时图搜索

问题陈述

离线目标条件强化学习（GCRL）旨在利用预收集的数据集训练智能体以达成用户指定的目标，从而避免在线交互带来的成本和安全风险。虽然标准离线 GCRL 策略在中等时域任务中表现有效，但在长时域任务中往往失效。在复杂环境（例如大型迷宫）中，价值估计的误差会累积，导致策略不可靠，无法将数据集中不同部分的行为拼接起来。

针对这一问题的先前解决方案引入了显著的复杂性，例如计算密集型生成规划器、训练分布值函数集成、利用专门的几何表示，或依赖离线数据集之外的额外数据。这些方法通常基于一种假设，即标准的目标条件价值函数本质上过于嘈杂或不可靠，无法支持直接的长时域规划。

方法论：测试时图搜索（TTGS）

作者提出了测试时图搜索（TTGS），这是一种轻量级、无需训练的规划包装器，旨在增强冻结的 GCRL 策略。TTGS 完全在测试时运行，不需要额外的监督、参数更新或在线交互。

核心组件

图构建：
- 从离线数据集中采样一部分状态作为图的顶点。
- 利用距离信号为这些顶点之间的边分配权重。该信号可源自：
  - 价值导出的距离： 将预训练的目标条件价值函数 $V(s, g)$ 映射为估计的步数 $\hat{d}(s, g)$ 。论文提供了针对常见奖励约定的闭式映射（例如稀疏终端奖励或每步惩罚）。
  - 领域特定距离： 在可用时使用几何度量，如身体位置之间的欧几里得距离。
- 软惩罚机制： 为解决价值函数高估连通性（在间隙处创建“虫洞”）的问题，TTGS 对超过信任区域阈值 $\tau$ 的转换采用超线性惩罚函数 $p(\cdot)$ 。距离 $D_{ij} < \tau$ 的边保留其原始距离，而距离 $D_{ij} \ge \tau$ 的边被赋予权重 $p(D_{ij})$ （例如 $x \cdot 1000^{x/\tau}$ ）。这既保留了局部度量结构，又引导规划器走向一系列短小且可信的跳跃，防止图因硬阈值而碎片化，或允许不可行的长距离跳跃。
测试时规划：
- 最短路径搜索： 给定起始状态 $s_0$ 和目标 $g$ ，算法定位图中最近的顶点，并使用 Dijkstra 算法计算最短路径。该引导路径在每个回合中计算一次。
- 自适应子目标选择： 在执行过程中，智能体并非盲目跟随路径。相反，它根据步数预算 $T$ 从预计算的路径中选择一个子目标。智能体识别路径上距离当前状态在预算 $T$ 范围内的最远航点。如果不存在这样的航点，则选择下一个直接航点以确保向前推进。
- 策略执行： 冻结的基础策略 $\pi(a | s, \tilde{g})$ 被调用，输入为当前状态和选定的子目标 $\tilde{g}$ 。

诊断工具

论文引入了最大跳跃比率（ $\rho$ ）作为一种无需 rollout 的诊断指标，用于预测 TTGS 是否对新任务有益。 $\rho$ 是规划路径上最大边成本与总估计距离的比率。低 $\rho$ 表示有足够的中间状态覆盖（有利于 TTGS），而高 $\rho$ 表明数据集缺乏桥接状态，此时 TTGS 将退化为基础策略的行为。

主要贡献

价值函数的重新评估： 作者证明，此前被认为过于不可靠而无法用于搜索的标准离线 GCRL 价值函数，在经过新颖的软惩罚机制处理后，编码了足够的局部几何结构，可用于稳健的长时域规划。
无需训练的框架： TTGS 提供了一种方法，通过重用现有策略和价值函数来提升长时域性能，无需修改训练流程，也不需要额外的监督或在线交互。
最小开销下的性能提升： 实验结果表明，TTGS 显著提高了最先进离线 GCRL 智能体（HIQL, QRL, GCIQL, SAW, OTA）的成功率，且计算开销微乎其微（每个回合规划时间 < 1 秒）。

实验结果

该方法在涵盖运动（pointmaze, antmaze, humanoidmaze）和操纵任务的OGBench基准上进行了评估。

运动任务： TTGS 在基础策略通常失效的长时域“拼接”任务中取得了显著增益。
- 在 pointmaze-giant-stitch-v0 上，HIQL 的成功率从 0.0% 提升至 80.9%，GCIQL 从 0.0% 提升至 98.0%。
- 在 humanoidmaze-giant-stitch-v0 上，HIQL 从 4.4% 提升至 78.1%。
- 这些改进往往达到或超过了需要辅助训练或生成模型的复杂方法。
操纵任务： 在评估目标位于数据流形之外（例如 scene-play-v0）的任务中，TTGS 提供的增益极小（0–2 个百分点），但未降低性能；当缺乏中间状态时，它正确地退化为基础策略。
消融实验：
- 软惩罚与硬惩罚： 移除软惩罚（使用原始距离）或使用硬阈值（移除长边）会因图断开或路径不可行而显著降低拼接任务的性能。
- 子目标选择： 选择可达的最远航点的自适应策略优于总是选择下一个直接航点的简单策略。
- 距离来源： TTGS 在价值导出距离和简单的欧几里得身体位置距离上均有效，展示了其灵活性。

意义与主张

论文主张，通常被认为长时域规划所必需的额外复杂性往往是多余的。通过利用标准价值函数中已存在的潜在几何结构，并在测试时应用轻量级图搜索，从业者可以显著扩展现有离线 GCRL 智能体的能力。

作者强调，TTGS 是一种保守、安全的规划包装器：它仅依赖检索到的数据集状态，避免了生成式方法中常见的合成物理上不可能轨迹的问题。当离线数据缺乏连接起点和终点所需的中间状态时，TTGS 会优雅地退化为基础策略的行为，而不是生成不可靠的规划。这项工作表明，基于价值的 GCRL 智能体往往留下了未使用的有用几何结构，而 TTGS 提供了一种无需重新训练即可恢复该结构以用于长时域规划的方案。