The gathering problem for two oblivious robots with unreliable compasses

DOI10.1137/100797916MaRDI QIDQ2884572zbMATHOpenAlexFDO

Authors Taisuke Izumi, Samia Souissi, Yoshiaki Katayama, Nobuhiro Inuzuka, Xavier Défago, Koichi Wada, Masafumi Yamashita

Publication date 30 May 2012

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1111.1492

zbMATH Keywords

distributed algorithmmobile robotgathering problem

Mathematics Subject Classification ID

Artificial intelligence for robotics (68T40) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

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

(42)

• On the computational power of energy-constrained mobile robots: algorithms and cross-model analysis
• Compatibility of convergence algorithms for autonomous mobile robots (extended abstract)
• Fault-induced dynamics of oblivious robots on a line
• scientific article; zbMATH DE number 7561452 (Why is no real title available?)
• Rendezvous with constant memory
• The topology of look-compute-move robot wait-free algorithms with hard termination
• Group search of the plane with faulty robots
• The agreement power of disagreement
• Rendezvous of two robots with constant memory
• Deterministic rendezvous with different maps
• Rendezvous on a Line by Location-Aware Robots Despite the Presence of Byzantine Faults
• Monotonic self-stabilization and its application to robust and adaptive pattern formation
• On the power of bounded asynchrony: convergence by autonomous robots with limited visibility
• Robots and Demons (The Code of the Origins)
• Asynchronous approach in the plane: a deterministic polynomial algorithm
• The Agreement Power of Disagreement
• Dynamic Compass Models and Gathering Algorithms for Autonomous Mobile Robots
• Byzantine gathering in polynomial time
• Optimal rendezvous on a line by location-aware robots in the presence of spies*
• Autonomous mobile robots with lights
• When patrolmen become corrupted: monitoring a graph using faulty mobile robots
• Distributed computing by mobile robots: uniform circle formation
• Gathering problems for autonomous mobile robots with lights
• Price of asynchrony in mobile agents computing
• Gathering anonymous, oblivious robots on a grid
• Asynchronous Gathering Algorithms for Autonomous Mobile Robots with Lights
• Gathering Anonymous, Oblivious Robots on a Grid
• A unified approach for gathering and exclusive searching on rings under weak assumptions
• Gathering of robots on meeting-points: feasibility and optimal resolution algorithms
• Rendezvous of Asynchronous Mobile Robots with Lights
• Mutual visibility by luminous robots without collisions
• Randomized gathering of asynchronous mobile robots
• Gathering Problem of Two Asynchronous Mobile Robots with Semi-dynamic Compasses
• Search on a line with faulty robots
• Pattern formation by oblivious asynchronous mobile robots
• Byzantine gathering in polynomial time
• Wait-free gathering without chirality
• Optimal \(\mathcal{L} \)-algorithms for rendezvous of asynchronous mobile robots with external-lights
• Gathering Autonomous Mobile Robots with Dynamic Compasses: An Optimal Result
• Fault-tolerant gathering of asynchronous oblivious mobile robots under one-axis agreement
• Linear rendezvous with asymmetric clocks
• Gathering in the plane of location-aware robots in the presence of spies

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)