Where Paths Collide: A Comprehensive Survey of Classic and Learning-Based Multi-Agent Pathfinding

• URL: http://arxiv.org/abs/2505.19219v2
• Date: Thu, 31 Jul 2025 14:16:44 GMT
• Title: Where Paths Collide: A Comprehensive Survey of Classic and Learning-Based Multi-Agent Pathfinding
• Authors: Shiyue Wang, Haozheng Xu, Yuhan Zhang, Jingran Lin, Changhong Lu, Xiangfeng Wang, Wenhao Li,
• Abstract summary: Multi-Agent Path Finding (MAPF) is a fundamental problem in artificial intelligence and robotics.<n>This survey bridges the long-standing divide between classical algorithmic approaches and emerging learning-based methods in MAPF research.
• Score: 19.93293239540926
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• Deep Research Agents: A Systematic Examination And Roadmap [79.04813794804377]
  Deep Research (DR) agents are designed to tackle complex, multi-turn informational research tasks.<n>In this paper, we conduct a detailed analysis of the foundational technologies and architectural components that constitute DR agents.
  arXiv  Detail & Related papers  (2025-06-22T16:52:48Z)
• Anomaly Detection and Generation with Diffusion Models: A Survey [51.61574868316922]
  Anomaly detection (AD) plays a pivotal role across diverse domains, including cybersecurity, finance, healthcare, and industrial manufacturing.<n>Recent advancements in deep learning, specifically diffusion models (DMs), have sparked significant interest.<n>This survey aims to guide researchers and practitioners in leveraging DMs for innovative AD solutions across diverse applications.
  arXiv  Detail & Related papers  (2025-06-11T03:29:18Z)
• From LLM Reasoning to Autonomous AI Agents: A Comprehensive Review [1.4929298667651645]
  We present a comparison of benchmarks developed between 2019 and 2025 that evaluate large language models and autonomous AI agents.<n>We propose a taxonomy of approximately 60 benchmarks that cover knowledge reasoning, mathematical problem-solving, code generation and software engineering, factual grounding and retrieval, domain-specific evaluations, multimodal and embodied tasks, task orchestration, and interactive assessments.<n>We present real-world applications of autonomous AI agents in materials science, biomedical research, academic ideation, software engineering, synthetic data generation, mathematical problem-solving, geographic information systems, multimedia, healthcare, and finance.
  arXiv  Detail & Related papers  (2025-04-28T11:08:22Z)
• Large Language Model Agent: A Survey on Methodology, Applications and Challenges [88.3032929492409]
  Large Language Model (LLM) agents, with goal-driven behaviors and dynamic adaptation capabilities, potentially represent a critical pathway toward artificial general intelligence.<n>This survey systematically deconstructs LLM agent systems through a methodology-centered taxonomy.<n>Our work provides a unified architectural perspective, examining how agents are constructed, how they collaborate, and how they evolve over time.
  arXiv  Detail & Related papers  (2025-03-27T12:50:17Z)
• A Comprehensive Survey on Multi-Agent Cooperative Decision-Making: Scenarios, Approaches, Challenges and Perspectives [6.277211882332452]
  Multi-agent cooperative decision-making involves multiple agents working together to complete established tasks and achieve specific objectives.<n>These techniques are widely applicable in real-world scenarios such as autonomous driving, drone navigation, disaster rescue, and simulated military confrontations.
  arXiv  Detail & Related papers  (2025-03-17T17:45:46Z)
• SIGMA: Sheaf-Informed Geometric Multi-Agent Pathfinding [4.801673346687721]
  The Multi-Agent Path Finding (MAPF) problem aims to determine the shortest and collision-free paths for multiple agents in a known, potentially obstacle-ridden environment.<n>We introduce a new framework that applies sheaf theory to decentralized deep reinforcement learning, enabling agents to learn geometric cross-dependencies between each other.<n>In particular, we incorporate a neural network to approximately model the consensus in latent space based on sheaf theory and train it through self-supervised learning.
  arXiv  Detail & Related papers  (2025-02-10T13:17:34Z)
• POGEMA: A Benchmark Platform for Cooperative Multi-Agent Pathfinding [76.67608003501479]
  We introduce POGEMA, a comprehensive set of tools that includes a fast environment for learning, a problem instance generator, and a visualization toolkit.<n>We also introduce and define an evaluation protocol that specifies a range of domain-related metrics, computed based on primary evaluation indicators.<n>The results of this comparison, which involves a variety of state-of-the-art MARL, search-based, and hybrid methods, are presented.
  arXiv  Detail & Related papers  (2024-07-20T16:37:21Z)
• An Extensible Benchmark Suite for Learning to Simulate Physical Systems [60.249111272844374]
  We introduce a set of benchmark problems to take a step towards unified benchmarks and evaluation protocols. We propose four representative physical systems, as well as a collection of both widely used classical time-based and representative data-driven methods.
  arXiv  Detail & Related papers  (2021-08-09T17:39:09Z)
• Efficient Model-Based Multi-Agent Mean-Field Reinforcement Learning [89.31889875864599]
  We propose an efficient model-based reinforcement learning algorithm for learning in multi-agent systems. Our main theoretical contributions are the first general regret bounds for model-based reinforcement learning for MFC. We provide a practical parametrization of the core optimization problem.
  arXiv  Detail & Related papers  (2021-07-08T18:01:02Z)
• Compilation-based Solvers for Multi-Agent Path Finding: a Survey, Discussion, and Future Opportunities [7.766921168069532]
  We show the lessons learned from past developments and current trends in the topic and discuss its wider impact. Two major approaches to optimal MAPF solving include (1) dedicated search-based methods, which solve MAPF directly, and (2) compilation-based methods that reduce a MAPF instance to an instance in a different well established formalism.
  arXiv  Detail & Related papers  (2021-04-23T20:13:12Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.