The multi-robot path planning problem is the problem of finding optimal (or close to optimal) paths for n robots simultaneously without collisions where each robot has a designated start and goal state. This problem can be solved in different ways, ranging from greedy search methods to heuristic algorithms.
The following videos can be insightful:
-
https://www.youtube.com/watch?v=VJkFHIUHHXw (View the bit from 1:30 – 4:45. You can view the rest of the video but the content is based on a course and may be a bit advanced.)
-
Amazon is run by robots? https://www.youtube.com/watch?v=TUx-ljgB-5Q
The goal is to implement a program that creates a grid (environment in which the robots operate) and initial information which includes the number of robots (at least 3), their starting and goal positions on the grid, as well as the position of obstacles. The program should show how the robots traverse their paths to their goal states on the grid.
The program must be able to:
i) Read the input (number of robots, start & goal states, position of obstacles, etc.)
ii) Show the movement of the robots.
iii) Display the output.
This project was originally implemented as a basic pathfinding algorithm. It has since been redesigned into a more structured and visually interpretable system, focusing on clarity, visualization and improved architecture.
- Added visual representation of pathfinding process
- Refactored algorithm structure for clarity
- Improved design for extensibility
- Enhanced readability and system layout
- Some structural improvements were assisted using AI tools to enhance readability and visualization quality
Conflict-Based Search with A* guarantees collision-free paths through two layers working together. Here's how it actually works in the code:
Layer 1 — High-level CBS detects conflicts
After planning each agent independently, CBS scans all paths simultaneously, timestep by timestep, looking for two types of conflict:
-
Vertex conflict: two agents in the same cell at the same time:
- Agent A and Agent B both at (5,3) at t=7
-
Edge conflict: two agents swapping positions in the same step (they'd pass through each other):
- Agent A moves (3,4)→(4,4) while
- Agent B moves (4,4)→(3,4) between t=6 and t=7
When a conflict is found, CBS branches the constraint tree and it creates two child nodes, one that tells A "you cannot be there" and one that tells B "you cannot be there". Only the affected agent is re-planned.
Layer 2 — Low-level A enforces the constraints
-
A* does not plan in 2D space, it plans in (cell, time) space. Every constraint passed down from CBS is checked at each expansion:
-
A vertex constraint (agent, cell, t) makes that state illegal.
A* will never expand through it. An edge constraint (agent, from, to, t) removes that move entirely from the neighbour list. This continues up the constraint tree until a plan set with zero conflicts is found. That final set is provably collision-free by construction.
What could still look like a collision in the UI?
-
If two agents appear to overlap visually, it's almost always one of these:
- The plan succeeded but the animation renders two agents on the same pixel because their cells are adjacent and the sprite is larger than a cell thus not a true collision.
-
The solver hit maxNodes or maxT budget and returned null, so agents fall back to their start positions.
Yes, this needs fixing.