The gathering problem for two oblivious robots with unreliable compasses
From MaRDI portal
(Redirected from Publication:2884572)
Abstract: Anonymous mobile robots are often classified into synchronous, semi-synchronous and asynchronous robots when discussing the pattern formation problem. For semi-synchronous robots, all patterns formable with memory are also formable without memory, with the single exception of forming a point (i.e., the gathering) by two robots. However, the gathering problem for two semi-synchronous robots without memory is trivially solvable when their local coordinate systems are consistent, and the impossibility proof essentially uses the inconsistencies in their coordinate systems. Motivated by this, this paper investigates the magnitude of consistency between the local coordinate systems necessary and sufficient to solve the gathering problem for two oblivious robots under semi-synchronous and asynchronous models. To discuss the magnitude of consistency, we assume that each robot is equipped with an unreliable compass, the bearings of which may deviate from an absolute reference direction, and that the local coordinate system of each robot is determined by its compass. We consider two families of unreliable compasses, namely,static compasses with constant bearings, and dynamic compasses the bearings of which can change arbitrarily. For each of the combinations of robot and compass models, we establish the condition on deviation phi that allows an algorithm to solve the gathering problem, where the deviation is measured by the largest angle formed between the x-axis of a compass and the reference direction of the global coordinate system: phi < pi/2 for semi-synchronous and asynchronous robots with static compasses, phi < pi/4 for semi-synchronous robots with dynamic compasses, and phi < pi/6 for asynchronous robots with dynamic compasses. Except for asynchronous robots with dynamic compasses, these sufficient conditions are also necessary.
Recommendations
- Gathering Problem of Two Asynchronous Mobile Robots with Semi-dynamic Compasses
- Dynamic Compass Models and Gathering Algorithms for Autonomous Mobile Robots
- Distributed computing by mobile robots: gathering
- Gathering Autonomous Mobile Robots with Dynamic Compasses: An Optimal Result
- scientific article; zbMATH DE number 1688369
Cited in
(50)- When patrolmen become corrupted: monitoring a graph using faulty mobile robots
- Distributed computing by mobile robots: uniform circle formation
- Gathering of robots on meeting-points: feasibility and optimal resolution algorithms
- The topology of look-compute-move robot wait-free algorithms with hard termination
- Search on a line with faulty robots
- Monotonic self-stabilization and its application to robust and adaptive pattern formation
- On the computational power of energy-constrained mobile robots: algorithms and cross-model analysis
- Byzantine gathering in polynomial time
- Randomized gathering of asynchronous mobile robots
- Fault-induced dynamics of oblivious robots on a line
- Gathering anonymous, oblivious robots on a grid
- Asynchronous approach in the plane: a deterministic polynomial algorithm
- Deterministic rendezvous with different maps
- Group search of the plane with faulty robots
- Fault-tolerant gathering of asynchronous oblivious mobile robots under one-axis agreement
- Price of asynchrony in mobile agents computing
- Gathering problems for autonomous mobile robots with lights
- The agreement power of disagreement
- Rendezvous of two robots with constant memory
- Wait-free gathering without chirality
- Gathering Problem of Two Asynchronous Mobile Robots with Semi-dynamic Compasses
- Gathering Autonomous Mobile Robots with Dynamic Compasses: An Optimal Result
- Byzantine gathering in polynomial time
- Rendezvous on a Line by Location-Aware Robots Despite the Presence of Byzantine Faults
- Gathering Anonymous, Oblivious Robots on a Grid
- Optimal rendezvous on a line by location-aware robots in the presence of spies*
- Optimal rendezvous \(\mathcal{L}\)-algorithms for asynchronous mobile robots with external-lights
- Linear rendezvous with asymmetric clocks
- A unified approach for gathering and exclusive searching on rings under weak assumptions
- Pattern formation by oblivious asynchronous mobile robots
- Mutual visibility by luminous robots without collisions
- Dynamic Compass Models and Gathering Algorithms for Autonomous Mobile Robots
- Robots and Demons (The Code of the Origins)
- Gathering in the plane of location-aware robots in the presence of spies
- Rendezvous with constant memory
- Optimal \(\mathcal{L} \)-algorithms for rendezvous of asynchronous mobile robots with external-lights
- Compatibility of convergence algorithms for autonomous mobile robots (extended abstract)
- Rendezvous of Asynchronous Mobile Robots with Lights
- The Agreement Power of Disagreement
- Asynchronous Gathering Algorithms for Autonomous Mobile Robots with Lights
- On the power of bounded asynchrony: convergence by autonomous robots with limited visibility
- Gathering semi-synchronously scheduled two-state robots
- Optimal gathering of robots in anonymous butterfly networks via leader election
- Minimum algorithm sizes for the gathering and related problems of autonomous mobile robots
- Compatibility of convergence algorithms for autonomous mobile robots
- The minimum algorithm size of k-grouping by silent oblivious robots
- On the computational power of energy-constrained mobile robots
- Symmetry breaking in the plane. Rendezvous by robots with unknown attributes
- Universal pattern formation by oblivious robots under sequential schedulers
- Autonomous mobile robots with lights
This page was built for publication: The gathering problem for two oblivious robots with unreliable compasses
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2884572)
