CB-GCS: Conflict-Based Search on the Graph of Convex Sets for Multi-Agent Motion Planning

Multi-Agent Motion Planning (MAMP) seeks collision-free trajectories for multiple agents from their respective start to goal locations among static obstacles, while minimizing some cost function over the trajectories. Existing approaches include Mixed-Integer Programming (MIP) models, graph-based and sampling-based methods, and trajectory optimization, each with its own limitations. This paper introduces CB-GCS, a new approach that develops a Conflict-Based Search on the Graph of Convex Sets, to solve the MAMP. CB-GCS plans trajectories for agents in continuous workspaces, represented by time-augmented graphs of convex sets (T-GCS), and resolves agent-agent conflicts by adding constraints to the agents in that T-GCS. We test our CB-GCS against various baselines, including a graph-based method that combines search and sampling, as well as a Mixed-Integer Linear Program (MILP) formulation. The numerical results show that solutions found by our approach often have an optimality gap more than 10 times smaller than those found by the baseline when given the same amount of runtime limit.