Open Source Robotics

A curated collection of high-quality open source robotics projects, tools, and software to propel the robotics community forward.

Monte Carlo Tree Search

  • Also called: MCTS
  • Category: Planning & manipulation › Task-level
  • Tags: planning, tree-search, decision-making, pomdp, sampling-based

An online planning algorithm that grows a search tree by simulating many trajectories from a model and uses their returns to choose the most promising action.

Definition

Monte Carlo tree search (MCTS) is a family of planning algorithms that decide what to do next by building a search tree incrementally from simulated experience. Each iteration has four steps: selection walks down the tree from the current state, choosing children by a rule that balances actions with high estimated value against actions tried only a few times; expansion adds one or more new nodes; simulation (or rollout) estimates the value of the new node, classically by playing a random or simple default policy to the end of the episode; and backpropagation updates the visit counts and value estimates of every node on the path. After the time or iteration budget runs out, the algorithm commits to the root action that was visited most or has the best value, then repeats from the next state. The term was introduced by Rémi Coulom in 2006, and in the same year Kocsis and Szepesvári published UCT (Upper Confidence bounds applied to Trees), which uses the UCB1 bandit rule for selection and is the most widely used variant.

MCTS needs only a generative model: a simulator that, given a state and an action, returns a sampled next state and reward. It does not need an explicit transition matrix, a differentiable model or a hand-written heuristic, and it is an anytime algorithm, so more computation gives better decisions and the search can be stopped whenever an answer is needed. Under suitable conditions UCT converges to the optimal action as the number of simulations grows, but in practice the quality of a decision depends heavily on the budget, the rollout policy and how the search is guided. AlphaGo and AlphaZero showed that replacing random rollouts with learned value estimates and using a learned policy to bias selection makes the search far more efficient.

In robotics MCTS is used for decisions over a horizon where outcomes are uncertain. POMCP and its variant POUCT extend UCT to partially observable problems by searching over histories of actions and observations, which makes them common solvers for POMDP formulations of object search, active perception and information gathering. Continuous states and actions need extra care: progressive widening adds new child actions or sampled observations only as a node's visit count grows, and many robotics systems instead search over a discrete set of macro-actions or motion primitives while lower-level planners handle continuous motion.

Why it matters

Many robot decisions, such as where to look next or which object to move first, have outcomes that only show several steps later and depend on uncertain observations. MCTS gives a practical way to plan over such horizons with nothing more than a simulator, and it scales to problems where solving the full MDP or POMDP offline is out of reach.

Key applications

  • Object search and active perception formulated as POMDPs
  • Task and motion planning, choosing the order of symbolic actions
  • Decision making for autonomous driving at intersections and merges
  • Multi-robot coordination and exploration
  • Planning with learned models, as in AlphaZero-style systems

In practice

A mobile manipulator has to find several objects in a cluttered room. The team models the task as a POMDP with a belief over object locations, macro-actions for moving to viewpoints and a detection action, and an observation model for the camera. At each decision, POUCT runs a few thousand simulations from the current belief within a fixed time budget, using the generative model to sample object locations and detections. The robot executes the root action with the highest value, updates its belief with the real detection result and plans again. The engineers tune the exploration constant, the rollout policy and the search horizon, and keep the macro-action set small enough that the tree can grow deep within the budget.

Common misconceptions

  • MCTS is a learning algorithm — it is a planning method that needs a model or simulator; it is often combined with learned value and policy networks, but the search itself does not learn a policy
  • MCTS requires random rollouts to the end of the episode — rollouts can use heuristic policies, truncated horizons or a learned value function instead
  • MCTS works directly on continuous actions — standard UCT assumes a finite set of actions, so continuous problems need progressive widening, sampling or a discrete set of macro-actions
  • MCTS finds the optimal action — it converges toward it only as simulations grow; with a real-time budget the result is approximate and depends on how the search is guided

Who should know this

  • Planning and decision-making engineers
  • Researchers working on POMDPs and active perception
  • Task and motion planning developers
  • Reinforcement learning practitioners combining search and learning

Related technologies

  • UCT
  • POMCP
  • AlphaZero
  • Progressive Widening
  • Upper Confidence Bound (UCB1)

Related terms

  • Markov Decision Process (MDP)
  • Partially Observable Markov Decision Process (POMDP)
  • Belief-Space Planning
  • Task and Motion Planning
  • Robotic information gathering
  • Reinforcement Learning

Related projects

  • 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

Videos

  • Monte Carlo Tree Search: John Levine
  • AI 101: Monte Carlo Tree Search: AI and Games

This website requires JavaScript to function properly. Please enable JavaScript to explore our collection of open source robotics projects.