Fast and Certifiable Trajectory Optimization

📄 arXiv: 2406.05846v3 📥 PDF

作者: Shucheng Kang, Xiaoyang Xu, Jay Sarva, Ling Liang, Heng Yang

分类: math.OC, cs.RO

发布日期: 2024-06-09 (更新: 2024-09-02)

💡 一句话要点

提出STROM框架，通过半定规划快速求解带证书非凸轨迹优化问题

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

关键词: 轨迹优化 半定规划 ADMM算法 GPU加速 非凸优化

📋 核心要点

  1. 现有轨迹优化方法在求解非凸问题时，速度慢或无法保证解的最优性，面临计算效率和证书保证的挑战。
  2. STROM框架利用稀疏Lasserre层级结构生成半定规划(SDP)松弛，并设计链式多块SDP结构，提升求解效率。
  3. cuADMM求解器基于GPU并行化加速SDP求解，在多个轨迹优化问题中实现了分钟级甚至秒级的求解速度，并提供次优性证书。

📝 摘要（中文）

本文提出半定轨迹优化(STROM)框架，用于计算由多项式目标和约束定义的非凸轨迹优化问题的快速且可验证的最优解。STROM采用稀疏二阶Lasserre层级结构，生成轨迹优化的半定规划(SDP)松弛。与现有工具(如Matlab中的YALMIP和SOSTOOLS)不同，STROM生成仅包含正半定(PSD)变量的链式多块SDP，并且速度快两个数量级。STROM的核心是cuADMM，这是第一个基于ADMM的SDP求解器，用CUDA实现并在GPU中运行(带有C/C++扩展)。cuADMM建立在对称Gauss-Seidel ADMM算法之上，并利用GPU并行化来加速求解稀疏线性系统和投影到PSD锥上。在五个轨迹优化问题(倒立摆、手推车-摆杆、车辆着陆、飞行机器人和汽车倒车)中，cuADMM在几分钟(其他求解器需要数小时或内存不足)或几秒钟(其他求解器需要数分钟)内计算出最优轨迹(认证的次优性低于1%)。此外，在倒立摆问题中，当通过数据驱动初始化进行热启动时，cuADMM可提供实时性能：在0.66秒内提供可验证的最优轨迹，尽管SDP具有49,500个变量和47,351个约束。

🔬 方法详解

问题定义：论文旨在解决非凸轨迹优化问题，这类问题通常由多项式目标函数和约束定义。现有的轨迹优化工具，如YALMIP和SOSTOOLS，在处理大规模问题时，计算速度慢，甚至可能因为内存不足而无法求解。此外，这些工具通常难以提供解的最优性保证。

核心思路：论文的核心思路是利用半定规划(SDP)松弛来近似非凸轨迹优化问题，并通过高效的SDP求解器cuADMM来快速求解。通过Lasserre层级结构生成SDP松弛，可以将非凸问题转化为凸问题，从而可以使用凸优化方法进行求解。同时，论文设计了链式多块SDP结构，以进一步提高求解效率。

技术框架：STROM框架主要包含两个阶段：首先，利用稀疏二阶Lasserre层级结构生成轨迹优化问题的SDP松弛；然后，使用cuADMM求解器求解生成的SDP问题。cuADMM求解器基于对称Gauss-Seidel ADMM算法，并在GPU上实现，以加速计算。整体流程是从非凸轨迹优化问题到SDP松弛，再到cuADMM求解，最终得到可验证的最优轨迹。

关键创新：论文的关键创新在于以下几点：一是提出了STROM框架，该框架能够快速生成轨迹优化问题的SDP松弛；二是设计了链式多块SDP结构，这种结构更适合ADMM算法求解；三是开发了cuADMM求解器，该求解器利用GPU并行化加速SDP求解，显著提高了计算效率。与现有方法相比，STROM框架能够更快地求解非凸轨迹优化问题，并提供解的最优性保证。

关键设计：cuADMM求解器的关键设计包括：使用对称Gauss-Seidel ADMM算法，该算法具有良好的收敛性；利用GPU并行化加速稀疏线性系统的求解和投影到PSD锥上的计算；采用CUDA实现，以充分利用GPU的计算能力。此外，论文还探索了数据驱动的初始化方法，以进一步提高求解速度。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

实验结果表明，cuADMM在五个轨迹优化问题中，能够在几分钟甚至几秒钟内计算出最优轨迹，且次优性低于1%。在倒立摆问题中，通过数据驱动初始化，cuADMM能够在0.66秒内提供可验证的最优轨迹，即使SDP具有49,500个变量和47,351个约束。相比之下，其他求解器需要数小时或因内存不足而无法求解。

🎯 应用场景

该研究成果可广泛应用于机器人、自动驾驶、航空航天等领域，例如无人机的轨迹规划、自动驾驶车辆的路径规划、以及飞行器的着陆控制等。通过快速求解轨迹优化问题，可以提高系统的响应速度和安全性，并降低能源消耗。此外，该方法提供的最优性保证，对于安全关键型应用尤为重要。

📄 摘要（原文）

We propose semidefinite trajectory optimization (STROM), a framework that computes fast and certifiably optimal solutions for nonconvex trajectory optimization problems defined by polynomial objectives and constraints. STROM employs sparse second-order Lasserre's hierarchy to generate semidefinite program (SDP) relaxations of trajectory optimization. Different from existing tools (e.g., YALMIP and SOSTOOLS in Matlab), STROM generates chain-like multiple-block SDPs with only positive semidefinite (PSD) variables. Moreover, STROM does so two orders of magnitude faster. Underpinning STROM is cuADMM, the first ADMM-based SDP solver implemented in CUDA and runs in GPUs (with C/C++ extension). cuADMM builds upon the symmetric Gauss-Seidel ADMM algorithm and leverages GPU parallelization to speedup solving sparse linear systems and projecting onto PSD cones. In five trajectory optimization problems (inverted pendulum, cart-pole, vehicle landing, flying robot, and car back-in), cuADMM computes optimal trajectories (with certified suboptimality below 1%) in minutes (when other solvers take hours or run out of memory) and seconds (when others take minutes). Further, when warmstarted by data-driven initialization in the inverted pendulum problem, cuADMM delivers real-time performance: providing certifiably optimal trajectories in 0.66 seconds despite the SDP has 49,500 variables and 47,351 constraints.