论文标题
基于图形的多机器人路径查找和计划
Graph-Based Multi-Robot Path Finding and Planning
论文作者
论文摘要
审查的目的 为多个机器人计划无碰撞路径对于现实世界多机器人系统很重要，并且已作为图形上的优化问题进行了研究，称为多代理路径查找（MAPF）。这篇评论调查了不同类别的经典和最先进的MAPF算法，以及不同的研究试图解决将MAPF技术推广到现实世界情景的挑战。 最新发现 最佳地解决MAPF问题在计算上具有挑战性。最近的进步导致了MAPF算法，该算法可以在运行时计算数百个机器人和数千个导航任务的无碰撞路径。 MAPF的许多变体已被正式化，以使MAPF技术适应不同的现实世界要求，例如机器人运动学的考虑，实时系统的在线优化以及任务分配和路径计划的集成。 概括 用于MAPF问题的算法技术已经解决了多个多机器人应用程序的重要方面，包括自动化的仓库履行和分类，自动化的火车调度以及非全面机器人和四轮驱动器的导航。这展示了它们用于大型多机器人系统的现实应用的潜力。
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.
