Unified Global Formation Path Planning Strategy for Multi-Agent Systems Using Graph of Convex Sets

Abstract

To enhance the quality and scalability of global formation path planning in multi-agent systems, this letter proposes a unified strategy based on the Graph of Convex Sets (GCS) framework. The formation path planning problem is formulated as a shortest path problem within the GCS framework. The translation-only rigid (TO) and translation-and-scaling (TS) cases yield Mixed-Integer Convex Programming (MICP) problems with tight convex relaxations, whereas the translation-scaling-rotation (TSR) case combines the relaxed GCS formulation with nonlinear refinement during rounding. This approach enables simultaneous planning of optimal paths and formation configurations using convex optimization and rounding techniques. The framework supports a wide range of formation constraints, including rigid and flexible formations, ensuring adaptability to diverse scenarios while maintaining a scalable geometric representation as the number of agents increases. By exploiting the convex hull property of formation shapes, most constraints and costs are expressed in convex form, enabling efficient computation for the convex cases. Tests and comparisons across multiple scenarios validate the method's effectiveness in computing collision-free, scalable, and high-quality global formation paths and configurations.