スペクトル展開を用いたモンテカルロ木探索による動的システムの計画
Monte Carlo Tree Search with Spectral Expansion for Planning with Dynamical Systems
連続力学系の局所線形化スペクトルから低次元の離散表現を構築し、モンテカルロ木探索をリアルタイム計画に適用する手法を提案。ドローン・宇宙機・地上車両で有効性を実証。
著者: Benjamin Riviere, John Lathrop, Soon-Jo Chung
分類: cs.RO
原文アブストラクト
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.
