基于谱扩展树搜索的机器人实时连续空间全局最优规划研究

本研究由加州理工学院工程与应用科学系的Benjamin Rivière、John Lathrop和Soon-Jo Chung共同完成，其研究成果以“Monte Carlo Tree Search with Spectral Expansion for Planning with Dynamical Systems”为题，于2024年12月4日发表在学术期刊《Science Robotics》上。

学术背景 研究的核心科学领域是机器人自主决策与规划。实现高性能、可靠的自主决策是机器人学的终极目标之一，但这一愿景仍遥不可及。其根本挑战在于高维连续空间系统决策问题的精确求解面临“维度灾难”。现有主流方法各有局限：采样运动规划方法通常在状态空间采样，难以高效处理高维动力学约束；基于凸优化的轨迹优化方法容易陷入局部最优；基于模型的强化学习通常需要离线训练，难以适应新环境或提供可解释的保证；而蒙特卡洛树搜索（Monte Carlo Tree Search， MCTS）这类强大的规划算法，需要离散的问题表示，这与物理世界的连续动力学特性不相容。因此，研究者亟需一种能够为具有连续非线性动力学的机器人系统，在实时计算条件下提供全局（或近似全局）最优决策的通用规划算法。

本研究的核心目标是解决上述难题。研究者们提出了一种名为“谱扩展树搜索”（Spectral Expansion Tree Search， SETS）的新型实时、基于树的规划算法。该算法旨在直接处理连续状态的马尔可夫决策过程（MDPs），其关键创新在于利用系统局部线性化的谱（spectrum）来构建一个低复杂度、且与原连续世界近似等效的离散表示，从而让MCTS能够有效地应用于连续动力学系统。研究者证明，对于一类广泛的、包含欠驱动非线性动力学、非凸奖励函数和非结构化环境的问题，SETS能够收敛到全局最优解的一个有界范围内。

详细研究方法与流程 本研究是一项算法开发与验证性研究，其工作流程主要包含两个相互关联的核心部分：1）SETS算法的设计与理论分析；2）在多种机器人平台和数值仿真中进行的系统性实验验证。研究涉及的对象包括：四旋翼无人机、履带式地面车辆、多个航天器模拟机器人以及一个数值仿真的滑翔机模型。每个实验都是一个独立的“问题实例”，旨在验证SETS在不同动力学、目标和约束下的通用性。

1. SETS算法设计： SETS是MCTS框架的一个扩展，其核心是引入了“谱扩展”（Spectral Expansion， SE）算子来替代传统的离散动作选择。具体工作流程（对应论文算法1）如下： * 初始化： 以当前机器人状态作为搜索树的根节点。 * 树搜索循环： 在给定的计算预算（如模拟次数）内重复以下步骤： * 选择（Selection）： 从根节点开始，根据树策略（Tree Policy）递归地选择子节点直至到达叶节点。树策略采用上置信界（Upper Confidence Bound）思想，平衡对高价值子节点（利用，Exploitation）和访问次数少子节点（探索，Exploration）的选择。与标准MCTS使用对数探索项不同，SETS采用多项式探索项，这在理论分析中得到了支持。 * 扩展（Expansion）与仿真（Simulation）： 如果选中的叶节点未完全扩展，则应用“谱扩展（SE）”算子生成一个新的子节点及其对应的轨迹。这是算法的核心创新步骤，具体过程如下： 1. 局部线性化与可控性格拉姆谱计算： 在当前节点状态（对于非线性系统，可选择沿一条名义轨迹）对系统动力学进行线性化。计算该局部线性化系统的可控性格拉姆（Controllability Gramian）矩阵。 2. 谱分析与模式提取： 对经过输入限幅归一化的可控性格拉姆矩阵进行特征分解。其特征向量定义了系统在该局部区域内“最自然”的运动模式（例如，对于四旋翼，模式可能对应垂直加速、俯仰或滚转机动），特征值则代表了激发相应模式所需的“控制能量”。 3. 参考轨迹生成： 选择当前待扩展的模式（特征向量的正负方向），计算将该线性系统在固定步长 h（分支长度）内驱动至该模式所对应端点所需的最小能量控制输入序列，从而得到一条线性参考轨迹。 4. 非线性跟踪与节点创建： 使用基于离散代数Riccati方程设计的线性二次型调节器（LQR）反馈控制器，驱动原始的非线性系统去跟踪上一步生成的线性参考轨迹。由此rollout出的非线性轨迹，其末端状态成为树的一个新子节点，累积的奖励值也被计算。 * 回传（Backup）： 从新扩展的节点（或终止状态）开始，将本次模拟获得的累积奖励值沿搜索路径反向传播，更新路径上所有节点的访问次数和总价值估计。 * 输出决策： 在计算预算用尽后，算法通常选择从根节点开始的、具有最高价值估计的轨迹作为当前的最优计划（在确定性奖励设定下，最高价值轨迹比平均价值更具理论保证）。

