通过并行分解轨迹实现常数时间优化,大幅提速长轨迹规划。
TOP: Trajectory Optimization via Parallel Optimization towards Constant Time Complexity
- 将轨迹分段并行求解,用共识交替方向乘子法降低复杂度。
- 每轮迭代时间复杂度降至O(1),百段轨迹提速超十倍。
- 支持凸约束闭式解,适用于现代GPU加速的大型轨迹场景。
优化广泛用于生成运动规划中的平滑轨迹。然而,现有轨迹优化方法在处理大规模长轨迹时表现不佳。尽管并行计算在某些领域加速了优化,但如何高效利用并行性解决轨迹优化仍是未解问题。本文提出一种基于共识交替方向乘子法(CADMM)的新框架,将轨迹分解为多个段,并行求解子问题。相比最先进的方法(SOTA)的O(N)复杂度,本框架将每轮迭代的时间复杂度降低至O(1),与段数无关。此外,我们引入闭式解来整合凸线性和二次约束以加速优化,并给出一般不等式约束的数值解。一系列仿真和实验表明,该方法在效率和光滑性上均优于SOTA。尤其在一百段的大规模轨迹中,实现了超过十倍的速度提升。为充分发挥算法在现代并行计算架构上的潜力,我们在GPU上部署该框架,成功支持数千段轨迹的高效运行。
原文摘要 · Abstract (English)
Optimization has been widely used to generate smooth trajectories for motion planning. However, existing trajectory optimization methods show weakness when dealing with large-scale long trajectories. Recent advances in parallel computing have accelerated optimization in some fields, but how to efficiently solve trajectory optimization via parallelism remains an open question. In this paper, we propose a novel trajectory optimization framework based on the Consensus Alternating Direction Method of Multipliers (CADMM) algorithm, which decomposes the trajectory into multiple segments and solves the subproblems in parallel. The proposed framework reduces the time complexity to O(1) per iteration to the number of segments, compared to O(N) of the state-of-the-art (SOTA) approaches. Furthermore, we introduce a closed-form solution that integrates convex linear and quadratic constraints to speed up the optimization, and we also present numerical solutions for general inequality constraints. A series of simulations and experiments demonstrate that our approach outperforms the SOTA approach in terms of efficiency and smoothness. Especially for a large-scale trajectory, with one hundred segments, achieving over a tenfold speedup. To fully explore the potential of our algorithm on modern parallel computing architectures, we deploy our framework on a GPU and show high performance with thousands of segments.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。