Decentralized Multiagent Trajectory Planning via Duality and Biconvex Optimization

In this work, we present novel approaches for solving decentralized trajectory planning for networked multiagent systems. We first provide a new formulation of the safety constraint facilitating faster convergence with safety guarantees, with a computation time that is a fraction of methods that are built upon sequential linearization. This newly proposed constraint reformulation is based on the combination of the dual problem to the minimum distance between convex sets on one hand, and biconvex optimization, on the other. This approach enables imposing safety constraints on the vehicular system that involve non-differentiable variables. The second important observation involves making the approach decentralized, leading to a scalable trajectory optimization algorithm based on the reformulated biconvex optimization, along with the successive convexification (SCvx). This algorithm features a minimum data sharing in comparison to the traditional distributed gradient method or dual decomposition-based algorithm like alternating direction method of multipliers (ADMM). Specifically, the number of variables shared in our setup is less than half that of the ADMM-based sequential convex programming (ADMM-SCP). We also show the strong convergence of the biconvex formulation to the partial minimum of the overall problem under mild assumptions. Numerical results with up to ten agents showcase our theoretical contributions. More generally, the proposed framework enables efficient coordination of large-scale cooperating unmanned vehicles navigating complex environments.