标题： TOP：通过并行优化实现轨迹优化以达到恒定的时间复杂度 显示英文标题

标题： TOP: Trajectory Optimization via Parallel Optimization towards Constant Time Complexity

摘要： 优化已被广泛用于生成运动规划的平滑轨迹。 然而，现有的轨迹优化方法在处理大规模长轨迹时表现出不足。 并行计算的最新进展加速了某些领域的优化，但如何通过并行性高效解决轨迹优化仍然是一个开放问题。 在本文中，我们提出了一种基于共识交替方向乘子法（CADMM）算法的新型轨迹优化框架，该框架将轨迹分解为多个段，并并行求解子问题。 与最先进的（SOTA）方法的O(N)相比，所提出的框架将每迭代的时间复杂度降低到O(1)与段数相关。 此外，我们引入了一种闭式解，将凸线性和二次约束整合以加快优化，并为一般不等式约束提供了数值解。 一系列仿真和实验表明，我们的方法在效率和光滑性方面优于SOTA方法。 特别是对于大规模轨迹，具有100个段，实现了十倍以上的加速。 为了充分利用我们的算法在现代并行计算架构上的潜力，我们将框架部署在GPU上，并展示了数千个段的高性能。 显示英文摘要

摘要： 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.