iDb-RRT: Sampling-based Kinodynamic Motion Planning with Motion Primitives and Trajectory Optimization

📄 arXiv: 2403.10745v1 📥 PDF

作者: Joaquim Ortiz-Haro, Wolfgang Hönig, Valentin N. Hartmann, Marc Toussaint, Ludovic Righetti

分类: cs.RO

发布日期: 2024-03-16

备注: Preprint, submitted to IROS 2024

💡 一句话要点

提出iDb-RRT以解决动态约束下的运动规划问题

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

关键词: 运动规划 动态约束 快速探索随机树 轨迹优化 机器人导航 自动驾驶 无人机飞行

📋 核心要点

  1. 现有的运动规划方法在引入动态约束后，面临计算复杂度高和信息不足的挑战。
  2. iDb-RRT结合了运动原语和轨迹优化，通过迭代搜索和优化的方式来解决运动规划问题。
  3. 在30个基准问题的测试中，iDb-RRT的求解速度比传统方法快10倍，尤其在复杂场景中表现突出。

📝 摘要（中文）

快速探索随机树（RRT）及其变体已成为寻找机器人系统中无碰撞路径的有效工具。然而，添加动态约束使得运动规划问题变得更加复杂，通常需要解决计算成本高的双值边界问题或传播随机控制输入。为此，本文提出了iDb-RRT，一种基于采样的运动规划算法，结合了运动原语和轨迹优化，能够在RRT框架内实现概率完备性，并可在前向或双向模式下实施。实验表明，iDb-RRT在复杂场景中找到解决方案的速度比以往方法快10倍，尤其是在需要长轨迹或穿越狭窄通道的情况下。

🔬 方法详解

问题定义：本文旨在解决在动态约束下的运动规划问题。现有方法在处理动态约束时，往往需要解决计算复杂度高的双值边界问题，或者依赖于随机控制输入，导致信息不足。

核心思路：iDb-RRT的核心思想是结合运动原语和轨迹优化，通过迭代的方式在RRT框架内进行高效的运动规划。这样的设计使得算法能够在保持概率完备性的同时，快速找到可行路径。

技术框架：iDb-RRT的整体架构包括两个主要模块：搜索模块和优化模块。搜索模块通过连接短轨迹（运动原语）来探索状态空间，而优化模块则在搜索后对轨迹进行修复和优化。

关键创新：iDb-RRT的主要创新在于将运动原语与轨迹优化结合在一起，形成了一种新的运动规划策略。这与传统的RRT方法相比，显著提高了在复杂环境中的路径规划效率。

关键设计：在算法设计中，关键参数包括运动原语的选择和优化过程中的损失函数设置。通过合理设计这些参数，iDb-RRT能够在不同的环境中保持高效的性能。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

在30个基准问题的实验中，iDb-RRT在复杂场景下的求解速度比以往方法快10倍，尤其在需要长轨迹或穿越狭窄通道的情况下，表现出显著的性能提升，证明了其在动态约束下的有效性。

🎯 应用场景

iDb-RRT算法在机器人导航、自动驾驶、无人机飞行等领域具有广泛的应用潜力。其高效的运动规划能力能够帮助机器人在复杂环境中快速找到安全路径，提升自主决策能力，具有重要的实际价值和未来影响。

📄 摘要（原文）

Rapidly-exploring Random Trees (RRT) and its variations have emerged as a robust and efficient tool for finding collision-free paths in robotic systems. However, adding dynamic constraints makes the motion planning problem significantly harder, as it requires solving two-value boundary problems (computationally expensive) or propagating random control inputs (uninformative). Alternatively, Iterative Discontinuity Bounded A (iDb-A), introduced in our previous study, combines search and optimization iteratively. The search step connects short trajectories (motion primitives) while allowing a bounded discontinuity between the motion primitives, which is later repaired in the trajectory optimization step. Building upon these foundations, in this paper, we present iDb-RRT, a sampling-based kinodynamic motion planning algorithm that combines motion primitives and trajectory optimization within the RRT framework. iDb-RRT is probabilistically complete and can be implemented in forward or bidirectional mode. We have tested our algorithm across a benchmark suite comprising 30 problems, spanning 8 different systems, and shown that iDb-RRT can find solutions up to 10x faster than previous methods, especially in complex scenarios that require long trajectories or involve navigating through narrow passages.