We study the problem of motion planning for a collection of $n$ labeled unit disc robots in a polygonal environment. We assume that the robots have \emph{revolving areas} around their start and final positions: that each start and each final is contained in a radius $2$ disc lying in the free space, not necessarily concentric with the start or final position, which is free from other start or final positions. This assumption allows a \emph{weakly-monotone} motion plan, in which robots move according to an ordering as follows: during the turn of a robot $R$ in the ordering, it moves fully from its start to final position, while other robots do not leave their revolving areas. As $R$ passes through a revolving area, a robot $R'$ that is inside this area may move within the revolving area to avoid a collision. Notwithstanding the existence of a motion plan, we show that minimizing the total traveled distance in this setting, specifically even when the motion plan is restricted to be weakly-monotone, is APX-hard, ruling out any polynomial-time $(1+\epsilon)$-approximation algorithm. On the positive side, we present the first constant-factor approximation algorithm for computing a feasible weakly-monotone motion plan. The total distance traveled by the robots is within an $O(1)$ factor of that of the optimal motion plan, which need not be weakly monotone. Our algorithm extends to an online setting in which the polygonal environment is fixed but the initial and final positions of robots are specified in an online manner. Finally, we observe that the overhead in the overall cost that we add while editing the paths to avoid robot-robot collision can vary significantly depending on the ordering we chose. Finding the best ordering in this respect is known to be NP-hard, and we provide a polynomial time $O(\log n \log \log n)$-approximation algorithm for this problem.
翻译:我们研究的是在多边形环境中收集有标签的 n$ 单位盘机器人的运动规划问题。 我们假设机器人在其起始位置和最后位置周围都有 emph{ revoluding 区域 : 每个开始和决赛区域都包含在位于自由空间的半径$2美元盘中, 不一定与起始位置或最后位置相提并论, 并且没有其它开始或最后位置。 这个假设允许在这样的运动计划中, 机器人按照以下命令移动 : 在机器人转手时, 它从开始点开始到最后位置, 而其他机器人则不离开其旋转区域。 当美元通过一个旋转区域, 一个在循环区域内的机器人 $R 可能移动到循环区域, 避免碰撞。 尽管存在一个运动计划, 我们显示, 将这一环境的最后距离降到最小, 特别是当运动计划被限制为软性, APX- R$ 开始, 完全从它的开始到最后位置, 而其他机器人不会离开其旋转区域。 当我们确定一个固定的电流运总计划时, 。