iDb-A*: Iterative Search and Optimization for Optimal Kinodynamic Motion Planning
作者: Joaquim Ortiz-Haro, Wolfgang Hoenig, Valentin N. Hartmann, Marc Toussaint
分类: cs.RO
发布日期: 2023-11-06
💡 一句话要点
提出iDb-A*以解决复杂动力学下的运动规划问题
🎯 匹配领域: 支柱一：机器人控制 (Robot Control)
关键词: 运动规划 机器人 动态系统 轨迹优化 算法设计 渐近最优性 高维系统
📋 核心要点
- 现有的运动规划算法在高维动态系统中收敛速度较慢，难以有效处理复杂动力学问题。
- iDb-A*算法通过迭代搜索与优化相结合，利用运动原语和局部优化来克服传统方法的局限性。
- 在43个不同问题的基准测试中，iDb-A*在解决问题实例和找到低成本解决方案方面均表现优异。
📝 摘要（中文）
针对具有复杂动力学的机器人系统的运动规划问题，现有的基于采样的算法在高维系统中收敛速度较慢。本文提出了一种新的运动规划算法——迭代不连续边界A（iDb-A），通过迭代结合搜索与优化来提高效率。该算法首先利用有限的短轨迹（运动原语）进行搜索，并允许它们之间存在有界的不连续性，然后通过轨迹优化局部修复这些不连续性。通过逐步减少允许的不连续性并引入更多的运动原语，iDb-A*实现了渐近最优性，并在多种动态系统中表现出色。实验表明，该方法在解决问题实例和找到低成本解决方案方面优于现有技术。
🔬 方法详解
问题定义：本文旨在解决复杂动力学下的运动规划问题，现有方法在高维系统中收敛速度慢，且初始猜测不够接近动态可行轨迹时，可能导致无效轨迹生成。
核心思路：iDb-A*算法通过迭代结合搜索与优化，首先使用有限的短轨迹进行搜索，允许它们之间存在有界的不连续性，然后通过轨迹优化来局部修复这些不连续性，从而提高规划效率。
技术框架：该算法的整体架构包括两个主要模块：搜索模块和优化模块。搜索模块生成运动原语并进行连接，优化模块则负责修复不连续性。两者通过迭代过程相互作用，逐步改进轨迹。
关键创新：iDb-A*的主要创新在于其允许的有界不连续性设计，使得搜索过程更加灵活，同时通过逐步减少不连续性来实现渐近最优性，这与传统方法的设计理念有本质区别。
关键设计：在参数设置上，算法通过调整不连续性界限和运动原语的数量来优化性能，损失函数则侧重于轨迹的平滑性和动态可行性，确保生成的轨迹符合实际动态约束。
🖼️ 关键图片
📊 实验亮点
在43个不同的动态系统问题中，iDb-A*算法相较于现有最先进的方法，解决了更多的问题实例，并且在找到低成本解决方案的速度上有显著提升，展现出优异的任何时刻性能。
🎯 应用场景
该研究的潜在应用领域包括无人机、自动驾驶汽车和其他需要复杂运动规划的机器人系统。通过提高运动规划的效率和可靠性，iDb-A*能够在实际应用中显著提升机器人系统的性能，具有广泛的实际价值和未来影响。
📄 摘要（原文）
Motion planning for robotic systems with complex dynamics is a challenging problem. While recent sampling-based algorithms achieve asymptotic optimality by propagating random control inputs, their empirical convergence rate is often poor, especially in high-dimensional systems such as multirotors. An alternative approach is to first plan with a simplified geometric model and then use trajectory optimization to follow the reference path while accounting for the true dynamics. However, this approach may fail to produce a valid trajectory if the initial guess is not close to a dynamically feasible trajectory. In this paper, we present Iterative Discontinuity Bounded A (iDb-A), a novel kinodynamic motion planner that combines search and optimization iteratively. The search step utilizes a finite set of short trajectories (motion primitives) that are interconnected while allowing for a bounded discontinuity between them. The optimization step locally repairs the discontinuities with trajectory optimization. By progressively reducing the allowed discontinuity and incorporating more motion primitives, our algorithm achieves asymptotic optimality with excellent any-time performance. We provide a benchmark of 43 problems across eight different dynamical systems, including different versions of unicycles and multirotors. Compared to state-of-the-art methods, iDb-A* consistently solves more problem instances and finds lower-cost solutions more rapidly.