Do Robots Dream of Random Trees? Monte Carlo Tree Search for Dynamical, Partially Observable, and Multi-Agent Systems

Citation

Rivière, Benjamin Pierre (2024) Do Robots Dream of Random Trees? Monte Carlo Tree Search for Dynamical, Partially Observable, and Multi-Agent Systems. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/dbwa-we50. https://resolver.caltech.edu/CaltechTHESIS:06032024-152357240

Abstract

Autonomous robots are poised to transform various aspects of society, spanning transportation, labor, and scientific space exploration. A critical component to enable their capabilities is the algorithm that interprets sensor data to generate intelligent planned behavior. Although reinforcement learning methods that train parameterized policies offline from data have shown recent success, they are inherently limited when robots inevitably encounter situations outside their training domain. In contrast, optimal control techniques, which compute trajectories in real-time using numerical optimization, typically yield only locally optimal solutions.

This research endeavors to bridge the gap by developing algorithms that compute trajectories in real-time while converging towards globally optimal solutions. Building upon the Monte Carlo Tree Search (MCTS) framework—a stochastic tree search method that simulates future trajectories while balancing exploration and exploitation—the research focus is twofold: (i) constructing an efficient discrete representation of continuous systems in a decision trees, and (ii) searching on the resulting tree while balancing exploration and exploitation to achieve global optimality.

The study spans theoretical analysis, algorithmic design, and hardware demonstrations across dynamical, partially observable, and multi-agent systems. By addressing these critical questions, this research aims to advance the field of autonomous robotics, enabling the deployment of intelligent robots in complex and diverse environments.

Thesis Files