Multi-Robot Pathfinding Simulator

A* hands one robot its shortest path. Put three robots on the same grid and every path becomes a constraint on every other — a plan is now a promise about where you will be, and when.

Built during my internship at U R Rao Satellite Centre (Mission Planning & Operations, under Mr. M. Srikanth; Group Director Mr. K. Subbarao). The target is an Industry 4.0 "dark factory" floor — where robots, not people, move the goods.

Python + Pygame, a 30×30 grid world with static and moving obstacles. One search core serves both A* and Dijkstra (a heapq priority queue over came_from / g_score dictionaries); a BFS variant runs the same maps for the comparison. Movement is 8-directional with an octile heuristic and a turn-penalty cost (0.1) folded into g, so path quality reflects how a real base actually turns.

Multiple robots take goals round-robin and coordinate through a space-time reservation table: each path claims cells in time, and later planners treat those claims as constraints. Line-of-sight smoothing straightens the result. Every run logs to CSV; the sim renders open/closed sets live and an exploration overlay of where the grid got searched.

Adding 8-directional movement quietly broke the heuristic's honesty. With orthogonal moves costing 1 and diagonals √2, a naive Manhattan heuristic stops being admissible on that grid — A* can over- or under-estimate and lose its guarantees. The fix was an octile / Euclidean-consistent heuristic (dx + dy + (√2 − 2)·min(dx, dy)) and moving the turn cost into g rather than h, so the heuristic stayed admissible while paths still straightened.

With moving 'worker' obstacles, a robot has to stop mid-path and re-plan — and the first version leaked. Residual open/closed-set and g-score state carried between successive A* calls and corrupted the next path. The fix was a full per-call reset of g / f / parent / direction across the grid before each search, plus a main-loop check that only triggers a replan when a future path cell becomes occupied — bounded to three attempts.

Running pathfinding and Pygame rendering in one blocking loop made the GUI hang and hid what the search was doing. I restructured robot motion as per-frame generators — yield-per-frame — stepped from the main loop, so several robots animate concurrently without freezing the event loop, and the open/closed sets stay visible during the search.