How to Make Fat Autonomous Robots See all Others Fast?

摘要

The coordination problems arising in a team of autonomous mobile robots have received a lot of attention in the distributed robotics community. Along those lines, we study in this paper the problem of coordinating autonomous mobile robots to reposition on a convex hull so that each robot sees all others. In particular, we consider non-transparent fat robots operating in the 2-dimensional plane. They are abstracted as unit discs and they make local decisions with vision being the only mean of coordination among them. We develop a (deterministic) distributed algorithm that solves the problem for a team of N ≥ 3 fat robots in O(N) time avoiding collisions under the semi-synchronous scheduler. The main idea is to enforce the robots to reach a configuration in which (i) the robots' centers form a convex hull; (ii) all robots are on the convex hull's boundary; and (iii) each robot can see all other robots. The result is achieved assuming some reasonable conditions on the input configuration and showing that starting from any input configuration that satisfies our conditions, robots reach such a configuration in linear time and terminate.