Pairwise is Not Enough: Hypergraph Neural Networks for Multi-Agent Pathfinding

AI summary

Overview

Research area: Multi-agent reinforcement/imitation learning, combinatorial search (Multi-Agent Path Finding), and graph representation learning — specifically hypergraph neural networks.

Technical level: Advanced. Understanding the methodology requires familiarity with graph/hypergraph neural networks, attention mechanisms, imitation learning, and MAPF terminology (sum-of-costs, collision shielding, PIBT, Shapley values).

Scope: This paper proposes HMAGAT, an attentional hypergraph neural network policy for MAPF that replaces pairwise GNN message passing with group-level (hyperedge) interactions, and demonstrates state-of-the-art learning-based MAPF performance with a 1M-parameter model trained on 21K instances.

What This Paper Is About

Multi-Agent Path Finding (MAPF) asks a team of agents on a four-connected grid to reach distinct goals without vertex or edge collisions, and solving it optimally is NP-hard. Existing learning-based solvers model agent interactions pairwise, using graph neural networks (GNNs) or transformers, even though MAPF is fundamentally a group problem where optimality generally requires reasoning over the full joint state of all agents. The paper's goal is to remove this representational bottleneck by explicitly modelling higher-order group interactions with directed hypergraphs, and to show that such an inductive bias matters more than model size or training data volume.

Key Contributions

1. HMAGAT (Hypergraph Multi-Agent Attention Network): A novel imitation learning framework for MAPF built on attentional message passing over directed hypergraphs, with singleton-head, multi-node-tail hyperedges and hyperedge features. It builds on MAGAT but replaces GNN layers with HGNN layers, and also adopts stacking three GNN layers and position-based edge features from follow-up MAGAT work.

