Coordinated Motion Planning: Reconfiguring a Swarm of Labeled Robots with Bounded Stretch
Coordinated Motion Planning: Reconfiguring a Swarm of Labeled Robots with Bounded Stretch
复制标题
DOI：
10.4230/lipics.socg.2018.29
复制
发表时间：
2018-01
期刊：
影响因子：
--
通讯作者：
E. Demaine;S. Fekete;Phillip Keldenich;H. Meijer;Christian Scheffer
中科院分区：
文献类型：
--
作者：
E. Demaine;S. Fekete;Phillip Keldenich;H. Meijer;Christian Scheffer
我们提出了一些突破协调运动规划，其中的目标是重新配置一群标记的凸对象的组合成一个给定的目标安排的平行，连续，无碰撞的翻译。这类问题可以追溯到Schwartz和Sharir（1983）的经典著作，他们给出了一种方法来判断障碍物之间的一组圆盘是否存在协调运动;他们的方法在障碍物的复杂性方面是多项式的，但在圆盘的数量方面是指数的。其他以前的工作主要集中在顺序时间表上，其中一个机器人一次移动。我们提供了常数因子近似算法，用于在没有障碍物的情况下，最大限度地减少一群机器人的协调，{\em并行}运动计划的执行时间，提供了一定量的可分性。我们的算法实现{\em常数拉伸因子}：如果所有机器人从各自的起始位置最多$d$个单位，则整个调度的总持续时间为$O（d）$。扩展包括未标记的机器人和不同类别的机器人。我们还证明，找到一个计划，执行时间最短是NP-难的，即使是没有任何固定的障碍物的网格安排。另一方面，我们表明，密集包装的磁盘，不能很好地分离，拉伸因子$\欧米茄（N^{1/4}）$可能是必需的。在积极的一面，我们建立了一个拉伸因子$O（N^{1/2}）$，即使在这种情况下。
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 $\Omega(N^{1/4})$ may be required. On the positive side, we establish a stretch factor of $O(N^{1/2})$ even in this case.