将连续动力系统转为离散树搜索，实现实时机器人规划
Monte Carlo Tree Search with Spectral Expansion for Planning with Dynamical Systems
- 用局部线性化系统的谱分解构建低复杂度离散表示
- 在无人机、航天器等场景中实时发现多样最优轨迹
- 适用于非线性、欠驱动、非凸奖励的复杂动力系统
机器人实现实时复杂行为规划，而非依赖预设或离线学习的策略，可减少对特定问题定制算法的需求。蒙特卡洛树搜索（MCTS）是一种强大的规划算法，能策略性探索未来可能性，但其需要离散问题表示，与物理世界的连续动力学不兼容。本文提出谱展开树搜索（Spectral Expansion Tree Search, SETS），一种基于树结构的实时规划器，利用局部线性化系统谱特征，构建连续世界的一种低复杂度且近似等价的离散表示。我们证明，在连续、确定性且可微的马尔可夫决策过程（MDP）类问题下，SETS 收敛至全局最优解的界，该类问题涵盖欠驱动非线性动力学、非凸奖励函数及无结构环境。我们在无人机、航天器和地面车辆机器人以及一个数值实验中验证了SETS，这些任务均无法被现有方法直接求解。实验表明，SETS可在实时条件下自动发现多种最优行为与运动轨迹。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。