具有谱扩展的蒙特卡洛树搜索用于动态系统规划

2024年12月来自加州理工的论文“Monte Carlo tree search with spectral expansion for planning with dynamical systems”。

机器人能够通过实时计算来规划复杂行为，而不是遵循预先设计或离线学习的例程，这减轻了对每个问题实例进行专门算法或训练的需要。蒙特卡罗树搜索（MCTS）是一种强大的规划算法，它可以战略性地探索模拟的未来可能性，但它需要离散的问题表示，而这与物理世界的连续动态不相容。本文提出谱扩展树搜索 (SETS)，这是一种基于树的实时规划器，它使用局部线性化系统谱来构建连续世界低复杂度和近似等效的离散表示。

SETS 收敛到连续、确定和可微分马尔可夫决策过程（MDP）的全局最优解界，这是一类广泛的问题，包括欠驱动非线性动态、非凸奖励函数和非结构化环境。在无人机、航天器和地面车辆机器人上进行 SETS 实验验证，并进行一项数值实验，每个实验都无法用现有方法直接解决。SETS 可以实时自动发现一组多样化的最佳行为和运动轨迹。

赋予机器人高性能、可靠的自主决策能力是机器人研究的最终目标，并将实现海上、空中和太空自主探索、自动驾驶汽车和城市空中交通等应用。这些自主机器人需要做出涵盖低级物理运动（即运动规划）和高级策略（例如选择目标、排序动作和优化其他决策变量）的决策。

机器人自主性的这一愿景仍然难以实现，因为在高维连续空间系统中准确解决决策问题，会出现“维数灾难”（1）。鉴于这种复杂性，许多部署中的自主机器人避免使用一般的问题公式，而是利用特定的问题结构来获得计算优势。例如，运动规划可以用基于采样的方法（2-4）解决，轨迹优化可以用凸优化（5、6）解决，高级离散决策可以用值迭代（7）解决。这些方法还可以分层组合以用于复杂行为，例如自主多航天器在轨检查 (8)、机器人操作 (9、10) 和自动驾驶城市车辆 (11、12)。针对特定问题的解决方案很容易理解，可以提高计算效率，并且已被证明是有效的。然而，这些解决方案是有限的，因为它们不能轻易地适应新问题，给多任务自主性设计人员增加了越来越多的负担。此外，还存在一些问题，它们不能轻易分解为计算上可处理的子问题。

强化学习是一种使用轨迹数据来训练最佳策略的替代方法。与上述方法不同，这种方法是一种通用程序，可以直接应用于更广泛的问题。这一特性使无人机竞赛 (13)、直升机飞行 (14)、抓取 (15) 和双足运动 (16) 等重要的新功能成为可能。然而，这些方法通常需要离线训练阶段，因此它们在新的或变化的环境中操作从根本上受到限制。此外，这些黑箱方法是无法解释的，对最优性、稳定性或鲁棒性的保证有限。

一些规划和 基于模型的强化学习方法 使用基于树的算法（17-19），这些算法使用一组统称为蒙特卡洛树搜索（MCTS）（20）的方法，从当前状态战略性地探索模拟的未来轨迹。与 离线学习方法 相比，MCTS 使用实时计算生成高质量的解决方案：给定系统的动态和奖励函数，目标是在可用的计算预算下返回最佳规划。然而，虽然树的节点和边是自然定义的离散空间，但机器人的连续空间提出了新的挑战。连续空间的均匀空间和时间离散化，会导致非常大的树和缓慢的收敛速度：对底层连续问题的离散表示不佳。

优化和基于梯度的规划

一些规划问题可以用凸优化技术 (5、6) 解决。利用快速数值求解器 [例如 (29)]，这类方法已被证明可以实时解决各种具有挑战性的动态问题，包括四旋翼无人机竞赛 (30)、在轨组装 (31)、双足运动 (32)、群体协调 (33) 和群体覆盖 (34)。各种技术，包括序贯凸规划 (5、33)、共置 colocation (32) 以及单次和多次样本方法 (35-37)，使该方法能够应用于非凸问题，尽管这些方法的理论分析表明收敛仅限于局部最小值 (38、39)。一般规划问题的状态、输入、动态和奖励规范都可能产生局部最小值陷阱，在这些陷阱下，纯粹的开发策略将无法找到全局最优解。经典的例子是虫子陷阱 bug trap 问题 (40)，其中障碍物配置将导致不需要探索的方法收敛到高度次优点。最近的研究 (41) 提出通过将环境划分为凸集并求解松弛混合整数规划来避免运动规划中的局部最小值。

