HELSA: Hierarchical Reinforcement Learning with Spatiotemporal Abstraction for Large-Scale Multi-Agent Path Finding

The Multi-Agent Path Finding (MAPF) problem is a critical challenge in dynamic multi-robot systems. Recent studies have revealed that multi-agent reinforcement learning (MARL) is a promising approach to solving MAPF problems in a fully decentralized manner. However, as the size of the multi-robot system increases, sample inefficiency becomes a major impediment to learning-based methods. This paper presents a hierarchical reinforcement learning (HRL) framework for large-scale multi-agent path finding, featuring applying spatial and temporal abstraction to capture intermediate reward and thus encourage efficient exploration. Specifically, we introduce a meta controller that partitions the map into interconnected regions and optimizes agents' region-wise paths towards globally better solutions. Additionally, we design a lower-level controller that efficiently solves each sub-problem by incorporating heuristic guidance and an inter-agent communication mechanism with RL-based policies. Our empirical results on test instances of various scales demonstrate that our method outperforms existing approaches in terms of both success rate and makespan.

I. Introduction

In multi-robot systems, the ability to navigate effectively and efficiently is crucial. Such systems may entail thousands of automated mobile robots (AMRs) that have to find collision-free paths in a collaborative manner [1]. The Problem of multi-agent path finding is a challenging NP-hard problem [2] with numerous variants [3], and it has been of interest to researchers in the field of multi-agent systems ever since its inception.