Advertisement
Published in:
2013 | OriginalPaper | Chapter
Rendezvous of Two Robots with Constant Memory
Authors : Paola Flocchini, Nicola Santoro, Giovanni Viglietta, Masafumi Yamashita
Published in: Structural Information and Communication Complexity
Publisher: Springer International Publishing
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
We study the impact that persistent memory has on the classical
rendezvous
problem of two mobile computational entities, called robots, in the plane. It is well known that, without additional assumptions, rendezvous is impossible if the entities have no persistent memory, even if the system is semi-synchronous and movements are rigid. It has been recently shown that if each entity is endowed with
O
(1) bits of persistent visible memory (called lights), they can rendezvous even if the system is asynchronous.
In this paper we investigate the rendezvous problem in two weaker settings in systems of robots endowed with visible lights: in
FState
, a robot can only see its own light, while in
FComm
a robot can only see the other robot’s light. Among other things, we prove that, with rigid movements, finite-state robots can rendezvous in semi-synchronous settings, and finite-communication robots are able to rendezvous even in asynchronous ones. All proofs are constructive: in each setting, we present a protocol that allows the two robots to rendezvous in finite time.