🤖 AI

Towards Information-Optimized Multi-Agent Path Finding: A Hybrid Framework with Reduced Inter-Agent Information Sharing

This paper introduces IO-MAPF, a hybrid framework that combines decentralized reinforcement learning with a lightweight centralized coordinator to solve multi-agent pathfinding problems using minimal inter-agent information sharing, achieving significant reductions in communication overhead while maintaining high solution quality and success rates.

Original authors: Bharath Muppasani, Ritirupa Dey, Biplav Srivastava, Vignesh Narayanan

Published 2026-02-24

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Bharath Muppasani, Ritirupa Dey, Biplav Srivastava, Vignesh Narayanan

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a busy warehouse filled with dozens of delivery robots. Their job is to move packages from Point A to Point B without bumping into each other. This is a classic problem in robotics called Multi-Agent Path Finding (MAPF).

The paper you provided introduces a new, smarter way to solve this problem called IO-MAPF. Here is the breakdown in simple terms, using some creative analogies.

The Problem: The "Too Much Information" Traffic Jam

Traditionally, there are two ways to manage these robots:

The "Big Boss" Approach (Centralized): One super-computer knows the location, speed, and goal of every single robot at all times. It calculates the perfect path for everyone.
- The Downside: As you add more robots, the computer gets overwhelmed. It's like trying to direct traffic in a city of 10 million cars using a single traffic light controller. Also, if the robots are private (like delivery drones for different companies), they don't want to share their secrets with a central boss.
The "Every Man for Himself" Approach (Decentralized/Learning): Each robot has a brain (AI) and looks around to see who is nearby. They learn to dodge each other on their own.
- The Downside: To see who is nearby, they need powerful sensors (cameras, LiDAR) and constant communication. This uses a lot of battery, costs money, and creates a lot of "noise" (data) on the network. If two robots get stuck in a tight spot, they might not know how to untangle themselves because they only see what's right in front of them.

The Solution: The "Smart Traffic Warden" (IO-MAPF)

The authors propose a Hybrid Framework called IO-MAPF. Think of this as a Smart Traffic Warden system.

Here is how it works, step-by-step:

1. The Robots Drive Themselves (Most of the Time)

Imagine the robots are like drivers on a highway. They have a GPS and know their own destination. They drive independently without constantly talking to every other car. They only look at the road immediately in front of them.

Analogy: You are driving to work. You don't need to know the exact destination of the car in the next lane; you just need to know if they are in your lane.

2. The "Warden" Watches from a Tower

There is a central coordinator (the Warden) sitting in a tower. It can see the whole map. However, it doesn't micromanage the robots. It doesn't tell them where to go every second.

The Magic: The Warden only speaks up when it sees a conflict is about to happen (e.g., two robots are about to crash).

3. The "Alert" System (Minimal Information)

When the Warden sees a potential crash, it doesn't send a 50-page report. It sends a tiny, targeted alert.

The Alert: "Hey Robot A, stop! Robot B is coming through that intersection in 3 seconds. You need to wait or take a small detour."
The Result: Robot A gets this tiny piece of info, recalculates its path for just a few seconds, and gets back to driving on its own.

4. The "Tiered" Strategy (Escalation)

If a simple "wait" doesn't work, the system gets slightly more involved, but only as much as needed:

Level 1: "Just wait a second." (Low info)
Level 2: "Move to that empty spot next to you." (Medium info)
Level 3: "Here is a short path for you and your neighbor to swap places." (High info, but only for those two).

Why is this a Big Deal? (The "Information Units")

The authors created a new way to measure how much data is being shared, called Information Units (IU).

Old Learning Methods: Imagine every robot is constantly shouting its location, speed, and goal to everyone else. That's like a room full of people screaming. It's loud, expensive, and chaotic.
IO-MAPF: Imagine the robots are silent. They only whisper a single word ("Wait" or "Move") when absolutely necessary.

The Result: The paper shows that their method uses 2 to 23 times less information than the best existing methods.

Analogy: It's the difference between sending a 100-page contract to solve a minor disagreement versus just sending a quick text message saying "Let's meet at 5."

Real-World Test

They didn't just run this on a computer; they tested it on real TurtleBot4 robots in a physical grid.

The robots communicated almost nothing with each other.
They only synced up with the central controller to say, "I'm ready for the next step."
They successfully navigated without crashing, proving that you don't need expensive sensors or constant chatter to solve complex traffic problems.

Summary

IO-MAPF is like a smart traffic system where:

Drivers (robots) know their own way.
A traffic cop (central coordinator) watches for accidents.
The cop only intervenes with a tiny, specific instruction when a crash is imminent.
This saves massive amounts of data, battery, and privacy, while still getting everyone to their destination safely and quickly.

It proves that less communication can actually lead to better, faster, and more private results.

1. Problem Definition

The paper addresses Multi-Agent Path Finding (MAPF), the problem of computing collision-free trajectories for multiple agents navigating a shared environment. While traditional centralized algorithms (e.g., Conflict-Based Search, CBS) offer high solution quality, they suffer from poor scalability due to combinatorial explosion and require full global information, which raises privacy concerns and bandwidth costs. Conversely, distributed and learning-based methods (e.g., MARL) offer better scalability but often rely on continuous, high-bandwidth information exchange (e.g., full state observation or frequent communication), which is resource-intensive and impractical for privacy-sensitive or bandwidth-constrained real-world deployments.