与这些方法相比，SETS 通过对精心构建的自然运动表示进行离散搜索来提供全局最优解。例如，四旋翼飞行器避开了障碍物和阵风（wind gusts）造成的局部最小值陷阱，滑翔机暂时忽略了访问目标的高回报，而是导航到热气流以保持高度和能量约束。

基于采样的运动规划

用于克服问题数据中固有非凸性（例如障碍物配置中的陷阱）的标准机器人方法，是基于采样的搜索 (4)。基础方法，例如概率路线图 (3) 和快速探索随机树 (RRT) (2) 及其变型 [例如，RRT* (42)]，对配置进行采样并使用本地规划器构建树和图，在之上执行全局优化。尽管 RRT 最初是为运动动力学规划而设计的，但这些规划器最常用作几何路径规划器。

将基于采样的规划应用于动态系统有两个挑战：首先，高阶状态增加搜索空间的维数，导致收敛速度慢和性能差；其次，这些方法依赖于能够解决任意两点边界值问题本地规划器的存在。应对这些挑战是一个活跃的研究领域。例如，稳定-稀疏-RRT (43) 通过对控制输入进行采样来生成动态可行路径，从而放宽局部规划器的知识，然后修剪冗余边以维护稀疏树。另一项工作 (44) 考虑使用准-蒙特卡洛采样（QMS）来加速控制-仿射和无漂移控制-仿射系统树搜索的收敛。不连续-有界 A* (45) 在运动原语的离散结构上规划高维动态系统，不过其运动原语是通过采样输入和目标状态离线生成的。运动原语的生成和集成到离散规划中有着丰富的历史 (46–48)。

差分快速行进树 (DFMT) 方法 (49) 使用可控性 Gramian 进行具有动态约束的规划。 DFMT 使用 Gramian 来验证给定两点边界值问题的可达性，其终点从状态空间均匀采样。此外，DFMT 考虑线性系统和单个全局 Gramian。其他融合控制和规划的方法是 LQR 树 (50) 和漏斗库（funnel library）规划 (51)，它们都依赖于平方和（Sum-Of-Square）规划来计算离散规划器搜索的吸引区域。

大多数连续空间规划算法很难扩展到高维空间，因为它们通过从状态或动作空间采样来生成节点和边。实时搜索高维非线性动力学的运动规划器（例如具有 DNN 建模风效应的 12D 四旋翼飞行器）并不存在。

最近有大量关于基于采样的模型预测控制方法的研究，包括交叉熵运动规划(59)和模型预测路径积分控制(60)。通过对许多轨迹进行采样然后进行加权平均，这些方法在自动驾驶(60)和操控(61)等场景中表现出色。这些方法还显示出与高保真模拟器(62)和学习动态模型(60)的直接集成。这些策略传统上用高斯噪声扰动输入以促进探索。然而，如果不仔细调整噪声分布和平均温度，这可能会导致探索缓慢或生成的策略陷入局部最小值。可以考虑对抽象进行采样，比如状态空间中的样条(61)，这些都是活跃的研究领域。

在部分可观测的情况下研究基于采样的搜索。处理连续状态和动作空间的算法集中于粒子滤波方法，并专门克服不确定观测所固有的挑战，例如在树中共享观测数据（63）、渐近加宽（56）或线性滤波（57）。最近的一项研究将随机规划问题转化为确定性规划问题（64），将处理随机动态和观测的难度转移到决策框架中。

强化学习

问题设置最接近 基于模型强化学习 中的规划：一旦学习了动态和奖励模型，规划组件就会找到最佳价值和策略。使用动态和奖励模型的经典规划方法是价值和策略迭代（1、7）。这些方法的基本问题在现代方法中仍然存在，即表示高维连续空间具有很高的复杂性（53、65）。直接方法是离散化状态和动作空间并运行值迭代，但这具有在状态维度上呈指数级增长的存储复杂性，使得这些方法对于高维机器人应用而言在计算上难以处理。多重网格 multigrid（66）和自适应网格 adaptive grid（67）表示方面的研究已经发展，但扩展到高维系统的实际收益微乎其微。最近的研究（68）提出一种基于张量的方法，该方法利用价值函数的低秩分解，从而能够在与具有可比维度的系统上实现有效的离散化和改进的策略生成。

