TY - GEN
T1 - Rendezvous of two robots with constant memory
AU - Flocchini, Paola
AU - Santoro, Nicola
AU - Viglietta, Giovanni
AU - Yamashita, Masafumi
PY - 2013
Y1 - 2013
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=84892972810&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84892972810&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-03578-9_16
DO - 10.1007/978-3-319-03578-9_16
M3 - Conference contribution
AN - SCOPUS:84892972810
SN - 9783319035772
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 189
EP - 200
BT - Structural Information and Communication Complexity - 20th International Colloquium, SIROCCO 2013, Revised Selected Papers
T2 - 20th International Colloquium on Structural Information and Communication Complexity, SIROCCO 2013
Y2 - 1 July 2013 through 3 July 2013
ER -