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.
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: