2024-12-04 カリフォルニア工科大学(Caltech)
＜関連情報＞
- https://www.caltech.edu/about/news/helping-robots-make-good-decisions-in-real-time
- https://www.science.org/doi/10.1126/scirobotics.ado1010
動的システムによる計画のためのスペクトル展開を用いたモンテカルロ・ツリー探索 Monte Carlo tree search with spectral expansion for planning with dynamical systems
Benjamin Rivière, John Lathrop, and Soon-Jo Chung
Science Robotics Published:4 Dec 2024
DOI:https://doi.org/10.1126/scirobotics.ado1010
Editor’s summary
Autonomous robots require effective decision-making processes to adapt to complex new environments. Monte Carlo tree search (MCTS) is a planning algorithm that uses real-time computation to strategically explore future decisions, but it cannot be directly applied to generate physical motions for robots. Rivière et al. have now developed Spectral Expansion Tree Search that enables real-time MCTS-based planning by computing an efficient discrete representation of the physical world. The framework was deployed on various robots that were shown to be capable of autonomously discovering optimal trajectories to avoid dynamic obstacles, traverse windy gusts, support a human driver in shared control tasks, and capture and redirect an uncontrolled agent. —Amos Matsiko
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 that 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, nonconvex reward functions, and unstructured environments. We experimentally validated 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 that SETS automatically discovers a diverse set of optimal behaviors and motion trajectories in real time.
