2013 | OriginalPaper | Buchkapitel
Rendezvous of Two Robots with Constant Memory
verfasst von : Paola Flocchini, Nicola Santoro, Giovanni Viglietta, Masafumi Yamashita
Erschienen in: Structural Information and Communication Complexity
Verlag: Springer International Publishing
Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. 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.