Conflict-Based Search As a Protocol: A Multi-Agent Motion Planning Protocol for Heterogeneous Agents, Solvers, and Independent Tasks
Rishi Veerapaneni, Ho Kwan Alvin Tang, Yidai Cen, Haodong He, Sophia Zhao, Viraj Shah, Ziteng Ji, Gabriel Olin, Jon Arrizabalaga, Yorai Shaoul, Jiaoyang Li, Maxim Likhachev
AI summary
Problem
Real-world multi-agent systems will increasingly combine robots from different manufacturers with proprietary, algorithmically diverse motion planners, but existing coordination methods require all agents to share the same underlying solver.
Approach
The authors formalize Conflict-Based Search as a protocol that requires only a simple plan() API returning a constrained path, cost, and space-time volume, allowing a central planner to iteratively resolve conflicts by querying diverse, black-box solvers.
Key results
- Formalizes the Algorithmically Heterogeneous MAMP problem setting
- Defines a minimal single-agent planning API for CBS integration
- Successfully coordinates diverse solvers including A*, RRT, optimization, diffusion, and RL
- Supports independent task types like coverage and surveillance beyond start-goal planning
Why it matters
It enables seamless, vendor-agnostic coordination of diverse robotic fleets, lowering deployment barriers for real-world multi-robot applications.
Abstract
Imagine the future construction site, hospital, or office with dozens of robots bought from different manufactur- ers. How can we enable these different robots to effectively move in a shared environment, given that each robot may have its own independent motion planning system? This work shows how we can get efficient collision-free movements between algorithmically heterogeneous agents by using Conflict-Based Search (Sharon et al. 2015) as a protocol. At its core, the CBS Protocol requires one specific single-agent motion planning API; finding a collision-free path that satisfies certain space-time constraints. Given such an API, CBS uses a central planner to find collision-free paths - independent of how the API is implemented. We demonstrate how this protocol enables multi- agent motion planning for a heterogeneous team of agents completing independent tasks with a variety of single-agent planners including: Heuristic Search (e.g., A*), Sampling Based Search (e.g., RRT), Optimization (e.g., Direct Collocation), Diffusion, and Reinforcement Learning.