Conflict-Based Search as a Protocol: A Multi-Agent Motion Planning Protocol for Heterogeneous Agents, Solvers, and Independent Tasks

Rishi Veerapaneni1, Alvin Tang†1, Haodong He†1, Sophia Zhao†1, Viraj Shah†1, Yidai Cen†1, Ziteng Ji†2, Gabriel Olin‡1, Jon Arrizabalaga‡1, Yorai Shaoul‡1, Jiaoyang Li1, Maxim Likhachev1
1Carnegie Mellon University, 2UC Berkeley
†, ‡Indicates equal contribution respectively, ordered alphabetically
arXiv

CBS Protocol in action: Multi-agent motion planning with 6 agents with different single-agent planners, dynamics, and independent tasks. Colored Xs indicate constraints added to single-agent planners.

Abstract

Imagine the future construction site, hospital, office, or even sophisticated household with dozens of robots bought from different manufacturers. How can we enable these different systems 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 show 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.

Algorithmically Heterogeneous Multi-Agent Motion Planning (AH-MAMP)

Taking a step back, to our knowledge the problem of Multi-Agent Motion Planning (MAMP) with algorithmically heterogeneous solvers has not been explored by the MAMP community. In particular, existing MAMP methods for heterogeneous teams focus on robots with different capabilities but use algorithmically homogeneous solutions. On the other hand, existing multi-agent task planning/coordination methods focus on heterogeneous behaviors or task assignment and not on collision-free movement. Thus, part of the goal of this work is to bring attention to the problem of planning collision-free paths for agents with different single-agent solvers, which we call Algorithmically Heterogeneous Multi-Agent Motion Planning (AH-MAMP). AH-MAMP tries to achieve collision-free motion planning for heterogeneous single-agent solvers without being able to modify the solvers. Solutions for AH-MAMP instead require designing multi-agent protocols with well-defined single-agent APIs, with the protocol/API abstraction enabling using heterogeneous single-agent solvers.

CBS Protocol Overview

CBS Protocol Diagram

We depict using the CBS Protocol. Given a Multi-Agent Motion Planning (MAMP) problem, each agent defines a plan() API that satisfies the CBS Protocol requirements. At its core, the plan() API (blue box) takes in a set of space-time constraints (locations to avoid at certain times) and outputs a collision-free path satisfying the constraints, and the associated occupied space-time volume and cost. The plan() API for each agent is input into the CBS Protocol (which has no other knowledge except for collision detection), which uses the APIs and outputs a collision-free solution. Since the CBS Protocol just requires that each agent defines their own plan() API following the requirements, each agent has full flexibility in how they implement the API. This allows them to use their own single-agent solvers which incorporates their own kinodynamic constraints, and even allow them to do different independent tasks (e.g., coverage or circling a target point). The CBS Protocol easily enables adding new agents with different single-agent solvers and tasks as each agent just needs to implement the plan() API.

Visualizations with Heterogeneous Agents, Solvers, and Independent Tasks

Our experiments seek to show the generality of the CBS Protocol to plan for a team of algorithmically heterogeneous agents with different single-agent solvers and tasks. We implemented the following single-agent solvers with each defining the plan() API. Note that using a Reinforcement Learning single-agent solver with CBS had not been done before.

Solver Dynamics Tasks
A* 4-connected, Dubin's, Ackermann Start-Goal, Coverage
RRT Omnidirectional, 4-connected Start-Goal, Coverage
Direct Collocation Ackermann Start-Goal, "Surveillance" (circling a target point)
Diffusion Omnidirectional Start-Goal (with/without motion patterns)
Reinforcement Learning Unicycle Start-Goal, Coverage

BibTeX

@article{veerapaneni2025cbs_protocol,
  title={Conflict-Based Search as a Protocol: A Multi-Agent Motion Planning Protocol for Heterogeneous Agents, Solvers, and Independent Tasks},
  author={Veerapaneni, Rishi and Tang, Alvin and He, Haodong and Zhao, Sophia and Shah, Viraj and Cen, Yidai and Ji, Ziteng and Olin, Gabriel and Arrizabalaga, Jon and Shaoul, Yorai and Li, Jiaoyang and Likhachev, Maxim},
  journal={arXiv preprint arXiv:2510.00425},
  year={2025}
}