Optimal probabilistic ring exploration by semi-synchronous oblivious robots
Optimal probabilistic ring exploration by semi-synchronous oblivious robots
复制标题
半同步遗忘机器人的最优概率环探索
DOI：
10.1016/j.tcs.2013.05.031
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
S. Tixeuil
中科院分区：
文献类型：
--
作者：
Stéphane Devismes;F. Petit;S. Tixeuil
我们考虑一个由k个相同的、不经意的、半同步的移动机器人组成的团队，他们能够感知(即，观察)他们的环境，但无法交流，并在受限的路径上进化。以前在这种弱场景中的结果表明，当问题要由确定性机器人解决时，初始对称性产生高下界。在此背景下，我们开始了概率界和解的研究，并集中于任意大小为n的匿名无向环的探索问题。我们知道，如果k和n互质，k=Θ(Logn)确定性机器人是求解该问题的充要条件。通过对比，我们证明了四个相同的概率机器人是解决相同问题的必要条件和充分条件，同时也消除了互质约束。我们的积极成果是建设性的。
We consider a team of k identical, oblivious, and semi-synchronous mobile robots that are able to sense (ie, view) their environment, yet are unable to communicate, and evolve on a constrained path. Previous results in this weak scenario show that initial symmetry yields high lower bounds when problems are to be solved by deterministic robots. In this paper, we initiate research on probabilistic bounds and solutions in this context, and focus on the exploration problem of anonymous unoriented rings of any size n. It is known that k= Θ (log n) deterministic robots are necessary and sufficient to solve the problem, provided that k and n are coprime. By contrast, we show that four identical probabilistic robots are necessary and sufficient to solve the same problem, also removing the coprime constraint. Our positive results are constructive.