Feasibility of Polynomial-time Randomized Gathering for Oblivious Mobile Robots
Feasibility of Polynomial-time Randomized Gathering for Oblivious Mobile Robots
复制标题
遗忘移动机器人多项式时间随机采集的可行性
DOI：
10.1109/tpds.2012.212
复制
发表时间：
2013
影响因子：
5.3
通讯作者：
Fukuhito Oosita
中科院分区：
文献类型：
--
作者：
Taisuke Izumi;Tomoko Izumi;Sayaka Kamei;Fukuhito Oosita
我们考虑收集 n 个匿名且不经意的移动机器人的问题，这要求所有机器人在有限时间内在非预定点相遇。虽然在不假设机器人具有任何额外功能的情况下无法确定性地解决收集问题，但随机方法可以轻松解决该问题。然而，目前已知的随机解决方案的时间复杂度在没有额外假设的情况下以 n 为指数。这一事实产生了以下两个问题：是否可以构建具有多项式期望时间的随机收集算法？如果不可能，获得这样的算法所需的最小附加假设是什么？在本文中，我们从多重性检测能力的角度解决这些问题。我们新引入了两种较弱的多重性检测变体，称为局部强多重性和局部弱多重性，并研究这些功能是否允许具有多项式预期时间的收集算法。本文的贡献是表明，任何仅假设局部弱多重性检测的算法都需要指数轮数。另一方面，我们可以使用局部强多重性检测获得恒定轮次的聚集算法。这些结果意味着多重性检测的两种模型在计算能力方面存在显着差异。有趣的是，如果我们再假设所有机器人最初都是分散的（即没有两个机器人停留在同一位置），那么这些差异就会消失。假设局部弱多重性检测和分散的初始配置，我们可以获得期望轮数恒定的收集算法。
We consider the problem of gathering n anonymous and oblivious mobile robots, which requires that all robots meet in finite time at a nonpredefined point. While the gathering problem cannot be solved deterministically without assuming any additional capabilities for the robots, randomized approaches easily allow it to be solvable. However, the randomized solutions currently known have a time complexity that is exponential in n with no additional assumption. This fact yields the following two questions: Is it possible to construct a randomized gathering algorithm with polynomial expected time? If it is not possible, what is the minimal additional assumption necessary to obtain such an algorithm? In this paper, we address these questions from the aspect of multiplicity-detection capabilities. We newly introduce two weaker variants of multiplicity detection, called local-strong and local-weak multiplicity, and investigate whether those capabilities permit a gathering algorithm with polynomial expected time or not. The contribution of this paper is to show that any algorithm only assuming local-weak multiplicity detection takes exponential number of rounds in expectation. On the other hand, we can obtain a constant-round gathering algorithm using local-strong multiplicity detection. These results imply that the two models of multiplicity detection are significantly different in terms of their computational power. Interestingly, these differences disappear if we take one more assumption that all robots are scattered (i.e., no two robots stay at the same location) initially. We can obtain a gathering algorithm that takes a constant number of rounds in expectation, assuming local-weak multiplicity detection and scattered initial configurations.