蒙特卡洛搜索树在自动驾驶行为决策中的工程落地与调优实践

1. 为什么在自动驾驶里聊蒙特卡洛搜索树第一次在自动驾驶规划模块的评审会上听到有人提蒙特卡洛搜索树MCTS我的反应是这不是AlphaGo下围棋用的东西吗怎么跑到车道上来了。后来真正把一段城区无保护左转的决策逻辑拆开看才发现这个疑问本身问得不对——MCTS从来不是某个特定领域的专属算法它是一套在巨大且不确定的搜索空间里做序贯决策的通用框架。围棋的状态空间大到无法穷举自动驾驶的交互博弈同样如此你不知道对向那台车会不会抢行不知道旁边车道那台车下一秒会不会并线也不知道路口那个行人会不会突然迈步。这种别人也在做决策、而且我看不透他的场景恰恰是MCTS最擅长处理的地带。这篇东西不是教科书式的算法推导而是把我自己在做行为决策模块时围绕MCTS踩过的坑、做过的取舍、以及最后落地的工程方案完整讲一遍。核心关键词就几个蒙特卡洛搜索树、UCT、rollout、行为决策、博弈交互、置信上界、剪枝。如果你正在做自动驾驶的决策规划或者对序贯决策算法怎么从论文落到车上感兴趣这篇应该能给你省不少试错时间。我会从整体设计思路讲到具体实现再到实际调试中那些文档里不会写的坑尽量做到你看完能直接对着改自己的代码。先说清楚MCTS在自动驾驶里到底解决什么问题。传统的规则式决策比如有限状态机本质上是把什么情况做什么动作提前写死。直行、跟车、换道、左转每个状态配一套触发条件。这套东西在结构化高速场景里够用因为交互简单、参与者行为规范。但一到城区复杂路口状态机的组合爆炸就压不住了对向车、行人、非机动车、相邻车道每个参与者都有多种可能行为状态数呈指数增长你根本写不完规则。MCTS的价值在于它不需要你穷举所有情况而是通过采样的方式把计算资源集中投到看起来有希望的分支上用有限的算力逼近一个足够好的决策。这就是它和穷举搜索、和纯规则方法的根本区别。2. 蒙特卡洛搜索树的核心机制拆解2.1 四个阶段到底在干什么MCTS的经典流程分四步选择、扩展、模拟、回溯。很多人背得滚瓜烂熟但真到用的时候说不清每一步为什么这么设计。我用自动驾驶左转博弈的场景把它串一遍。选择阶段从根节点出发每次挑一个子节点往下走挑的依据是UCT公式。这个公式是MCTS的灵魂它把利用和探索两件事捏在一起。利用就是选当前看起来胜率高的分支探索就是给访问次数少的分支一点机会。公式长这样UCT Q/N c * sqrt(ln(N_parent) / N)Q是累计收益N是访问次数c是探索常数。第一项Q/N是平均收益代表利用第二项是探索项访问次数越少这项越大。c控制两者的平衡c大偏探索c小偏利用。在自动驾驶里这个c的取值非常讲究后面我会专门讲。扩展阶段走到一个还有未展开子节点的节点时生成一个新节点。在围棋里就是落一子在自动驾驶里就是执行一个动作——加速、减速、保持、左转一点、右转一点。这里的关键是动作空间怎么定义定义粗了决策不精细定义细了树爆炸。模拟阶段也叫rollout从新节点开始用一套快速策略一路走到终局得到一个收益值。围棋里是随机落子到终局自动驾驶里则是用简化模型快速推演未来几秒的演化。这一步是MCTS算力消耗的大头也是工程上最需要优化的地方。回溯阶段把模拟得到的收益沿着路径往回传更新每个节点的Q和N。这样下一次选择时好分支的Q/N会更高自然被优先选到。注意四步里最容易出问题的是模拟阶段。很多人直接照搬围棋的随机rollout结果在自动驾驶里完全不可用因为车辆运动有动力学约束随机动作根本走不出合理轨迹。这个坑我在第三节会详细讲怎么填。2.2 UCT公式里那个c到底怎么调c这个探索常数理论上有个推荐值sqrt(2)但那是针对收益归一化到[0,1]且奖励分布比较规整的场景。自动驾驶的收益函数往往不是这个量级而且不同场景下收益的方差差别很大。我实测下来的经验是c不能设成固定值要跟收益的量纲挂钩。具体做法是先把收益归一化。比如把安全、效率、舒适三个维度的加权得分映射到[0,1]区间然后c取0.5到1.5之间。城区复杂交互场景c取大一点鼓励探索因为对手行为不确定性高多试几个分支更稳妥高速巡航场景c取小一点因为交互简单快速收敛到最优跟车策略更重要。还有一个更细的点c可以随搜索深度衰减。浅层节点多探索深层节点多利用。因为越往深处模拟的误差越大过度探索深层分支意义不大。我一般让c从根节点的1.2线性衰减到叶节点的0.6左右实测决策稳定性有明显提升。2.3 收益函数怎么设计才不翻车MCTS最终选哪个动作取决于收益函数怎么定义。这是整个算法里最玄学也最考验工程经验的部分。自动驾驶的收益至少要覆盖三个维度安全、效率、舒适。安全维度核心指标是碰撞风险和最小安全距离。我一般用负的碰撞概率加上一个距离惩罚项距离越近惩罚越大而且是非线性增长接近碰撞时惩罚急剧上升。效率维度用通行时间或者速度保持度衡量鼓励尽快通过路口。舒适维度用加速度变化率、 jerk、方向盘转角变化率来惩罚避免决策出来的轨迹让乘客难受。难点在于三个维度的权重怎么定。我的做法是分层加权安全是硬约束权重给到压倒性的大一旦有碰撞风险其他维度得分再高也直接判负效率和舒适在安全满足的前提下做权衡城区拥堵场景效率权重高一点高速巡航舒适权重高一点。这个权重不是拍脑袋定的是拿大量仿真场景跑回归调出来的后面实操部分我会讲怎么调。3. 把MCTS落到自动驾驶决策模块的完整方案3.1 动作空间设计离散还是连续这是落地第一个要拍板的事。围棋是离散的361个点选一个。自动驾驶的动作空间本质是连续的——加速度连续、曲率连续。直接上连续空间MCTS的扩展和模拟都会变得极其复杂。我的选择是离散化加动作原语。具体做法把动作拆成横向和纵向两组原语。纵向原语包括急减速、缓减速、保持、缓加速、急加速五档对应加速度大概-3、-1.5、0、1.5、3 m/s²。横向原语包括左转大、左转小、保持、右转小、右转大五档对应曲率变化。两组组合起来是25个动作但实际不会全用根据当前场景裁剪掉明显不合理的比如已经在最左车道就不会有左转动作。为什么用五档而不是更细因为再细下去相邻档位的收益差异会被模拟噪声淹没MCTS根本区分不出来反而浪费算力。五档是实测下来既能保证决策精度、又不至于让树爆炸的平衡点。当然如果你的算力充裕可以做到七档但收益提升很有限。3.2 模拟策略从随机到启发式前面说了直接随机rollout在自动驾驶里不可用。我的方案是启发式快速模拟。具体讲从扩展节点开始不再随机选动作而是用一套简化的规则策略推演默认保持当前动作如果预测到碰撞风险就减速如果前方空旷就加速。这套规则比完整决策模块简单得多但比随机强太多能在毫秒级推演出未来3到5秒的演化。模拟的步长也有讲究。太细比如0.1秒一步5秒要模拟50步算力吃不消太粗比如1秒一步又会漏掉关键的动态变化。我一般用0.2到0.5秒的变步长交互激烈时用0.2秒平稳时用0.5秒。模拟的终止条件也要设计好要么到达预测时域终点要么发生碰撞要么进入一个明确的终局状态比如完成左转。提示模拟策略的质量直接决定MCTS的上限。我见过有人为了省算力用纯随机模拟结果搜索出来的决策还不如规则方法。启发式模拟虽然写起来麻烦但这是绕不过去的投入。3.3 树的规模控制与实时性保障自动驾驶是硬实时系统决策周期通常要求100毫秒以内留给MCTS的时间可能只有几十毫秒。这个时间预算下树不可能长得很大。我的经验是单次决策的模拟次数控制在500到2000次之间具体看算力平台。超过这个量级实时性就保不住了。控制树规模有几个手段。一是深度限制搜索深度一般不超过5到6层对应未来2到3秒的决策。再深下去预测误差太大搜了也没意义。二是宽度限制每个节点最多保留5到8个子节点用先验知识或者快速评估筛掉明显差的。三是时间预算硬截断不管搜到哪一步时间到了立刻返回当前最优这是实时系统的铁律。还有一个工程技巧复用上一周期的搜索结果。决策是周期性执行的上一周期搜过的子树这一周期可以直接拿来当先验省掉大量重复搜索。这个优化在实测中能把有效模拟次数提升30%以上。4. 实操过程与关键环节实现4.1 节点数据结构与内存管理先看节点怎么定义。每个节点至少要存这些信息状态自车位置、速度、周围参与者状态、动作从父节点到本节点的动作、访问次数N、累计收益Q、子节点列表、父节点指针。用C写大概长这样struct MCTSNode { State state; // 该节点对应的场景状态 Action action; // 从父节点到本节点的动作 double Q; // 累计收益 int N; // 访问次数 MCTSNode* parent; // 父节点指针 std::vectorMCTSNode* children; // 子节点 std::vectorAction untried; // 未扩展的动作 };内存管理是个容易被忽视的坑。MCTS每周期要创建和销毁大量节点如果直接用new/delete内存碎片和分配开销会拖垮实时性。我的做法是预分配对象池启动时一次性申请一大块内存节点从池里取用完还回去避免频繁的系统调用。对象池大小根据最大模拟次数和平均树规模估算一般留2到3倍余量。4.2 选择阶段的实现细节选择阶段从根节点往下走每步用UCT选子节点。实现时有个细节未完全扩展的节点要优先扩展而不是直接进选择。也就是说如果当前节点还有untried动作先扩展一个而不是继续往下选。这是标准MCTS的做法保证树是逐步长全的。UCT计算要注意数值稳定性。当N为0时探索项会除零所以要特判N为0的节点直接给无穷大收益优先访问。另外ln(N_parent)当N_parent为1时是0探索项为0这时候只能靠利用项区分所以根节点第一次扩展后要尽快让各子节点都至少访问一次。4.3 模拟阶段的加速技巧模拟是算力大头加速手段主要有三个。第一用简化动力学模型完整模型要考虑轮胎侧偏、悬架等模拟时用自行车模型甚至更简单的点质量模型就够了精度损失在可接受范围。第二并行模拟如果平台支持多线程把不同rollout分到不同线程实测能接近线性加速。第三提前终止模拟过程中一旦检测到碰撞或者明显劣势立刻终止并返回低收益不用跑完全程。我实测过一组数据单线程纯串行模拟1000次rollout大概要80毫秒改成四线程并行降到25毫秒左右再加上提前终止能压到15毫秒以内。这个提升对实时性来说是决定性的。4.4 收益计算与回溯回溯就是把模拟得到的收益沿着路径往回传更新每个节点的Q和N。这里有个细节收益要不要打折。也就是说深层节点的收益传到根节点时要不要乘一个折扣因子。我的做法是要打折折扣因子取0.9到0.95。因为越深的模拟误差越大对当前决策的参考价值越低打个折更合理。收益计算本身要封装成一个独立函数输入是模拟终局的状态输出是一个标量收益。这个函数要处理各种边界情况碰撞了返回负无穷到达目标返回正收益超时返回中性收益。写的时候要特别注意数值范围避免出现inf或者nan污染整棵树。5. 常见问题与排查技巧实录5.1 决策抖动怎么破这是MCTS落地最常见的问题相邻两个决策周期选出来的动作来回跳一会儿加速一会儿减速乘客体验极差。根因通常是搜索的随机性加上收益接近时的平局。解决办法有几个。一是增加模拟次数让收益估计更稳定但受实时性限制。二是动作平滑对连续几个周期的决策结果做低通滤波但这会引入延迟。三是在收益函数里加动作一致性惩罚如果本周期动作和上周期差异大扣分。我用的是组合方案适度增加模拟次数加动作一致性惩罚实测抖动明显减少同时延迟可控。5.2 搜索陷入局部最优MCTS理论上会收敛到全局最优但前提是模拟次数足够多。实际算力受限时容易陷在某个局部最优分支里出不来。表现就是决策一直很保守比如明明可以走的空档它非要等。排查思路先看探索常数c是不是太小太小会导致探索不足。再看先验知识是不是把某些分支过早剪掉了剪枝太激进会误杀好分支。我的经验是保留一定的探索比例即使某个分支当前看起来差也给它少量访问机会避免过早下定论。5.3 实时性不达标实时性问题是工程落地的大敌。排查顺序先看单次模拟耗时如果单次就超预算说明模拟策略太重要简化。再看模拟次数是不是设太多适当降低。然后看内存分配有没有瓶颈对象池是不是够大。最后看有没有不必要的拷贝状态传递尽量用引用或者移动语义。我整理了一个排查速查表现象可能原因排查方向单次决策超时模拟次数过多降低rollout上限单次模拟过慢动力学模型太重换简化模型内存增长异常节点未回收检查对象池归还逻辑决策抖动收益接近随机性加一致性惩罚决策保守探索不足调大c或增加探索树规模失控宽度未限制加子节点数上限5.4 与下游规划模块的接口MCTS输出的是一个决策动作或者一条粗略轨迹下游规划模块要把它细化成可执行的平滑轨迹。接口设计要注意MCTS输出的动作要带置信度规划模块根据置信度决定是直接执行还是再优化。如果MCTS自己都不确定比如两个分支收益接近规划模块应该更保守。还有一个坑MCTS的决策周期和规划模块的周期可能不一致。MCTS可能100毫秒一次规划可能50毫秒一次。这时候要做决策保持规划模块在两次MCTS决策之间沿用上一次的决策避免频繁切换。6. 参数调优与场景适配经验6.1 不同场景的参数配置MCTS的参数不是一套走天下要按场景配。我一般分三档高速巡航、城区跟车、复杂路口交互。高速巡航场景交互简单c取0.6模拟次数800深度4层收益里效率权重高。城区跟车c取0.9模拟次数1200深度5层舒适权重提上来。复杂路口c取1.3模拟次数2000深度6层安全权重压倒一切同时开启更激进的剪枝控制树规模。这套配置是拿仿真回归跑出来的每个场景跑几千个case看决策成功率、碰撞率、通行效率几个指标逐步调出来的。没有捷径就是堆场景堆时间。6.2 先验知识怎么注入纯MCTS从零开始搜效率低。注入先验知识能大幅加速收敛。注入方式有两种一是初始化时给子节点赋先验收益让搜索一开始就偏向合理分支二是剪枝时用先验筛掉明显不合理的动作。先验知识从哪来可以从规则策略来比如规则说该减速了那减速分支给高先验。也可以从学习模型来用一个轻量网络预测各动作的胜率。我用的是规则先验为主简单可靠不依赖训练数据。注意先验不能太强否则会压制探索退化成规则方法。先验收益的权重要控制好一般不超过总收益的30%。6.3 和其他决策方法的对比MCTS不是唯一选择也不是所有场景都最优。我做个横向对比方法优势劣势适用场景有限状态机简单、可解释、实时性好组合爆炸、难覆盖复杂交互高速结构化场景博弈论方法理论完备、交互建模清晰计算复杂、假设强两车博弈学习方法端到端、泛化潜力大数据依赖、可解释差数据充足场景MCTS处理不确定性强、无需大量数据算力消耗大、调参复杂复杂交互决策实际项目中我很少单用某一种而是混合架构规则做兜底和安全校验MCTS做复杂场景的决策学习模型做先验加速。各取所长。7. 一些踩坑之后的个人体会MCTS在自动驾驶里能不能用好算法本身只占三成剩下七成是工程。我见过太多人把论文里的MCTS直接搬过来结果实时性崩了、决策抖了、场景覆盖不了最后归咎于算法不行。其实问题往往出在模拟策略太粗糙、收益函数没调好、树规模没控制住这些工程细节上。我个人最大的体会是先把模拟策略和收益函数做扎实再谈搜索优化。模拟策略决定了搜索的上限收益函数决定了搜索的方向这两个不对搜索再快也是白搭。我早期为了追求搜索速度用了很粗糙的模拟结果决策质量还不如规则方法后来老老实实把模拟策略重写了一遍效果立竿见影。另一个体会是不要迷信单次决策的最优性。自动驾驶是连续决策单次最优不等于全局最优。有时候当前看起来次优的决策反而给后续留了更大空间。所以我在收益函数里会加一个未来可选性的考量鼓励决策保留更多后续选择而不是把路走死。最后分享一个小技巧用日志回放做离线调参。把实车或者仿真的场景数据录下来离线反复跑MCTS调参数、改收益函数比在线调效率高得多。我一般会攒几百个典型场景做回归集每次改完参数跑一遍看各项指标有没有退化避免改一个场景好了、另一个场景崩了。这套流程虽然土但真的管用。