论文标题
有效地重新配置连接的标记机器人
Efficiently Reconfiguring a Connected Swarm of Labeled Robots
论文作者
论文摘要
在考虑$ N $标记的机器人的群体运动计划时，我们需要通过一系列平行的无碰撞机器人运动来重新布置给定的启动配置为所需的目标配置。目的是在最短的时间内达到新配置；一个重要的限制是始终保持群体连接。以前已经考虑过这种类型的问题，最近值得注意的结果可以达到不一定连接的重新配置：如果将起始配置映射到目标配置，则需要最大的曼哈顿距离为$ d $，则可以将整体时间表的总总持续时间限制为$ \ \ \ \ \ \ \ \ \ mathcal {o}（O}（o}（d）$，这是最佳的，而常数为常数。但是，只有在允许断开连接的重新配置或用于缩放的配置（通过增加给定对象的所有维度通过相同的乘法因子增加）的缩放配置时，才能实现恒定拉伸。 我们通过（1）为连接，标记的重新配置的$ω（\ sqrt {n}）$建立$ω（\ sqrt {n}）$的下限来解决这些主要的开放问题，最重要的是，（2）证明，对于缩放布置，可以实现连接的重新配置的不断扩展。此外，我们表明（3）决定是否可以实现2个制造物，而可以检查多项式时间是否可以实现1个制造pan，这是NP完整的。
When considering motion planning for a swarm of $n$ labeled robots, we need to rearrange a given start configuration into a desired target configuration via a sequence of parallel, collision-free robot motions. The objective is to reach the new configuration in a minimum amount of time; an important constraint is to keep the swarm connected at all times. Problems of this type have been considered before, with recent notable results achieving constant stretch for not necessarily connected reconfiguration: If mapping the start configuration to the target configuration requires a maximum Manhattan distance of $d$, the total duration of an overall schedule can be bounded to $\mathcal{O}(d)$, which is optimal up to constant factors. However, constant stretch could only be achieved if disconnected reconfiguration is allowed, or for scaled configurations (which arise by increasing all dimensions of a given object by the same multiplicative factor) of unlabeled robots. We resolve these major open problems by (1) establishing a lower bound of $Ω(\sqrt{n})$ for connected, labeled reconfiguration and, most importantly, by (2) proving that for scaled arrangements, constant stretch for connected reconfiguration can be achieved. In addition, we show that (3) it is NP-complete to decide 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.
