Bilevel MCTS for Amortized O(1) Node Selection in Classical Planning¶

会议: AAAI 2026
arXiv: 2508.08385
代码: https://github.com/guicho271828/downward-mcts
领域: 经典规划 / 搜索算法
关键词: MCTS, 经典规划, O(1)节点选择, 树崩塌, UCB1-Normal2, IPC基准, 敏捷规划

一句话总结¶

提出双层MCTS（Bilevel MCTS），在MCTS选中的叶节点处运行深度比例预算的最优优先搜索，将节点选择均摊复杂度从 \(O(\log N)\) 降至 \(O(1)\)，辅以树崩塌（Tree Collapsing）减少动作选择步数，最终整合为 Nεbula 规划器，在IPC2018/2023基准上以192.2/230.6解题数（5min/30min）超越LAMA、DecStar、NOLAN、SM-Type-LAMA等全部SOTA。

研究背景与动机¶

领域现状：MCTS在博弈搜索（围棋、Backgammon）中取得巨大成功，但在经典规划社区并不流行。主流方法仍以队列式前向最优优先搜索（GBFS/A*）为主，近期试图解决探索-利用平衡的方法（如Softmin-type）也未采用MAB统计工具。

现有痛点：MCTS使用树形OPEN表，节点选择需从根节点递归下降到叶子，复杂度为 \(O(BD)\)（\(B\)为分支因子，\(D\)为深度），在平衡树中等价于 \(O(\log N)\)；而传统数组优先队列（Dial's algorithm）的popmin仅需 \(O(1)\)。实验散点图显示GUCTN2的节点处理速度可比GBFS慢三个数量级。

核心矛盾：博弈搜索中深度受限（围棋 \(d \leq 361\)），选择开销可忽略不计；但经典规划的搜索深度可任意大（\(k\)盘汉诺塔解长 \(2^k - 1\)），选择成本成为主要瓶颈。log-log散点图确认节点/秒与平均搜索深度呈明显反相关。

本文目标：消除MCTS因深度增长导致的节点选择效率瓶颈，使其在保留UCB1-Normal2探索-利用平衡优势的同时，匹配队列式搜索的底层效率，并最终超越现有SOTA规划器。

切入角度：不是改进启发式质量，而是从复杂度瓶颈分析入手——在MCTS选中的叶节点处启动带预算的BFS子搜索，预算与当前深度 \(D\) 成正比，从而"分摊"掉 \(O(D)\) 的树遍历开销。

核心idea：三层技术协同——(a) Bilevel MCTS用 \(b=D\) 的BFS实现均摊 \(O(1)\) 选择（Thm. 3）；(b) Tree Collapsing让子节点数不足阈值 \(\theta\) 的节点被跳过，减少无信息量的动作选择步；(c) Dynamic Tree Collapsing将 \(\theta\) 设为当前深度，免去超参调优；最终与novelty metric和交替队列正交组合成Nεbula。

方法详解¶

整体框架¶

