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.
본 연구는 다중에이전트 스케줄링 및 경로탐색 문제를 풀기 위한 새로운 기법을 제안한다. 다중에이전트 스케줄링 및 경로탐색 문제는 상위 수준에서 다중에이전트의 작업 목표들을 스케줄링 하는 과정과 하위 수준에서 스케줄링을 따르는 경로를 탐색하는 과정으로 구성 된다. 우리의 알고리즘은 상위 수준 스케줄링 과정에 그래프 인공 신경망을 적용하고 하위 수준 경로 탐색 과정에 스케줄을 기반으로 경로를 탐색하는 솔버를 활용한다. 이러한 접근 방식을 통해 우리가 제안하는 방법론이 이전의 state-of-the-art 알고리즘보다 다중에이전트 스케줄링 및 경로탐색 문제를 보다 잘 해결함을 입증한다.
