SDHN: Skewness-Driven Hypergraph Networks for Enhanced Localized Multi-Robot Coordination

Delin Zhao, Yanbo Shan, Chang Liu, Shenghang Lin, Yingxin Shou, Bin XuarXiv 2025 · DOI · arXiv

Introduction

In multi-agent reinforcement learning (MARL), effective coordination is essential for robots to achieve collective goals. Traditional methods typically model agent relationships using standard graphs, where edges connect exactly two robots. However, real-world scenarios—such as drones maintaining formation or robots navigating dense warehouse environments—frequently involve higher-order dependencies where three or more agents must synchronize simultaneously.

While hypergraphs allow for "edges" connecting any number of nodes, existing hypergraph-based approaches often suffer from two primary limitations:

  1. Arbitrary Structure: They may generate random or overly complex group connections that do not reflect efficient teamwork.
  2. Rigidity: Deterministic models often struggle to adapt to the noise and uncertainty of dynamic environments.

To address these challenges, we present the Skewness-Driven Hypergraph Network (SDHN), which prioritizes efficient, localized team-ups while maintaining global mission awareness.

Methodology: Skewness-Driven Coordination

SDHN operates within a Centralized Training with Decentralized Execution (CTDE) paradigm. The framework introduces a novel approach to modeling group interactions through three core components:

Stochastic Hyperedge Representation

Rather than using fixed connections, SDHN models hyperedges as Bernoulli distributions. By employing the Gumbel-Softmax trick, the model samples these connections during training while remaining differentiable. This stochasticity allows the system to handle environmental uncertainty more robustly than deterministic alternatives.

The Skewness Loss ($L_{Sk}$)

The primary innovation of SDHN is the Skewness Loss. Inspired by natural systems like hunting packs, this loss function mathematically biases the hypergraph generator toward a Small-Hyperedge Dominant (SHD) structure. This ensures the formation of many small, localized groups and very few massive, global ones, mimicking the way efficient teams naturally organize.

Architecture of the SDHN framework, highlighting the Skewness Loss and stochastic hypergraph generation.

Hypergraph Convolutional Network (HGCN)

The HGCN facilitates message passing between agents based on the generated hypergraph. This ensures that critical information reaches the appropriate "sub-teams" at the right time, optimizing local coordination without losing sight of the global objective.

Experimental Evaluation

The model was evaluated on two challenging multi-robot benchmarks:

  • Moving Agents in Formation (MAIF): Robots must maintain a specific geometric shape while navigating toward a target.
  • Robotic Warehouse (RWARE): A grid-world simulation where multiple robots coordinate to deliver items without colliding.

Testing involved varying robot counts (from 3 to 30) to assess the scalability of the coordination mechanism.

Key Results and Insights

SDHN demonstrates significant improvements in both efficiency and scalability compared to standard baselines like QMIX, MAPPO, and DICG.

Efficiency and Scalability

In the MAIF task, SDHN achieved a 23% reduction in makespan (total task completion time) compared to MAPPO. As the number of robots increased, standard methods often failed to complete tasks or showed significantly degraded performance. In contrast, SDHN maintained high performance and rapid convergence even with 20+ robots.

Average makespan comparison showing SDHN's superior performance and scalability as the number of robots increases.

The Importance of Local Priority

Ablation studies confirmed that simply using a hypergraph is insufficient. Without the skewness loss, generators create a "flat" distribution of connections that fails to capture the essential local clusters needed for complex maneuvers. By enforcing a skewed distribution, SDHN enables robots to focus on immediate partners while maintaining a loose eye on the overall mission—a strategy that proves both robust and efficient.

Conclusion

SDHN provides a powerful framework for multi-robot coordination by leveraging the natural efficiency of localized group interactions. By combining stochastic hyperedge representations with a novel skewness loss, the system achieves superior scalability and performance in complex environments. Future research will focus on transitioning these simulated successes to physical hardware, addressing real-world challenges such as communication latency and sensor noise.

Summary updated

Abstract

Multi-Agent Reinforcement Learning is widely used for multi-robot coordination, where simple graphs typically model pairwise interactions. However, such representations fail to capture higher-order collaborations, limiting effectiveness in complex tasks. While hypergraph-based approaches enhance cooperation, existing methods often generate arbitrary hypergraph structures and lack adaptability to environmental uncertainties. To address these challenges, we propose the Skewness-Driven Hypergraph Network (SDHN), which employs stochastic Bernoulli hyperedges to explicitly model higher-order multi-robot interactions. By introducing a skewness loss, SDHN promotes an efficient structure with Small-Hyperedge Dominant Hypergraph, allowing robots to prioritize localized synchronization while still adhering to the overall information, similar to human coordination. Extensive experiments on Moving Agents in Formation and Robotic Warehouse tasks validate SDHN's effectiveness, demonstrating superior performance over state-of-the-art baselines.
BibTeX
@misc{zhao2025sdhn,
  author = {Delin Zhao and Yanbo Shan and Chang Liu and Shenghang Lin and Yingxin Shou and Bin Xu},
  title = {{SDHN: Skewness-Driven Hypergraph Networks for Enhanced Localized Multi-Robot Coordination}},
  year = {2025},
  eprint = {2504.06684},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2504.06684},
}
Figure