Rendezvous of Two Robots with Visible Bits
Rendezvous of Two Robots with Visible Bits
复制标题
两个机器人与可见位点的会合
DOI：
10.1007/978-3-642-45346-5_21
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
G. Viglietta
中科院分区：
文献类型：
--
作者：
G. Viglietta
研究两个机器人在平面（或直线）上运动的交会问题。机器人是自主的、匿名的、不经意的，并且携带着双方都能看到的彩色灯光。我们考虑确定性分布式算法，其中机器人不使用距离信息，但试图减少（或增加）他们的距离由一个常数因子，取决于他们的灯的颜色。我们给出了一个完整的表征的颜色的数量是必要的，以解决交会问题在每一个可能的模型，从完全同步到半同步到异步，刚性和非刚性，特别地，我们证明了在具有任意初始构型的非刚性异步模型中，三种颜色是充分的。相反，两种颜色是不够的刚性异步模型与任意初始配置和非刚性异步模型与预置的初始配置。此外，如果机器人能够区分零和非零距离，我们展示了他们如何解决交会和检测终止使用只有三种颜色，即使在非刚性异步模型与任意初始配置。
We study the rendezvous problem for two robots moving in the plane (or on a line). Robots are autonomous, anonymous, oblivious, and carry colored lights that are visible to both. We consider deterministic distributed algorithms in which robots do not use distance information, but try to reduce (or increase) their distance by a constant factor, depending on their lights’ colors.We give a complete characterization of the number of colors that are necessary to solve the rendezvous problem in every possible model, ranging from fully synchronous to semi-synchronous to asynchronous, rigid and non-rigid, with preset or arbitrary initial configuration.In particular, we show that three colors are sufficient in the non-rigid asynchronous model with arbitrary initial configuration. In contrast, two colors are insufficient in the rigid asynchronous model with arbitrary initial configuration and in the non-rigid asynchronous model with preset initial configuration.Additionally, if the robots are able to distinguish between zero and non-zero distances, we show how they can solve rendezvous and detect termination using only three colors, even in the non-rigid asynchronous model with arbitrary initial configuration.
DOI：
--
发表时间：
2012
期刊：
影响因子：
--
作者：
Hiroyuki Shimada;Takami Miki;Akiko Tamura;Suzuka Ataka;Masanori Emoto;Yoshiki Nishizawa;Shantanu Das
通讯作者：
Shantanu Das
DOI：
--
发表时间：
2008
期刊：
影响因子：
--
作者：
N.Inuzuka;Y.Tomida;T.Izumi;Y.Katayama;K.Wada
通讯作者：
K.Wada