Optimal Randomized Complete Visibility on a Grid for Asynchronous Robots with Lights

• DOI: 10.15803/ijnc.11.1_50
• Publication Date: 2021-01-14T22:12:06Z
• Authors: Gokarna Sharma; Ramachandran Vaid...; Jerry L. Trahan
• Keywords: Visibility

We consider the distributed setting of N autonomous mobile robots that operate in Look-Compute-Move (LCM) cycles and communicate with other using colored lights (the model. This model assumes obstructed visibility where a robot cannot see another if third is positioned between them on straight line connecting them. In this paper, we movements to be grid (integer plane) unbounded size. any given step at point can move only an adjacent its north, south, east or west. The naturally discretizes 2-dimensional plane finds applications many real-life robotic systems. Complete Visibility problem reposition (starting arbitrary, but distinct, initial positions) so that, termination, each visible all others. objective simultaneously minimize (or provide trade-off between) two fundamental performance metrics: (i) time solve (ii) area occupied by solution. also number distinct colors used light. first O(max{D,N})-time algorithm for asynchronous setting, D diameter configuration. final configuration O(N^2); both are optimal. randomized no symmetry breaking mechanism available robots. our depends whether leader election required not: 17 not 32 required.