A message-passing algorithm for multi-agent trajectory planning
This addresses trajectory planning for multi-agent systems, which is an incremental improvement over existing methods.
The paper tackles the problem of computing collision-free global trajectories for multiple agents with specified start and end configurations, using an improved ADMM-based approach that is naturally parallelizable and adaptable to different cost functionals, with results showing computational requirements scale well with agent count.
We describe a novel approach for computing collision-free \emph{global} trajectories for $p$ agents with specified initial and final configurations, based on an improved version of the alternating direction method of multipliers (ADMM). Compared with existing methods, our approach is naturally parallelizable and allows for incorporating different cost functionals with only minor adjustments. We apply our method to classical challenging instances and observe that its computational requirements scale well with $p$ for several cost functionals. We also show that a specialization of our algorithm can be used for {\em local} motion planning by solving the problem of joint optimization in velocity space.