Monte Carlo Tree Search
- 又稱: MCTS
- 類別: Planning & manipulation › Task-level
- 標籤: planning, tree-search, decision-making, pomdp, sampling-based
一種線上規劃演算法,藉由從模型模擬許多條軌跡來擴展搜尋樹,並利用這些軌跡的回報來選出最有希望的動作。
定義
蒙地卡羅樹搜尋(Monte Carlo tree search,MCTS)是一類規劃演算法,透過模擬經驗逐步建構搜尋樹,藉此決定下一步要做什麼。每次迭代有四個步驟:選擇(selection)從目前狀態沿著樹往下走,挑選子節點時所用的規則會在估計價值高的動作與只試過幾次的動作之間取得平衡;擴展(expansion)加入一個或多個新節點;模擬(simulation,或稱 rollout)估計新節點的價值,傳統做法是執行一個隨機或簡單的預設策略直到回合結束;反向傳播(backpropagation)更新路徑上每個節點的造訪次數與價值估計。時間或迭代預算用完後,演算法採用根節點上造訪次數最多或價值最佳的動作,再從下一個狀態重新開始。這個名詞由 Rémi Coulom 在 2006 年提出;同一年,Kocsis 與 Szepesvári 發表了 UCT(Upper Confidence bounds applied to Trees),它在選擇步驟中使用 UCB1 吃角子老虎機規則,是使用最廣泛的變體。
MCTS 只需要一個生成模型:一個在給定狀態與動作後,回傳取樣所得的下一個狀態與獎勵的模擬器。它不需要明確的轉移矩陣、可微分模型或手寫的啟發式函數,而且它是一種隨時演算法(anytime algorithm),因此計算越多,決策越好,並且可以在需要答案的任何時候停止搜尋。在適當條件下,隨著模擬次數增加,UCT 會收斂到最佳動作;但實務上,決策品質在很大程度上取決於預算、rollout 策略,以及搜尋如何受到引導。AlphaGo 與 AlphaZero 顯示,以學習而得的價值估計取代隨機 rollout,並用學習而得的策略來偏置選擇,能讓搜尋效率大幅提升。
在機器人領域,MCTS 用於結果不確定、需要跨越一段時間範圍的決策。POMCP 及其變體 POUCT 藉由在動作與觀測的歷史上搜尋,把 UCT 延伸到部分可觀測的問題,因此成為物體搜尋、主動感知與資訊蒐集等 POMDP 建模問題的常用求解器。連續的狀態與動作需要額外處理:漸進加寬(progressive widening)只在節點的造訪次數增加時,才加入新的子動作或取樣觀測;許多機器人系統則改為在一組離散的巨集動作或運動基元上搜尋,由低階規劃器處理連續運動。
為何重要
許多機器人決策,例如下一步要看向哪裡、先移動哪個物體,其結果要在幾步之後才會顯現,而且取決於不確定的觀測。MCTS 提供一種實用的方法,只需要一個模擬器就能在這樣的時間範圍內規劃,並能擴展到離線求解完整 MDP 或 POMDP 力有未逮的問題。
主要應用
- 以 POMDP 建模的物體搜尋與主動感知
- 任務與運動規劃,決定符號動作的順序
- 自動駕駛在路口與匯入車道時的決策
- 多機器人協調與探索
- 以學習而得的模型進行規劃,如 AlphaZero 式的系統
實際應用
一台移動式操作臂必須在雜亂的房間裡找到幾個物體。團隊把這項任務建模為 POMDP:對物體位置維持一個信念,設定移動到各個觀察視點的巨集動作與一個偵測動作,並為攝影機建立觀測模型。每次做決策時,POUCT 在固定的時間預算內,從目前的信念出發執行幾千次模擬,利用生成模型對物體位置與偵測結果進行取樣。機器人執行根節點上價值最高的動作,以實際的偵測結果更新信念,然後重新規劃。工程師調整探索常數、rollout 策略與搜尋時間範圍,並讓巨集動作集合維持得夠小,使搜尋樹能在預算內長得夠深。
常見誤解
- MCTS 是一種學習演算法 — 它是需要模型或模擬器的規劃方法;它常與學習而得的價值網路和策略網路結合,但搜尋本身並不學習策略
- MCTS 需要隨機 rollout 直到回合結束 — rollout 也可以改用啟發式策略、截斷的時間範圍或學習而得的價值函數
- MCTS 可直接處理連續動作 — 標準 UCT 假設動作集合是有限的,因此連續問題需要漸進加寬、取樣或一組離散的巨集動作
- MCTS 會找到最佳動作 — 它只有在模擬次數增加時才會朝最佳動作收斂;在即時預算下,結果是近似的,並取決於搜尋如何受到引導
誰需要了解
- 規劃與決策工程師
- 研究 POMDP 與主動感知的研究人員
- 任務與運動規劃開發人員
- 結合搜尋與學習的強化學習實務工作者
相關技術
- UCT
- POMCP
- AlphaZero
- 漸進加寬(Progressive Widening)
- 信賴上界(Upper Confidence Bound,UCB1)
相關術語
- Markov Decision Process (MDP)
- Partially Observable Markov Decision Process (POMDP)
- Belief-Space Planning
- Task and Motion Planning
- Robotic information gathering
- Reinforcement Learning
相關專案
- BehaviorTree.CPP: C++ behavior tree library for robot task planning, powering Nav2 and ROS 2 systems
- OMPL: Sampling-based motion planning library powering MoveIt and countless robotics applications
影片
- Monte Carlo Tree Search: John Levine
- AI 101: Monte Carlo Tree Search: AI and Games