2. 实验验证流程： 研究者在四个精心设计的实验场景中验证了SETS，每个场景都旨在挑战现有方法的极限。 * 实验一（四旋翼无人机穿越危险风场）： * 研究对象与目标： 一个12状态维度的四旋翼模型（动力学通过深度神经网络增强了风扰动力模型），任务是在一个充满移动球形障碍物和可控气流（产生“危险”与“安全”区域）的三维竞技场中，以最短时间访问多个监测目标。 * 处理与测试： SETS作为模型预测控制（MPC）中的规划模块运行，每5秒重新规划一次10秒的轨迹。研究展示了SETS实时生成的搜索树（投影到二维平面），并分析了在静止空气和热气流中系统可控性格拉姆谱的变化，解释了不同运动模式的可控性差异。最终，通过实际飞行轨迹和任务完成时间（37秒访问所有目标）来评估性能。 * 实验二（人机协同的履带车辆）： * 研究对象与目标： 一辆履带式车辆，在包含斜坡、弯道、锯齿路段的复杂赛道上，与人类驾驶员进行“平行自主”共享控制。目标是在驾驶员可能发出不安全指令（导致碰撞或翻车）的情况下，辅助车辆安全通过赛道，同时处理执行器的对抗性性能降级。 * 处理与测试： SETS作为规划模块，每0.1秒规划未来1.6秒的轨迹。它接收来自基础视觉模型构建的危险地图以及自适应控制器更新的动力学参数。实验记录了专业驾驶员在有/无SETS辅助下通过赛道时的安全违规次数，并展示了SETS在狭窄弯道自动减速和转向以避免碰撞的决策过程。同时，通过对比执行器正常和降级时的系统谱，说明了SETS如何理解并适应车辆能力的变化。 * 实验三（多航天器协作捕获目标）： * 研究对象与目标： 两个由绳索网连接的协作航天器（模拟器），需捕获并重定向第三个无协作的目标航天器。这是一个具有接触力和绳索动力学的高维、欠驱动问题。 * 处理与测试： SETS控制两个协作航天器的推力器，同时预测三个航天体及弹簧-质量-阻尼器有限元模型描述的绳索网的动力学。实验测试了四种不同的目标初始位置和速度配置。通过展示系统可控性谱（显示接触发生后目标状态才变得可控），并分析最终目标速度方向的变化，验证了SETS能自动产生“部署-捕获-重定向”或“蹦床式”弹射等复杂协调行为。 * 实验四（数值仿真：滑翔机持久观测）： * 研究对象与目标： 一个六自由度滑翔机模型，任务是在存在热上升气流的区域长期观测一个地面目标。滑翔机需在气动阻力消耗能量和利用热能补充能量之间做出权衡，否则会坠毁。 * 处理与测试： 此实验主要用于系统性分析和基线比较。研究者运行SETS并分析搜索树数据，包括：1）价值收敛分析：改变分支长度 h，观察根节点价值估计随模拟次数增加的变化，验证理论预测的收敛速度与稳态误差的权衡关系；2）策略收敛分析：通过树中各深度节点访问次数的集中程度，衡量策略置信度随计算量增加而加深的程度；3）基线比较：将SETS与多种基线方法对比，包括均匀离散化（UD）、双重渐进扩展（DPW）等表示方法，以及MCTS和预测采样（PS）等探索策略。结果表明，谱扩展表示（SE）是性能提升的最关键因素。

数据分析流程贯穿于算法和实验中。理论分析（定理证明）使用数学推导来建立算法收敛性的上界。实验数据分析则包括：可视化搜索树和轨迹；绘制可控性格拉姆谱图以解释系统模式；记录并比较任务完成指标（如时间、安全违规次数、速度方向）；以及从仿真中提取价值估计和访问计数数据进行统计绘图，以验证收敛特性。

