Dispersion of Mobile Robots: The Power of Randomness
Dispersion of Mobile Robots: The Power of Randomness
复制标题
移动机器人的分散：随机性的力量
DOI：
--
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
W. Moses
中科院分区：
文献类型：
--
作者：
A. R. Molla;W. Moses
我们考虑昆虫之间的合作，将其建模为图表上移动机器人之间的合作。在此设置中，我们考虑移动机器人在图上的分散问题。在图上研究移动机器人是一个有趣的范例，有许多有趣的问题和应用。 Augustine 和 Moses Jr. [4] 提出了这种情况下的分散问题，要求最初任意放置在 n 个节点图上的 n 个机器人一起工作，以快速达到每个节点只有一个机器人的配置。之前关于这个问题的工作着眼于实现分散的时间和每个机器人所需的内存量之间的权衡。然而，对确定性算法的权衡进行了分析，发现每个机器人实现分散所需的最小内存为 (varOmega (log n)) 位。在本文中，我们表明，通过利用随机性的力量，可以在每个机器人上使用 (O(log varDelta )) 位内存实现分散，其中 (varDelta ) 是图的最大度数。此外，我们还展示了任何随机算法解决色散问题的匹配下界 (varOmega (log varDelta )) 位。我们进一步将问题扩展到一般的 k 分散问题，其中 (k> n) 个机器人需要分散在 n 个节点上，使得最多 (lceil k/n
ceil ) 机器人位于最终配置中的每个节点。
We consider cooperation among insects, modeled as cooperation between mobile robots on a graph. Within this setting, we consider the problem of mobile robot dispersion on graphs. The study of mobile robots on a graph is an interesting paradigm with many interesting problems and applications. The problem of dispersion in this context, introduced by Augustine and Moses Jr. [4], asks that n robots, initially placed arbitrarily on an n node graph, work together to quickly reach a configuration with exactly one robot at each node. Previous work on this problem has looked at the trade-off between the time to achieve dispersion and the amount of memory required by each robot. However, the trade-off was analyzed for deterministic algorithms and the minimum memory required to achieve dispersion was found to be (varOmega (log n)) bits at each robot. In this paper, we show that by harnessing the power of randomness, one can achieve dispersion with (O(log varDelta )) bits of memory at each robot, where (varDelta ) is the maximum degree of the graph. Further, we show a matching lower bound of (varOmega (log varDelta )) bits for any randomized algorithm to solve dispersion. We further extend the problem to a general k-dispersion problem where (k> n) robots need to disperse over n nodes such that at most (lceil k/n
ceil ) robots are at each node in the final configuration.
使用对数内存进行树探索
影响因子：
1.3
作者：
Ambühl C
通讯作者：
Ambühl C