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