2018/01/05 by Erik D. Demaine, Demaine, Erik D., Sándor P. Fekete +7 · 2 citations
Computer Science · Engineering · #Computational Geometry (cs.CG) #Data Structures and Algorithms (cs.DS) #F.2.2 #FOS: Computer and information sciences #I.2.9 #Modular Robots and Swarm Intelligence #Optimization and Search Problems #Robotic Path Planning Algorithms #Robotics (cs.RO)
paper · pdf · doi:10.48550/arxiv.1801.01689
openalex publication_date 2018/01/05 · openalex created_date 2022/10/03 · openalex updated_date 2026/07/28
We present a number of breakthroughs for coordinated motion planning, in\nwhich the objective is to reconfigure a swarm of labeled convex objects by a\ncombination of parallel, continuous, collision-free translations into a given\ntarget arrangement. Problems of this type can be traced back to the classic\nwork of Schwartz and Sharir (1983), who gave a method for deciding the\nexistence of a coordinated motion for a set of disks between obstacles; their\napproach is polynomial in the complexity of the obstacles, but exponential in\nthe number of disks. Other previous work has largely focused on em\nsequential schedules, in which one robot moves at a time.\n We provide constant-factor approximation algorithms for minimizing the\nexecution time of a coordinated, em parallel motion plan for a swarm of\nrobots in the absence of obstacles, provided some amount of separability.\n Our algorithm achieves em constant stretch factor: If all robots are at\nmost d units from their respective starting positions, the total duration of\nthe overall schedule is O(d). Extensions include unlabeled robots and\ndifferent classes of robots. We also prove that finding a plan with minimal\nexecution time is NP-hard, even for a grid arrangement without any stationary\nobstacles. On the other hand, we show that for densely packed disks that cannot\nbe well separated, a stretch factor \Ω(N1/4) may be required. On the\npositive side, we establish a stretch factor of O(N1/2) even in this case.\n