HI-MAPF — Bharath Muppasani

Full Results Page Demo Video Results BibTeX

2–510×IU reduction vs. baselines

5TurtleBot4 robots

4Benchmark maps

199 IUHardware total (vs 42,413)

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.

I-MAPF: Information-Centric Formulation

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

\mathcal{I}_i(t) = \bigl(\mathcal{M}_i,\;\mathcal{S}_i,\;\mathcal{O}_j,\;\mathcal{E}_{ij}(t)\bigr)

$\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)$.

MAPF coordination paradigms and four-stage pipeline — Left: Example MAPF problem with vertex/edge collisions. Top right: Inter-agent information available under centralized, distributed, and decentralized paradigms. Bottom right: General four-stage MAPF pipeline — path planning, collision detection, resolution, and replanning.

Information Units (IU)

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

Definition (Information Unit): An IU is one atomic datum of the form $(v, s, t, e) \in V \times S \times T \times E$, where $v$ is a grid cell, $s$ is its state (free, obstacle, occupied, reserved), $t$ is a timestep, and $e$ is a scalar message entry. Any sensing output or transmitted message is modeled as a finite multiset of IUs.

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

Core principle: Minimize sensing, communication, and computation resources per agent. Planning is decentralized by default; information sharing is conflict-driven and tiered.

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.

Tiered Replanning Strategies

S4.1 — Yield

Local Coordination

Agent performs a short-horizon yield: moves to a nearby parking cell, waits while protected agents pass, then resumes.

Cost: 1 IU

S4.2 — Static Replan

Bounded Constraint

Agent replans a bounded path segment treating conflict cells $\Delta_c$ as forbidden static obstacles. Uses A*.

Cost: $|\Delta c|$ IUs

S4.3 — Dynamic Replan

Time-Indexed Avoidance

Agent receives short sub-paths of conflicting agents as time-varying obstacles over horizon $r$. Uses RL policy.

Cost: $r$ IUs

S4.4 — Joint A*

Coupled Replanning

A tightly coupled subset $A_c^J$ is replanned jointly over a bounded window. Maximum IU, used sparingly.

Cost: $|A_c^J| \cdot r$ IUs

Protected agent Replanning agent Conflict region Parking/bay

Strategy Allocation & Effectiveness

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

S4.1 Yield

91–99%

usage share

91–99% success

S4.2 Static

1–8%

usage share

99–100% success

S4.3 Dynamic

<0.5%

usage share

11% success

S4.4 Joint A*

<0.5%

usage share

72–100% success

▸ Per-Map Strategy Breakdown

Map	Yield	Static	Dynamic	Joint
random-32	91.8% (91.4% sr)	7.6% (99.1%)	0.3% (11.1%)	0.3% (71.7%)
random-64	97.9% (97.9% sr)	2.0% (98.7%)	0.0%	0.0%
den312d	98.1% (98.0% sr)	1.9% (100%)	0.0%	0.0%
warehouse	99.2% (99.2% sr)	0.8% (100%)	N/A	N/A

Results

Hardware Validation (5 TurtleBot4)

All five algorithms achieve 100% success rate across five problem instances. HI-MAPF achieves the lowest average makespan (12.2) and the lowest total IU (199), compared to 42,413 IU for SCRIMP (213×).

Algorithm	Success Rate	Avg Makespan	Total IU	IU Multiplier	Exec Time (s)
HI-MAPF	100%	12.2	199	1.0×	181.5
MAPF-GPT-2M	100%	13.6	588	3.0×	176.2
DCC	100%	19.4	596	3.0×	235.0
EPH	100%	21.8	623	3.1×	234.9
SCRIMP	100%	16.4	42,413	213.0×	211.2

Physical deployment: 5 TurtleBot4 robots in a 6×6 grid using ROS 2

Multi-axis comparison of hardware deployment results

Multi-axis comparison: HI-MAPF achieves the most balanced profile across makespan, IU, and communication frequency

Hardware demo: robots communicate only via lightweight alert protocol.

Information Unit Breakdown

HI-MAPF

IU dominated by initial map broadcast (71%), with remaining IU from conflict-triggered constraints during replanning. No onboard perception required.

199 IU 1.0×

SCRIMP

99% of IU from 512-dim inter-agent messages transmitted via transformer-based communication module at every timestep.

42,413 IU 213×

DCC & EPH

IU dominated by per-timestep position broadcasts and action transmissions (49–53%), with FOV sensing contributing ~20–22%.

596–623 IU 3.0–3.1×

MAPF-GPT-2M

Competitive makespan (13.6) but requires 11×11 FOV observations (~41% of IU) compared to 3×3 in SCRIMP.

588 IU 3.0×

Simulation Benchmarks

We evaluated HI-MAPF on four standard MAPF benchmarks against CBS, SCRIMP, DCC, MAPF-GPT-2M, and EPH across 8–128 agents.

HI-MAPF MAPF-GPT-2M DCC EPH SCRIMP

Quantitative results across agent densities. View full per-map results →

Publications

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

Bharath Muppasani, Risha Patel, Biplav Srivastava, Vignesh Narayanan

BibTeX

@inproceedings{muppasani2025himapf, title={HI-MAPF: Towards Resource-Efficient Multi-Agent Deployment}, author={Muppasani, Bharath and Patel, Risha and Srivastava, Biplav and Narayanan, Vignesh}, year={2025}, note={Under Review} }