精读笔记

Problem Setting

《Contact Planning for Multilegged Robots Under Constraints Through Parallel MCTS》（IEEE Transactions on Robotics / 2025）处理的是一个很具体但很硬的规划问题：多足机器人在复杂 3D 环境，尤其是稀疏落足点环境中，如何在有限时间内生成一条长时域、物理上可转移的离散接触序列。这里真正难的不是“给一条腿找一个落脚点”，而是每一步同时决定 gait、哪些腿支撑、哪些腿摆动、身体姿态/COG、每只脚的落足位置，并且每条边都要满足稳定、接触、运动学、关节力矩和碰撞约束。

关键矛盾是搜索空间和物理可行性之间的冲突。若只做启发式或局部落足，速度快但容易走进死胡同；若把所有变量和约束都放进图搜索/MIP/采样框架，可行性更强但高维组合爆炸会让运行时间不可接受。尤其在 sparse foothold 场景，可行解不是连续厚区域，而是少量离散通道；随机采样和宽度优先式搜索都容易把预算花在无效接触上。本文试图解决的不是最优接触规划，而是 time-limited 下尽快找到“足够长、足够可执行”的接触序列。

Motivation

作者对已有路线的判断比较明确：传统 decoupled heuristic 缺少未来视野，MIP 有全局性但整数变量和非凸约束扩展性差，RRT/PRM 在稀疏可行空间里无效采样太多，contact-implicit TO 更适合作为后端并依赖好的离散初值。也就是说，领域里缺的不是又一个单步 foothold selector，而是一个能在高维离散组合空间里利用有限 online compute 的搜索机制，并且搜索过程中不能把物理约束留给后端兜底。

这也是作者选择 MCTS 的原因：MCTS 的价值不在于理论最优，而在于它可以把搜索偏向 rollout 中看起来更有前途的分支，并且天然支持 anytime 和并行化。本文的关键缺口判断是：已有 MCTS 用于腿式机器人时通常动作空间过简化，或者 reachability checker 不够物理，导致规划结果可能只是“搜索上可达”，而不是“机器人上可执行”。因此本文真正想补的是“物理可达性约束 + 长时域启发式搜索”的接口。

Core Idea

核心思想可以概括为：把 contact planning 中最昂贵也最容易出错的物理可行性判断前移到 MCTS 的 expansion 阶段，让搜索树只在“边可行”的状态空间中生长；然后用并行 MCTS 的 test-time compute 在这个被约束后的巨大树中寻找长而高质量的分支。这里的建模改变是，节点不只是几何位置或抽象 gait，而是包含 base pose、COG、support/swing 状态、leg availability、foothold 和 contact normal 的完整接触状态；边的存在由多约束 transition feasibility 决定。

这引入了一个很强的 inductive bias：搜索不再平均探索所有动作组合，而是优先探索沿全局 guided path、满足准静态和运动学/力约束、且 rollout 能走得更远的接触模式。和 prior 的本质区别不是“用了 MCTS”本身，而是 MCTS 的动作生成被物理可达性重塑了；同时，backup 策略刻意从平均价值转向近似最大价值/深度优先，从而更像在有限时间内寻找一条可通行 corridor，而不是估计每个节点的真实期望收益。这种 bias 在稀疏可行解场景中是合理的，因为 planner 只需要一条好路径，不需要完整刻画所有策略价值。

Method

方法层面真正必要的机制有四个。

第一，path-guided candidate generation。它解决的是完全无引导接触搜索维度过高的问题。全局路径并不保证接触可行，只提供方向和局部搜索窗口，相当于把高维 contact search 限制到一条可能可通行的走廊附近。这个设计牺牲全局完备性，换取搜索效率，是本文能 practical 的前提之一。

第二，constrained expansion。每次扩展先枚举/生成候选 gait、COG configuration 和 foothold，再用静力稳定、接触承载/摩擦、运动学 convex hull、关节力矩可行性和碰撞条件过滤。它的作用不是事后评价节点，而是改变搜索树拓扑：不可转移的边根本不进入树。这是保证结果物理可信的核心。

第三，node evaluation + valueless node evaluation。节点价值偏向 simulation 中前进距离、扩展序列平均步长、稳定裕度和父子距离。VNE 把没有候选子节点或只通向死路的节点赋负值，并通过 backup 传播。这对 sparse foothold 特别关键，因为大量局部看似合理的接触状态其实是 trap；如果不显式传播“死路”信息，MCTS 会反复浪费预算。

第四，并行 MCTS 的工程化搜索策略。hash-driven root/tree parallelism 增加 test-time search budget；virtual loss 避免多个 worker 扎堆同一高分支；maximum/power backup 和 depth-first backup 则把搜索推向更深处。这里 DFB 是很激进的选择：它不是为了保持标准 MCTS 的价值估计一致性，而是为了在有限时间内尽快延长可行序列。

Key Insight / Why It Works

本文最关键的 insight 是：多足接触规划中的 MCTS 不应该被理解为通用强化学习式 policy improvement，而更像 constrained combinatorial search with online compute。它有效的原因有三层。

第一，物理约束前置显著提高有效分支密度。稀疏落足环境中的失败主要不是因为缺少搜索深度，而是因为无效分支太多。把静力、运动学、力矩、碰撞等约束做成 transition filter，相当于在树生成阶段做强剪枝，使 rollout 得到的价值更有意义。这是本文最实质的贡献。

第二，maximum/DFB backup 与任务目标匹配。标准 MCTS 的平均 backup 在这里反而不合适，因为 contact planning 不是要估计从某节点随机执行策略的期望回报，而是要找到一个可行长序列。一个节点下面只要有少数高价值子分支，就值得继续探索。最大化 backup 虽然更贪心，但对“找一条路”比对“评估一个策略”更合理。DFB 进一步把这种倾向推到极致，可能破坏收敛，但在 time-limited planning 中换来了更深树和更快发现通路。

