2025/06/11 by Teng Guo, Guo, Teng
Computer Science · Engineering · #Computational Geometry and Mesh Generation #FOS: Computer and information sciences #Robotic Path Planning Algorithms #Robotics (cs.RO) #Vehicle Routing Optimization Methods
paper · pdf · doi:10.48550/arxiv.2506.09914
openalex publication_date 2025/06/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 δ∈ (0, 0.5]) for up to (m1 m2)/(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.