Model Predictive Trees: Sample-Efficient Receding Horizon Planning with Reusable Tree Search

📄 arXiv: 2411.15651v1 📥 PDF

作者: John Lathrop, Benjamin Rivi`ere, Jedidiah Alindogan, Soon-Jo Chung

分类: cs.RO, eess.SY

发布日期: 2024-11-23

备注: Presented at the 2024 IEEE/RSJ International Conference on Intelligent Robots and Systems

🔗 代码/项目: GITHUB

💡 一句话要点

提出模型预测树(MPT)，通过复用树搜索信息提升采样效率，用于解决动态环境下的轨迹规划问题。

🎯 匹配领域: 支柱一：机器人控制 (Robot Control)

关键词: 模型预测控制 树搜索 轨迹规划 机器人 自主导航

📋 核心要点

  1. 现有轨迹规划方法通常仅复用上一迭代的最优轨迹作为热启动，忽略了其他有价值的信息。
  2. MPT算法通过复用整个最优子树，引导搜索避开低质量区域，同时探索高质量区域，提升采样效率。
  3. 实验表明，MPT算法在数值模拟和实际机器人操作任务中，均优于现有基于采样的交叉熵方法。

📝 摘要（中文）

本文提出了一种名为模型预测树(MPT)的后退水平线树搜索算法，该算法通过高效地复用信息来提高性能。与现有求解器仅将前一次迭代中质量最高的轨迹作为“热启动”复用不同，我们的方法复用整个最优子树，从而使搜索能够同时避开低质量区域并朝向高质量区域。我们通过分析时变动力学下的诱导跟踪误差来表征树复用的限制，揭示了搜索深度和变化动力学的时间尺度之间的权衡。在数值研究中，我们的算法优于具有热启动的最先进的基于采样的交叉熵方法。我们在一个自主车辆测试平台上演示了我们的规划器，执行一个非抓取操作任务：推动目标物体通过障碍物场。与这项工作相关的代码将在https://github.com/jplathrop/mpt上提供。

🔬 方法详解

问题定义：论文旨在解决动态环境下，机器人进行轨迹规划时采样效率低下的问题。现有的基于采样的规划方法，例如交叉熵方法，通常只利用上一轮迭代的最优轨迹作为“热启动”，而忽略了搜索树中其他有价值的信息，导致采样效率不高，尤其是在复杂或高维环境中。

核心思路：MPT的核心思路是复用整个最优子树，而不仅仅是最优轨迹。通过保留和更新搜索树，算法可以记住哪些区域是低质量的，从而避免重复搜索，同时记住哪些区域是高质量的，从而集中搜索资源。这种方式可以更有效地利用历史信息，加速搜索过程。

技术框架：MPT算法的整体框架仍然是后退水平线规划(Receding Horizon Planning)的框架，但在每一步迭代中，MPT会保留并更新上一轮迭代构建的搜索树。具体流程如下： 1. 初始化：在初始时刻，随机生成一棵搜索树。 2. 搜索：在当前状态下，利用上一轮迭代的搜索树作为先验信息，进行树搜索，扩展和评估新的轨迹。 3. 优化：选择当前最优的轨迹。 4. 更新：根据当前状态和动力学模型，更新搜索树，为下一轮迭代做准备。 5. 执行：执行最优轨迹的第一个动作，并进入下一个状态。 6. 重复：重复步骤2-5，直到任务完成。

关键创新：MPT的关键创新在于提出了复用整个最优子树的策略。与传统方法只复用最优轨迹相比，MPT能够更充分地利用历史信息，从而提高采样效率。此外，论文还分析了时变动力学对树复用的限制，揭示了搜索深度和动力学变化时间尺度之间的权衡关系。

关键设计：MPT算法的关键设计包括： 1. 树的表示：搜索树需要能够有效地存储状态、动作和成本信息。 2. 树的更新策略：需要设计合理的策略来更新搜索树，例如剪枝、扩展和重新评估节点。 3. 成本函数：成本函数需要能够准确地反映轨迹的质量，并引导搜索朝着期望的方向进行。 4. 搜索深度：搜索深度需要根据动力学变化的时间尺度进行调整，以保证算法的性能。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

论文通过数值实验和实际机器人操作实验验证了MPT算法的有效性。在数值实验中，MPT算法优于具有热启动的基于采样的交叉熵方法。在实际机器人操作实验中，MPT算法成功地控制自主车辆完成了一个非抓取操作任务：推动目标物体通过障碍物场。实验结果表明，MPT算法能够有效地提高采样效率，并实现鲁棒的轨迹规划。

🎯 应用场景

MPT算法适用于各种需要进行轨迹规划的机器人应用，例如自动驾驶、无人机、机器人操作等。尤其是在动态环境或计算资源有限的情况下，MPT算法能够通过高效地复用信息，提高规划效率和性能。该算法的实际价值在于降低了机器人对计算资源的需求，使其能够在更复杂的环境中自主运行。未来，MPT算法可以进一步扩展到多智能体系统，实现协同规划。

📄 摘要（原文）

We present Model Predictive Trees (MPT), a receding horizon tree search algorithm that improves its performance by reusing information efficiently. Whereas existing solvers reuse only the highest-quality trajectory from the previous iteration as a "hotstart", our method reuses the entire optimal subtree, enabling the search to be simultaneously guided away from the low-quality areas and towards the high-quality areas. We characterize the restrictions on tree reuse by analyzing the induced tracking error under time-varying dynamics, revealing a tradeoff between the search depth and the timescale of the changing dynamics. In numerical studies, our algorithm outperforms state-of-the-art sampling-based cross-entropy methods with hotstarting. We demonstrate our planner on an autonomous vehicle testbed performing a nonprehensile manipulation task: pushing a target object through an obstacle field. Code associated with this work will be made available at https://github.com/jplathrop/mpt.