Monte Carlo Tree Search with Spectral Expansion for Planning with Dynamical Systems

Benjamin Rivière, John Lathrop, Soon-Jo Chung

Abstract

The ability of a robot to plan complex behaviors with real-time computation, rather than adhering to predesigned or offline-learned routines, alleviates the need for specialized algorithms or training for each problem instance. Monte Carlo Tree Search is a powerful planning algorithm that strategically explores simulated future possibilities, but it requires a discrete problem representation that is irreconcilable with the continuous dynamics of the physical world. We present Spectral Expansion Tree Search (SETS), a real-time, tree-based planner that uses the spectrum of the locally linearized system to construct a low-complexity and approximately equivalent discrete representation of the continuous world. We prove SETS converges to a bound of the globally optimal solution for continuous, deterministic and differentiable Markov Decision Processes, a broad class of problems that includes underactuated nonlinear dynamics, non-convex reward functions, and unstructured environments. We experimentally validate SETS on drone, spacecraft, and ground vehicle robots and one numerical experiment, each of which is not directly solvable with existing methods. We successfully show SETS automatically discovers a diverse set of optimal behaviors and motion trajectories in real time.

Introduction

Robotic decision-making in the real world is notoriously difficult because it involves high-dimensional, continuous state spaces and complex, nonlinear dynamics. This leads to the "curse of dimensionality." Traditional approaches usually fall into three camps: trajectory optimization, which is fast but prone to local minima; reinforcement learning, which requires massive offline training; and Monte Carlo Tree Search (MCTS), which excels at global exploration but requires a discrete problem representation. Uniformly discretizing a robot's continuous world leads to massive, unmanageable search trees. SETS addresses the fundamental question: How can we discretize a continuous dynamical system for tree search in a way that is both computationally efficient and mathematically sound?

Methodology

The core innovation of SETS is Spectral Expansion. Instead of branching the search tree in arbitrary directions, SETS uses the physics of the robot to determine the most effective directions for exploration.

Conceptual diagram of Spectral Expansion Tree Search (SETS) components, showing nodes, edges, and reachable sets.

At each node in the search tree, the algorithm performs a local linearization of the robot's dynamics and computes the controllability Gramian. By performing a spectral decomposition of this Gramian, SETS identifies the "natural modes" of the system—the directions in which the robot can most effectively move. The tree expands along these spectral modes, limiting the branching factor to a linear relationship with the state dimension ($2n$). To ensure the real, nonlinear robot can follow the paths generated by the linear approximation, SETS employs a tracking controller based on the Discrete Algebraic Riccati Equation (DARE).

Experimental Validation

The paper validates SETS across four distinct and challenging scenarios:

  • Quadrotor in a Wind Field: Navigating a complex wind tunnel using a Deep Neural Network to model residual forces.
  • Tracked Ground Vehicle: A parallel autonomy setup assisting a human driver through chicanes and slippery slopes.
  • Collaborative Spacecraft: Two tethered robots coordinating to capture uncooperative space debris.
  • Aerodynamic Glider: A simulation where the glider must discover how to exploit thermal updrafts.
Experimental setup for the tracked ground vehicle in outdoor (E) and obstacle-laden (F) environments.

Key Results and Insights

SETS demonstrates several key advantages over existing methods:

  • Global Optimality: The algorithm is proven to converge to a bound of the global optimum for a broad class of nonlinear problems.
  • Discovered Behaviors: SETS "discovers" complex strategies—such as the glider circling in thermals or the spacecraft using trampoline-like maneuvers—without explicit programming.
  • Real-Time Performance: The algorithm ran on-board hardware (e.g., NVIDIA Orin) in real-time, re-planning trajectories for the tracked vehicle every 100ms.
  • Adaptability: When the tracked vehicle's actuators were degraded by 25%, the algorithm automatically updated its spectral modes to reflect the new capabilities.

Conclusion

Spectral Expansion Tree Search (SETS) bridges the gap between the global search power of MCTS and the continuous dynamics of physical robots. By using the system's own controllability spectrum as a natural coordinate system for search, it achieves exponential complexity reduction while providing rigorous guarantees. Future work will focus on extending these guarantees to stochastic environments and integrating DNN-based heuristics to further accelerate search in complex environments.

Summary updated

Abstract

The ability of a robot to plan complex behaviors with real-time computation, rather than adhering to predesigned or offline-learned routines, alleviates the need for specialized algorithms or training for each problem instance. Monte Carlo Tree Search is a powerful planning algorithm that strategically explores simulated future possibilities, but it requires a discrete problem representation that is irreconcilable with the continuous dynamics of the physical world. We present Spectral Expansion Tree Search (SETS), a real-time, tree-based planner that uses the spectrum of the locally linearized system to construct a low-complexity and approximately equivalent discrete representation of the continuous world. We prove SETS converges to a bound of the globally optimal solution for continuous, deterministic and differentiable Markov Decision Processes, a broad class of problems that includes underactuated nonlinear dynamics, non-convex reward functions, and unstructured environments. We experimentally validate SETS on drone, spacecraft, and ground vehicle robots and one numerical experiment, each of which is not directly solvable with existing methods. We successfully show SETS automatically discovers a diverse set of optimal behaviors and motion trajectories in real time.
BibTeX
@inproceedings{riviere2024monte,
  author = {Benjamin Rivière and John Lathrop and Soon-Jo Chung},
  title = {{Monte Carlo Tree Search with Spectral Expansion for Planning with Dynamical Systems}},
  booktitle = {Sci. Robotics},
  year = {2024},
  url = {https://openreview.net/forum?id=DHN6lO86sE},
}
Figure