Constant-Time Complete Visibility for Robots with Lights: The Asynchronous Case
Open Access
- 9 February 2021
- journal article
- research article
- Published by MDPI AG in Algorithms
- Vol. 14 (2) , 56
Abstract
We consider the distributed setting of N autonomous mobile robots that operate in Look-Compute-Move (LCM) cycles and use colored lights (the robots with lights model). We assume obstructed visibility where a robot cannot see another robot if a third robot is positioned between them on the straight line segment connecting them. In this paper, we consider the problem of positioning N autonomous robots on a plane so that every robot is visible to all others (this is called the Complete Visibility problem). This problem is fundamental, as it provides a basis to solve many other problems under obstructed visibility. In this paper, we provide the first, asymptotically optimal, time, color algorithm for Complete Visibility in the asynchronous setting. This significantly improves on an -time translation of the existing time, color semi-synchronous algorithm to the asynchronous setting. The proposed algorithm is collision-free, i.e., robots do not share positions, and their paths do not cross. We also introduce a new technique for moving robots in an asynchronous setting that may be of independent interest, called Beacon-Directed Curve Positioning.
Keywords
This publication has 34 references indexed in Scilit:
- Leader election and gathering for asynchronous fat robots without common chiralityJournal of Discrete Algorithms, 2015
- Getting close without touching: near-gathering for autonomous mobile robotsDistributed Computing, 2015
- Logarithmic-Time Complete Visibility for Robots with Lights2015
- Gathering fat mobile robots with slim omnidirectional camerasTheoretical Computer Science, 2014
- Distributed Computing by Oblivious Mobile RobotsSynthesis Lectures on Distributed Computing Theory, 2012
- A New Approach for Analyzing Convergence Algorithms for Mobile Robots2011
- Connectivity-Preserving Scattering of Mobile Robots with Limited Visibility2010
- Characterizing geometric patterns formable by oblivious anonymous mobile robotsTheoretical Computer Science, 2010
- Gathering few fat mobile robots in the planeTheoretical Computer Science, 2009
- Local spreading algorithms for autonomous robot systemsTheoretical Computer Science, 2008