Asynchronous Exclusive Perpetual Grid Exploration without Sense of Direction
Asynchronous Exclusive Perpetual Grid Exploration without Sense of Direction
复制标题
异步独家永无方向感的网格探索
DOI：
10.1007/978-3-642-25873-2_18
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
S.Tixeuil
中科院分区：
文献类型：
--
作者：
F.Bonnet;A.Milani;M.Potop-Butucaru;S.Tixeuil
在本文中，我们研究了独家永久探索网格形网络使用匿名，遗忘和完全异步的机器人。我们的研究结果适用于没有方向感的机器人（即它们不同意共同的北方，也不同意共同的左和右;此外，每个机器人的“北”和“左”由对手决定，该对手安排机器人执行，并且可能在特定机器人的调用之间发生变化）。本文主要讨论了在一般网格中解决该问题所需的机器人的最小数目问题，并证明了在网格大小为n × m且3 ≤n≤morn= 2且m ≥ 4的条件下，三个确定性机器人是解决该问题的充分必要条件.也许令人惊讶的是，与停止问题的探索结果（网格是“更容易”探索和停止比环相对于机器人的数量），独家永久的探索需要尽可能多的机器人在环中的grid. Further，我们提出了一个分类的配置，这样的配置检查的空间大大减少。这种预处理奠定了基础，我们的算法的自动验证一般网格，因为它允许避免组合爆炸。
In this paper, we investigate the exclusive perpetual exploration of grid shaped networks using anonymous, oblivious and fully asynchronous robots. Our results hold for robots without sense of direction (i.e.they do not agree on a common North, nor do they agree on a common left and right ; furthermore, the “North” and “left” of each robot is decided by an adversary that schedules robots for execution, and may change between invocations of particular robots). We focus on the minimal number of robots that are necessary and sufficient to solve the problem in general grids.In more details, we prove that three deterministic robots are necessary and sufficient, provided that the size of the grid isn×mwith 3 ≤n≤morn= 2 andm≥ 4. Perhaps surprisingly, and unlike results for the exploration with stop problem (where grids are “easier” to explore and stop than rings with respect to the number of robots), exclusive perpetual exploration requires as many robots in the ring as in the grid.Furthermore, we propose a classification of configurations such that the space of configurations to be checked is drastically reduced. This pre-processing lays the bases for the automated verification of our algorithm for general grids as it permits to avoid combinatorial explosion.
登录
查看更多内容
异步、匿名、不经意的机器人形成任意模式
DOI：
10.1016/j.tcs.2008.07.026
发表时间：
2008
期刊：
Theor. Comput. Sci.
影响因子：
--
作者：
P. Flocchini;G. Prencipe;N. Santoro;P. Widmayer
通讯作者：
P. Widmayer
DOI：
10.1007/978-3-642-15763-9_29
发表时间：
2010
期刊：
--
影响因子：
--
作者：
Lélia Blin;A. Milani;M. Potop;S. Tixeuil
通讯作者：
S. Tixeuil
利用对称性：异步遗忘机器人聚集在环上
DOI：
--
发表时间：
2008
期刊：
International Conference on Principles of Distributed Systems
影响因子：
--
作者：
R. Klasing;A. Kosowski;A. Navarra
通讯作者：
A. Navarra
异步遗忘机器人的最优网格探索
DOI：
10.1007/978-3-642-33536-5_7
发表时间：
2011
期刊：
--
影响因子：
--
作者：
Stéphane Devismes;Anissa Lamani;F. Petit;Pascal Raymond;S. Tixeuil
通讯作者：
S. Tixeuil
DOI：
10.1016/j.tcs.2013.05.031
发表时间：
2009
期刊：
ArXiv
影响因子：
--
作者：
Stéphane Devismes;F. Petit;S. Tixeuil
通讯作者：
S. Tixeuil