Parallel Collaborative Motion Planning with Alternating Direction Method of Multipliers

Collaborative motion planning for multi-agent systems is a challenging problem because of the existence of highly nonlinear and nonconvex constraints. Such difficulties also lead to inavoidable computational inefficiency, which significantly prohibits applying the existing collaborative motion planning algorithms to complex scenarios. This paper proposes a parallel computational algorithm to achieve collaborative motion planning efficiently, considering the nonlinear dynamics model and the nonconvex collision-avoidance constraints. Specifically, the alternating direction method of multipliers (ADMM) framework is elegantly incorporated to separate the large-scale cooperative nonconvex planning problem as two tractable and manageable subproblems, where the two subproblems handle the dynamics constraints and collision-free constraints, respectively. In the proposed approach, the differential dynamic programming (DDP) method is utilized to effectively solve the nonlinear subproblem with the dynamics constraints; meanwhile, the interior point (IPOPT) method is employed to address the nonconvex subproblem derived from the collision-avoidance constraints. Finally, two simulation scenarios are successfully implemented to illustrate the effectiveness of the proposed algorithm.