arXiv:2608.00959cs.GTcs.RO2026-08

开源加速求解机器人多智能体轨迹优化问题,性能媲美闭源工具。

MixedComplementarityProblems.jl: A Fast, Batched, Open-Source Interior Point Solver for Mixed Complementarity Problems

论文配图:MixedComplementarityProblems.jl: A Fast, Batched, Open-Source Interior Point Solver for Mixed Complementarity Problems
图 1 · 摘自论文原文
  • 基于内点法的纯Julia实现,支持批量并行处理参数化问题。
  • 在多智能体变道任务中,批量求解速度比调用PATH快100倍。
  • 可无缝适配CPU多线程与GPU,适合机器人规划等需要高效批处理的场景。

混合互补问题(MCP)是非线性规划和非合作博弈的一阶最优性条件,也是机器人中多智能体轨迹优化的自然建模方式。主流求解器PATH虽性能优异但为闭源。本文提出MixedComplementarityProblems.jl,一个纯Julia编写的开源内点法求解器,能:(i) 在标准基准上达到与PATH相当的可靠性;(ii) 原生支持跨CPU线程或NVIDIA GPU的批量并行处理;(iii) 高效实现解对问题参数的自动微分。在代表机器人规划的多智能体变道轨迹游戏中,其多线程CPU版本批量求解速度比逐次调用PATH快约100倍。未修改的GPU后端也显著更快,但在每实例的KKT系统规模较小时仍不及多线程CPU;当系统增大时,GPU优势显现,并对该临界点进行了量化分析。本文描述了求解器的内点公式、统一支持密集、批处理稀疏与单一大型线性代数后端的抽象机制,并在随机生成的二次规划与轨迹游戏上对比了与PATH的性能表现。

原文摘要 · Abstract (English)

Mixed complementarity problems (MCPs) arise as the first-order optimality conditions of nonlinear programs and noncooperative games, and provide a natural formulation for multi-agent trajectory optimization problems that appear throughout robotics. The dominant solver for problems of this form is PATH, which offers strong performance on robotics problems but remains closed-source. We present MixedComplementarityProblems.jl, an open-source, pure Julia implementation of an interior point method for parametric MCPs that: (i) matches PATH's reliability on standard benchmarks, (ii) natively supports batched, parallel processing of many parameter instances, either across CPU threads or on an NVIDIA GPU, and (iii) supports efficient automatic differentiation of solutions with respect to problem parameters. On a multi-agent lane-change trajectory game representative of robotics planning problems, our CPU-multithreaded batched solver clears a batch of parametric instances ~100x faster than sequential calls to PATH. A GPU backend, running the same solver implementation unmodified, also clears these batches far faster than PATH, but does not outperform the multithreaded CPU on this problem; the GPU pulls ahead only once each per-instance KKT system grows large, and we characterize this regime dependence. We describe the solver's interior point formulation, the abstraction that lets a single solver implementation run unmodified across dense, batched-sparse, and single-large linear-algebra backends, and report benchmarks against PATH on both randomly generated quadratic programs and trajectory games.

优化求解机器人规划并行计算Julia

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。