HI-MAPF

Abstract

Multi-Agent Path Finding (MAPF) is central to coordinating multiple agents in shared environments. Existing solutions impose significant requirements on communication, sensing, and computation, limiting their applicability in resource-constrained robotic deployments. Centralized search methods require full access to global state information and high-bandwidth channels, while distributed learning-based methods depend on sophisticated onboard perception (e.g., LiDAR, RGB-D cameras) and frequent inter-agent communication.

To address these limitations, we formulate Information-Centric MAPF (I-MAPF) and introduce HI-MAPF, a hybrid framework that augments decentralized planning with a lightweight centralized coordinator. We further introduce a method-agnostic metric, Information Units (IU), to quantify coordination overhead as a proxy for deployment cost. We evaluate HI-MAPF against recent communication-focused algorithms in both simulation (8–128 agents across structured and unstructured environments) and on ground robots in a physical deployment, demonstrating 2× to 510× reduction in information sharing while maintaining high success rates.

Demo Video

I-MAPF: Information-Centric Formulation

We characterize MAPF coordination by the information available to each agent \(i\) at time \(t\):

• \(\mathcal{M}_i = (V, E, O)\) — (possibly partial) environment knowledge: grid cells, edges, and obstacles
• \(\mathcal{S}_i = (s_i^t, g_i^t, \pi_{i|t_s:t_r})\) — self-state: current position, goal, and planned trajectory
• \(\mathcal{O}_j = \{(s_j^t, g_j^t, \pi_{j|t_s:t_r})\}_{j \in \mathcal{N}_i(t)}\) — other-agent information available through sensing or communication
• \(\mathcal{E}_{ij}(t)\) — event-triggered coordination signals: predicted collisions, deadlocks, or constraint/alert messages

Different MAPF paradigms differ in how much of \(\mathcal{I}_i(t)\) each agent accesses: Centralized methods use global \(\mathcal{M}\) and all agents' trajectories. Distributed methods restrict \(\mathcal{M}_i\) to a local FOV and \(\mathcal{O}_j\) to neighbors. Hybrid methods (including HI-MAPF) selectively reveal \(\mathcal{O}_j\) and constraints in response to \(\mathcal{E}_{ij}(t)\).

Information Units (IU)

To enable principled comparison of information consumption across MAPF paradigms, we define:

Lower IU indicates lower bandwidth, energy, and onboard hardware burden, improving feasibility for long-term robotic deployment. A \(d\)-dimensional inter-agent message vector (e.g., SCRIMP's 512-dim messages) contributes \(d\) IUs per transmission.

HI-MAPF Framework

HI-MAPF operates as a four-stage pipeline that iterates until all conflicts are resolved:

• S1 — Decentralized Planning: Each agent independently computes a path using A* with only map knowledge \(\mathcal{M}_i\) and its own start/goal. No inter-agent communication. 0 inter-agent IU.
• S2 — Centralized Conflict Detection: A coordinator scans all submitted trajectories for vertex and edge conflicts.
• S3 — Heuristic Control: For each conflict \(c = (t_j, \Delta_c, A_c)\), the controller selects a replanning agent via Fewest Future Collisions (FFC) heuristic and issues an alert \(\mathcal{A}(c) = (a_{c_k}, t_{j-r}, \Delta_c)\) — only the conflict location and time, a payload of a few bytes.
• S4 — Tiered Replanning: The selected agent replans using one of four escalating strategies, each consuming more information but applied only when lower tiers fail.

Repair Modes

The replanning stage itself is tiered. Lower-cost modes are tried first, so the more expensive coupled repairs remain available without becoming the default behavior.

Interactive Strategy Explorer

The interactive view below shows the same escalation policy visually. Each mode reveals only the amount of information needed for that repair tier to succeed.

Strategy Allocation & Effectiveness

Across all simulated benchmarks (8–128 agents), the vast majority of conflicts are resolved at the cheapest tier:

Hardware Validation

We validated HI-MAPF on a five-robot TurtleBot4 testbed laid out as a six-by-six grid. The goal was to see how much information each method had to reveal in order to finish the same coordination task.

Deployment Demo

The physical deployment complements the summary table with direct evidence from the testbed: robot layout, benchmark outcome snapshots, and a short hardware run video.

Information Unit Breakdown

Simulation Benchmarks

The simulation suite used four benchmark maps and compared HI-MAPF against learning-based and hybrid baselines across agent counts from 8 to 128. The chart selector summarizes the main trends without forcing the reader through a wall of raw numbers.

Publications

• Under Review

  HI-MAPF: Towards Resource-Efficient Multi-Agent Deployment with Minimal Inter-Agent Information Sharing

  Bharath Muppasani, Risha Patel, Biplav Srivastava, Vignesh Narayanan

BibTeX