COORDINATED MOTION PLANNING: RECONFIGURING A SWARM OF LABELED ROBOTS WITH BOUNDED STRETCH.

We develop constant-factor approximation algorithms for minimizing the execution time of a coordinated parallel motion plan for a relatively dense swarm of homogeneous robots in the absence of obstacles. In our first model, each robot has a specified start and destination on the square grid, and in each round of coordinated parallel motion, every robot can move to any adjacent position that is either empty or simultaneously being vacated by another robot. In this model, our algorithm achieves constant stretch factor: if every robot starts at distance at most d from its destination, then the total duration of the overall schedule is O(d), which is optimal up to constant factors. Our result holds for distinguished robots (each robot has a specific destination), identical (unlabeled) robots, and most generally, classes of different robot types (where each destination specifies a required type of robot). We also show that finding the optimal coordinated parallel motion plan is NP-hard, justifying approximation algorithms. In our second model, each robot is a unit-radius disk in the plane, and robots can translate continuously in parallel subject to not intersecting, i.e., having disk centers at L2-distance at least 2. We prove the same result--constant-factor approximation algorithm to minimizing execution time via constant stretch factor---when the pairwise L∞ -distance between disk centers is at least 2√ 2 = 2.8284 . . . . On the other hand, for N densely packed disks at distance at most 2 + δ for a sufficiently small δ > 0, we prove that a stretch factor of Ω(N1/4) is sometimes necessary (when densely packed), while a stretch factor of O (N1/2) is always possible. [ABSTRACT FROM AUTHOR]