Optimizing Crowd-Aware Multi-Agent Path Finding through Local Communication with Graph Neural Networks

Multi-Agent Path Finding (MAPF) in crowded environments presents a challenging problem in motion planning, aiming to find collision-free paths for all agents in the system. MAPF finds a wide range of applications in various domains, including aerial swarms, autonomous warehouse robotics, and self-driving vehicles. Current approaches to MAPF generally fall into two main categories: centralized and decentralized planning. Centralized planning suffers from the curse of dimensionality when the number of agents or states increases and thus does not scale well in large and complex environments. On the other hand, decentralized planning enables agents to engage in real-time path planning within a partially observable environment, demonstrating implicit coordination. However, they suffer from slow convergence and performance degradation in dense environments. In this paper, we introduce CRAMP, a novel crowd-aware decentralized reinforcement learning approach to address this problem by enabling efficient local communication among agents via Graph Neural Networks (GNNs), facilitating situational awareness and decision-making capabilities in congested environments. We test CRAMP on simulated environments and demonstrate that our method outperforms the state-of-the-art decentralized methods for MAPF on various metrics. CRAMP improves the solution quality up to 59% measured in makespan and collision count, and up to 35% improvement in success rate in comparison to previous methods.

Authors

• Phu Pham
• Aniket Bera

Keywords

• Measurement
• Training
• Technological innovation
• Robot kinematics
• Reinforcement learning
• System recovery
• Path planning
• Graph neural networks
• Planning
• Safety
• Pathfinding
• Local Communication
• Multi-Agent Path Finding
• Collision
• Simulation Environment
• Autonomous Vehicles
• Number Of Agents
• Solution Quality
• Curse Of Dimensionality
• Agent System
• Makespan
• Dense Environments
• Improve Success Rates
• Field Of View
• Local Information
• Dynamic Environment
• Local Policy
• Multi-agent Systems
• Multi-agent Reinforcement Learning
• Reinforcement Learning Techniques
• Crowd Density
• Deadlock
• Deep Reinforcement Learning
• Imitation Learning
• Curriculum Level
• Binary Cross-entropy Loss
• Deep Reinforcement Learning Techniques
• Policy Network