We consider the problem of coordinated motion planning for a swarm of simple, identical robots: From a given start grid configuration of robots, we need to reach a desired target configuration via a sequence of parallel, continuous, collision-free robot motions, such that the set of robots induces a connected grid graph at all integer times. The objective is to minimize the makespan of the motion schedule, i.e., to reach the new configuration in a minimum amount of time. We show that this problem is NP-hard, even for deciding whether a makespan of 2 can be achieved, while it is possible to check in polynomial time whether a makespan of 1 can be achieved. On the algorithmic side, we establish simultaneous constant-factor approximation for two fundamental parameters, by achieving constant stretch for constant scale. Scaled shapes (which arise by increasing all dimensions of a given object by the same multiplicative factor) have been considered in previous seminal work on self-assembly, often with unbounded or logarithmic scale factors; we provide methods for a generalized scale factor, bounded by a constant. Moreover, our algorithm achieves a constant stretch factor: If mapping the start configuration to the target configuration requires a maximum Manhattan distance of $d$, then the total duration of our overall schedule is $O(d)$, which is optimal up to constant factors.
翻译:我们考虑对一组简单、相同的机器人进行协调运动规划的问题:从一个特定起始的机器人网格配置中,我们需要通过一个平行、连续、无碰撞的机器人动作序列来达到一个理想的目标配置,让一组机器人在所有整数时间都产生一个连接的网格图。目标是将运动时间表的成份最小化,即在最短的时间内达到新配置。我们显示,这个问题是难以解决的,甚至是为了确定是否能够实现一个2的成份,同时有可能在多元时间内检查一个1的成份是否能够实现。在算法方面,我们为两个基本参数同时建立恒定的方位近距离,在固定的尺度上达到一个固定的伸缩缩放。在以前关于自我组合的半成份工作中已经考虑到了规模的形状(通过增加一个特定对象的方位,也就是在最小的成份上达到新的成份来达到新的配置),我们提供了一个通用的成份比例系数,由固定的成份数开始。此外,如果我们总的成份的成份是固定的成份的成份,那么,我们的成份的成份就要求一个固定不变的成份的成份的成份。