NLNS-MASPF for solving Multi-Agent scheduling and Path-Finding

Abstract

In this work, we propose a novel method, NLNS-MASPF, to solve the Multi-Agent Scheduling and Pathfinding (MASPF) problem. The problem exhibits a bi-level structure, consisting of High-level Scheduling and Low-level Pathfinding. Our method applies a graph neural network in the high-level scheduling process and utilizes a MAPF solver with a schedule segmenting technique in the low-level pathfinding process. Through these approaches, NLNS-MASPF has experimentally demonstrated superior performance compared to the previous state-of-the-art MASPF algorithm, LNS-PBS, in solving the MASPF problem.