HiRiSC: hierarchical risk-shaped coordination with sparse hypergraph communication for congested multi-agent path finding
- 23 July 2026
- journal article
- Published by IOP Publishing in Measurement Science and Technology
- Vol. 37 (29) , 296304
Abstract
Decentralised multi-agent path finding in congested and obstacle-rich environments remains difficult because agents must coordinate under partial observation, limited bandwidth, and bounded per-step computation. Existing decentralised solvers often address communication efficiency, congestion handling, and execution safety separately, which can reduce their reliability when dense local interactions amplify non-stationarity and make distance-based neighbourhoods poorly aligned with coordination relevance. This paper proposes hierarchical risk shaped structured communication (HiRiSC), a bandwidth-aware decentralised framework that couples hypergraph-sparse communication with CFL-clamped congestion risk shaping. STAGE-Comm constructs feature-space coalitions, converts them into second-order hypergraph priors, and learns a discrete sparse adjacency through straight-through Gumbel–Softmax. Direction-sensitive gating further modulates asymmetric information flow according to relative spatial relations, reducing redundant message updates while preserving task-relevant interactions within the feasible visibility mask. VPG-HCHD builds a congestion look-ahead signal from density, flow coherence, and goal-directed progress. A CFL-clamped finite-volume diagnostic limits non-physical density transport in the predicted density field and provides an interpretable reliability indicator for risk-aware value shaping. Residual conflicts are handled by a bounded execution cascade that combines a constant-time shield, priority inheritance with backtracking-based local arbitration, and short-horizon TE-A* repair under reservation constraints. Experiments on random maps and structured den312d and warehouse benchmarks show that HiRiSC achieves 95%–100% success in the tested dense settings, reduces communication overhead and runtime relative to the corresponding baselines, and maintains stable performance under bandwidth limits, packet loss up to 20%, and effective-speed and sensing heterogeneity. Ablation results further indicate that structured sparse communication, congestion-aware risk shaping, and execution-time arbitration provide complementary contributions.Keywords
Funding Information
- Tianshan Youth Top Talents Program of Xinjiang Uygur Autonomous Region (2024TSYCCX0009)
- Key R&D Program of Xinjiang Uygur Autonomous Region (2022B01050-2)
This publication has 24 references indexed in Scilit:
- CBS-Budget (CBSB): A complete and bounded suboptimal search for multi-agent path findingArtificial Intelligence, 2025
- Multi-agent cooperative area coverage: A two-stage planning approach based on reinforcement learningInformation Sciences, 2024
- HiSOMA: A hierarchical multi-agent model integrating self-organizing neural networks with multi-agent deep reinforcement learningExpert Systems with Applications, 2024
- Learning team-based navigation: a review of deep reinforcement learning techniques for multi-agent pathfindingArtificial Intelligence Review, 2024
- MACNS: A generic graph neural network integrated deep reinforcement learning based multi-agent collaborative navigation system for dynamic trajectory planningInformation Fusion, 2024
- A review of graph-based multi-agent pathfinding solvers: From classical to beyond classicalKnowledge-Based Systems, 2023
- Learning structured communication for multi-agent reinforcement learningAutonomous Agents and Multi-Agent Systems, 2022
- PRIMAL$_2$: Pathfinding Via Reinforcement and Imitation Multi-Agent Learning - LifelongIEEE Robotics and Automation Letters, 2021
- Conflict-based search for optimal multi-agent pathfindingArtificial Intelligence, 2015
- Social force model for pedestrian dynamicsPhysical Review E, 1995