GPU Accelerated Convex Approximations for Fast Multi-Agent Trajectory Optimization

In this letter, we present a computationally efficient trajectory optimizer that can exploit GPUs to jointly compute trajectories of tens of agents in under a second. At the heart of our optimizer is a novel reformulation of the non-convex collision avoidance constraints that reduces the core computation in each iteration to a large scale, convex, unconstrained Quadratic Program (QP). Importantly, our QP structure requires us to compute the associated matrix factorization/inverse only once for a fixed number of agents. Moreover, we can do it offline and then use the same for different problem instances. This further simplifies the solution process, effectively reducing it to a few matrix-vector products. For a large number of agents, this computation can be trivially accelerated on GPUs using existing off-the-shelf libraries. We validate our optimizer's performance on challenging benchmarks and show substantial improvement over state of the art in computation time and trajectory quality.