Graph-Based Multi-Robot Path Finding and Planning

Abstract

Purpose of Review Planning collision-free paths for multiple robots is important for real-world multi-robot systems and has been studied as an optimization problem on graphs, called Multi-Agent Path Finding (MAPF). This review surveys different categories of classic and state-of-the-art MAPF algorithms and different research attempts to tackle the challenges of generalizing MAPF techniques to real-world scenarios. Recent Findings Solving MAPF problems optimally is computationally challenging. Recent advances have resulted in MAPF algorithms that can compute collision-free paths for hundreds of robots and thousands of navigation tasks in seconds of runtime. Many variants of MAPF have been formalized to adapt MAPF techniques to different real-world requirements, such as considerations of robot kinematics, online optimization for real-time systems, and the integration of task assignment and path planning. Summary Algorithmic techniques for MAPF problems have addressed important aspects of several multi-robot applications, including automated warehouse fulfillment and sortation, automated train scheduling, and navigation of non-holonomic robots and quadcopters. This showcases their potential for real-world applications of large-scale multi-robot systems.

This preprint has not undergone peer review (when applicable) or any post-submission improvements or corrections. The Version of Record of this article is published in Current Robotics Reports, and is available online at https://doi.org/10.1007/s43154-022-00083-8

References in corpus (8)

• PRIMAL2: Pathfinding via Reinforcement and Imitation Multi-Agent Learning -- Lifelong
• Overview: Generalizations of Multi-Agent Path Finding to Real-World Scenarios
• Optimal Target Assignment and Path Finding for Teams of Agents
• AI Buzzwords Explained: Multi-Agent Path Finding (MAPF)
• Feasibility Study: Moving Non-Homogeneous Teams in Congested Video Game Environments
• MAPFAST: A Deep Algorithm Selector for Multi Agent Path Finding using Shortest Path Embeddings
• Flatland Competition 2020: MAPF and MARL for Efficient Train Coordination on a Grid World
• Modifying Optimal SAT-based Approach to Multi-agent Path-finding Problem to Suboptimal Variants

Cited by in corpus (3)

• Learning Team-Based Navigation: A Review of Deep Reinforcement Learning Techniques for Multi-Agent Pathfinding
• Large-Scale Multirobot Coverage Path Planning on Grids With Path Deconfliction
• beSnake: A routing algorithm for scalable spin-qubit architectures