Search-Based Optimal Solvers for the Multi-Agent Pathfinding Problem: Summary and Challenges
Ariel Felner, Roni Stern, Solomon Eyal Shimony, Eli Boyarski, Meir Goldenberg, Guni Sharon, Nathan Sturtevant, Glenn Wagner, Pavel Surynek
2021Proceedings of the International Symposium on Combinatorial Search184 citationsDOIOpen Access PDF
Abstract
Multi-agent pathfinding (MAPF) is an area of expanding research interest. At the core of this research area, numerous diverse search-based techniques were developed in the past 6 years for optimally solving MAPF under the sum-of-costs objective function. In this paper we survey these techniques, while placing them into the wider context of the MAPF field of research. Finally, we provide analytical and experimental comparisons that show that no algorithm dominates all others in all circumstances. We conclude by listing important future research directions.
Topics & Concepts
PathfindingListing (finance)Context (archaeology)Computer scienceFunction (biology)Field (mathematics)Mathematical optimizationTheoretical computer scienceMathematicsShortest path problemEconomicsGeographyEvolutionary biologyPure mathematicsFinanceArchaeologyBiologyGraphMetaheuristic Optimization Algorithms ResearchRobotic Path Planning AlgorithmsEvolutionary Algorithms and Applications