# Conflict-based Search for Multi-Robot Motion Planning with Kinodynamic Constraints

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Jul 2022.

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

- [Learning Team-Based Navigation: A Review of Deep Reinforcement Learning Techniques for Multi-Agent Pathfinding](https://mlsanity.com/paper/2308.05893/) (2023)
- [Multi-agent Path Finding for Cooperative Autonomous Driving](https://mlsanity.com/paper/2402.00334/) (2024)
- [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)
- [Clique Analysis and Bypassing in Continuous-Time Conflict-Based Search](https://mlsanity.com/paper/2312.16106/) (2023)
- [Multi-agent Path Finding for Mixed Autonomy Traffic Coordination](https://mlsanity.com/paper/2409.03881/) (2024)
- [Search-Based Spatiotemporal and Multi-Robot Motion Planning on Graphs of Space-Time Convex Sets](https://mlsanity.com/paper/2607.00444/) (2026)
- [LUCID: An Agentic AI Framework on Digital-Twin in the Loop for QoS-Guaranteeing Robotic Control](https://mlsanity.com/paper/2608.28437/) (2026)
- [From Discrete Plans to Real-World Execution: A World-Model-Driven Framework for Execution-Aware Multi-Agent Path Finding](https://mlsanity.com/paper/2511.21886/) (2025)
- [GRACE: A Unified 2D Multi-Robot Path Planning Simulator & Benchmark for Grid, Roadmap, And Continuous Environments](https://mlsanity.com/paper/2603.10858/) (2026)

## Abstract (arXiv)

Multi-robot motion planning (MRMP) is the fundamental problem of finding non-colliding trajectories for multiple robots acting in an environment, under kinodynamic constraints. Due to its complexity, existing algorithms either utilize simplifying assumptions or are incomplete. This work introduces kinodynamic conflict-based search (K-CBS), a decentralized (decoupled) MRMP algorithm that is general, scalable, and probabilistically complete. The algorithm takes inspiration from successful solutions to the discrete analogue of MRMP over finite graphs, known as multi-agent path finding (MAPF). Specifically, we adapt ideas from conflict-based search (CBS) - a popular decentralized MAPF algorithm - to the MRMP setting. The novelty in this adaptation is that we work directly in the continuous domain, without the need for discretization. In particular, the kinodynamic constraints are treated natively. K-CBS plans for each robot individually using a low-level planner and and grows a conflict tree to resolve collisions between robots by defining constraints for individual robots. The low-level planner can be any sampling-based, tree-search algorithm for kinodynamic robots, thus lifting existing planners for single robots to the multi-robot settings. We show that K-CBS inherits the (probabilistic) completeness of the low-level planner. We illustrate the generality and performance of K-CBS in several case studies and benchmarks.