Multi-Agent Robot Pathfinding
Coordinating collision-free robot paths with space-time reservations, conflict-guided priorities, and experimental peer-to-peer negotiation.
CSMI17 Artificial Intelligence team project with Mohd. Kaif and Ujjwal Sinha.
Overview & Research Motivation
A team project for CSMI17 Artificial Intelligence, exploring how robots can reach individual goals on a shared grid without occupying the same cell or swapping positions at the same time. The implementation connects canonical single-agent A* search to centralized multi-agent planning and an experimental decentralized negotiation protocol.
An interactive Python/Tkinter workbench exposes search frontiers, priority rankings, time-indexed reservations, and negotiation messages. Reproducible paired experiments compare planners on identical maps and endpoints, separating the effects of reservations, initial ordering, and priority promotion.
The Core Systems Problem
- Individually optimal paths can collide when several robots share corridors and intersections.
- Fixed priorities can block otherwise feasible plans, while decentralized replanning must reach agreement using exchanged proposals rather than a shared route planner.
My Specific Technical Contributions
- Collaborated on the implementation and evaluation of the single-agent and multi-agent pathfinding workbench as part of a three-member coursework team.
System Architecture & Verification Pipeline
Single-Agent Search
Canonical A* with Manhattan, Euclidean, Chebyshev, and zero heuristics on static four-connected grids, with shared tie-breaking and search accounting.
Conflict-Guided Space-Time A*
Ranks robots using predicted conflicts, constrained path positions, and independent path length; reserves vertices, reverse edges, and persistent goals, with bounded failed-agent promotion and whole-order restarts.
Decentralized Negotiation
Private per-robot controllers exchange versioned proposals and replan against superior peer paths. Matching version vectors and a final collision check precede joint execution.
Interactive Evaluation Workbench
Tkinter playback exposes actual search states, reservations, priority changes, and message events; seeded benchmarks record scenario fingerprints and paired planner metrics.
Evaluation & Benchmark Results
Technical Stack & Tools
Known Limitations
- Evaluation uses static grids, discrete time, and robots that remain at their goals after arrival; it does not model physical robot dynamics.
- Prioritized planning with finite search horizons and bounded restarts is neither complete nor globally optimal; a planning failure does not prove joint infeasibility.
- Decentralized negotiation is a sequential Python simulation of reliable synchronous messaging, without packet loss, transport delays, or hardware parallelism.
Connected Systems & Inquiries
A sensor prototype and designed analytics pipeline for condition monitoring of industrial motors and pumps.
Built discrete-event models in FlexSim to represent multi-stage manufacturing flow and multimodal distribution, combining production routing, material handling, transport networks, and operational visualization.