1. 为什么在自动驾驶里聊蒙特卡洛搜索树第一次在自动驾驶规划模块的评审会上听到有人提蒙特卡洛搜索树Monte Carlo Tree SearchMCTS我下意识觉得这玩意儿不是下围棋用的吗怎么跑到车上了。后来真正把一段城区无保护左转的决策逻辑啃下来才发现这个疑问本身就问错了方向——MCTS从来不是某个特定领域的专属工具它是一套在巨大且不确定的搜索空间里做序贯决策的通用框架。自动驾驶的决策规划本质上就是这样一个问题状态空间连续且维度极高其他交通参与者的意图不可完全观测动作一旦执行就不可撤销还得在几十到几百毫秒内给出结果。这几个约束叠在一起恰好落在MCTS最擅长也最头疼的区间里。这篇东西我想聊的不是教科书上那套UCB公式推导而是把它放回自动驾驶决策规划的真实语境里它到底解决什么问题、和传统的有限状态机或者采样规划器比优势在哪、工程落地时哪些参数是命门、哪些坑我踩过。适合已经了解基础规划概念、想深入决策层算法的同学也适合刚接触自动驾驶、想搞明白决策和规划到底怎么分工的入门者。我会尽量把每个选择背后的为什么讲透而不是甩一堆公式让你自己悟。需要先明确一个前提MCTS在自动驾驶里通常不直接输出油门刹车方向盘它更多出现在行为决策层或者粗粒度轨迹选择层负责在几个候选行为跟车、换道、让行、抢行之间做带前瞻的权衡把选出来的高层意图交给下游的优化器或控制器去细化。理解这个定位后面很多设计取舍就顺了。2. 蒙特卡洛搜索树到底在搜什么2.1 从博弈树到行车决策树的思维迁移传统博弈树搜索比如Minimax要求把整棵树展开到终局然后自底向上回传价值。围棋的状态空间是10的170次方量级象棋也有10的40次方以上全展开根本不可能。MCTS的思路转变在于我不求全局最优我用随机采样的方式把计算预算集中投到看起来最有希望的分支上。它通过反复执行选择-扩展-模拟-回传四个步骤逐步把一棵不对称的树建起来树越深的地方说明那条路径越值得深挖。迁移到自动驾驶这棵树的节点就是某个时刻的自车状态环境状态边就是自车采取的一个动作或行为。比如根节点是当前我在路口等待左转对向有直行车流它的子节点可能是我加速抢在头车之前通过我等这辆车过去再走我缓慢蠕行试探对方意图。每个子节点继续往下展开就形成了一棵描述未来若干秒可能演化路径的树。MCTS要做的是在有限的计算时间内判断哪条根分支的期望回报最高。这里有个关键认知MCTS输出的不是一条精确轨迹而是一个动作分布的统计估计。它告诉你在当前局面下抢行这条分支被访问了800次平均回报0.3让行被访问了1200次平均回报0.7于是你选让行。这种用访问次数和平均价值共同决定的机制天然带有探索与利用的平衡比单纯贪心要稳。2.2 四个核心步骤在行车场景里的具体含义选择Selection从根节点出发每次选一个子节点往下走直到遇到一个还没完全展开的节点。选哪个子节点的依据是UCTUpper Confidence Bound for Trees公式它把节点的平均回报和探索奖励加起来。探索奖励那一项和父节点访问次数/该子节点访问次数的比值有关访问得少的节点会被补偿一个较大的探索值从而有机会被重新光顾。在行车场景里这意味着即使某个行为当前看起来不好比如让行导致通行效率低只要它被访问得少算法仍会给它机会去验证避免过早陷入局部最优。扩展Expansion到达一个未完全展开的节点后给它添加一个或多个新的子节点。自动驾驶里这一步通常不是随机加而是从预定义的行为原语集合里挑或者从采样器里采一批候选动作。这里就有工程取舍了动作空间设计得太粗只有加速/减速/保持树会很浅、决策粒度不够设计得太细连续加速度值分支因子爆炸计算扛不住。模拟Simulation/Rollout从新节点开始用一个相对简单的策略比如固定跟车模型、恒定速度假设快速推演到某个终止条件到达规划时域末端、发生碰撞、到达目标。这一步是MCTS的灵魂也是最容易被误解的地方。很多人以为模拟必须很精确其实恰恰相反——模拟要的是快和相对无偏用大量粗糙但独立的采样来逼近期望。如果每个rollout都跑一遍完整的动力学优化那计算量直接爆炸MCTS的采样优势就没了。回传Backpropagation把模拟得到的回报沿着刚才走过的路径反向更新每个节点的访问次数和累计价值。注意回报的定义直接决定了算法行为。碰撞给大负值、到达目标给正值、通行效率给小的正奖励、舒适性给惩罚项这些权重的相对大小会显著改变决策风格。2.3 为什么它适合自动驾驶的不确定性场景自动驾驶最难受的地方在于其他交通参与者是活的。一个行人站在路边他可能马上过马路也可能只是等人。传统确定性规划器要么假设最坏情况永远假设他会冲出来导致过度保守、频繁急刹要么假设最可能情况赌他不出来风险高。MCTS的随机模拟天然能表达这种多模态在模拟阶段我可以让行人以一定概率过马路、一定概率不动跑很多次rollout最后统计出来的期望回报就隐含了对这种不确定性的加权。再一个优势是随时可中断。MCTS是 anytime 算法给它10毫秒它能给个粗糙答案给它100毫秒它能给个更靠谱的答案。这对车载实时系统太重要了——规划周期是硬约束算法必须在预算内出结果而不是算完为止。相比之下很多基于优化的方法在复杂场景下可能迭代不收敛你得额外加超时兜底逻辑。3. 和传统决策方法硬碰硬对比3.1 有限状态机简单可靠但组合爆炸绝大多数量产车的决策层用的是有限状态机FSM或者层次状态机。它的好处是可解释、可验证、行为确定出了问题能精确定位到哪条转移边。比如跟车状态下如果前车距离大于阈值且相邻车道空闲转移到换道状态。这套逻辑在高速巡航这种场景里非常成熟。但它的软肋在城区复杂交互里暴露得很彻底。状态和转移条件是人手写的场景一多状态数呈组合爆炸。左转要处理对向直行、对向左转、行人、非机动车、路口内滞留车辆每个因素都要加状态和条件最后维护成本极高而且状态之间的优先级冲突很难调和。更致命的是FSM没有前瞻——它只看当前满足哪个转移条件不会去评估我如果现在抢行三秒后会不会被卡在路口中间。MCTS在这里的补位价值就是用搜索代替手写规则把前瞻评估交给模拟。你不需要穷举所有交互组合只需要定义好动作原语和回报函数让搜索自己去发现抢行三秒后会被堵这件事。3.2 采样规划器会采样但不会权衡意图采样类规划器比如RRT、Lattice Planner在轨迹层很能打它们撒一堆候选轨迹用代价函数打分选最优。但它们的短板在于缺乏对其他智能体反应的建模。一条轨迹的代价通常只考虑静态障碍和自车动力学对我这么走旁边那辆车会不会加速挤我这类博弈性交互基本无能为力。MCTS把对方会反应这件事显式地放进了树结构里。虽然标准MCTS是单智能体的但通过把其他车辆的行为也作为环境随机性建模在rollout里让它们按某种策略动作就能近似出交互效果。更进阶的做法是把它扩展成多智能体博弈树每个智能体轮流做决策这就接近了博弈论里的纳什均衡求解思路。3.3 各类方法横向对比维度有限状态机采样规划器蒙特卡洛搜索树前瞻能力无只看当前条件有限看单条轨迹代价强多步模拟交互建模手写规则难扩展弱通常忽略中到强可建模反应不确定性处理靠保守阈值靠代价加权天然支持概率采样可解释性极高中中靠访问统计实时性极高中到高取决于预算可调调参难度低但规则维护累中高回报函数敏感复杂场景表现差中好这张表不是要证明MCTS全面碾压而是说明它补的是前瞻和交互这两块短板。实际工程里更常见的是混合架构FSM管高层模式切换和兜底MCTS在关键博弈场景无保护左转、匝道汇入、环岛里做精细决策采样规划器负责轨迹细化。4. 工程落地的核心细节与参数命门4.1 动作空间设计粗一点还是细一点这是第一个要拍板的事。动作空间太粗比如只有{加速减速保持}三档树的分支因子是3深度10就是3的10次方约6万节点搜索能覆盖但决策粒度太糙选出来的加速到底加多少下游还得再猜。动作空间太细比如加速度离散成-3到3每隔0.5一档13个动作深度10就是13的10次方天文数字采样根本覆盖不过来。我的经验是分层设计高层用粗粒度行为原语5到8个每个原语内部再挂一个参数化的低级控制器。比如跟车这个原语内部用IDM模型根据前车距离自动算加速度MCTS只需要决定选跟车还是选换道不需要决定具体加速度值。这样分支因子控制在个位数深度可以做到8到12步每步0.5秒覆盖4到6秒的决策时域对城区场景基本够用。注意动作原语之间要有明确的语义区分避免两个原语在大多数情况下产生几乎相同的轨迹那等于白白浪费分支预算。设计完可以用离线数据统计一下各原语被选中的频率如果某个原语几乎从不被选要么是它没用要么是回报函数把它压死了。4.2 回报函数决定算法性格的地方回报函数是MCTS的价值观它直接决定车开得激进还是保守。我见过一个团队把碰撞惩罚设成-1000通行效率奖励设成1结果车在路口怂得不敢动因为任何有碰撞风险的行动期望值都被压到负无穷。后来把碰撞惩罚调到-100效率奖励调到5行为就正常多了。一个可用的回报函数通常包含这几项安全性碰撞、接近碰撞TTC低于阈值、违反交规给大负值通行效率向目标前进的距离、通过路口耗时给正值舒适性加速度、 jerk加加速度、曲率变化给惩罚合法性压线、闯红灯、超速给惩罚进度奖励到达目标区域给大正值权重量级要拉开安全项必须比效率项高至少一个数量级否则算法会为了省时间而冒险。但也不能高太多否则过度保守。这个平衡没有理论最优解只能靠场景测试调。4.3 UCT探索常数探索与利用的旋钮UCT公式里的探索常数c理论推荐值是√2≈1.414针对奖励归一化到[0,1]的情况。但实际调的时候这个值对行为影响很大。c越大算法越倾向于尝试访问少的节点行为越好奇、越多样c越小越倾向于利用当前已知的好分支行为越固执。在行车场景里我倾向于把c设得比理论值略小大概0.7到1.0之间。原因是行车决策的试错成本太高过度探索意味着频繁尝试奇怪的行为乘客体验差。但也不能太小太小就退化成贪心遇到局部最优出不来。这个值最好结合具体场景做网格搜索用离线回放数据评估不同c值下的通行效率和舒适性指标。4.4 模拟策略快而不过度简化Rollout策略的选择是个技术活。最粗暴的是随机策略但随机在连续动作空间里几乎必然导致车辆行为荒谬随机加减速模拟出来的回报没有参考价值。稍微好点的是固定策略比如所有车都保持当前速度简单但忽略了交互。比较实用的折中方案是用简化的IDM跟车模型恒定速度假设做rollout。IDM计算量极小能捕捉基本的跟车和避撞行为比随机策略靠谱得多又比完整优化快几个数量级。另一个技巧是限制rollout深度不一定要模拟到规划时域末端模拟2到3秒往往就能区分出好坏分支再深边际收益递减。实操心得rollout的随机性来源要设计好。如果所有rollout都用同一个确定性策略那模拟结果就没有方差MCTS退化成确定性搜索失去处理不确定性的能力。正确做法是在rollout里对关键不确定量其他车意图、行人行为做随机采样让每次模拟走不同的分支。5. 完整实操流程与关键环节实现5.1 环境建模与状态表示先把状态定义清楚。一个可用的状态向量通常包括自车位置、速度、加速度、航向角周围车辆的位置、速度、航向车道线信息交通灯状态目标点。维度轻松上几十维。MCTS不需要把整个状态向量塞进节点节点只需要存决策相关的关键量比如自车在哪个车道、相对目标点的进度、与最近交互对象的相对关系。状态离散化是个绕不开的问题。连续状态没法直接建树得做聚合。常见做法是按语义区间离散距离前车分{近中远}相对速度分{接近保持远离}组合起来形成有限的状态标签。粒度太细树爆炸太粗决策失真。我的经验是每个维度分3到5档总状态数控制在几百到几千量级。5.2 树的初始化与迭代控制根节点就是当前状态。每次规划周期开始时可以复用上一周期的树——把上一周期选中的分支对应的子树提升为新的根其余丢弃。这叫树复用能显著提升搜索效率因为相邻周期的场景高度相关。实测下来树复用能让有效搜索深度提升30%以上。迭代次数由时间预算决定。典型车载计算平台给决策层50到100毫秒单次rollout如果控制在0.1到0.5毫秒那能跑100到1000次迭代。迭代次数不是越多越好超过一定次数后边际收益递减而且可能因为过度搜索而想太多反而错过最佳决策时机。# MCTS主循环伪代码简化版 def mcts_search(root_state, time_budget_ms): root Node(root_state) deadline now() time_budget_ms while now() deadline: node select(root) # UCT选择 if not node.is_terminal(): node expand(node) # 扩展一个子节点 reward rollout(node) # 随机模拟 backpropagate(node, reward) # 回传更新 return best_child(root) # 返回访问次数最多的子节点5.3 回报计算与安全兜底回报计算要在rollout结束时进行。碰撞检测用简单的包围盒或圆形近似别用精确多边形太慢。TTC碰撞时间计算用相对距离除以相对速度低于阈值就给惩罚。到达目标用距离阈值判断。安全兜底是必须的。MCTS再聪明也可能因为搜索不充分而选出危险动作所以下游必须有一层独立的安全校验选出来的动作如果会导致TTC低于硬阈值或者违反交规直接否决退回到保守动作比如最大减速度刹车。这层校验不能依赖MCTS自己的回报函数必须是独立的、确定性的规则这样才能保证底线安全。5.4 参数选择过程实录拿一个无保护左转场景举例。规划时域设5秒每步0.5秒深度10。动作原语设6个加速通过、匀速通过、减速让行、停车等待、蠕行试探、退回等待区。探索常数c从0.5到1.5做网格搜索步长0.25。rollout策略用IDM其他车辆意图按70%直行、20%减速、10%让行的概率采样。测试下来c0.75时通行效率和舒适性的综合得分最高。c0.5时过于保守经常无谓等待c1.5时过于激进有几次模拟出抢行导致冲突。迭代次数从100增加到500决策质量提升明显从500增加到1000提升很小但耗时翻倍所以定在500次配合树复用实际单周期耗时约60毫秒满足100毫秒预算。6. 常见问题与排查技巧实录6.1 决策抖动相邻周期选不同行为这是最常被抱怨的问题。车在路口一会儿想走一会儿想等行为不连贯。根因通常是搜索的随机性导致每次结果略有不同加上场景本身处于决策边界。解决办法有几个一是树复用让上一周期的搜索成果影响本周期的先验二是加行为迟滞如果上一周期选了让行本周期让行的初始价值给个小加成除非有强证据表明该换三是在回报函数里加行为切换惩罚频繁切换行为本身扣分。6.2 计算超时复杂场景迭代不够场景一复杂分支因子和rollout耗时都上升固定迭代次数可能跑不完时间预算。对策是动态调整迭代次数设一个最小迭代数保证基本质量然后看剩余时间继续跑时间到就停。另外rollout要做早停一旦检测到碰撞或明显失败就立即返回不用跑完整个时域。6.3 回报函数调参困难回报函数权重多互相耦合调一个影响一片。我的做法是分层调先只开安全项确保车不撞再加效率项调到通行合理最后加舒适项微调平顺性。每次只动一个维度用固定的测试场景集评估别凭感觉。6.4 常见问题速查表现象可能原因排查方向解决手段决策抖动搜索随机性边界场景看相邻周期选中分支树复用迟滞切换惩罚过度保守碰撞惩罚过大检查回报权重降低安全项量级过度激进效率奖励过大检查回报权重提高安全项量级计算超时分支因子大/rollout慢profile各阶段耗时动态迭代rollout早停行为单一探索常数太小看访问分布增大c值模拟失真rollout策略太简对比模拟与真实换IDM限制深度避坑技巧别在真车上直接调MCTS参数先用离线回放数据做批量评估。把历史场景数据喂进去统计不同参数下的碰撞率、通行时间、jerk均值用数据说话。真车测试只用来验证最终选定的参数组合。7. 我对这套方法的一些真实体会MCTS在自动驾驶决策里不是银弹它的计算开销和调参复杂度决定了它更适合作为关键场景的增强模块而不是全场景的主力。高速巡航用FSM就够了没必要上MCTS徒增算力负担。但在城区无保护左转、环岛、匝道汇入这些博弈性强、规则难穷举的场景MCTS的前瞻和交互建模能力确实能带来质变。我踩过最大的坑是早期把回报函数设计得太复杂十几项加权结果调参调到怀疑人生而且各项之间互相干扰根本理不清谁在起作用。后来砍到五项核心指标反而效果更好。这件事让我明白MCTS的威力来自搜索不是来自回报函数的精巧。回报函数只要能把好坏区分开就行剩下的交给搜索去发现。另一个体会是树复用的价值被严重低估。很多人每次规划都从零建树浪费了大量计算。相邻周期的场景相关性极高复用上一周期的树相当于免费获得了先验知识实测能省30%到50%的迭代次数达到同等决策质量。这个优化实现起来不难但收益很实在。后续如果想继续深入可以往两个方向走一是把单智能体MCTS扩展成多智能体博弈搜索显式建模其他车的策略二是把rollout策略从固定模型换成学习出来的策略网络用数据驱动的方式提升模拟的真实性。这两个方向都有不少公开研究可以参考但工程落地的复杂度也会相应上升得权衡投入产出。