标准MCTS的一次迭代包含：(1) 选择——从根递归选动作直到叶节点；(2) 展开——生成叶节点的后继；(3) 评估——计算 \(h(s_n)\)；(4) 回溯——更新祖先节点统计量。Bilevel MCTS修改步骤(1)+(2)：到达深度 \(D\) 的叶节点后，以该叶为起点用优先队列 \(Q\)（按NEC \(f\) 排序）运行BFS，展开 \(b=D\) 个节点后暂停，将所有展开节点统一回溯。若 \(Q\) 使用数组优先队列（Dial 1969），则popmin为 \(O(1)\)，\(D\)步选择 + \(D\)步BFS使每节点均摊选择代价为常数。最终Nεbula将Bilevel GUCTN2 + DTC与\(w_{\#l,h^{FF}}\) novelty metric、LAMAe风格4队列交替（boost=10）、eager evaluation组合。

关键设计1：深度比例动态预算¶

功能：BFS预算 \(b\) 等于到达叶节点时经过的动作选择步数（即树深度 \(D\)），而非固定超参。
核心思路：深度越深树遍历开销越大，用更多BFS展开来分摊；浅层预算少，不偏离MAB策略太多。理论上 \(D\) 步选择 + \(D\) 步BFS = \(2D\) 步处理 \(D+1\) 个节点，均摊 \(O(1)\)。
设计动机：Thm. 2证明堆实现时均摊 \(O(\log\log N)\)，Thm. 3证明数组队列时均摊 \(O(1)\)。与固定预算（\(b \in \{10, 100, 1000, 10000\}\)）对比，固定策略在浅层浪费太多时间于BFS、深层又分摊不够，动态预算在总解题数（347 vs 最佳固定327）和IPC分数上全面优于固定方案。

关键设计2：树崩塌（Tree Collapsing）¶

功能：展开节点 \(p\) 后，若祖父 \(p'\) 的子节点数 \(|S(p')| + |S(p)| - 1 < \theta\)，则将 \(p\) 的所有子节点直接挂到 \(p'\) 下并丢弃 \(p\)，计划路径追踪表独立维护不受影响。
核心思路：子节点少的内部节点在MAB动作选择中信息量低——它无法有效缩小候选叶节点集合。跳过这些节点可减少有效树深度，从而减少NEC计算次数。
设计动机：与Bilevel存在协同效应。Bilevel中BFS期间回溯被暂停，崩塌使多个展开节点返回同一祖父节点 \(p'\)，在回溯队列 \(B\)（按 \(g\) 排序的有序集合）中被去重，显著减少回溯计算量。实验证实Tree Collapsing单独应用于基础GUCTN2效果有限，但与Bilevel结合后从328→347.2（+5.8%）。

关键设计3：动态树崩塌（DTC）¶

功能：崩塌阈值 \(\theta\) 不固定，而是动态设为被崩塌节点的当前深度。
核心思路：借鉴动态预算的成功——深层节点容忍更大的崩塌宽度，浅层保持精细的MAB选择。
设计动机：避免 \(\theta\) 调优。实验显示DTC（347解题、182.4分）接近最优固定 \(\theta=40\)（347.2解题、184.1分），消除了超参选择的负担。

关键设计4：Nεbula 配置组合¶

功能：将Bilevel GUCTN2 + DTC与三种正交探索技术组合——(1) novelty metric \(w_{\#l,h^{FF}}\)（\(w_{max}=2\)，分 \(h\) 值子集计算最小新颖状态命题组合大小）；(2) LAMAe风格4队列交替 \([\text{n2}([w,h^{FF}]), \text{pr}(h^{FF}), \text{n2}([w,\#l]), \text{pr}(\#l)]\)；(3) boosted preferred operators（boost=10）。
核心思路：MAB处理单启发式的探索/利用；novelty鼓励访问新颖状态（类似软性closed list）；交替队列多样化启发式——三者各解决探索的不同维度，正交互补。
设计动机：使用eager evaluation（非lazy），因MCTS需准确 \(h\) 值维护MAB统计量。用树形OPEN直接替换LAMAe中标准队列（而非像SM-Type-LAMA那样新增队列），保持4队列的简洁性。消融实验确认去掉任一组件均导致性能下降。

实验关键数据¶

表1：Bilevel + Tree Collapsing 消融实验（IPC18+23 总计，5min，\(h^{CEA}+h^{CG}+h^{FF}\) 三种启发式合计）¶

配置	GBFS	Softmin	GUCTN2 base	Bilevel \(\theta\)=0	Bilevel \(\theta\)=40	Bilevel DTC	固定预算 \(b\)=100
总解题数	252	316.8	247	328	347.2	347	326.8
IPC分数	144.2	169.9	141.0	173.8	184.1	182.4	175.7

Bilevel使GUCTN2从247→328（+33%），加Tree Collapsing后达347.2（+40.5%）
DTC免调参性能347接近最优固定 \(\theta=40\) 的347.2
固定预算最佳 \(b=100\) 仅326.8，远低于动态策略

表2：与SOTA规划器最终对比（IPC18+23，含5min与30min设定）¶

方法	ApxNovelty	LAMA	SM-Type-LAMA	DecStar	NOLAN	LAMAe+BFWS	Nεbula
5min 解题数	166	164	186.4	163	177	177	192.2
5min IPC分	90.3	90.2	99.3	89.2	95.4	92.8	99.4
30min 解题数	201	208	213.4	174	204	226	230.6
30min IPC分	113.9	113.7	123.4	108.6	117.6	118.7	126.8

5min下Nεbula解题数192.2领先SM-Type-LAMA（186.4）+3.1%，IPC分与之持平
30min下优势显著扩大：230.6 vs SM-Type-LAMA 213.4（+8.1%），IPC分126.8 vs 123.4
30min末期LAMAe+BFWS（226）缩小差距，原因是Nεbula树管理内存耗尽

表3：Nεbula 消融实验（5min IPC18+23）¶

配置	Nεbula完整	去MAB(LAMAe+BFWS)	去novelty(N2DTC+LAMAe)	去交替(N2DTC+BFWS)
解题数	192.2	177	156.2	167.4
IPC分	99.4	92.8	79.1	86.8

去掉任意一个组件均导致明显退化，验证三种探索机制的正交互补性。

关键发现¶

节点选择是经典规划MCTS的核心瓶颈：散点图显示GUCTN2节点/秒可比GBFS低1000倍以上，且与搜索深度的对数呈线性负相关，与Thm. 1的 \(O(\log N)\) 预测一致。
动态预算远优于固定预算：深度比例策略自适应地在浅层做少量BFS、深层做大量BFS，总体性能显著优于任何固定值——最佳固定 \(b=100\) 的IPC分（175.7）仍低于动态方案（182.4）。
Bilevel与Tree Collapsing的协同效应：单独加Tree Collapsing对基础GUCTN2几乎无效（仅 \(h^{FF}\)+IPC23有提升），但与Bilevel结合后因回溯队列 \(B\) 中重复项被去重而额外加速。
三种探索机制正交互补：消融实验显示去掉MAB/novelty/交替队列任一项分别导致解题数从192.2降至177/156.2/167.4，其中novelty的贡献最大。
长时间运行释放Bilevel MCTS真正潜力：5min时Nεbula仅微幅领先，30min时优势扩大到8%以上，但树管理的内存开销在末期成为限制因素。
UCB1-Normal2是MCTS用于规划的正确MAB选择：因启发式奖励无上界（不同于博弈的0/1奖励），满足 \([0,c]\) 有限支撑假设的UCB1不适用，需要假设高斯分布（无限支撑 \(\mathbb{R}\)）的UCB1-Normal2。

亮点与洞察¶

理论-实验闭环论证：Thm. 1分析瓶颈→散点图验证→Thm. 2-3设计方案→实验确认节点/秒提升，每一步理论预测都有对应的实证。
"少量MAB即可高效"的惊人发现：深层搜索中大部分节点由BFS展开而非MAB驱动，说明UCB1-Normal2只需少量样本即可提供足够的探索-利用平衡信号。
DTC的优雅统一：动态崩塌阈值 \(\theta=\text{depth}\) 与动态预算 \(b=D\) 共享"深度成比例"直觉，免超参且性能接近最优，是工程上极具吸引力的设计。
模块化组合范式：Nεbula展示了MAB+novelty+交替队列的正交堆叠方法论——每项技术解决探索的不同维度，为未来规划器设计提供可复用框架。
渐进式写作风格：论文交替引入改进和小实验，每一步都有即时验证，使读者能逐步理解设计决策的必要性。

局限与展望¶

内存开销：树管理比队列式搜索消耗更多内存，30min运行末期导致内存耗尽（8GB限制），LAMAe+BFWS因此缩小差距至226 vs 230.6，微优化树结构可扩大优势。
仅适用单位代价问题：\(O(1)\) 均摊保证依赖Dial数组优先队列（仅处理稠密整数键值），非单位代价问题需回退到堆实现，复杂度退化为 \(O(\log\log N)\)。
Lazy evaluation不兼容：MCTS需准确 \(h\) 值维护MAB统计量，lazy evaluation的实验结果主要为负面（附录Table 4），限制了进一步的评估时间节省。
Novelty metric未用近似版本：当前采用 \(w_{max}=2\) 精确计算，存储开销随命题数二次增长。结合ApxNovelty的Bloom filter近似或NOLAN的动态 \(w_{max}\) 选择值得探索。
部分超参仍需领域知识：虽然DTC消除了 \(\theta\) 调优，但boost值（10 vs LAMA的1000）、eager vs lazy、队列数量等配置仍基于经验。

评分¶

新颖性: ⭐⭐⭐⭐⭐ 从复杂度分析出发提出 \(O(1)\) 均摊的Bilevel架构，理论扎实（3条定理）且实际有效，DTC的免超参设计优雅
实验充分度: ⭐⭐⭐⭐⭐ IPC18+23标准基准、3种启发式、7种baseline/变体、详细消融（Bilevel/TC/DTC/固定预算/novelty/交替队列）、5min+30min双设定、5种随机种子
写作质量: ⭐⭐⭐⭐ 渐进式引入改进+即时实验验证的组织方式非常清晰，但信息密度极高，附录内容丰富（≥12个section）需多次阅读
价值: ⭐⭐⭐⭐⭐ Nεbula在IPC标准基准上创造新SOTA，方法论的模块化正交组合思想可推广至其他搜索问题