Robots
5 TurtleBots
Success Rate
99%
Scenarios
10 validated
Overview
A centralized multi-robot coordination system for 5 TurtleBot3 Burgers operating in a shared Gazebo environment. The system assigns inspection tasks optimally using the Hungarian algorithm and navigates each robot to its target using A* on a shared occupancy costmap, achieving 99% mission completion across 10 diverse scenarios.
Problem Statement
Multi-robot systems face two fundamental challenges: who goes where (task allocation) and how to get there without collisions (motion planning). Naive round-robin assignment wastes travel time, while decentralized planners often deadlock. This project implements a centralized coordinator that solves both problems globally — minimizing total travel distance while ensuring collision-free navigation.
Task Allocation — Hungarian Algorithm
Given N robots and M tasks, the system builds an N×M cost matrix where each entry is the Euclidean distance from robot i to task j. The Hungarian algorithm solves the linear assignment problem in O(N³) time, yielding the globally optimal assignment that minimizes total travel. When tasks arrive dynamically mid-mission, the allocator re-runs with remaining robots and unstarted tasks only.
Motion Planning — A* on Costmap
Each assigned robot plans a path using A* on a 0.05 m/cell occupancy costmap. The costmap inflates obstacle boundaries by the robot radius plus a safety margin, ensuring paths are inherently collision-safe with static obstacles. Paths are published as Nav2 goal sequences, with the TurtleBot's built-in DWB controller handling local trajectory following.
Collision Avoidance Between Robots
Dynamic collision avoidance between robots is handled by a priority-based reservation scheme. When two robots' planned paths share a cell within a 2 s time window, the lower-priority robot replans with the other's trajectory added as a dynamic obstacle. This avoids deadlocks without requiring full multi-agent path planning.
Validation
Ten scenarios were designed with increasing complexity: single-row tasks, scattered tasks, narrow corridors, dynamic arrivals, and simultaneous starts. Each scenario ran 5 times. Mission success (all tasks completed, no collisions) was achieved in 99 of 100 runs. The single failure was a localization drift event unrelated to the planner.
def allocate(robots, tasks):
C = build_cost_matrix(
robots, tasks
)
assign = hungarian(C)
for r, t in assign:
plan_path(r, t, costmap)Tools & Stack
Key Outcomes
99% mission success rate across 10 scenarios and 100 total runs
Optimal task assignment in under 3 ms for 5 robots and 8 tasks
Zero deadlocks across all validated scenarios
Supports dynamic task arrivals mid-mission without replanning full fleet