Multi-Robot Path Planning

A dependency-free C++17 package implementing three grid-based multi-agent path planners behind the same API:

• Conflict-Based Search (CBS): optimal for sum of costs within configured limits.
• Prioritized Planning: fast sequential planning in input-agent priority order.
• Reservation Tables (windowed cooperative A*/WHCA*): rolling-horizon planning with rotating priorities.

Detailed pseudocode for all three planners is available in ALGORITHM_PSEUDOCODE.md.

All planners allow four-neighbor moves and waiting. They prevent two robots from occupying one cell simultaneously and prevent robots from swapping across an edge in one timestep. A robot remains at its goal after its returned path ends.

Build and run

cmake -S . -B build
cmake --build build
ctest --test-dir build --output-on-failure
./build/mrpp_cli examples/crossing.cfg

On a multi-config Windows generator, the executable is usually build/Debug/mrpp_cli.exe.

On Windows, the complete configure, build, test, planner, and visualization workflow can be run with Conflict-Based Search on the ten-robot simulation as the default:

mrpp_simulation.bat

Select the default algorithm in configs/simulation.cfg by changing only this line:

algorithm=cbs

Accepted values are cbs, prioritized, and reservation_table. The selector references configs/house_exchange.cfg, which contains the shared 20×15 maze, houses, starts, and goals.

Pass a different configuration as the first argument when needed:

mrpp_simulation.bat configs\conflict_based_search.cfg

The shared planner scenario contains ten robots, ten unique starts, ten unique goals, and several obstacle groups:

mrpp_simulation.bat configs\conflict_based_search.cfg

Planner-specific configurations are stored in configs:

• configs/conflict_based_search.cfg
• configs/prioritized_planning.cfg
• configs/reservation_table.cfg

All three files reference the same map, starts, goals, and planning limits; only algorithm differs. Goal positions represent each robot's house. Robots 1/10, 2/9, and 3/7 start in each other's houses. Robots 4, 6, 5, and 8 form a four-house cycle, so every robot must move to reach its own house. Alternating gates in four long walls force substantial detours and interactions.

CTest executes the CLI once with every planner-specific configuration in addition to the C++ unit tests.

Python visualization

Install Matplotlib and animate the algorithm selected by the same configuration file:

python -m pip install matplotlib
python tools/visualize.py configs/reservation_table.cfg

The visualizer locates the normal CMake executable automatically. A custom executable and playback speed can be supplied with --executable and --interval:

python tools/visualize.py configs/prioritized_planning.cfg --executable build/Debug/mrpp_cli.exe --interval 300

Use --save solution.gif to export an animation. GIF export may require Pillow; MP4 export requires an FFmpeg installation. Colored circles are robots, matching dashed squares are goals, and faint lines show paths travelled so far.

Configuration

The file is key=value. algorithm accepts cbs, prioritized, or reservation_table. Each agent is id,start_x,start_y,goal_x,goal_y. The ASCII map begins after map= and uses . for free cells and # for obstacles. See the files in configs.

max_time bounds path length, max_iterations bounds CBS high-level expansions, and window_size controls the reservation-table horizon.

Library API

Include mrpp/planner.h, call createPlanner(name), then call plan(grid, agents, options). Every implementation returns the same PlanningResult, with paths in the same order as input agents.