Representation-Optimal Multi-Robot Motion Planning using Conflict-Based Search
This addresses motion planning for heterogeneous robotic teams in continuous environments, which is an incremental advance over existing discrete methods.
The paper tackled the Multi-Agent Motion Planning problem in continuous spaces with heterogeneous agents by adapting Conflict-Based Search from discrete multi-agent pathfinding, resulting in faster planning and higher-quality solutions for teams of up to 32 agents and 8 high-DOF manipulators.
Multi-Agent Motion Planning (MAMP) is the problem of computing feasible paths for a set of agents given individual start and goal states. Given the hardness of MAMP, most of the research related to multi-agent systems has focused on multi-agent pathfinding (MAPF), which simplifies the problem by assuming a shared discrete representation of the space for all agents. The Conflict-Based Search algorithm (CBS) has proven a tractable means of generating optimal solutions in discrete spaces. However, neither CBS nor other discrete MAPF techniques can be directly applied to solve MAMP problems because of the assumption of the shared discrete representation of the agents' state space. In this work, we solve MAMP problems by adapting the techniques discovered in the MAPF scenario by CBS to the more general problem with heterogeneous agents in a continuous space. We demonstrate the scalability teams 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.