另一种强化学习方法是 无模型方法 ，它直接学习观察结果和最优动作之间的相关性，而无需明确使用动态或奖励函数（69、70）。策略梯度方法提供了一种处理连续状态和动作空间的强大技术， 近端策略优化PPO （71）等方法已成为社区中的标准工具。在特殊情况下，例如线性二次调节（72），存在全局收敛结果。然而，这些算法在连续空间中的一般收敛仅限于局部驻点 stationary points（73）。人们进行了额外的工作来对问题之间的这些驻点进行分类，得出关于结构相似性的结论，从而帮助策略梯度方法全局收敛（74）。这些方法虽然功能强大且通用，但需要大量数据集和离线训练阶段。这些方法从根本上受到域迁移的影响，即离线训练环境与部署系统环境之间的差异。

开发实时智能的一个自然方向，是通过可以在任意点（arbitrary point）停止的随时（any-time）算法，返回令人满意的解决方案，并且随着时间的流逝，解决方案的质量会不断提高。在决策领域，典型的例子是 MCTS (20)，这是一种模拟随机轨迹同时偏向高回报行动的算法。穷举 (75) 和均匀随机搜索 (28) 已被证明在某些情况下是有效的，但 MCTS 的改进战略探索，能够在较简单的技术无法有效搜索组合大空间的问题中实现收敛。尽管 MCTS 在游戏等传统人工智能环境中表现非常出色，但高维和连续世界的复杂性提出了根本性的挑战。已经研究了使用模拟器 (28) 的随机搜索，但所研究的搜索策略扩展性较差。直接去采样动作空间 (54)，即使采用复杂的策略 (76、77)，也会产生宽度和深度较大的树：采样高维连续动作空间会产生高分支因子，而离散化时间会在视野范围内产生大量决策。

时间抽象或选项 (78) 是一个原则框架，用于对动作序列进行决策并降低决策的复杂性。选项类似于运动规划中的运动原语。在规划 (79) 和使用 MCTS (80、81) 中，已经开展了选项构建工作，其中选项是手工制作的。在部分可观察的设置中，也有选项构建 (82) 的工作。

数据驱动方法 (83) 以及与基于梯度的技术 (84–86) 的组合也已用于决策。然而，它们在离线训练阶段对大量演示数据的依赖限制了它们在提前知道完整问题数据的系统和场景中的适用性。相比之下，SETS 方法可以部署在一个从未见过的问题上，并且在任何允许的计算预算下，都可以生成一个近似最优的决策规划，并且随着时间的推移，其质量会提高。

如图所示SETS方法和实验概述。（A）SetS 是一种基于树动态系统规划算法。树的边缘（显示为灰色）是通过跟踪局部线性化的光谱模式（显示为蓝色）和非线性反馈控制来构建的。（B 到 F）证明 SetS 广泛应用于机器人领域，涵盖地面、空中和空间领域。

问题描述

考虑一个 MDP (87)，一个抽象的问题描述，写成一个元组：⟨X, U, F, R, D, Ω, K, γ⟩。这里 X 是一个紧凑的状态空间，U 是一个紧凑的动作空间，F 是离散时间动态，R → [0, 1] 是分阶奖励，D 是终端奖励，Ω 是一组不安全的状态，K 是时间范围，γ ∈ [0, 1] 是折扣因子。在初始状态 x0 下，规划问题是选择一个动作序列，使分阶奖励加上终端奖励的总和最大化，但要受到动态和状态/动作约束。

强化学习社区和最优控制中考虑类似的一个范围决策框架。这里所考虑的问题空间集中于具有连续状态和动作空间的平滑、确定性和非线性动态。由于考虑的系统在连续时间内运行，因此均匀地离散化时间，因此每个离散时间步 k 的持续时间为 ∆t 秒。

蒙特卡洛树搜索

SETS 的伪代码如算法 1 所示。SETS 使用专门的节点扩展算子执行 MCTS，在伪代码中定义为 SE 。简要总结 MCTS 的过程，文献 (20) 中有更深入的描述：尽管机器人还有剩余的预算，但还是模拟从当前世界状态到 MDP 范围的未来状态轨迹。在每个节点，树策略通过平衡访问计数的探索和观察奖励的开发来选择最佳子节点。如果节点未完全扩展，则通过采取行动并及时向前迈进来生成新的子节点。当模拟轨迹终止时，累积的奖励和访问计数信息会反向传播到树上，更新路径中每个节点的总值和访问次数，然后该过程进行迭代。采用以下符号表示伪代码：p 是“路径”和一次迭代中的节点列表，i 是单个节点，r(i) 是对节点 i 的奖励，C(i) 是节点 i 的子节点集，Ṽ(i, l ) 是迭代 l 次后节点 i 的总值，T(i, l ) 是迭代 l 次后节点 i 的访问次数，V(i, l ) 是迭代 l 次 后节点 i 的平均值。

