# Representation-Optimal Multi-Robot Motion Planning using Conflict-Based Search

arXiv: https://arxiv.org/abs/1909.13352 · HTML: https://mlsanity.com/paper/1909.13352/

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Sep 2019.

## Built on by (most cited first, 16 of 16)

- [LaCAM: Search-Based Algorithm for Quick Multi-Agent Pathfinding](https://mlsanity.com/paper/2211.13432/) (2022)
- [Multi-Robot Motion Planning with Diffusion Models](https://mlsanity.com/paper/2410.03072/) (2024)
- [Multi-Agent Motion Planning For Differential Drive Robots Through Stationary State Search](https://mlsanity.com/paper/2412.13359/) (2024)
- [CTRMs: Learning to Construct Cooperative Timed Roadmaps for Multi-agent Path Planning in Continuous Spaces](https://mlsanity.com/paper/2201.09467/) (2022)
- [Cooperative Task and Motion Planning for Multi-Arm Assembly Systems](https://mlsanity.com/paper/2203.02475/) (2022)
- [Accelerating Search-Based Planning for Multi-Robot Manipulation by Leveraging Online-Generated Experiences](https://mlsanity.com/paper/2404.00143/) (2024)
- [Hypergraph-based Multi-Robot Task and Motion Planning](https://mlsanity.com/paper/2210.04333/) (2022)
- [The Parameterized Complexity of Coordinated Motion Planning](https://mlsanity.com/paper/2312.07144/) (2023)
- [Optimal and Bounded Suboptimal Any-Angle Multi-agent Pathfinding](https://mlsanity.com/paper/2404.16379/) (2024)
- [Space-Time Graphs of Convex Sets for Multi-Robot Motion Planning](https://mlsanity.com/paper/2503.00583/) (2025)
- [Search-Based Spatiotemporal and Multi-Robot Motion Planning on Graphs of Space-Time Convex Sets](https://mlsanity.com/paper/2607.00444/) (2026)
- [Scalable Multi-robot Motion Planning for Congested Environments With Topological Guidance](https://mlsanity.com/paper/2210.07141/) (2022)
- [PRISM: Complete Online Decentralized Multi-Agent Pathfinding with Rapid Information Sharing using Motion Constraints](https://mlsanity.com/paper/2505.08025/) (2025)
- [An Analysis of Constraint-Based Multi-Agent Pathfinding Algorithms](https://mlsanity.com/paper/2511.18604/) (2025)
- [GRACE: A Unified 2D Multi-Robot Path Planning Simulator & Benchmark for Grid, Roadmap, And Continuous Environments](https://mlsanity.com/paper/2603.10858/) (2026)
- [Topology-Driven Anti-Entanglement Control for Soft Robots](https://mlsanity.com/paper/2605.05236/) (2026)

## Abstract (arXiv)

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.