提出可证明最优的多机器人路径规划方法，解决仓库与停车场中的高效避障问题。
From Theory to Practice: Advancing Multi-Robot Path Planning Algorithms and Applications
- 基于魔方表法实现近似最优路径规划，支持上千机器人在二维网格中运行
- 在真实场景中验证了最优布局与无死锁停车系统，提升运输效率
- 拓展至非完整约束机器人，生成符合运动限制的平滑路径
多机器人路径规划（MRPP）问题旨在高效地将多个机器人从起点规划到目标点，同时避免碰撞。尽管在解的质量和运行时间方面已有进展，其复杂性与工业应用价值仍持续推动研究。本论文提出具有可证明保证的可扩展MRPP方法及实用启发式策略。首先，针对二维网格上的密集型MRPP问题（如仓储与包裹系统），提出魔方表方法，在最多可容纳 $\frac{m_1 m_2}{2}$ 个机器人的情况下，实现 $(1 + δ)$-最优完成时间（$δ \in (0, 0.5]$），并能高效求解大规模实例，建立新的理论基准。其次，面向真实世界中的MRPP问题，设计结构化环境（如仓库、停车系统）的最优布局，并提出一种基于拼图的无死锁自动驾驶停车系统。此外，将MRPP扩展至Reeds-Shepp型机器人，引入运动基元与平滑技术，确保在非完整约束下生成可行且高效的路径。仿真与真实实验在城市驾驶与机器人运输场景中验证了该方法的有效性。
原文摘要 · Abstract (English)
The labeled MRPP (Multi-Robot Path Planning) problem involves routing robots from start to goal configurations efficiently while avoiding collisions. Despite progress in solution quality and runtime, its complexity and industrial relevance continue to drive research. This dissertation introduces scalable MRPP methods with provable guarantees and practical heuristics. First, we study dense MRPP on 2D grids, relevant to warehouse and parcel systems. We propose the Rubik Table method, achieving $(1 + δ)$-optimal makespan (with $δ\in (0, 0.5]$) for up to $\frac{m_1 m_2}{2}$ robots, solving large instances efficiently and setting a new theoretical benchmark. Next, we address real-world MRPP. We design optimal layouts for structured environments (e.g., warehouses, parking systems) and propose a puzzle-based system for dense, deadlock-free autonomous vehicle parking. We also extend MRPP to Reeds-Shepp robots, introducing motion primitives and smoothing techniques to ensure feasible, efficient paths under nonholonomic constraints. Simulations and real-world tests validate the approach in urban driving and robotic transport scenarios.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。