The gathering problem for two oblivious robots with unreliable compasses

DOI10.1137/100797916zbMATH Open1242.68178arXiv1111.1492OpenAlexW2049232787MaRDI QIDQ2884572FDOQ2884572

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)

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.

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

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
• Publication:2762510

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)

Cited In (44)

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

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)