标准 MCTS 变型 (18) 使用一个对数探索项，而 SETS 使用一个多项式探索项（参见算法 1 的第 6 行），其中常数 c = 1、c = 0.5 和 c = 1。该技术得到了我们在定理 2 中的理论分析以及其他 MCTS 变体的支持，无论是在理论（54、88）还是实践（89）。尽管动态、奖励和 SE 算子都是确定性的，但 SETS 是一种随机算法，因为当一个节点的多个子节点未被访问时，该算法会随机选择一个。这种随机性与原始 MCTS 算法相同，在算法 1 的 第 6 行 中有所说明。

从线性化系统中，构造了可控性矩阵 C ，它是从控制动作序列到最终终端状态的线性映射。该矩阵及其相关的Gramian 矩阵在线性控制理论 (90) 中众所周知，具有两个重要特性：首先，对于线性系统，一个单位控制能量可达的状态集，是一个由 Gramian 矩阵谱参数化的椭圆；其次，可控性矩阵的伪逆应用于可行的期望终端状态，可计算驱动该系统到达该状态的最小能量控制输入。

在算法 1 的 第 19 和 20 行 中，在计算 Gramian 矩阵之前，输入会根据其控制限值进行缩放。此过程将可达集的有界能量概念，缩放到这个控制限值，而不是有可能相差数量级的输入。这里可以选择另一个预处理矩阵 S 来创建控制能量不同的权衡。除了告知输入重缩放之外，椭圆可达集属性还揭示了线性系统的一种简单探索策略：通过 Gramian 谱计算的椭圆顶点，形成这个可达集的有界覆盖。

在 第 22 至 24 行 中，计算线性化的参考轨迹。分别使用整数截断除法（integer floor division）// 和模数运算符 % 迭代遍历各种模式。在正向和负向访问每个模式意味着一个总分支因子 2n，其中 n 是状态维度。映射到所需状态的可控性矩阵伪逆，为线性化系统产生一条轨迹，根据伪逆映射属性，该轨迹是最小能量并达到目标。然而，最小和有界能量的概念是覆盖整个轨迹的，为了验证每个单独的控制动作是否有效，用一个剪断操作施加有界输入约束：给定一个向量和一个间隔，间隔之外的值被剪断到间隔的边。

虽然参考轨迹对于局部线性化系统是动态可行的，但实际分支轨迹必须满足非线性动力学。在 第 25 至 28 行 中，用现有的软件实现 (92) 从离散代数 Riccati 方程 (91) 计算反馈控制器，并推出非线性系统的轨迹，该轨迹跟踪线性参考轨迹到所需模式。在 第 28 和 29 行 中，用多步符号表示动态和奖励，例如 F/H(x/0, u/[H])=F(... F(F(x/0, u/1), u/2), ..., u/H)。

启发式和深度学习

以增加分支因子为代价，用户可以添加手动设计的节点扩展启发式方法来指导搜索。在四旋翼飞行器实验中，使用启发式方法将系统引导到最近的目标，方法是将最近的目标投影到线性集作为分支选项。这类似于基于采样运动规划社区 (40) 中使用的目标偏差采样。对于其余实验，没有使用启发式方法，而仅依赖于 SETS 的自然探索。以类似于 AlphaZero (89) 和在神经树扩展方面的工作 (93) 方式，也可以结合基于 DNN 的启发式方法来预测下一个子状态值。

用户还可以通过优先考虑某些自由度来手动降低分支因子。在四旋翼飞行器实验中，仅在速度和角速度模式之间搜索才能获得更高的性能。从物理上讲，系统保持了其平移和调整姿态的能力，因为最大程度地激发速度和角速度坐标特征向量也分别引起位置和姿态的变化。这种推理适用于许多二阶系统，并且在所有实验中都应用它。最终的实施细节，是返回最大值轨迹（而不是最高平均值的子轨迹）。这种做法保持了理论保证，因为由于确定性奖励设置，最大值轨迹的值始终高于平均值。

SETS 重要性

期望 SETS 能够对自主机器人领域和自主决策研究产生积极影响。从设计角度来看，SETS 提供了许多重要优势：首先，SETS 解决了广泛的马尔可夫决策过程 (MDP)，因此可以自然地与其他自主组件交互，并可用于新的和多样化的任务和系统。这减轻了设计人员的负担，并扩展了自主行为的操作范围。其次，由于 SETS 的搜索树可以可视化和分析，因此它具有高度的可解释性，并且可以由用户进行调整和验证。第三，由于 SETS 足够高效，可以实时运行，因此它可以通过实时计算即时对新信息做出反应。出于这些原因，SETS 可以成为广泛自主应用中规划人员的默认选择。