2. Hypergraph generation strategies: Several methods for dynamically constructing directed hypergraphs from agent configurations, including Lloyd (Voronoi/Lloyd's algorithm) hypergraphs, k-means hypergraphs (diffused colours plus k-means clustering and a "soft boundary" operation, reducing complexity from O(|V|³) to O(k|V|)), and shortest-distance-based hypergraphs based on whether one agent can encounter another while visiting a third.

3. Empirical state-of-the-art results: HMAGAT beats the previous SoTA learning model while using only ~1.2% of the parameters and ~1% of the training data — concretely, a 1M-parameter model trained on 21K instances outperforming the 85M-parameter MAPF-GPT (also described in the conclusion as an 85× larger model trained on 100× more data).

4. Analysis of attention dilution and group interactions: Formal and empirical investigation of why pairwise attention fails in dense settings, including an informal proof that GNNs suffer attention dilution, an informal proof that the HGNN architecture mitigates it, and hand-crafted scenario analyses using attention score variation and Shapley values.

Main Findings

• HMAGAT is state of the art among learning-based MAPF solvers: It consistently obtains higher-quality solutions than MAGAT, MAPF-GPT (2M), MAPF-GPT (6M), and MAPF-GPT-DDG (2M), and remains competitive with MAPF-GPT (85M) while being significantly faster.

• Highest-density performance gap is large: On the highest agent density Dense Warehouse scenario, HMAGAT achieves a 75+% success rate while other methods achieve <11%. In the Maze maps HMAGAT beats MAPF-GPT (85M) on solution quality; MAPF-GPT (85M) outperforms HMAGAT in the Room and Warehouse maps except in that highest-density Dense Warehouse case.

• Scalability: MAPF-GPT (85M) fails to scale to the large ost003d map, where HMAGAT obtains solutions close to lacam3's quality.

• Colouring strategy comparison: k-means and Lloyd's HMAGAT both have consistently high solution quality, with k-means being faster, especially on larger maps.

• HGNN beats GNN in a stripped-down comparison (Table 1), where the HGNN model is HMAGAT with only the GNN-to-HGNN replacement and GNN is MAGAT. Success rates went from GNN to HGNN: 72.7% → 75.8% (Dense Maze), 2.3% → 39.8% (Dense Warehouse), 66.4% → 75.0% (Dense Room), 100.0% → 100.0% (ost003d), 100.0% → 100.0% (Paris). Relative SoC improved from 2.07 ± 0.09 → 1.79 ± 0.09 (Dense Maze), 2.12 ± 0.10 → 1.78 ± 0.08 (Dense Warehouse), 2.63 ± 0.07 → 2.35 ± 0.06 (Dense Room), 1.06 ± 0.00 → 1.05 ± 0.00 (ost003d), and 1.03 ± 0.00 → 1.02 ± 0.00 (Paris).

• Attention dilution confirmed empirically: In the first-layer attention scores on sampled Dense Warehouse and Dense Maze instances with 128 agents, the GNN model concentrates scores in the higher-middle range, leaving very few agents receiving high attention, while the HGNN model keeps more agents in the highest attention bin.

• Attention is more stable to irrelevant agents (Scenario 1, Table 2): Coefficient of variation of first-layer attention scores for agent 0 as agents are added to an irrelevant group — GNN: 29.4%, 20.0%, 14.9%, 39.2% across groups 0–3; HGNN: 6.0%, 4.3%, 7.4%, 14.7%. The ratios of GNN to HGNN variation are 4.94, 4.66, 2.01, and 2.66.

• HGNN captures group interaction where GNN cannot (Scenario 2, Table 3): Percentage Shapley values for agents 1–4 with respect to agent 0 — GNN assigns 15.0%, 60.3%, 13.1%, 11.6%, with agent 3 having only +13% more influence than agent 4; HGNN assigns 19.0%, 59.6%, 19.3%, 2.1%, with agent 3 having +802% more influence than agent 4.

• Every component contributes (ablation): Starting from MAGAT and incrementally adding components up to HMAGAT improves both success rate and solution quality, except the RL-based temperature sampling, which trades off success rate for improved solution quality.

Methodology in Plain English

The researchers treat MAPF as an imitation learning problem. They generate expert trajectories with lacam3, a state-of-the-art anytime MAPF solver, over 21K instances (20% with randomly placed obstacles, 80% maze-like), with map sizes from 17×17 to 21×21 and 16, 24, or 32 agents; for comparison, MAPF-GPT used 3.75M instances.

Each agent observes a 4-channel local tensor centred on its position of shape 4 × (2R^obs+1) × (2R^obs+1), containing an obstacle map, an agent map, a projection of the goal direction, and a normalised cost-to-go map; the paper uses R^obs = 5. A CNN encodes this observation into a node feature. Instead of passing messages only between pairs of agents, the model groups agents into directed hyperedges with a single head agent and multiple tail agents, and messages flow from tail nodes to hyperedges to head nodes through attention weights. Hyperedge features are three-dimensional vectors of relative position and Manhattan distance to the hyperedge centre. The communication radius is R^comm = 7.

Hypergraphs are constructed dynamically using colouring strategies: a Lloyd/Voronoi-based partition, or a faster k-means variant that diffuses colours from randomly sampled vertices and clusters the resulting vectors, in both cases with a "soft boundary" operation that allows vertices to hold multiple colours so that agents are not artificially separated; half of the least populous colours are discarded and their regions reassigned to neighbouring colours. A third, non-colouring approach builds tails from shortest-path distance relationships between agents.

Training uses cross-entropy loss for 200 epochs (~100 hours on an NVIDIA L40S GPU, AdamW optimiser). To handle distributional shift, an on-demand dataset aggregation scheme collects new trajectories where the model fails; once 80% success rate is reached, the system checks whether the model's solution exceeds δ_buf = 1.2 times the expert length and, if so, extracts instances every h = 16 steps and solves them with lacam3 using [1, 2, 10] s timeouts, capped at 30 quality-improvement expert calls per online expert phase. A post-training phase follows MAPF-GPT-DDG: all 500 instances, a 1:3 ratio of quality-improvement to pre-collected instances, run for 20 epochs (~30 hours on an L40S).

Finally, because GNNs are known to be miscalibrated with low confidence in predictions, an RL module dynamically sets a softmax temperature τ between 0.5 and 1.0 per agent based on local observability and action log-odds, trained with PPO for 50 epochs (~3 hours) with clip ratio 0.2, discount factor 0.99, GAE λ of 0.95, learning rate 3×10⁻⁴, and batch size 64.

Evaluation compares against MAGAT, MAPF-GPT (2M, 6M, 85M), and MAPF-GPT-DDG (2M), using PIBT-based collision shielding for all methods. Metrics are success rate, average relative sum-of-costs against lacam3 with a 30 s budget, and average runtime per map, averaged over 128 instances with 95% confidence intervals. Maps used are Sparse Maze and Empty Room (256 step limit, 60 s time limit), Dense Maze, Dense Room and Dense Warehouse (512 step limit, 60 s), and ost003d (1024 step limit, 90 s).

Why This Matters

Impact on research: The paper argues that appropriate inductive biases — explicit group interaction modelling — can be more critical than training data size or parameter count for multi-agent problems, since HMAGAT matches or beats a model 85× larger trained on 100× more data. It also provides a mechanistic explanation (attention dilution, failure to represent group effects) for why pairwise GNN attention degrades in dense settings, and shows that hypergraphs are viable beyond the modest team sizes (~10¹ agents) studied in prior HGNN multi-agent work. The paper positions group interaction modelling as previously unexplored in the MAPF solver landscape.

Real-world applications named in the paper:

• Warehouse automation (including robotic warehouses)
• Autonomous driving
• Traffic management
• Manufacturing process control

Industry relevance: MAPF is described as tailored to industrial setups such as warehouse automation, and the paper's emphasis on small model size (1M parameters) and fast runtime matters for deployment, since learning-based solvers are adopted specifically to alleviate the online computational burden of optimal search. The staged training relies on cheaply generated demonstration data, which the authors note is inexpensive with modern MAPF solvers.

Future Directions

• Scaling hypergraph methods to larger and denser settings: MAPF-GPT (85M) fails to scale to ost003d while HMAGAT remains close to lacam3's quality, raising the question of how far HGNN-based policies can scale in map size and agent count.

• Closing the remaining gap on Room and Warehouse maps: MAPF-GPT (85M) still outperforms HMAGAT on Room and Warehouse maps except at the highest density in Dense Warehouse, so the conditions under which pairwise or transformer representations retain an advantage remain open.

• Extending hypergraph inductive biases to other highly-coupled multi-agent problems: The authors explicitly motivate future research on hypergraph-based methods for challenging multi-agent problems with highly coupled interactions.

• Combining inductive biases with model scaling: The paper frames better inductive biases as a complementary strategy to training larger models, suggesting that combining both is an untested direction.

• Hypergraph construction and calibration: The paper offers three generation strategies (Lloyd, k-means, shortest-distance) and notes that HGNNs are likely to inherit the miscalibration of GNNs, which required a learned temperature sampler; improved or adaptive hypergraph generation and calibration remain open areas.

Target Audience

This paper is most valuable to researchers and graduate students working on multi-agent systems, learning-based MAPF, and graph/hypergraph representation learning who want to understand when pairwise message passing breaks down and how higher-order structures fix it. It is also relevant to practitioners in warehouse automation, autonomous driving, traffic management, and manufacturing who need strong coordination quality at low inference cost and small model size. Readers need a solid background in neural message passing and attention to follow the architecture and the formal analysis, though the empirical sections (success rates, Rel. SoC, and the hand-crafted scenario studies) are accessible to anyone familiar with MAPF evaluation.

Authors’ abstract

Multi-Agent Path Finding (MAPF) is a representative multi-agent coordination problem, where multiple agents are required to navigate to their respective goals without collisions. Solving MAPF optimally is known to be NP-hard, leading to the adoption of learning-based approaches to alleviate the online computational burden. Prevailing approaches, such as Graph Neural Networks (GNNs), are typically constrained to pairwise message passing between agents. However, this limitation leads to suboptimal behaviours and critical issues, such as attention dilution, particularly in dense environments where group (i.e. beyond just two agents) coordination is most critical. Despite the importance of such higher-order interactions, existing approaches have not been able to fully explore them. To address this representational bottleneck, we introduce HMAGAT (Hypergraph Multi-Agent Attention Network), a novel architecture that leverages attentional mechanisms over directed hypergraphs to explicitly capture group dynamics. Empirically, HMAGAT establishes a new state-of-the-art among learning-based MAPF solvers: e.g., despite having just 1M parameters and being trained on 100$\times$ less data, it outperforms the current SoTA 85M parameter model. Through detailed analysis of HMAGAT's attention values, we demonstrate how hypergraph representations mitigate the attention dilution inherent in GNNs and capture complex interactions where pairwise methods fail. Our results illustrate that appropriate inductive biases are often more critical than the training data size or sheer parameter count for multi-agent problems.