# Where Paths Collide: A Comprehensive Survey of Classic and Learning-Based Multi-Agent Pathfinding arXiv: https://arxiv.org/abs/2505.19219 ยท HTML: https://mlsanity.com/paper/2505.19219/ ## Key facts - Cited by 3 papers in the map (data through 14 Oct 2026). - Placed in General LLM agent frameworks and benchmarks, one of 16 directions in LLM agents and tool use. - Builds on 27 of its 207 references that are in the map. - First posted on arXiv 25 May 2025. ## Placed in - LLM agents and tool use / [General LLM agent frameworks and benchmarks](https://mlsanity.com/agents/general-llm-agent-frameworks-and-benchmarks/) ## Builds on (most cited first, 27 of 27) - [Lifelong Multi-Agent Path Finding for Online Pickup and Delivery Tasks](https://mlsanity.com/paper/1705.10868/) (2017) - [Flatland-RL : Multi-Agent Reinforcement Learning on Trains](https://mlsanity.com/paper/2012.05893/) (2020) - [Perceive, Reflect, and Plan: Designing LLM Agent for Goal-Directed City Navigation without Instructions](https://mlsanity.com/paper/2408.04168/) (2024) - [Why Solving Multi-agent Path Finding with Large Language Model has not Succeeded Yet](https://mlsanity.com/paper/2401.03630/) (2024) - [POGEMA: A Benchmark Platform for Cooperative Multi-Agent Pathfinding](https://mlsanity.com/paper/2407.14931/) (2024) - [Improving LaCAM for Scalable Eventually Optimal Multi-Agent Pathfinding](https://mlsanity.com/paper/2305.03632/) (2023) - [Multi-Agent Path Finding in Continuous Spaces with Projected Diffusion Models](https://mlsanity.com/paper/2412.17993/) (2024) - [CTRMs: Learning to Construct Cooperative Timed Roadmaps for Multi-agent Path Planning in Continuous Spaces](https://mlsanity.com/paper/2201.09467/) (2022) - [Ensembling Prioritized Hybrid Policies for Multi-agent Pathfinding](https://mlsanity.com/paper/2403.07559/) (2024) - [LNS2+RL: Combining Multi-Agent Reinforcement Learning with Large Neighborhood Search in Multi-Agent Path Finding](https://mlsanity.com/paper/2405.17794/) (2024) - [Physics-informed Neural Mapping and Motion Planning in Unknown Environments](https://mlsanity.com/paper/2410.09883/) (2024) - [MAPFAST: A Deep Algorithm Selector for Multi Agent Path Finding using Shortest Path Embeddings](https://mlsanity.com/paper/2102.12461/) (2021) - [Offline Time-Independent Multi-Agent Path Planning](https://mlsanity.com/paper/2105.07132/) (2021) - [Social Behavior as a Key to Learning-based Multi-Agent Pathfinding Dilemmas](https://mlsanity.com/paper/2408.03063/) (2024) - [Large-Scale Multirobot Coverage Path Planning on Grids With Path Deconfliction](https://mlsanity.com/paper/2411.01707/) (2024) - [winPIBT: Extended Prioritized Algorithm for Iterative Multi-agent Path Finding](https://mlsanity.com/paper/1905.10149/) (2019) - [Automatic Algorithm Selection In Multi-agent Pathfinding](https://mlsanity.com/paper/1906.03992/) (2019) - [Multi Agent Path Finding using Evolutionary Game Theory](https://mlsanity.com/paper/2212.02010/) (2022) - [Confidence-Based Curriculum Learning for Multi-Agent Path Finding](https://mlsanity.com/paper/2401.05860/) (2024) - [Multi-agent navigation based on deep reinforcement learning and traditional pathfinding algorithm](https://mlsanity.com/paper/2012.09134/) (2020) - [Reevaluation of Large Neighborhood Search for MAPF: Findings and Opportunities](https://mlsanity.com/paper/2407.09451/) (2024) - [Multi-Agent Target Assignment and Path Finding for Intelligent Warehouse: A Cooperative Multi-Agent Deep Reinforcement Learning Perspective](https://mlsanity.com/paper/2408.13750/) (2024) - [Multi-agent Path Finding with Continuous Time Viewed Through Satisfiability Modulo Theories (SMT)](https://mlsanity.com/paper/1903.09820/) (2019) - [On the Tour Towards DPLL(MAPF) and Beyond](https://mlsanity.com/paper/1907.07631/) (2019) - [Scalable Mechanism Design for Multi-Agent Path Finding](https://mlsanity.com/paper/2401.17044/) (2024) - [LLMDR: LLM-Driven Deadlock Detection and Resolution in Multi-Agent Pathfinding](https://mlsanity.com/paper/2503.00717/) (2025) - [Formalization of Optimality Conditions for Smooth Constrained Optimization Problems](https://mlsanity.com/paper/2503.18821/) (2025) ## Built on by (most cited first, 3 of 3) - [Safe and Interpretable Multimodal Path Planning for Multi-Agent Cooperation](https://mlsanity.com/paper/2602.19304/) (2026) - [GRAND: Guidance, Rebalancing, and Assignment for Networked Dispatch in Multi-Agent Path Finding](https://mlsanity.com/paper/2512.03194/) (2025) - [Plan First, Diffuse Later: Extrinsic Graph Guidance for Long-Horizon Diffusion Planning](https://mlsanity.com/paper/2605.16863/) (2026) ## Abstract (arXiv) Multi-Agent Path Finding (MAPF) is a fundamental problem in artificial intelligence and robotics, requiring the computation of collision-free paths for multiple agents navigating from their start locations to designated goals. As autonomous systems become increasingly prevalent in warehouses, urban transportation, and other complex environments, MAPF has evolved from a theoretical challenge to a critical enabler of real-world multi-robot coordination. This comprehensive survey bridges the long-standing divide between classical algorithmic approaches and emerging learning-based methods in MAPF research. We present a unified framework that encompasses search-based methods (including Conflict-Based Search, Priority-Based Search, and Large Neighborhood Search), compilation-based approaches (SAT, SMT, CSP, ASP, and MIP formulations), and data-driven techniques (reinforcement learning, supervised learning, and hybrid strategies). Through systematic analysis of experimental practices across 200+ papers, we uncover significant disparities in evaluation methodologies, with classical methods typically tested on larger-scale instances (up to 200 by 200 grids with 1000+ agents) compared to learning-based approaches (predominantly 10-100 agents). We provide a comprehensive taxonomy of evaluation metrics, environment types, and baseline selections, highlighting the need for standardized benchmarking protocols. Finally, we outline promising future directions including mixed-motive MAPF with game-theoretic considerations, language-grounded planning with large language models, and neural solver architectures that combine the rigor of classical methods with the flexibility of deep learning. This survey serves as both a comprehensive reference for researchers and a practical guide for deploying MAPF solutions in increasingly complex real-world applications.