MAPF-GPT: Imitation Learning for Multi-Agent Pathfinding at Scale
This addresses the NP-hard MAPF problem for applications like automated warehouses and transportation systems, offering a novel learning-based approach that is incremental in its method.
The paper tackles the multi-agent pathfinding (MAPF) problem by developing MAPF-GPT, a foundation model based on imitation learning and transformers that generates actions without heuristics or communication. It demonstrates zero-shot learning, outperforms current learnable solvers on diverse instances, and is computationally efficient during inference.
Multi-agent pathfinding (MAPF) is a problem that generally requires finding collision-free paths for multiple agents in a shared environment. Solving MAPF optimally, even under restrictive assumptions, is NP-hard, yet efficient solutions for this problem are critical for numerous applications, such as automated warehouses and transportation systems. Recently, learning-based approaches to MAPF have gained attention, particularly those leveraging deep reinforcement learning. Typically, such learning-based MAPF solvers are augmented with additional components like single-agent planning or communication. Orthogonally, in this work we rely solely on imitation learning that leverages a large dataset of expert MAPF solutions and transformer-based neural network to create a foundation model for MAPF called MAPF-GPT. The latter is capable of generating actions without additional heuristics or communication. MAPF-GPT demonstrates zero-shot learning abilities when solving the MAPF problems that are not present in the training dataset. We show that MAPF-GPT notably outperforms the current best-performing learnable MAPF solvers on a diverse range of problem instances and is computationally efficient during inference.