1. 為什么在自動駕駛里聊蒙特卡洛搜索樹第一次在自動駕駛規(guī)劃模塊的評審會上聽到有人提蒙特卡洛搜索樹MCTS我的反應是這不是AlphaGo下圍棋用的東西嗎怎么跑到車道上來了。后來真正把一段城區(qū)無保護左轉(zhuǎn)的決策邏輯拆開看才發(fā)現(xiàn)這個疑問本身問得不對——MCTS從來不是某個特定領(lǐng)域的專屬算法它是一套在巨大且不確定的搜索空間里做序貫決策的通用框架。圍棋的狀態(tài)空間大到無法窮舉自動駕駛的交互博弈同樣如此你不知道對向那臺車會不會搶行不知道旁邊車道那臺車下一秒會不會并線也不知道路口那個行人會不會突然邁步。這種別人也在做決策、而且我看不透他的場景恰恰是MCTS最擅長處理的地帶。這篇東西不是教科書式的算法推導而是把我自己在做行為決策模塊時圍繞MCTS踩過的坑、做過的取舍、以及最后落地的工程方案完整講一遍。核心關(guān)鍵詞就幾個蒙特卡洛搜索樹、UCT、rollout、行為決策、博弈交互、置信上界、剪枝。如果你正在做自動駕駛的決策規(guī)劃或者對序貫決策算法怎么從論文落到車上感興趣這篇應該能給你省不少試錯時間。我會從整體設(shè)計思路講到具體實現(xiàn)再到實際調(diào)試中那些文檔里不會寫的坑盡量做到你看完能直接對著改自己的代碼。先說清楚MCTS在自動駕駛里到底解決什么問題。傳統(tǒng)的規(guī)則式?jīng)Q策比如有限狀態(tài)機本質(zhì)上是把什么情況做什么動作提前寫死。直行、跟車、換道、左轉(zhuǎn)每個狀態(tài)配一套觸發(fā)條件。這套東西在結(jié)構(gòu)化高速場景里夠用因為交互簡單、參與者行為規(guī)范。但一到城區(qū)復雜路口狀態(tài)機的組合爆炸就壓不住了對向車、行人、非機動車、相鄰車道每個參與者都有多種可能行為狀態(tài)數(shù)呈指數(shù)增長你根本寫不完規(guī)則。MCTS的價值在于它不需要你窮舉所有情況而是通過采樣的方式把計算資源集中投到看起來有希望的分支上用有限的算力逼近一個足夠好的決策。這就是它和窮舉搜索、和純規(guī)則方法的根本區(qū)別。2. 蒙特卡洛搜索樹的核心機制拆解2.1 四個階段到底在干什么MCTS的經(jīng)典流程分四步選擇、擴展、模擬、回溯。很多人背得滾瓜爛熟但真到用的時候說不清每一步為什么這么設(shè)計。我用自動駕駛左轉(zhuǎn)博弈的場景把它串一遍。選擇階段從根節(jié)點出發(fā)每次挑一個子節(jié)點往下走挑的依據(jù)是UCT公式。這個公式是MCTS的靈魂它把利用和探索兩件事捏在一起。利用就是選當前看起來勝率高的分支探索就是給訪問次數(shù)少的分支一點機會。公式長這樣UCT Q/N c * sqrt(ln(N_parent) / N)Q是累計收益N是訪問次數(shù)c是探索常數(shù)。第一項Q/N是平均收益代表利用第二項是探索項訪問次數(shù)越少這項越大。c控制兩者的平衡c大偏探索c小偏利用。在自動駕駛里這個c的取值非常講究后面我會專門講。擴展階段走到一個還有未展開子節(jié)點的節(jié)點時生成一個新節(jié)點。在圍棋里就是落一子在自動駕駛里就是執(zhí)行一個動作——加速、減速、保持、左轉(zhuǎn)一點、右轉(zhuǎn)一點。這里的關(guān)鍵是動作空間怎么定義定義粗了決策不精細定義細了樹爆炸。模擬階段也叫rollout從新節(jié)點開始用一套快速策略一路走到終局得到一個收益值。圍棋里是隨機落子到終局自動駕駛里則是用簡化模型快速推演未來幾秒的演化。這一步是MCTS算力消耗的大頭也是工程上最需要優(yōu)化的地方。回溯階段把模擬得到的收益沿著路徑往回傳更新每個節(jié)點的Q和N。這樣下一次選擇時好分支的Q/N會更高自然被優(yōu)先選到。注意四步里最容易出問題的是模擬階段。很多人直接照搬圍棋的隨機rollout結(jié)果在自動駕駛里完全不可用因為車輛運動有動力學約束隨機動作根本走不出合理軌跡。這個坑我在第三節(jié)會詳細講怎么填。2.2 UCT公式里那個c到底怎么調(diào)c這個探索常數(shù)理論上有個推薦值sqrt(2)但那是針對收益歸一化到[0,1]且獎勵分布比較規(guī)整的場景。自動駕駛的收益函數(shù)往往不是這個量級而且不同場景下收益的方差差別很大。我實測下來的經(jīng)驗是c不能設(shè)成固定值要跟收益的量綱掛鉤。具體做法是先把收益歸一化。比如把安全、效率、舒適三個維度的加權(quán)得分映射到[0,1]區(qū)間然后c取0.5到1.5之間。城區(qū)復雜交互場景c取大一點鼓勵探索因為對手行為不確定性高多試幾個分支更穩(wěn)妥高速巡航場景c取小一點因為交互簡單快速收斂到最優(yōu)跟車策略更重要。還有一個更細的點c可以隨搜索深度衰減。淺層節(jié)點多探索深層節(jié)點多利用。因為越往深處模擬的誤差越大過度探索深層分支意義不大。我一般讓c從根節(jié)點的1.2線性衰減到葉節(jié)點的0.6左右實測決策穩(wěn)定性有明顯提升。2.3 收益函數(shù)怎么設(shè)計才不翻車MCTS最終選哪個動作取決于收益函數(shù)怎么定義。這是整個算法里最玄學也最考驗工程經(jīng)驗的部分。自動駕駛的收益至少要覆蓋三個維度安全、效率、舒適。安全維度核心指標是碰撞風險和最小安全距離。我一般用負的碰撞概率加上一個距離懲罰項距離越近懲罰越大而且是非線性增長接近碰撞時懲罰急劇上升。效率維度用通行時間或者速度保持度衡量鼓勵盡快通過路口。舒適維度用加速度變化率、 jerk、方向盤轉(zhuǎn)角變化率來懲罰避免決策出來的軌跡讓乘客難受。難點在于三個維度的權(quán)重怎么定。我的做法是分層加權(quán)安全是硬約束權(quán)重給到壓倒性的大一旦有碰撞風險其他維度得分再高也直接判負效率和舒適在安全滿足的前提下做權(quán)衡城區(qū)擁堵場景效率權(quán)重高一點高速巡航舒適權(quán)重高一點。這個權(quán)重不是拍腦袋定的是拿大量仿真場景跑回歸調(diào)出來的后面實操部分我會講怎么調(diào)。3. 把MCTS落到自動駕駛決策模塊的完整方案3.1 動作空間設(shè)計離散還是連續(xù)這是落地第一個要拍板的事。圍棋是離散的361個點選一個。自動駕駛的動作空間本質(zhì)是連續(xù)的——加速度連續(xù)、曲率連續(xù)。直接上連續(xù)空間MCTS的擴展和模擬都會變得極其復雜。我的選擇是離散化加動作原語。具體做法把動作拆成橫向和縱向兩組原語?？v向原語包括急減速、緩減速、保持、緩加速、急加速五檔對應加速度大概-3、-1.5、0、1.5、3 m/s2。橫向原語包括左轉(zhuǎn)大、左轉(zhuǎn)小、保持、右轉(zhuǎn)小、右轉(zhuǎn)大五檔對應曲率變化。兩組組合起來是25個動作但實際不會全用根據(jù)當前場景裁剪掉明顯不合理的比如已經(jīng)在最左車道就不會有左轉(zhuǎn)動作。為什么用五檔而不是更細因為再細下去相鄰檔位的收益差異會被模擬噪聲淹沒MCTS根本區(qū)分不出來反而浪費算力。五檔是實測下來既能保證決策精度、又不至于讓樹爆炸的平衡點。當然如果你的算力充?？梢宰龅狡邫n但收益提升很有限。3.2 模擬策略從隨機到啟發(fā)式前面說了直接隨機rollout在自動駕駛里不可用。我的方案是啟發(fā)式快速模擬。具體講從擴展節(jié)點開始不再隨機選動作而是用一套簡化的規(guī)則策略推演默認保持當前動作如果預測到碰撞風險就減速如果前方空曠就加速。這套規(guī)則比完整決策模塊簡單得多但比隨機強太多能在毫秒級推演出未來3到5秒的演化。模擬的步長也有講究。太細比如0.1秒一步5秒要模擬50步算力吃不消太粗比如1秒一步又會漏掉關(guān)鍵的動態(tài)變化。我一般用0.2到0.5秒的變步長交互激烈時用0.2秒平穩(wěn)時用0.5秒。模擬的終止條件也要設(shè)計好要么到達預測時域終點要么發(fā)生碰撞要么進入一個明確的終局狀態(tài)比如完成左轉(zhuǎn)。提示模擬策略的質(zhì)量直接決定MCTS的上限。我見過有人為了省算力用純隨機模擬結(jié)果搜索出來的決策還不如規(guī)則方法。啟發(fā)式模擬雖然寫起來麻煩但這是繞不過去的投入。3.3 樹的規(guī)?？刂婆c實時性保障自動駕駛是硬實時系統(tǒng)決策周期通常要求100毫秒以內(nèi)留給MCTS的時間可能只有幾十毫秒。這個時間預算下樹不可能長得很大。我的經(jīng)驗是單次決策的模擬次數(shù)控制在500到2000次之間具體看算力平臺。超過這個量級實時性就保不住了?？刂茦湟?guī)模有幾個手段。一是深度限制搜索深度一般不超過5到6層對應未來2到3秒的決策。再深下去預測誤差太大搜了也沒意義。二是寬度限制每個節(jié)點最多保留5到8個子節(jié)點用先驗知識或者快速評估篩掉明顯差的。三是時間預算硬截斷不管搜到哪一步時間到了立刻返回當前最優(yōu)這是實時系統(tǒng)的鐵律。還有一個工程技巧復用上一周期的搜索結(jié)果。決策是周期性執(zhí)行的上一周期搜過的子樹這一周期可以直接拿來當先驗省掉大量重復搜索。這個優(yōu)化在實測中能把有效模擬次數(shù)提升30%以上。4. 實操過程與關(guān)鍵環(huán)節(jié)實現(xiàn)4.1 節(jié)點數(shù)據(jù)結(jié)構(gòu)與內(nèi)存管理先看節(jié)點怎么定義。每個節(jié)點至少要存這些信息狀態(tài)自車位置、速度、周圍參與者狀態(tài)、動作從父節(jié)點到本節(jié)點的動作、訪問次數(shù)N、累計收益Q、子節(jié)點列表、父節(jié)點指針。用C寫大概長這樣struct MCTSNode { State state; // 該節(jié)點對應的場景狀態(tài) Action action; // 從父節(jié)點到本節(jié)點的動作 double Q; // 累計收益 int N; // 訪問次數(shù) MCTSNode* parent; // 父節(jié)點指針 std::vectorMCTSNode* children; // 子節(jié)點 std::vectorAction untried; // 未擴展的動作 };內(nèi)存管理是個容易被忽視的坑。MCTS每周期要創(chuàng)建和銷毀大量節(jié)點如果直接用new/delete內(nèi)存碎片和分配開銷會拖垮實時性。我的做法是預分配對象池啟動時一次性申請一大塊內(nèi)存節(jié)點從池里取用完還回去避免頻繁的系統(tǒng)調(diào)用。對象池大小根據(jù)最大模擬次數(shù)和平均樹規(guī)模估算一般留2到3倍余量。4.2 選擇階段的實現(xiàn)細節(jié)選擇階段從根節(jié)點往下走每步用UCT選子節(jié)點。實現(xiàn)時有個細節(jié)未完全擴展的節(jié)點要優(yōu)先擴展而不是直接進選擇。也就是說如果當前節(jié)點還有untried動作先擴展一個而不是繼續(xù)往下選。這是標準MCTS的做法保證樹是逐步長全的。UCT計算要注意數(shù)值穩(wěn)定性。當N為0時探索項會除零所以要特判N為0的節(jié)點直接給無窮大收益優(yōu)先訪問。另外ln(N_parent)當N_parent為1時是0探索項為0這時候只能靠利用項區(qū)分所以根節(jié)點第一次擴展后要盡快讓各子節(jié)點都至少訪問一次。4.3 模擬階段的加速技巧模擬是算力大頭加速手段主要有三個。第一用簡化動力學模型完整模型要考慮輪胎側(cè)偏、懸架等模擬時用自行車模型甚至更簡單的點質(zhì)量模型就夠了精度損失在可接受范圍。第二并行模擬如果平臺支持多線程把不同rollout分到不同線程實測能接近線性加速。第三提前終止模擬過程中一旦檢測到碰撞或者明顯劣勢立刻終止并返回低收益不用跑完全程。我實測過一組數(shù)據(jù)單線程純串行模擬1000次rollout大概要80毫秒改成四線程并行降到25毫秒左右再加上提前終止能壓到15毫秒以內(nèi)。這個提升對實時性來說是決定性的。4.4 收益計算與回溯回溯就是把模擬得到的收益沿著路徑往回傳更新每個節(jié)點的Q和N。這里有個細節(jié)收益要不要打折。也就是說深層節(jié)點的收益?zhèn)鞯礁?jié)點時要不要乘一個折扣因子。我的做法是要打折折扣因子取0.9到0.95。因為越深的模擬誤差越大對當前決策的參考價值越低打個折更合理。收益計算本身要封裝成一個獨立函數(shù)輸入是模擬終局的狀態(tài)輸出是一個標量收益。這個函數(shù)要處理各種邊界情況碰撞了返回負無窮到達目標返回正收益超時返回中性收益。寫的時候要特別注意數(shù)值范圍避免出現(xiàn)inf或者nan污染整棵樹。5. 常見問題與排查技巧實錄5.1 決策抖動怎么破這是MCTS落地最常見的問題相鄰兩個決策周期選出來的動作來回跳一會兒加速一會兒減速乘客體驗極差。根因通常是搜索的隨機性加上收益接近時的平局。解決辦法有幾個。一是增加模擬次數(shù)讓收益估計更穩(wěn)定但受實時性限制。二是動作平滑對連續(xù)幾個周期的決策結(jié)果做低通濾波但這會引入延遲。三是在收益函數(shù)里加動作一致性懲罰如果本周期動作和上周期差異大扣分。我用的是組合方案適度增加模擬次數(shù)加動作一致性懲罰實測抖動明顯減少同時延遲可控。5.2 搜索陷入局部最優(yōu)MCTS理論上會收斂到全局最優(yōu)但前提是模擬次數(shù)足夠多。實際算力受限時容易陷在某個局部最優(yōu)分支里出不來。表現(xiàn)就是決策一直很保守比如明明可以走的空檔它非要等。排查思路先看探索常數(shù)c是不是太小太小會導致探索不足。再看先驗知識是不是把某些分支過早剪掉了剪枝太激進會誤殺好分支。我的經(jīng)驗是保留一定的探索比例即使某個分支當前看起來差也給它少量訪問機會避免過早下定論。5.3 實時性不達標實時性問題是工程落地的大敵。排查順序先看單次模擬耗時如果單次就超預算說明模擬策略太重要簡化。再看模擬次數(shù)是不是設(shè)太多適當降低。然后看內(nèi)存分配有沒有瓶頸對象池是不是夠大。最后看有沒有不必要的拷貝狀態(tài)傳遞盡量用引用或者移動語義。我整理了一個排查速查表現(xiàn)象可能原因排查方向單次決策超時模擬次數(shù)過多降低rollout上限單次模擬過慢動力學模型太重換簡化模型內(nèi)存增長異常節(jié)點未回收檢查對象池歸還邏輯決策抖動收益接近隨機性加一致性懲罰決策保守探索不足調(diào)大c或增加探索樹規(guī)模失控寬度未限制加子節(jié)點數(shù)上限5.4 與下游規(guī)劃模塊的接口MCTS輸出的是一個決策動作或者一條粗略軌跡下游規(guī)劃模塊要把它細化成可執(zhí)行的平滑軌跡。接口設(shè)計要注意MCTS輸出的動作要帶置信度規(guī)劃模塊根據(jù)置信度決定是直接執(zhí)行還是再優(yōu)化。如果MCTS自己都不確定比如兩個分支收益接近規(guī)劃模塊應該更保守。還有一個坑MCTS的決策周期和規(guī)劃模塊的周期可能不一致。MCTS可能100毫秒一次規(guī)劃可能50毫秒一次。這時候要做決策保持規(guī)劃模塊在兩次MCTS決策之間沿用上一次的決策避免頻繁切換。6. 參數(shù)調(diào)優(yōu)與場景適配經(jīng)驗6.1 不同場景的參數(shù)配置MCTS的參數(shù)不是一套走天下要按場景配。我一般分三檔高速巡航、城區(qū)跟車、復雜路口交互。高速巡航場景交互簡單c取0.6模擬次數(shù)800深度4層收益里效率權(quán)重高。城區(qū)跟車c取0.9模擬次數(shù)1200深度5層舒適權(quán)重提上來。復雜路口c取1.3模擬次數(shù)2000深度6層安全權(quán)重壓倒一切同時開啟更激進的剪枝控制樹規(guī)模。這套配置是拿仿真回歸跑出來的每個場景跑幾千個case看決策成功率、碰撞率、通行效率幾個指標逐步調(diào)出來的。沒有捷徑就是堆場景堆時間。6.2 先驗知識怎么注入純MCTS從零開始搜效率低。注入先驗知識能大幅加速收斂。注入方式有兩種一是初始化時給子節(jié)點賦先驗收益讓搜索一開始就偏向合理分支二是剪枝時用先驗篩掉明顯不合理的動作。先驗知識從哪來可以從規(guī)則策略來比如規(guī)則說該減速了那減速分支給高先驗。也可以從學習模型來用一個輕量網(wǎng)絡預測各動作的勝率。我用的是規(guī)則先驗為主簡單可靠不依賴訓練數(shù)據(jù)。注意先驗不能太強否則會壓制探索退化成規(guī)則方法。先驗收益的權(quán)重要控制好一般不超過總收益的30%。6.3 和其他決策方法的對比MCTS不是唯一選擇也不是所有場景都最優(yōu)。我做個橫向?qū)Ρ确椒▋?yōu)勢劣勢適用場景有限狀態(tài)機簡單、可解釋、實時性好組合爆炸、難覆蓋復雜交互高速結(jié)構(gòu)化場景博弈論方法理論完備、交互建模清晰計算復雜、假設(shè)強兩車博弈學習方法端到端、泛化潛力大數(shù)據(jù)依賴、可解釋差數(shù)據(jù)充足場景MCTS處理不確定性強、無需大量數(shù)據(jù)算力消耗大、調(diào)參復雜復雜交互決策實際項目中我很少單用某一種而是混合架構(gòu)規(guī)則做兜底和安全校驗MCTS做復雜場景的決策學習模型做先驗加速。各取所長。7. 一些踩坑之后的個人體會MCTS在自動駕駛里能不能用好算法本身只占三成剩下七成是工程。我見過太多人把論文里的MCTS直接搬過來結(jié)果實時性崩了、決策抖了、場景覆蓋不了最后歸咎于算法不行。其實問題往往出在模擬策略太粗糙、收益函數(shù)沒調(diào)好、樹規(guī)模沒控制住這些工程細節(jié)上。我個人最大的體會是先把模擬策略和收益函數(shù)做扎實再談搜索優(yōu)化。模擬策略決定了搜索的上限收益函數(shù)決定了搜索的方向這兩個不對搜索再快也是白搭。我早期為了追求搜索速度用了很粗糙的模擬結(jié)果決策質(zhì)量還不如規(guī)則方法后來老老實實把模擬策略重寫了一遍效果立竿見影。另一個體會是不要迷信單次決策的最優(yōu)性。自動駕駛是連續(xù)決策單次最優(yōu)不等于全局最優(yōu)。有時候當前看起來次優(yōu)的決策反而給后續(xù)留了更大空間。所以我在收益函數(shù)里會加一個未來可選性的考量鼓勵決策保留更多后續(xù)選擇而不是把路走死。最后分享一個小技巧用日志回放做離線調(diào)參。把實車或者仿真的場景數(shù)據(jù)錄下來離線反復跑MCTS調(diào)參數(shù)、改收益函數(shù)比在線調(diào)效率高得多。我一般會攢幾百個典型場景做回歸集每次改完參數(shù)跑一遍看各項指標有沒有退化避免改一個場景好了、另一個場景崩了。這套流程雖然土但真的管用。