Exclusive Perpetual Ring Exploration without Chirality
Exclusive Perpetual Ring Exploration without Chirality
复制标题
独家无手性永动机探索
DOI：
10.1007/978-3-642-15763-9_29
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
S. Tixeuil
中科院分区：
文献类型：
--
作者：
Lélia Blin;A. Milani;M. Potop;S. Tixeuil
研究了离散空间中移动的匿名遗忘机器人的排他性永久探索问题。我们的结果适用于最通用的设置：机器人是异步的，没有任何方向感，因此左右方向感（即手性）由调度机器人执行的对手决定，并且可能在特定机器人的调用之间发生变化（因为机器人是健忘的）。我们调查的最小和最大数量的机器人是必要的和足够的，以解决排他性的永久探索问题。在最小的方面，我们证明了三个确定性机器人是必要和充分的，只要环的sizenof至少是10，并表明，没有协议与三个机器人可以独家永远探索一个环的大小小于10。在最大值方面，我们证明了k =n-5个机器人是必要的，也是充分的，当它们与k互质时，它们可以独占地永远探索一个sizen环。
In this paper, we study the exclusive perpetual exploration problem with mobile anonymous and oblivious robots in a discrete space. Our results hold for the most generic settings: robots are asynchronous and are not given any sense of direction, so the left and right sense (i.e.chirality) is decided by the adversary that schedules robots for execution, and may change between invocations of a particular robots (as robots are oblivious). We investigate both the minimal and the maximal number of robots that are necessary and sufficient to solve the exclusive perpetual exploration problem. On the minimal side, we prove that three deterministic robots are necessary and sufficient, provided that the sizenof the ring is at least 10, and show that no protocol with three robots can exclusively perpetually explore a ring of size less than 10. On the maximal side, we prove thatk=n− 5 robots are necessary and sufficient to exclusively perpetually explore a ring of sizenwhennis co-prime withk.