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.
Phu Pham, Aniket Bera
# Crowd-Aware Multi-Agent Pathfinding With Boosted Curriculum Reinforcement Learning

###### Abstract

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. The current approaches for MAPF can be broadly categorized into two main categories: centralized and decentralized planning. Centralized planning suffers from the curse of dimensionality 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 crowd-aware decentralized approach to address this problem by leveraging reinforcement learning guided by a boosted curriculum-based training strategy. 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 58% measured in makespan and collision count, and up to 5% in success rate in comparison to previous methods.

## I Introduction

Multi-Agent Path Finding (MAPF) presents challenges with broad applications in autonomous warehouses, robotics, aerial swarms, and self-driving vehicles [1, 2, 3, 4, 5, 6]. The objective is to plan paths for multiple agents to navigate from start to goal positions in obstacle-laden environments. A critical constraint of such systems is to guarantee that agents can navigate concurrently without collisions. Two main categories of approaches are centralized and decentralized planning. Centralized planners [7, 8, 9, 10] aim to find optimal solutions. They are effective in small and sparse environments but face limitations in real-time performance and scalability in dense and complicated environments [11, 12]. These methods require complete a knowledge of the environment and full replanning when a change occurs, leading to exponential computation times with increased agents, obstacles, and world size. Recent studies [13, 10] have sought to discover real-time solutions. However, these solutions remain sub-optimal and still necessitate access to global information about the world.

On the contrary, decentralized methods [14, 15, 16, 17, 18, 1] seek to tackle these challenges by allowing each agent to acquire local policies. In these approaches, agents have the capacity to reactively plan paths within partially observable environments. Such methods prove beneficial in situations where agents lack comprehensive knowledge of the world, as is often the case in the domain of autonomous vehicles. Rather than pursuing an optimal solution for all agents, decentralized planners train local policies that rapidly generate sub-optimal solutions as a tradeoff between speed and solution quality. Given that agents make their decisions based on local information, decentralized approaches often face challenges in achieving effective global coordination among agents. In cluttered, dynamic environments characterized by congestion or rapid changes, agents may tend to prioritize their individual goals, potentially resulting in conflicts and inefficiencies that affect the overall system's performance.

To tackle these challenges, we introduce a novel approach that extends the capabilities of PRIMAL [14] and incorporates the presence of dense crowds into the policy learning process, guided by a boosted curriculum training strategy. Our proposed methodology, referred to as CRAMP, focuses on training intelligent agents to navigate through dense and dynamic environments efficiently. We formulate the MAPF problem as a sequential decision-making task and employ deep reinforcement learning techniques to teach agents to make optimal decisions while considering the presence of other agents and the constantly changing environment.

The key contribution of CRAMP lies in its curriculum-driven training strategy, which progressively exposes agents to increasingly complex scenarios. By starting with simple environments and gradually increasing the difficulty, our approach facilitates smoother learning convergence and improved generalization to real-world MAPF scenarios. Furthermore, we introduce crowd-awareness mechanisms that enable agents to adapt their policies dynamically based on

Fig. 1: _Path comparison between PRIMAL and CRAMP, our novel crowd-aware approach for multi-agent pathfinding problem in densely populated environments. The solution proposed by CRAMP is much shorter compared to PRIMAL._