Mutual Visibility for Robots with Lights Tolerating Light Faults

Abstract

We consider the distributed setting of N autonomous mobile robots that operate in Look-Compute-Move cycles and communicate with other robots using colored lights (the robots with lights model). We study the fundamental Mutual Visibility problem of repositioning N robots on a plane so that each robot is visible to all others. We assume obstructed visibility under which a robot cannot see another robot if a third robot is positioned between them on the straight line connecting them. We are interested in light fault-tolerant algorithms; all existing algorithms for this problem are not tolerant to failures on the lights. Therefore, any algorithm for MUTUAL VISIBILITY is required to provide visibility to all N robots, independently of the behavior of the robots with faulty lights. We model light failures as crash faults in which each faulty agent is allowed to set its light to some color, and once the light is set to that color, that color will remain indefinitely thereafter for that agent. In this paper, we provide two algorithms, one tolerant against one faulty robot using 2 colors, which is optimal, and another against (up to) N-2 faulty robots using 4 colors, in a system of N > 3 robots.