Optimal Grid Exploration by Asynchronous Oblivious Robots
Optimal Grid Exploration by Asynchronous Oblivious Robots
复制标题
异步遗忘机器人的最优网格探索
DOI：
10.1007/978-3-642-33536-5_7
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
S. Tixeuil
中科院分区：
文献类型：
--
作者：
Stéphane Devismes;Anissa Lamani;F. Petit;Pascal Raymond;S. Tixeuil
我们通过一组异步的遗忘机器人来确定性地终止对网格的探索。我们首先考虑半同步原子模型ATOM。在这个模型中，我们展示了最小数量的机器人来解决问题w.r.t.的大小的网格。然后，我们考虑异步非原子模型CORDA。原子严格强于CORDA，以前的界限也保持在CORDA中，我们提出了确定性的算法在CORDA中，这些界限相匹配。上述结果表明，除了两种特殊情况，3个机器人是必要的，足以确定性地探索至少有三个节点的网格。对于剩下的两种情况，机器人的最佳数量分别是：（2，2）-网格为4个，（3，3）-网格为5个。
We considerdeterministic terminating explorationof a grid by a team of asynchronous oblivious robots. We first consider the semi-synchronous atomic model ATOM. In this model, we exhibit the minimal number of robots to solve the problemw.r.t.the size of the grid. We then consider the asynchronous non-atomic model CORDA. ATOM being strictly stronger than CORDA, the previous bounds also hold in CORDA, and we propose deterministic algorithms in CORDA that matches these bounds. The above results show that except in two particular cases, 3 robots are necessary and sufficient to deterministically explore a grid of at least three nodes. The optimal number of robots for the two remaining cases is: 4 for the (2,2)-Grid and 5 for the (3,3)-Grid, respectively.
DOI：
10.1007/978-3-642-25873-2_18
发表时间：
2011
期刊：
Proc.15th Intl.Conf.on Principles of Distributed Systems (OPODIS 2011)
影响因子：
--
作者：
F.Bonnet;A.Milani;M.Potop-Butucaru;S.Tixeuil
通讯作者：
S.Tixeuil