第三，并行化本质上是 test-time compute scaling。论文中相当一部分性能提升来自扩展节点数增加，而不是新的理论规划原理。virtual loss、hash 分配、VNE、DFB 都是在让并行预算少浪费。这里可以直接判断：并行 MCTS 的收益主要是 scaling + search bias，而非更强的最优性保证。

哪些是核心，哪些是辅助？核心是 constrained expansion、VNE/死路传播和偏最大值的 backup；接触软地面模型、COG convex hull 构造、力矩离散检查等是让约束更物理的必要增强，但其中不少是已有思想的重组和工程落地。full constraints 的代价很高，尤其碰撞/STOMP 占比大，说明真实性能上限可能受工程检查器而不是 MCTS 本身限制。

Relation To Prior Work

这篇最接近的谱系是 decoupled contact planning + search-based multicontact planning + MCTS。它不是 contact-implicit trajectory optimization，也不是 learning-based planner；它仍然依赖先验地图、显式约束和后端轨迹优化。

相对 heuristic foothold planner，实质差异是有长时域回溯和 rollout，不只看当前最优落足。相对 graph search/A*，差异是不用试图系统性展开整个离散图，而是通过 simulation value 引导树生长。相对 RRT/PRM，差异是采样不是均匀或随机连接，而是沿路径引导并由历史 rollout 价值选择。相对 MIP，差异是放弃全局最优和严格完整性，换取 anytime 和更容易塞入非凸/离散检查器的灵活性。

看似新的部分里，parallel MCTS、virtual loss、Zobrist hashing、maximum backup 都不是新思想；创新在于把这些搜索技巧针对多足接触规划重新组合，并与一套较完整的 reachability checker 绑定。比较实质的新增信息是：1）将多约束 transition feasibility 系统性放入 MCTS expansion；2）用 valueless node negative propagation 处理 trap states；3）对力矩约束采用沿过渡轨迹离散检查，而不是固定支撑下构造保守 COG 区域；4）指出并修正此前 COG workspace convex hull 在姿态不一致时的叠加问题。

Dataset / Evaluation

评估覆盖范围相对充分：六足机器人 sparse foothold 是最能体现本文优势的主场；人形场景用于证明方法不只适用于六足；软地面、负载、碰撞、楼梯和真机实验用于支撑“多约束物理可行性”的 claim。真机验证是加分项，尤其展示了约束是否纳入规划会改变 gait 和落足策略。

不过 evaluation 也有明显边界。首先，对比方法在 full constraints 下并不都具备同等实现，很多比较只能在简化约束下公平进行，因此“物理可行性优于主流方法”的 claim 有一定不对称性：本文方法能处理更多约束，部分原因是作者把这些检查器接进去了，而不是其他 planner 原理上不能接。其次，稀疏随机 foothold benchmark 很适合 MCTS + VNE 展示优势，但也可能偏向能快速发现单条通路的 anytime search。再次，人形 dense terrain 场景复杂度较低，作者自己也承认速度优势不明显，因此它更像 generality demo，而不是强 benchmark。

总体上，实验支持“在稀疏离散可行空间和有限时间下，该搜索策略更实用”这一核心结论；但不充分支持更强的全局说法，例如比 MIP/TO 在一般 multicontact planning 上更优。

Limitation

最根本限制是准静态假设。本文所有 reachability 基本围绕静力平衡、短步长、慢速移动和离散过渡检查展开，不提供动态可行性保证。跳跃、快速跨越、动量利用等行为不在能力边界内。

第二，方法把问题从优化求解转移到了候选生成和约束检查。若地图/SDF 不准、地形摩擦/刚度参数未知、足端接触模型失配，规划可行性会快速变成假象。软地面承载能力实验很有说服力，但也暴露了强依赖 terrain parameter 的问题；真实部署中这些参数很难稳定获得。

第三，长序列执行依赖控制器和状态估计精度。作者也指出实际中执行一步后的误差会让后续计划失效，因此真机采用只执行最新一步、持续重规划。这说明 planner 表面上生成长序列，但 deployment 更接近 receding-horizon contact selection；长期规划能力在真实系统中被控制误差显著削弱。

第四，DFB/maximum backup 是有代价的。它明显偏向深度和高分孤立分支，可能错过同层更稳健但短期分数不高的路线。论文用有限时间表现为其辩护是合理的，但理论上这不是稳健规划器，而是 aggressive anytime search。

第五，scalability 上限并不只由 MCTS 决定。full constraints 下碰撞检测和 STOMP 消耗巨大；worker 数增加后通信开销导致收益饱和。所谓 parallel scalability 是有限范围内成立，不是线性扩展。

Takeaway

• 1. 对接触规划这类“只需找到一条可行长路径”的问题，最大值导向/深度优先式 MCTS 往往比标准期望值估计更合适；不要机械套用 UCT 的平均 backup。
• 2. 物理约束最好进入搜索树生成过程，而不是作为后端失败后的惩罚。
• constrained expansion 比 reward penalty 更关键，因为它改变了有效分支密度。
• 3. sparse feasible space 中，显式识别 trap states 并向上传播负价值非常重要；VNE 这个思想可迁移到其他机器人任务，如多接触操作、移动操作、狭窄通道导航。

一句话总结

这篇论文把多足长时域接触规划推进为“多约束可达性过滤 + 并行 MCTS test-time search”的实用框架，贡献主要在搜索偏置和物理可行性耦合，而不是全局最优规划理论。