Visibility and Pattern Formation Problems in Robotics

Abstract

We study four problems related to robotics and computational geometry. We consider the Mutual Visibility problem for fat robots with lights: given a set of n ≥ 1 unit disk robots in the Euclidean plane, the robots must reposition themselves to reach a configuration where they all see each other. 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 for point robots [28]. We consider the Pattern Formation problem for fat robots: given a set of n ≥ 1 unit disk robots in the Euclidean plane, the robots must reposition themselves to form a given target pattern. We consider this problem for robots with lights and reduce the number of colors needed. In particular, we present an algorithm requiring 7 colors when scaling the target pattern is allowed and an 8-color algorithm if scaling is not allowed. Our algorithms run in O(n) rounds plus the time needed for the robots to elect a leader. We also consider robots with memory and present an algorithm that runs in O(n) + O(q log n) rounds, where q > 0 is related to Leader Election. We assume that the robots have a small O(1)-sized memory that they can use to store information, but that cannot be communicated to the other robots. We consider the shortest paths of mutually visible robots: given a set of n point robots inside a simple polygon P, the task is to move the robots from their starting positions to their target positions along their shortest paths, while the mutual visibility of these robots is preserved. We present an O(mn) time algorithm, where m is the complexity of the polygon, when all the starting positions lie on a line segment S, all the target positions lie on a line segment T, and S and T do not intersect. We also argue that there is no polynomial-time algorithm, whose running time depends only on n and m, that uses a single strategy for the case where S and T intersect.