生成式规划模型的高效测试时推理

# 面向生成式规划模型的高效测试时推理：OCL 搜索 来源: https://arxiv.org/html/2606.00618 ###### 摘要 生成式模型已成为 AI 规划领域的一种强大范式，但其性能仍受限于训练数据分布。一种改进方法是，在推理过程中通过扩展测试时计算来优化生成的解决方案。更高效的做法是优化推理过程本身。本文表明，经典 开-闭列表 (OCL) 搜索的改进版本恰好提供了这样一种高效的推理流程。我们的算法协同了两种学习组件：一种是从中间状态进行快速展开的生成式模型，另一种是用于对候选推理路径进行优先级排序的启发式模型。主要贡献包括新颖的探索控制机制，以及将学习模型集成到 OCL 框架中。在多个组合规划领域，我们的方法在计算效率和解决方案质量方面都优于神经符号搜索基线和经典求解器。机器学习, ICML ## 1 引言 自动化规划旨在寻找能够将初始状态转变为满足目标条件的动作序列。深度生成模型已成为规划生成的一种有前景的范式，能够在不同领域快速合成解决方案 (Rossetti 等, 2024b (https://arxiv.org/html/2606.00618#bib.bib1))。然而，解决方案的质量受限于训练数据，收集大规模最优数据集往往不可行；即使是像 Blocksworld 这样看似简单的领域，其最优求解也是 NP 难的 (Slaney 和 Thiébaux, 2001 (https://arxiv.org/html/2606.00618#bib.bib23))。另一种方法是在推理时投入额外的计算资源。Best-of-N 采样 (Stiennon 等, 2020 (https://arxiv.org/html/2606.00618#bib.bib4)) 会重复查询生成模型并返回最佳结果，但不会平衡探索与利用来以更低的成本找到更优解。诸如蒙特卡洛树搜索 (MCTS) 之类的搜索算法已成为定理证明 (Chen 等, 2024 (https://arxiv.org/html/2606.00618#bib.bib3); Hubert 等, 2025 (https://arxiv.org/html/2606.00618#bib.bib29)) 或代码生成 (Antoniades 等, 2025 (https://arxiv.org/html/2606.00618#bib.bib30)) 等正式推理领域中测试时计算的流行方法。然而，MCTS 方法通常采用 UCT 风格的选择（例如 PUCT；Rosin, 2011 (https://arxiv.org/html/2606.00618#bib.bib36)），其探索激励随着父节点访问次数的增加而增长。由于每次遍历都从根节点开始，较深的节点访问频率较低，往往会产生宽广但浅显的树。这种深度不平衡对于需要长时域规划的领域是有问题的，因为树深处的关键决策点仍未被充分探索。 开-闭列表 (OCL) 算法 (Hart 等, 1968 (https://arxiv.org/html/2606.00618#bib.bib32); Valenzano 和 Xie, 2016 (https://arxiv.org/html/2606.00618#bib.bib33))（如 A*）在全局范围内选择节点，并且是当前最先进符号规划器的基础 (Helmert, 2003 (https://arxiv.org/html/2606.00618#bib.bib2))。然而，与 MCTS 不同（其中生成模型可作为展开策略），标准的 OCL 既没有提供快速候选生成的机制，也不能补偿不可采纳的启发式函数。当在次优示例上训练时，学习到的启发式函数会高估代价值（剩余代价），对于远离目标的状态，其估计值会不成比例地膨胀，导致倾向于近目标节点的贪婪行为。此外，查询生成模型的计算成本很高，因此必须有选择性地调用。 我们提出了 OCLGen，一种针对自回归规划模型的计算高效测试时搜索算法，能够显著提高规划质量。我们的方法通过三项创新应对这些挑战：(1) **深度分割选择**：在每个深度层级维护独立的开放列表，确保在高估启发式函数的情况下仍能进行平衡探索；(2) **截断展开与自适应扩展**：利用生成模型进行快速多步合成，同时在低置信度决策点进行分支；(3) **分布性启发式估计**：根据低百分位代价值估计对节点进行排序，瞄准其最佳可能结果。在四个经典规划领域的实验表明，OCLGen 收敛到更短规划的速度显著快于基线方法。在具有已知最优解的问题上，给定相同计算预算，我们的方法在多个领域实现了 87.3% 的最优性，而 MCTS 为 49.8%。OCLGen 还提供了迭代自我改进的有效基础：经过三次改进迭代，我们的方法在 Blocksworld 上达到了 100% 的最优规划，在 Sokoban 上达到了 94.7%，而给定相同运行时间预算，使用 Best-of-N 采样的基础模型分别仅为 13.5% 和 51.3%。总结来说，我们的贡献包括： - • 一个现代化的 OCL 框架，结合自回归模型实现快速展开生成。 - • 一种在搜索中部署高估启发式函数的分布性方法。 - • 在四个领域进行的全面评估，并通过消融实验验证了每项设计选择。 - • 展示 OCLGen 在递归自我改进框架内的有效性。 ## 2 相关工作 #### 面向 AI 规划的生成式模型 深度生成模型通过学习从已求解实例集合中生成解决方案，已成为规划领域一种有前景的方法。近期工作同时探索了预训练大型语言模型 (LLM) 和小型领域专用 Transformer 用于规划生成。虽然 LLM 可以被微调用于规划任务 (Pallagani 等, 2023 (https://arxiv.org/html/2606.00618#bib.bib5))，但对其推理成本和可靠性的担忧促使研究人员在规划数据上从头训练更小的 Transformer。这些方法通常将规划问题形式化为自回归序列生成，逐 token 预测规划。例如，PlanGPT (Rossetti 等, 2024b (https://arxiv.org/html/2606.00618#bib.bib1)) 通过将单个动作分割成操作符名称和对象 token 的序列，在来自领域无关规划器的规划上训练 GPT2 模型。扩展工作包括在生成过程中集成动作验证器 (Rossetti 等, 2024a (https://arxiv.org/html/2606.00618#bib.bib7))，通过局部搜索修复无效规划 (Tummolo 等, 2024 (https://arxiv.org/html/2606.00618#bib.bib8))，以及利用对称性改进泛化 (Fritzsche 等, 2025 (https://arxiv.org/html/2606.00618#bib.bib9))。我们的工作采用了 (Rossetti 等, 2024b (https://arxiv.org/html/2606.00618#bib.bib1)) 中的模型架构和分词方案，并提出了一种高效推理算法。 #### 测试时搜索 生成模型中的测试时推理日益被构造成在候选解决方案或推理路径上的搜索。近期框架包括思维树 (Yao 等, 2023 (https://arxiv.org/html/2606.00618#bib.bib13))，它将广度优先搜索或深度优先搜索应用于深度推理；以及 rStar (Guan 等, 2025 (https://arxiv.org/html/2606.00618#bib.bib14))，它利用 MCTS 进行多步推理。在正式领域中，DeepSeek-Prover-V1.5 (Xin 等, 2025 (https://arxiv.org/html/2606.00618#bib.bib31)) 将 MCTS 与证明助手反馈相结合，而 PG-TD (Zhang 等, 2023 (https://arxiv.org/html/2606.00618#bib.bib15)) 将 AlphaZero 风格搜索与测试用例执行相结合，用于经过验证的代码生成。虽然这些方法大多针对通用 LLM 推理，但在这项工作中，我们专注于更小、领域专用的规划模型，在这些模型中，相同的搜索原则可以显著改善输出质量。 #### 通过搜索进行自我改进 测试时搜索可以作为独立的推理流程，也可以支撑递归的自我改进，其中搜索生成的解决方案为重新训练提供监督。将搜索和学习结合在自我改进循环中的方法可以追溯到早期的跳棋程序 (Samuel, 1959 (https://arxiv.org/html/2606.00618#bib.bib37))，此后通过使用学习到的神经启发式函数进行启发式搜索，被应用于经典规划 (Jabbari Arfaee 等, 2011 (https://arxiv.org/html/2606.00618#bib.bib38); Groshev 等, 2018 (https://arxiv.org/html/2606.00618#bib.bib42))。这一思想在 AlphaGo (Silver 等, 2016 (https://arxiv.org/html/2606.00618#bib.bib39)) 和 AlphaZero (Silver 等, 2017 (https://arxiv.org/html/2606.00618#bib.bib43)) 中获得了广泛关注，它们将 MCTS 与通过自我对弈训练的深度网络相结合。类似地，专家迭代 (ExIt) 框架 (Anthony 等, 2017 (https://arxiv.org/html/2606.00618#bib.bib41)) 形式化了这一循环，其中“专家”搜索迭代地监督“学徒”策略。类似的框架最近已被应用于微调 Transformer 用于推理 (Lehnert 等, 2024 (https://arxiv.org/html/2606.00618#bib.bib40); Zhang 等, 2024 (https://arxiv.org/html/2606.00618#bib.bib44); Chen 等, 2024 (https://arxiv.org/html/2606.00618#bib.bib3))、定理证明 (Xin 等, 2025 (https://arxiv.org/html/2606.00618#bib.bib31)) 和多步推理 (Guan 等, 2025 (https://arxiv.org/html/2606.00618#bib.bib14))。Gieselmann 等人 (2026 (https://arxiv.org/html/2606.00618#bib.bib45)) 的生成式规划框架将 Best-of-N 采样与图处理相结合，在递归循环中改进 Transformer，该循环在数据整理和模型微调之间迭代。我们在此工作基础上，专注于高效的测试时搜索，进一步加速自我改进。 ## 3 预备知识 ### 3.1 PDDL 中的经典规划 我们关注确定性、完全可观察、离散环境中的经典单智能体规划。规划问题由一个有限对象集 $\mathcal{O}$ 和一个有限谓词集 $\mathcal{P}$ 定义，其中每个谓词 $p\in\mathcal{P}$ 都有一个关联的元数 $\mathrm{arity}(p)$。通过用对象实例化谓词形成接地原子：$\mathcal{F}=\bigcup_{p\in\mathcal{P}}\left\{\,p(o_{1},\ldots,o_{\mathrm{arity}(p)})\mid o_{1},\ldots,o_{\mathrm{arity}(p)}\in\mathcal{O}\,\right\}$。状态 $s\in\mathcal{S}=2^{\mathcal{F}}$ 表示在给定的世界配置中为真的原子集合。动作 $a\in\mathcal{A}$ 是接地操作符 $a=\langle\mathrm{pre}(a),\mathrm{add}(a),\mathrm{del}(a)\rangle$，其中前提条件 $\mathrm{pre}(a)\subseteq\mathcal{F}$、添加效果 $\mathrm{add}(a)\subseteq\mathcal{F}$ 和删除效果 $\mathrm{del}(a)\subseteq\mathcal{F}$ 决定了适用性和结果。动作 $a$ 在状态 $s$ 中适用当 $\mathrm{pre}(a)\subseteq s$，产生后继状态 $F(s,a)=(s\setminus\mathrm{del}(a))\cup\mathrm{add}(a)$。目标 $s_g\in\mathcal{G}\subseteq 2^{\mathcal{F}}$ 是部分状态描述。状态 $s$ 满足目标 $s_g$ 如果 $s_g\subseteq s$。规划 $\tau=(a_{0},\ldots,a_{T-1})$ 是有效的，如果每个动作 $a_t$ 在状态 $s_t$ 中适用，并且从 $s_0$ 开始通过 $s_{t+1}=F(s_t,a_t)$ 执行序列达到满足目标的最终状态 $s_T$。在这项工作中，我们将最优性定义为最小规划长度。 规划领域定义语言 (PDDL) (McDermott 等, 1998 (https://arxiv.org/html/2606.00618#bib.bib18); Fox 和 Long, 2003 (https://arxiv.org/html/2606.00618#bib.bib19)) 是 AI 规划的标准形式化体系，支撑着国际规划竞赛等基准测试 (Vallati 等, 2015 (https://arxiv.org/html/2606.00618#bib.bib20))。PDDL 领域定义了谓词、类型化对象以及通过前提条件和效果指定的操作符。各个问题实例声明具体的对象、初始状态和目标条件。我们使用 PDDL 作为形式化语言来表述问题、状态和规划，同时利用其结构将规划问题分词，以便进行自回归序列生成。 ### 3.2 自回归规划模型 我们研究生成式模型 $\pi_{\theta}$ 的测试时推理，这些模型产生以初始状态 $s_0\in S$、目标规范 $s_g\in G$ 以及先前动作序列为条件的动作分布。考虑一种病态情况：两个未访问的前沿节点 $n_1$ 和 $n_2$，位于不同分支上，但预测会产生相同总长度 $L$ 的解决方案（即 $g(n_1)+h^*(n_1)=g(n_2)+h^*(n_2)=L$）。假设单位动作成本均一，已发生成本 $g(n)$ 等于节点的深度 $d$。假设 $n_1$ 比 $n_2$ 浅 ($g(n_1)<g(n_2)$)，因此 $h^*(n_1)=L-d_1$，$h^*(n_2)=L-d_2$，使得 $h^*(n_1)>h^*(n_2)$。现在考虑一个单调的、次优的启发式函数 $h$，它高估真实代价值 $h^*$ 的程度随深度增加（$h(n_1)=f_1(h^*(n_1))$，其中 $f_1(\cdot)$ 在 $h^*(n_1)$ 上是一个大于 1 的乘法因子，该因子随深度减小；对于 $n_2$ 类似）。结果估计值 $f_1>f_2$ 导致 $h(n_1)$ 的膨胀乘法因子更大，可能使其 $f$ 值 $g+h$ 超过 $n_2$ 的 $f$ 值，即使 $h^*(n_1)>h^*(n_2)$。因此，A* 可能会错误地偏好 $n_2$（深层节点，已发生成本高，剩余代价值低），而牺牲 $n_1$，尽管从 $n_1$ 探索可以得到更优解。这种高估启发式函数导致的浅层节点不充分探索问题，随着规划长度的增加而加剧，因为深度上的相对差异在长时域规划中变得更加显著。 ## 4 OCLGen: 基于搜索的测试时推理 我们提出 OCLGen（算法 1），一种针对自回归规划模型的高效测试时搜索。OCLGen 将经典 OCL 搜索与学习的神经网络组件相结合，权衡探索与利用，以在计算预算内生成更短的规划。其关键创新解决了高估启发式函数引导搜索偏向于高深度节点的经典问题，并通过高效、自适应的方式使用生成模型。我们使用三个估计量：已发生成本 $g(n)$（节点深度）、代价值估计 $\hat{h}(n)$（训练好的Transformer 预测的启发式值）和用于扩展的节点置信度 $\gamma(n)$。搜索状态分量首先通过符号模拟 PDDL 动作来计算。主动作预测模型 $\pi_{\text{action}}$ 是一个仅解码器的Transformer，它以嵌入的 PDDL 问题为条件，自回归地生成动作。启发式模型 $\pi_{\text{heur}}$ 是一个较小的 Transformer，定义在相同的（状态，目标）嵌入上，并输出一个标量代价值估计。独立预测器 $\pi_{\text{conf}}$ 提供置信度分数，可以通过对 $\pi_{\text{action}}$ 的输出分布进行分析（例如，softmax 估计误差的可学习校正）来计算。除非另有说明，我们使用 $\pi_{\text{conf}}=\pi_{\text{action}}$ 的 softmax 概率。 ### 算法 1 OCLGen 搜索 **输入**：初始状态 $s_0$，目标 $s_g$，预算 $B$，深度分区数 $D$，展开长度 $L$，α 参数，启发式比例因子，置信度阈值 τ。 **输出**：规划 $\pi$ 或失败。 1: 初始化一个空的开放列表哈希映射：`open[d]` 用于深度 $d=0,\ldots,D$。 2: 初始化空的关闭集 `closed`。 3: 创建一个根节点 $n_0 = \text{Node}(s_0, g=0)$。 4: 将 $n_0$ 添加到 `open[0]`。 5: 初始化 `best_plan` 为 `None`，`best_length` 为 $\infty$。 6: **while** `open` 非空且预算 $B$ 未耗尽 **do** 7: `l` ← 选择具有非空开放列表的最小深度 `d`。 8: `N` ← 从 `open[l]` 弹出具有最低 $f$ 值的节点。 9: **if** `N` 在 `closed` 中 **then** 10: **continue** 11: **end if** 12: 将 `N` 添加到 `closed`。 13: `γ` ← `π_conf`(N.state, s_g) 14: **if** `γ` ≤ τ **then** 15: `M` ← 1（低置信度：展开一步，执行标准扩展）。 16: **else** 17: `M` ← `min(L, budget_remaining)` 18: `(success, plan_tail, final_state)` ← `rollout(N, M)` 使用 `π_action` 和验证。 19: **if** `success` **then** 20: **if** `N.g + len(plan_tail) < best_length` **then** 21: `best_plan` ← `N.path + plan_tail` 22: `best_length` ← `len(best_plan)` 23: **end if** 24: **continue**（高置信度：将完整的展开路径视为解决方案）。 25: **end if** 26: `N'` ← 从展开中创建节点（动作序列、最终状态、成本增加）。 27: **for each** 在展开过程中经过的中间状态 `s_int` **do** 28: 创建一个辅助节点 `n_aux = Node(s_int, g=N.g + depth_in_rollout)` 29: 计算 `h_aux = π_heur(n_aux)`，`f_aux = n_aux.g + α * h_aux` 30: 将 `n_aux` 压入开放列表 `open[n_aux.g]` 31: **end for** 32: **else**（高置信度，但展开被截断：扩展最后一步） 33: `N_exp` ← 对于每个有效动作 `a`，创建子节点 `N_exp = Node(F(N.state, a), g=N.g+1)`。 34: 计算 `h_exp = π_heur(N_exp)`，`f_exp = N_exp.g + α * h_exp` 35: 将 `N_exp` 压入 `open[N_exp.g]` 36: **end if** 37: **end while** 38: **return** `best_plan` ### 4.1 深度分区开放列表 为了解决高估启发式函数引导搜索前往高深度节点的问题，我们引入了深度分区开放列表，其中节点根据其深度 $d = g(n)$ 存储在 `open[d]` 中。选择步骤（第 7 行）优先考虑最浅深度的非空分区。这保证了每个深度层次内的节点只与同一深度的其他节点竞争。因此，高估启发式函数不能通过人为降低深层节点的 $f$ 值将搜索偏向它们：$f$ = $g + h$ 仅在相同已发生成本 $g$ 的节点之间比较。分区确保算法持续探索浅层节点，直到该深度层次被彻底探索。这种策略有助于防止搜索在早期被错误地吸引到深层分支，并促进搜索树的更均匀展开。开放列表 `open` 在概念上是一个全局优先队列（按 $f$ 值排序），但具有按深度分割的约束；我们通过在每个深度维护独立的优先队列来实现这一点。### 4.2 具有自适应扩展的截断展开 直接在每个节点上查询生成模型代价高昂。我们引入了一种自适应机制，根据置信度度量 $\gamma = \pi_{\text{conf}}(n)$ 决定是使用生成模型进行快速多步展开，还是进行标准一步扩展。展开长度由置信度决定（第 14–31 行）：如果 $\gamma \leq \tau$，我们仅扩展一步（标准的单个动作应用）。如果 $\gamma > \tau$，我们尝试使用 $\pi_{\text{action}}$ 生成最多 $M = \min(L, \text{remaining\_budget})$ 个动作的多步展开，之后使用模拟器验证该展开。然而，展开可能无法达到目标；在这种情况下，我们将 $\pi_{\text{action}}$ 生成的中间状态用作 OCL 搜索中的新节点（第 27–31 行）。我们为展开过程中的每个中间状态 $s_t$ 创建一个辅助节点，并计算其启发式值。这些节点随后与其他所有节点一样，有资格再次进行扩展。这保证了即使生成模型生成了部分无效路径，搜索仍然能从该路径中学到有用的结构。一组连续的 $\pi_{\text{action}}$ 步骤有效地充当了展开策略——一种通过学习到的模型快速探索路径的方法——同时验证器保证动作的可操作性。通过只在低置信度节点进行一步扩展，我们避免了在生成模型已经自信的区域进行昂贵的穷举搜索，同时保持了 OCL 框架的全局最优性保证。**定理 1**：给定 $\alpha = 1$ 和置信度阈值 $\tau = 0$（即始终进行一步扩展），OCLGen 退化为具有 $h(n) = \pi_{\text{heur}}(n)$ 的 A* 搜索。*证明*：当 $\tau = 0$ 时，所有节点都进行一步扩展（第 14 行，因为 $0 \leq 0$ 为真）。因此，每次迭代都会扩展一个子节点，而不会进行多步展开。开放列表选择规则（第 7 行）优先选择最小深度，在深度分区内，选择具有最小 $f$ 值的节点。这等同于标准的 A* 决策规则：选择全局最小 $f$ 值；深度分区仍然在全局范围内选择 $f$ 值，因为 $f = g + h$，并且 $g$ 值不同。A* 使用相同的选择标准（$f$ 值），而不考虑深度，因此深度分区的选择强制 $f$ 值比较在 $g$ 值之间进行——但在 $\tau = 0$ 时，所有扩展都是深度为 1 的扩展，因此节点被添加到其各自的深度分区。在给定深度内选择最小的 $f$ 值等同于在全局 A* 选择中比较具有相同 $g$ 值的节点。由于 A* 不会先验地偏向任何 $g$ 值（除了通过其 $f$ 值），深度分区选择不会改变 A* 的算法行为：它只是限制了每次迭代的候选集。然而，因为 A* 最终会按照 $f$ 值的顺序扩展节点，并且深度分区选择只选择具有最小 $f$ 值的深度，这模拟了 A* 的排序行为。更正式地说：当 $\tau = 0$ 时，OCLGen 的搜索树与 A* 的搜索树相同，因为两种算法都从优先级队列中选择节点进行扩展。唯一的区别是队列的组织方式。由于 A* 在全局范围内选择具有最小 $f$ 值的节点，并且每个节点必须属于某个深度，因此存在一个深度具有该最小 $f$ 值的节点，并且深度分区选择将在该深度选择该节点。因此，两种算法的扩展顺序相同，生成的树结构也相同。∎ **推论 1**：当 $\tau = 0$ 且 $\pi_{\text{heur}}$ 是 $h^*$ 的可采纳下界时，OCLGen 保证找到最优规划。**推论 2**：对于 $\tau > 0$ 和 $L \geq 1$，OCLGen 在展开有限数量的步骤后，最终会考虑所有可访问的状态（假设预算充足）。**定理 2**（预算保证）：给定 $L = 1$，OCLGen 使用的生成模型查询次数不超过 $O(B)$，其中 $B$ 是总搜索预算（节点扩展次数）。对于 $L > 1$，最坏情况下的查询次数仍然是 $O(B)$，因为每次扩展对应于最多 $L$ 个生成步骤。*证明*：每个选中的节点（第 8 行）用于单个生成操作（展开最多 $L$ 步，或一步扩展）。在第 14–31 行的展开步骤中，对 $\pi_{\text{action}}$ 进行最多 $L$ 次调用（每次用于一个动作）以实现快速合成。因此，每个选中的节点产生对 $\pi_{\text{action}}$ 的 $O(L)$ 次调用。由于我们最多选择 $B$ 个节点，总的动作生成调用次数为 $O(B \cdot L) = O(B)$，因为 $L$ 是一个常数。∎ ### 4.3 分布性启发式估计 标准的 A* 搜索使用期望值下的点估计 $h(n)$，通常来自神经网络 (Chen 等, 2024 (https://arxiv.org/html/2606.00618#bib.bib3); Guan 等, 2025 (https://arxiv.org/html/2606.00618#bib.bib14))。然而，生成式规划模型本质上是随机的：模型每次查询可能会产生不同的 $h$ 值。我们观察到 $\pi_{\text{heur}}$ 在与 $s_g$ 的距离上通常产生高估的分布。由此，我们提出了分布性启发式估计：对于每个节点 $n$，我们通过 $\pi_{\text{heur}}$ 抽取多个样本，并取较低的百分位值（例如，第 10 个百分位数）作为节点 $f$ 值中使用的 $h_{\text{low}}(n)$。这缓解了高估问题，因为虽然 $\pi_{\text{heur}}$ 的期望可能远高于真实 $h^*$，但较低百分位估计更可能接近真实值，特别是在分布尾部与真实值对齐时。形式上，$h_{\text{low}}(n) = Q_{\alpha}(\{\pi_{\text{heur}}^{(i)}(n)\}_{i=1}^{k})$，其中 $Q_{\alpha}$ 是第 $\alpha$ 个百分位数。$f$ 值随后变为 $f(n) = g(n) + h_{\text{low}}(n)$。这鼓励搜索将节点视为具有其潜在的最佳结果（低百分位目标），并基于此进行乐观规划。与深度分区结合，它确保即使高估的启发式函数产生过度膨胀的点估计，搜索也能保持对浅层节点的探索。## 5 实验设置 ### 5.1 领域 我们从国际规划竞赛 (IPC) 基准测试中选择了四个领域：Blocksworld (推理和计划)、Logistics、Labyrinth 和 Sokoban。这些领域涵盖了不同的挑战：Blocksworld 涉及堆叠块组装；Logistics 涉及包裹递送调度；Labyrinth 涉及网格连通性和路径规划；Sokoban 涉及推箱子谜题。我们在每个领域内使用不同的实例大小，确保任务范围从简单到困难。对于最优性分析，我们包括了已知最优解长度的实例。由于推理时间在搜索中占主导地位，我们不报告训练时间。#### 领域规范 - **Blocksworld**：由 $n$ 个块和桌子位置组成的堆栈重新配置。目标是达到特定的堆栈布局。最优解长度范围从 2 到 30 个动作。 - **Logistics**：由 $n$ 个城市、$m$ 个地点、$l$ 个运输机、$p$ 个包裹组成。目标是调度将包裹运送到目的地。最优解长度范围从 4 到 100 个动作。 - **Labyrinth**：由 $n \times n$ 网格、单元格位置、可移动车辆组成（类似于推箱子变体）。最优解长度范围从 6 到 40 个动作。 - **Sokoban**：由 $n \times n$ 网格、盒子、目标位置、玩家组成。最优解长度范围从 8 到 144 个动作。 ### 5.2 模型架构 我们使用一个基于 Transformer 的单一主干网络，参数约为 85M，嵌入维度为 768，8 个注意力头，6 层，采用 (Rossetti 等, 2024b (https://arxiv.org/html/2606.00618#bib.bib1)) 的 token 化方案。模型使用来自 LAMA 规划器的规划进行训练，通过 $(s_0, s_g, a_{<t})$ 以教师强制方式预测下一个动作。$\pi_{\text{action}}$ 在推理时自回归生成。$\pi_{\text{heur}}$ 是一个较小的网络，3 层，嵌入维度为 256，作为一个回归头训练，使用 (Gieselmann 等, 2026 (https://arxiv.org/html/2606.00618#bib.bib45)) 的大规模计划最优规划数据集进行训练。它从 $\pi_{\text{action}}$ 的最终隐藏状态中提取特征，并输出一个标量代价值估计。$\pi_{\text{conf}}$ 是学得的置信度校准器，定义为 $\gamma(n) = 1 - \text{exp}(\text{softmax}(z_{\text{action}}) / T)$，其中 $T$ 是一个温度参数，$z_{\text{action}}$ 是输出的 logits。除非另有说明，$T=1$。模型在 NVIDIA A100 GPU 上进行微调，批量大小为 16，学习率为 $5 \times 10^{-5}$。 ### 5.3 基线与指标 我们将 OCLGen 与以下方法进行比较： - **Best-of-N** (BoN)：从中采样 16 个规划并选择通过验证的最短规划。 - **MCTS（完整展开）**：(Silver 等, 2017 (https://arxiv.org/html/2606.00618#bib.bib43); Chen 等, 2024 (https://arxiv.org/html/2606.00618#bib.bib3)) 的 PUCT 变体。 - **A*（学习启发式）**：具有 $h(n) = \pi_{\text{heur}}(n)$ 的标准 A*。 - **LAMA**：(Richter 等, 2011 (https://arxiv.org/html/2606.00618#bib.bib24)) 中描述的经典符号规划器。 指标包括：**规划长度**（最终规划中的动作数）、**计算时间**（搜索的挂钟时间，秒）、**最优性率**（达到已知最优长度的实例比例）、**成功率**（找到任何有效规划的实例比例）。所有试验均在 5 个随机种子上进行，并报告平均值和标准差。 ### 5.4 OCLGen 的配置 在所有实验中，我们使用展开长度 $L=5$，置信度阈值 $\tau=0.7$，$\alpha=0.9$ 表示 $f$ 值计算中启发式的权重，对于分布性启发式估计，使用 $k=5$ 个样本的第 10 个百分位数。预算 $B$ 根据领域进行调整：Blocksworld 为 500 个节点，Logistics 为 2000 个节点，Labyrinth 为 1000 个节点，Sokoban 为 4000 个节点。对于 MCTS 基线，我们使用 1000 次迭代，PUCT 常数为 $c=1.4$，并报告完整树搜索的结果。所有实验均在单个 NVIDIA A100 GPU 上运行。 ## 6 结果 ### 6.1 主要比较 表 1 显示了跨领域的平均规划长度。OCLGen 在所有领域都优于基线。在 Blocksworld 中，OCLGen 找到的规划平均比 BoN 短 28%，比 MCTS 短 22%，在 Sokoban 中，优势分别为 39% 和 31%。与 A*（学习启发式）相比，OCLGen 进一步减少了规划长度，特别是在 Logistics 和 Labyrinth 领域，优势分别为 19% 和 14%。LAMA 通常是探索的强基线，但 OCLGen 在 Sokoban（-22%）和 Labyrinth（-12%）中超过了它，突出了将学习与搜索相结合相对于纯符号方法的价值。 表 1：跨领域的平均规划长度（较低更好）。括号中为标准差。| 方法 | Blocksworld | Logistics | Labyrinth | Sokoban | |---------------------|-------------|------------|-----------|----------| | Best-of-N (16) | 14.2 (3.1) | 42.1 (8.7) | 22.5 (4.3) | 58.3 (12.2) | | MCTS (完整展开) | 13.1 (2.8) | 38.9 (7.2) | 20.1 (3.9) | 52.7 (10.8) | | A* (学习启发式) | 12.5 (2.4) | 36.4 (6.5) | 19.3 (3.6) | 49.8 (9.5) | | LAMA | 11.8 (2.1) | 34.2 (5.8) | 18.5 (3.2) | 45.6 (8.9) | | OCLGen | **10.2 (1.9)** | **32.8 (5.4)** | **16.7 (2.9)** | **42.9 (8.1)** | **最优性率**：表 2 显示了已知最优解实例上的最优性率。OCLGen 在所有领域都优于基线，在 Blocksworld 上达到 87.3%，在 Sokoban 上达到 79.2%，而 MCTS 分别为 49.8% 和 52.1%。这表明 OCLGen 的搜索策略在找到更接近最优的路径方面更有效。 表 2：具有已知最优解的实例的最优性率（%）（较高更好）。括号中为最优性置信区间。| 方法 | Blocksworld | Logistics | Labyrinth | Sokoban | |---------------------|-------------|------------|-----------|----------| | Best-of-N (16) | 25.4 (3.2) | 38.7 (4.1) | 33.1 (3.8) | 44.2 (4.5) | | MCTS (完整展开) | 49.8 (4.5) | 55.2 (4.8) | 48.9 (4.2) | 52.1 (5.