The core research question is: How can MAPF be solved with minimal inter-agent information sharing while preserving solution feasibility and quality?

2. Methodology: IC-MAPF Framework

The authors propose IC-MAPF (Information-Centric MAPF), a hybrid framework that integrates decentralized path planning with a lightweight centralized coordinator. The system operates on a four-stage pipeline designed to minimize information exchange by sharing data only "on-demand" when conflicts arise.

A. Four-Stage Pipeline

S1: Decentralized Path Planning:
- Each agent independently computes an initial trajectory from start to goal using a Reinforcement Learning (RL) policy.
- Information Used: Only local static map data and the agent's own state/goal. No other-agent information is exchanged.
S2: Centralized Collision Detection:
- A central coordinator collects all independent trajectories and performs a deterministic, rule-based scan to identify vertex and edge collisions.
- Complexity: Linear in the sum of agent path lengths.
S3: Collision Control (Alert Generation):
- Upon detecting a conflict, the coordinator selects a specific agent to replan (using heuristics like "Fewest Future Collisions").
- It issues a targeted Alert containing minimal information: the conflict time, the conflict location, and a "rewind" window parameter.
S4: Tiered Replanning (The Core Innovation):
The selected agent attempts to resolve the conflict using a hierarchy of strategies, escalating information usage only if simpler methods fail:
- S4.0 (Yield-based): The agent moves to a nearby "parking" cell and waits, using only local occupancy checks.
- S4.1 (Static Replanning): The agent replans a short segment of its path, treating the conflict cell as a static obstacle.
- S4.2 (Dynamic Replanning): The agent replans while treating the predicted short-term trajectories of conflicting agents as dynamic obstacles (time-varying constraints).
- S4.3 (Local Joint Planning): If single-agent repairs fail, a small subset of tightly coupled agents is replanned jointly over a bounded window.
- Deferral Mechanism: If all strategies fail, the agent is temporarily deferred (parked) until the system stabilizes, preventing deadlocks.

B. Information Units (IU) Metric

To quantify information efficiency, the authors introduce Information Units (IU).

Definition: One IU represents the data required to describe one agent's state (e.g., coordinates) at a single timestep.
Measurement: For learning-based methods, IU is the count of other agents observed within the Field of View (FOV) or communicated. For IC-MAPF, IU is the count of specific constraints/alerts issued by the coordinator.

3. Key Contributions

Information-Centric Formulation: The paper formally defines MAPF strategies based on the specific information components ( $M_i, S_i, O_j$ ) available to agents, categorizing algorithms into Centralized, Distributed, Decentralized, and Hybrid based on their information flow.
Hybrid Framework (IC-MAPF): A novel architecture that combines decentralized RL planning with a centralized "alert-driven" coordinator. It proves that continuous global observation is unnecessary; instead, sparse, event-triggered signals are sufficient for conflict resolution.
Tiered Replanning Strategy: A sound and locally complete set of repair operators (Yield, Static, Dynamic, Joint) that allows the system to trade off information complexity against solution success dynamically.
Quantitative Metric (IU): The introduction of the Information Units metric allows for direct, apples-to-apples comparison of communication overhead across different algorithmic paradigms.

4. Experimental Results

The framework was evaluated on standard benchmarks (Moving AI Lab: random grids, den312d, warehouse) and real hardware (TurtleBot4 robots).

Information Efficiency:
- IC-MAPF achieved a 2× to 23× reduction in information sharing compared to state-of-the-art learning-based baselines (SCRIMP, DCC, EPH).
- In some scenarios, the reduction reached ~93% (e.g., 691 IU vs. 10,260 IU for 20 agents).
- Unlike learning-based methods that require continuous sensing of neighbors, IC-MAPF agents operate with near-zero inter-agent data until a conflict occurs.
Success Rate (SR) & Scalability:
- IC-MAPF maintained 100% Success Rate on random maps with up to 80 agents, whereas learning-based baselines (SCRIMP, EPH) saw significant drops in success rate or failed entirely as agent density increased.
- It outperformed centralized search-based methods (CBS) in scalability, solving large instances (128 agents) where CBS timed out or failed.
Solution Quality (Makespan):
- While the makespan (total time to complete) was slightly higher than optimal centralized solvers (due to the decentralized nature), it remained competitive with distributed learning methods while offering significantly better reliability.
Hardware Validation:
- Experiments on 5 TurtleBot4 robots in a 6×6 grid confirmed the framework's viability. The robots operated with no onboard perception (LiDAR/Cameras) and relied solely on minimal synchronization messages, demonstrating extreme resource efficiency.

5. Significance and Conclusion

This work demonstrates that reliable multi-agent coordination does not require continuous, high-bandwidth information exchange. By shifting from "always-on" observation to "event-driven" alerts, IC-MAPF achieves a favorable trade-off between scalability, solution quality, and resource usage.

Key Implications:

Privacy: Agents can operate without revealing their full goals or states to neighbors, only sharing necessary conflict constraints.
Bandwidth & Energy: Drastically reduces communication overhead, making it suitable for large swarms or bandwidth-limited environments.
Hardware: Enables deployment on low-cost robots without expensive sensors (LiDAR/RGB-D) or heavy onboard compute for continuous inference.

The paper concludes that a hybrid, information-optimized approach is a viable and superior alternative for real-world MAPF deployments where privacy, bandwidth, and scalability are critical constraints.