Post

Conflict-Based Search for Multi-Agent Path Finding, From Scratch in C++

Conflict-Based Search (CBS) for multi-agent path finding in C++ from scratch: Dijkstra, A*, space-time A*, MovingAI benchmarks and OpenCV animation.

Conflict-Based Search for Multi-Agent Path Finding, From Scratch in C++

My first project at the SJTU RAP Lab, written before starting on VADER, multi-robot navigation in unknown environments. The goal was to understand multi-agent path finding by building the whole stack myself: graph search, the conflict-based solver, map parsing and visualisation.

In multi-agent path finding (MAPF), each agent has its own start and goal on a shared graph, and the agents must not occupy the same vertex or swap across the same edge at the same time.

What’s in it

  • Single-agent search: Dijkstra, A, and space-time A, where states carry a time step so an agent can wait.
  • Conflict-Based Search (Sharon et al., 2015), which works on two levels:
    • The low level plans each agent alone with space-time A*.
    • The high level searches a tree of constraints. When two agents’ paths conflict, it splits into two children, each forbidding one agent from the conflicting vertex or edge at that time step. It returns the optimal solution under the sum-of-costs objective.
  • MovingAI benchmark parsers for .map and .scen files, so the solver runs on standard instances.
  • OpenCV animation that replays the solved paths step by step.
  • Unit tests for each search and the parsers, built with CMake.

CBS on a larger arena map. Agents wait or detour exactly where their paths would otherwise conflict.

Demo video: youtube.com/watch?v=8sfq2VUD6cE Code: github.com/dunyanong/conflict-based-search

Why it mattered

CBS assumes the map is known and the plan is executed exactly. VADER drops both assumptions: robots discover the map as they go, and they only coordinate when they meet. That work still uses a CBS variant (CBS-AA) at its core, on a graph the robots build together.

This post is licensed under CC BY 4.0 by the author.