高效求解多智能体轨迹优化，速度随智能体数近似线性增长。
TurboADMM: A Structure-Exploiting Parallel Solver for Multi-Agent Trajectory Optimization
- 用ADMM分解问题，实现各智能体并行求解，保留时间结构。
- 利用Riccati递推提供高质量初始值，加速收敛。
- 复用QR分解结果，减少重复计算，适合高频率控制场景。
具有密集交互关系的多智能体轨迹优化需在控制周期内求解大规模耦合二次规划（QP），现有求解器难以同时利用时间结构、智能体分解和迭代相似性。通用求解器（如OSQP、MOSEK）常将问题视为整体，随智能体数量增加而出现可扩展性瓶颈；结构专用求解器（如HPIPM）虽通过Riccati递推利用时间结构，但在密集耦合约束下仍易失效。本文提出TurboADMM，一种专用于单机的QP求解器，通过系统性协同设计三个互补组件，在智能体数量上实现近似线性的实测复杂度：(1) 基于ADMM的分解将原问题拆分为可并行求解的个体子问题，即使在密集耦合下仍保持块三对角结构；(2) 利用Riccati递推提供高质量的原始-对偶初始化，显著加速各智能体子问题的收敛；(3) 在qpOASES中引入参数化QP热启动，复用相邻ADMM迭代间的KKT系统QR分解，有效降低重复计算开销。
原文摘要 · Abstract (English)
Multi-agent trajectory optimization with dense interaction networks require solving large coupled QPs at control rates, yet existing solvers fail to simultaneously exploit temporal structure, agent decomposition, and iteration similarity. One usually treats multi-agent problems monolithically when using general-purpose QP solvers (OSQP, MOSEK), which encounter scalability difficulties with agent count. Structure-exploiting solvers (HPIPM) leverage temporal structure through Riccati recursion but can be vulnerable to dense coupling constraints. We introduce TurboADMM, a specialized single-machine QP solver that achieves empirically near linear complexity in agent count through systematic co-design of three complementary components: (1) ADMM decomposition creates per-agent subproblems solvable in parallel, preserving block-tridiagonal structure under dense coupling; (2) Riccati warmstart exploits temporal structure to provide high-quality primal-dual initialization for each agent's QP; (3) parametric QP hotstart \footnote{In the paper, we refer warmstart as the technique that uses the Riccati equation results as auxiliary QP initialization for a single QP solve, while hotstart as reusing the QR factorization across QP solve iterations.}in qpOASES reuses similar KKT system factorizations across ADMM iterations.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。