Coordinated Motion Planning: Reconfiguring a Swarm of Labeled Robots with Bounded Stretch
This addresses coordinated motion planning for robot swarms, offering efficient algorithms with provable guarantees, though it builds incrementally on prior work by extending to parallel schedules.
The paper tackles the problem of reconfiguring a swarm of labeled convex robots via parallel, continuous, collision-free translations to minimize execution time, achieving a constant stretch factor of O(d) under separability conditions, with extensions to unlabeled robots and different classes, while proving NP-hardness for minimal time plans and establishing bounds like O(N^{1/2}) for densely packed cases.
We present a number of breakthroughs for coordinated motion planning, in which the objective is to reconfigure a swarm of labeled convex objects by a combination of parallel, continuous, collision-free translations into a given target arrangement. Problems of this type can be traced back to the classic work of Schwartz and Sharir (1983), who gave a method for deciding the existence of a coordinated motion for a set of disks between obstacles; their approach is polynomial in the complexity of the obstacles, but exponential in the number of disks. Other previous work has largely focused on {\em sequential} schedules, in which one robot moves at a time. We provide constant-factor approximation algorithms for minimizing the execution time of a coordinated, {\em parallel} motion plan for a swarm of robots in the absence of obstacles, provided some amount of separability. Our algorithm achieves {\em constant stretch factor}: If all robots are at most $d$ units from their respective starting positions, the total duration of the overall schedule is $O(d)$. Extensions include unlabeled robots and different classes of robots. We also prove that finding a plan with minimal execution time is NP-hard, even for a grid arrangement without any stationary obstacles. On the other hand, we show that for densely packed disks that cannot be well separated, a stretch factor $Ω(N^{1/4})$ may be required. On the positive side, we establish a stretch factor of $O(N^{1/2})$ even in this case.