Representation-Optimal Multi-Robot Motion Planning Using Conflict-Based Search

Abstract

Multi-Agent Motion Planning (MAMP) is the problem of computing feasible paths for a set of agents each with individual start and goal states within a continuous state space. Existing approaches can be split into coupled methods which provide optimal solutions but struggle with scalability or decoupled methods which provide scalable solutions but offer no optimality guarantees. Recent work has explored hybrid approaches that leverage the advantages of both coupled and decoupled approaches in an easier discrete subproblem, Multi-Agent Pathfinding (MAPF). In this work, we adapt recent developments in hybrid MAPF to the continuous domain of MAMP. We demonstrate the scalability of our method to manage groups of up to 32 agents, demonstrate the ability to handle up to 8 high-DOF manipulators, and plan for heterogeneous teams. In all scenarios, our approach plans significantly faster while providing higher quality solutions.