Mutual visibility by luminous robots without collisions
From MaRDI portal
Publication:528203
DOI10.1016/J.IC.2016.09.005zbMATH Open1370.68285arXiv1503.04347OpenAlexW2963114728MaRDI QIDQ528203FDOQ528203
G. Viglietta, Giuseppe Antonio Di Luna, N. Santoro, S. Gan Chaudhuri, Federico Poloni, P. Flocchini
Publication date: 12 May 2017
Published in: Information and Computation (Search for Journal in Brave)
Abstract: Consider a finite set of identical computational entities that can move freely in the Euclidean plane operating in Look-Compute-Move cycles. Let p(t) denote the location of entity p at time t; entity p can see entity q at time t if at that time no other entity lies in the line segment p(t)q(t). We consider the basic problem called Mutual Visibility: starting from arbitrary distinct locations, within finite time the entities must reach, without collisions, a configuration where they all see each other. This problem must be solved by each entity autonomously executing the same algorithm. We study this problem in the "luminous robots" model; in this generalization of the standard model of oblivious robots, each entity, called "robot", has an externally visible persistent light which can assume colors from a fixed set. The case where the number of colors is c=1 corresponds to the classical model without lights. In this paper we investigate under what conditions luminous robots can solve Mutual Visibility without collisions and at what cost (i.e., with how many colors). We establish a spectrum of results, depending on the power of the adversary, on the number c of colors, and on the a-priori knowledge the robots have about the system. Among such results, we prove that Mutual Visibility can always be solved without collisions in SSynch with c=2 colors and in ASynch with c=3 colors. If an adversary can interrupt and stop a robot moving to its computed destination, Mutual Visibility is still always solvable without collisions in SSynch with c=3 colors, and, if the robots agree on the direction of one axis, also in ASynch. All the results are obtained constructively by means of novel protocols. As a byproduct of our solutions, we provide the first obstructed-visibility solutions to two classical problems for oblivious robots: Collision-less Convergence to a point and Circle Formation.
Full work available at URL: https://arxiv.org/abs/1503.04347
Recommendations
- Mutual visibility by asynchronous robots on infinite grid
- Complete visibility for robots with lights in \(\mathrm{O}(1)\) time
- Optimum Algorithm for Mutual Visibility Among Asynchronous Robots with Lights
- Constant-time complete visibility for asynchronous robots with lights
- Uniform circle formation for swarms of opaque robots with lights
Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Artificial intelligence for robotics (68T40) Distributed systems (68M14)
Cites Work
- Title not available (Why is that?)
- Distributed Models and Algorithms for Mobile Robot Systems
- Distributed Computing by Mobile Robots: Gathering
- Distributed Anonymous Mobile Robots: Formation of Geometric Patterns
- Convergence Properties of the Gravitational Algorithm in Asynchronous Robot Systems
- Fault-Tolerant Gathering Algorithms for Autonomous Mobile Robots
- Characterizing geometric patterns formable by oblivious anonymous mobile robots
- Arbitrary pattern formation by asynchronous, anonymous, oblivious robots
- Gathering few fat mobile robots in the plane
- Title not available (Why is that?)
- Local spreading algorithms for autonomous robot systems
- Distributed Computing – IWDC 2005
- Non-uniform circle formation algorithm for oblivious mobile robots with convergence toward uniformity
- A distributed algorithm for gathering many fat mobile robots in the plane
- The gathering problem for two oblivious robots with unreliable compasses
- Rendezvous of two robots with visible bits
- Forming sequences of geometric patterns with oblivious mobile robots
- Rendezvous of Two Robots with Constant Memory
- Asynchronous Pattern Formation by Anonymous Oblivious Mobile Robots
Cited In (27)
- Explicit Communication Among Stigmergic Robots
- The mutual visibility problem for fat robots
- Mutual-visibility problems on graphs of diameter two
- Arbitrary pattern formation by asynchronous opaque robots with lights
- Mutual visibility in graphs
- Asynchronous Gathering Algorithms for Autonomous Mobile Robots with Lights
- Mutual visibility of luminous robots despite angular inaccuracy
- Optimal exclusive perpetual grid exploration by luminous myopic opaque robots with common chirality
- Mutual-visibility in strong products of graphs via total mutual-visibility
- Mutual-visibility sets in Cartesian products of paths and cycles
- The canonical amoebot model: algorithms and concurrency control
- Uniform circle formation for swarms of opaque robots with lights
- Mutual visibility on grid by asynchronous luminous robots
- Fault-tolerant complete visibility for asynchronous robots with lights under one-axis agreement
- TRAVERSING A GRAPH IN GENERAL POSITION
- Total mutual-visibility in graphs with emphasis on lexicographic and Cartesian products
- Mutual visibility by asynchronous robots on infinite grid
- Variety of mutual-visibility problems in graphs
- Fault-tolerant mutual visibility without any axis agreement in presence of mobility failure
- Perpetual torus exploration by myopic luminous robots
- Total mutual-visibility in Hamming graphs
- The \(k\)-distance mutual-visibility problem in graphs
- Mobile Robots with Uncertain Visibility Sensors: Possibility Results and Lower Bounds
- Formation of General Position by Asynchronous Mobile Robots Under One-Axis Agreement
- Meeting in a polygon by anonymous oblivious robots
- On the mutual visibility in Cartesian products and triangle-free graphs
- On the computational power of energy-constrained mobile robots: algorithms and cross-model analysis
This page was built for publication: Mutual visibility by luminous robots without collisions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q528203)
