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

arXiv: https://arxiv.org/abs/2309.10275 · HTML: https://mlsanity.com/paper/2309.10275/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 24 of its 49 references that are in the map.
- First posted on arXiv 19 Sep 2023.

## Builds on (most cited first, 24 of 24)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actor](https://mlsanity.com/paper/1801.01290/) (2018)
- [Asynchronous Methods for Deep Reinforcement Learning](https://mlsanity.com/paper/1602.01783/) (2016)
- [Overcoming Exploration in Reinforcement Learning with Demonstrations](https://mlsanity.com/paper/1709.10089/) (2017)
- [A Review of Cooperative Multi-Agent Deep Reinforcement Learning](https://mlsanity.com/paper/1908.03963/) (2019)
- [PRIMAL: Pathfinding via Reinforcement and Imitation Multi-Agent Learning](https://mlsanity.com/paper/1809.03531/) (2018)
- [Graph Neural Networks for Decentralized Multi-Robot Path Planning](https://mlsanity.com/paper/1912.06095/) (2019)
- [Demonstration-Guided Reinforcement Learning with Learned Skills](https://mlsanity.com/paper/2107.10253/) (2021)
- [EECBS: A Bounded-Suboptimal Search for Multi-Agent Path Finding](https://mlsanity.com/paper/2010.01367/) (2020)
- [PRIMAL2: Pathfinding via Reinforcement and Imitation Multi-Agent Learning -- Lifelong](https://mlsanity.com/paper/2010.08184/) (2020)
- [LaCAM: Search-Based Algorithm for Quick Multi-Agent Pathfinding](https://mlsanity.com/paper/2211.13432/) (2022)
- [Scalable Multi-Agent Reinforcement Learning through Intelligent Information Aggregation](https://mlsanity.com/paper/2211.02127/) (2022)
- [Distributed Heuristic Multi-Agent Path Finding with Communication](https://mlsanity.com/paper/2106.11365/) (2021)
- [Multi-Agent Path Finding with Prioritized Communication Learning](https://mlsanity.com/paper/2202.03634/) (2022)
- [GamePlan: Game-Theoretic Multi-Agent Planning with Human Drivers at Intersections, Roundabouts, and Merging](https://mlsanity.com/paper/2109.01896/) (2021)
- [On the Complexity of Multi-Agent Decision Making: From Learning in Games to Partial Monitoring](https://mlsanity.com/paper/2305.00684/) (2023)
- [Iterative Refinement for Real-Time Multi-Robot Path Planning](https://mlsanity.com/paper/2102.12331/) (2021)
- [Decentralized Control of Partially Observable Markov Decision Processes using Belief Space Macro-actions](https://mlsanity.com/paper/1502.06030/) (2015)
- [Improving Continuous-time Conflict Based Search](https://mlsanity.com/paper/2101.09723/) (2021)
- [Graph-based Decentralized Task Allocation for Multi-Robot Target Localization](https://mlsanity.com/paper/2309.08896/) (2023)
- [CL-MAPF: Multi-Agent Path Finding for Car-Like Robots with Kinematic and Spatiotemporal Constraints](https://mlsanity.com/paper/2011.00441/) (2020)
- [DroNeRF: Real-time Multi-agent Drone Pose Optimization for Computing Neural Radiance Fields](https://mlsanity.com/paper/2303.04322/) (2023)
- [Multi Agent Path Finding using Evolutionary Game Theory](https://mlsanity.com/paper/2212.02010/) (2022)
- [RAIST: Learning Risk Aware Traffic Interactions via Spatio-Temporal Graph Convolutional Networks](https://mlsanity.com/paper/2011.08722/) (2020)

## Abstract (arXiv)

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.