Rendezvous with constant memory
From MaRDI portal
Abstract: 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 are oblivious (i.e., have no persistent memory) even if the system is semi-synchronous (SSynch). It has been recently shown that rendezvous is possible even if the system is asynchronous (ASynch) if each robot is endowed with O(1) bits of persistent memory, can transmit O(1) bits in each cycle, and can remember (i.e., can persistently store) the last received transmission. This setting is overly powerful. In this paper we weaken that setting in two different ways: (1) by maintaining the O(1) bits of persistent memory but removing the communication capabilities; and (2) by maintaining the O(1) transmission capability and the ability to remember the last received transmission, but removing the ability of an agent to remember its previous activities. We call the former setting finite-state (FState) and the latter finite-communication (FComm). Note that, even though its use is very different, in both settings, the amount of persistent memory of a robot is constant. We investigate the rendezvous problem in these two weaker settings. We model both settings as a system 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. We prove, among other things, that finite-state robots can rendezvous in SSynch, and that finite-communication robots are able to rendezvous even in ASynch. All proofs are constructive: in each setting, we present a protocol that allows the two robots to rendezvous in finite time.
Recommendations
Cites work
- A new approach for analyzing convergence algorithms for mobile robots
- Convergence of Autonomous Mobile Robots with Inaccurate Sensors and Movements
- Convergence Properties of the Gravitational Algorithm in Asynchronous Robot Systems
- Distributed Anonymous Mobile Robots: Formation of Geometric Patterns
- Distributed computing by mobile robots: gathering
- Fault-Tolerant and Self-stabilizing Mobile Robots Gathering
- Fault-Tolerant Gathering Algorithms for Autonomous Mobile Robots
- Gathering of asynchronous robots with limited visibility
- Impossibility of gathering by a set of autonomous mobile robots
- Rendezvous of two robots with visible bits
- Self-stabilizing gathering with strong multiplicity detection
- The gathering problem for two oblivious robots with unreliable compasses
- The Multi-Agent Rendezvous Problem. Part 1: The Synchronous Case
Cited in
(19)- Gathering of robots on meeting-points: feasibility and optimal resolution algorithms
- Rendezvous of two robots with visible bits
- The topology of look-compute-move robot wait-free algorithms with hard termination
- On the computational power of energy-constrained mobile robots: algorithms and cross-model analysis
- On the robustness of a synchronized multi-robot system
- Meeting in a polygon by anonymous oblivious robots
- Gathering problems for autonomous mobile robots with lights
- Rendezvous of two robots with constant memory
- Continuous inspection with memory
- Optimal rendezvous \(\mathcal{L}\)-algorithms for asynchronous mobile robots with external-lights
- Gathering in dynamic rings
- Optimal \(\mathcal{L} \)-algorithms for rendezvous of asynchronous mobile robots with external-lights
- The canonical amoebot model: algorithms and concurrency control
- Rendezvous of Asynchronous Mobile Robots with Lights
- Stand Up Indulgent Rendezvous
- The Agreement Power of Disagreement
- Asynchronous Gathering Algorithms for Autonomous Mobile Robots with Lights
- Gathering semi-synchronously scheduled two-state robots
- On the computational power of energy-constrained mobile robots
This page was built for publication: Rendezvous with constant memory
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5964022)
