Multi-Agent Reinforcement Learning With Spatial Structure Awareness for Topological Map-Based Path-Finding

Abstract

Efficient Multi-Agent Path Finding (MAPF) is pivotal for warehouse logistics. While existing learning-based methods primarily rely on computationally intensive grid-based representations, topological maps offer a more flexible and scalable alternative - though this approach remains understudied. To address this gap, we propose a novel Multi-Agent Reinforcement Learning (MARL) framework for topological MAPF with three key innovations: (1) a graph-structured POMDP formulation utilizing our Breadth-First Neighbor-Limited Search (BFNLS) algorithm to define scalable observation/action spaces while maintaining fixed dimension; (2) a Graph Structure Awareness (GSA) model that combines spectral ( eigenvalue-based) and spatial (graph convolutional network-based) analysis to integrate local subgraph features with global topological importance metrics; and (3) a cooperative MARL architecture employing Value Decomposition Networks (VDN) to explicitly model agent dependencies through graph-aware credit assignment. Simulation results show our method achieves superior success rates compared to baseline methods and planning efficiency than search-based methods, and the real-robot experiments show the effectiveness in a physical setting.