Multi-Agent Path Finding (MAPF)
Contact: Students: Bharath Muppasani; Ritirupa Dey Faculty: Biplav Srivastava, Vignesh Narayanan
Key Idea
Our research enhances Multi-Agent Path Finding (MAPF) by developing a scalable hybrid framework that minimizes information sharing while ensuring collision-free solutions. We combine decentralized Reinforcement Learning with a lightweight central coordinator for dynamic conflict resolution. Additionally, we introduce the Multi-Agent Planning Ontology (maPO), a unified semantic schema that transforms raw MAPF execution traces into a queryable knowledge graph, enabling on-demand, human-readable explanations for planner behavior and improving transparency.
Scalable MAPF using a Hybrid Execution Strategy
Traditional centralized MAPF algorithms provide high-quality solutions but struggle to scale in large, multi-agent scenarios. To address this, we propose a hybrid framework that blends decentralized path planning with a lightweight centralized coordinator. Agents use a Reinforcement Learning (RL) policy to plan their paths based on local information. The central coordinator detects potential collisions and issues minimal, targeted alerts—such as conflict-cell flags or brief conflict tracks—to prompt agents to replan. This approach significantly reduces inter-agent information sharing compared to fully centralized or distributed methods, while still consistently finding feasible, collision-free solutions in large-scale scenarios.
Experimental Results
See our comparative report on inter-agent information sharing tests: View Report
Representative Publication
-
Scalable Multi-Agent Path Finding using Collision-Aware Dynamic Alert Mask and a Hybrid Execution Strategy
Anonymous Submission
[Paper]
maPO: An Ontology for Explainable MAPF
As multi-agent systems become more autonomous, the need for transparent and interpretable decision-making is critical. To address this, we introduce the Multi-Agent Planning Ontology (maPO), a unified semantic schema that formalizes MAPF concepts like collision events, conflict alerts, and replanning strategies. Our framework includes a log-to-graph pipeline that ingests planner execution traces and transforms them into a rich knowledge graph. This allows stakeholders to ask complex questions about the planner's behavior (e.g., "Why did an agent wait?") using SPARQL queries, which are then translated into human-readable explanations. A user study confirmed that our generated explanations are significantly clearer and more useful than raw planner data.
Representative Publication
-
maPO: An Ontology for Multi-Agent Path Finding and Its Usage for Explaining Planner Behaviour
Anonymous Submission
[Paper]
Explore the Ontology
Explore the maPO schema and generate explanations on our interactive web platform: Visit Web Platform