Non-uniform circle formation algorithm for oblivious mobile robots with convergence toward uniformity
Non-uniform circle formation algorithm for oblivious mobile robots with convergence toward uniformity
复制标题
DOI：
10.1016/j.tcs.2008.01.050
复制
发表时间：
2008-05
期刊：
影响因子：
--
通讯作者：
X. Défago;S. Souissi
中科院分区：
文献类型：
--
作者：
X. Défago;S. Souissi
本文提出了一种分布式算法，使一组移动的机器人自组织和定位成一个松散同步的环境中形成一个圆圈。尽管它表面上很简单，但问题的困难来自于对系统的弱假设。特别是，机器人是匿名的，不经意的（即， 无国籍），无法直接沟通，迷失方向的意义上说，他们没有共享一个共同的坐标系的知识。此外，机器人的激活并不同步。更具体地说，所提出的算法确保机器人确定性地形成一个非均匀的圆在有限数量的步骤，并收敛到所有机器人均匀地位于圆的边界上的情况。
This paper presents a distributed algorithm whereby a group of mobile robots self-organize and position themselves into forming a circle in a loosely synchronized environment. In spite of its apparent simplicity, the difficulty of the problem comes from the weak assumptions made on the system. In particular, robots are anonymous, oblivious (i.e., stateless), unable to communicate directly, and disoriented in the sense that they share no knowledge of a common coordinate system. Furthermore, robots’ activations are not synchronized. More specifically, the proposed algorithm ensures that robots deterministically form a non-uniform circle in a finite number of steps and converges to a situation in which all robots are located evenly on the boundary of the circle.