主要研究结果 1. 算法有效性得到广泛验证： 在四个差异巨大的实验场景中，SETS均成功在实时计算约束下，自动发现了复杂且近似最优的行为策略。四旋翼解决了动态约束下的旅行商问题；履带车实现了安全的人机共享控制；航天器团队完成了高难度的协同捕获任务；滑翔机发现了在观测目标与利用热气流间周期性振荡的生存策略。这些行为是“发现而非设计”的，证明了SETS的通用性。 2. 谱扩展表示的关键作用得到证实： 可控性格拉姆的谱为不同动力学系统（空中、地面、空间）提供了可解释的“自然运动”基。实验显示，该谱能反映系统能力的实时变化（如执行器降级），并能有效降低决策问题的复杂度。基线比较实验（图5c）明确指出，与其他表示方法（如均匀离散化）相比，谱扩展表示是提升规划性能的最主要因素，其重要性超过了探索策略的选择。 3. 理论收敛性得到支持： 数值实验（滑翔机案例）的结果与理论分析（定理3）一致。数据显示，分支长度 h 确实控制着收敛速度与渐进误差之间的权衡：较小的 h 误差更小但收敛慢，较大的 h 收敛快但误差更大。这为算法参数的系统性调优提供了指导。 4. 实现了对高维连续动力学系统的实时搜索： 研究成功展示了在12维四旋翼非线性动力学（含神经网络风模型）下的实时树搜索，这在以往的动力学运动规划方法中尚属罕见。SETS通过将分支因子从与动作维度指数相关降低到与状态维度线性相关，并减少时间步决策数（通过增加 h），实现了树规模的指数级缩减，从而克服了“维度灾难”的核心挑战。

研究结论与价值 本研究的结论是，所提出的谱扩展树搜索（SETS）算法是一种能够为具有连续、确定性、可微动力学的机器人系统提供实时、全局近似最优规划的通用且强大的工具。它成功地将蒙特卡洛树搜索的探索能力与基于动力学的谱分析相结合，创造了一个既高效又可解释的决策框架。

其科学价值在于：1）理论贡献：为连续空间MDPs提供了一个有界的离散近似表示方法（定理1），并为确定性MDPs下的MCTS提供了新的有限时间收敛性分析（定理2），后者无需已知问题的“间隙”（gap）参数。2）算法贡献：建立了动力学系统与机器学习（特别是基于树的规划）之间的新联系，证明系统谱可以作为在线学习的有效特征。3）领域贡献：为解决机器人自主决策中“通用性”与“最优性/实时性”难以兼得的长期挑战提供了新的可行路径。

其应用价值显著：1）减轻设计负担：SETS能直接处理广泛的MDPs，使机器人无需为每个新任务设计专用算法或进行大量离线训练，扩展了机器人的自主操作范围。2）提高可解释性：搜索树和系统谱可被可视化和分析，增强了决策过程的透明度，便于调试和验证。3）实现实时反应：算法效率足以支持模型预测控制框架，使机器人能基于实时计算对新信息做出反应。

研究亮点 1. 方法新颖性：首次将可控性格拉姆的谱系统地用于构造连续动力学系统的离散抽象，并集成到MCTS框架中，实现了原理上的创新。 2. 理论完整性：不仅提出了新算法，还提供了严格的收敛性证明，将表示误差和搜索收敛误差统一在一个理论框架内。 3. 验证全面性：跨越空中、地面、空间三大机器人领域，以及数值仿真，进行了深入且多样化的实验验证，充分证明了算法的广泛适用性和鲁棒性。 4. 问题通用性：所解决的问题超越了传统的“点到点”运动规划，涵盖了具有复杂奖励函数、动态约束和人机交互的通用决策任务，展现了更广阔的应用前景。

其他有价值内容 论文在“讨论”部分对SETS与现有主流方法（如优化规划、采样运动规划、强化学习）进行了深入且定性清晰的比较，阐述了SETS在避免局部最优、处理高维动力学、无需离线训练等方面的优势。此外，研究还展望了SETS对未来自主机器人研究和决策制定领域的潜在积极影响，包括作为自主系统中默认规划器的可能性，以及其谱特征在离线策略学习、动力学运动规划等其他领域的应用潜力。