2022/06/29 by Rusul J. Alsaedi, Alsaedi, Rusul J., Joachim Gudmundsson +3 · 3 citations
Computer Science · Engineering · #Computational Geometry (cs.CG) #FOS: Computer and information sciences #Modular Robots and Swarm Intelligence #Optimization and Search Problems #Robotic Path Planning Algorithms
paper · pdf · doi:10.48550/arxiv.2206.14423
openalex publication_date 2022/06/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Given a set of n≥ 1 unit disk robots in the Euclidean plane, we consider the fundamental problem of providing mutual visibility to them: the robots must reposition themselves to reach a configuration where they all see each other. This problem arises under obstructed visibility, where a robot cannot see another robot if there is a third robot on the straight line segment between them. This problem was solved by Sharma et al. [ICDCN, 2018] in the luminous robots model, where each robot is equipped with an externally visible light that can assume colors from a fixed set of colors, using 9 colors and O(n) rounds. In this work, we present an algorithm that requires only 2 colors and O(n) rounds. The number of colors is optimal since at least two colors are required even for point robots [Di Luna et al., Information and Computation, 2017].