Local Algorithms for Robotic Formation Problems

Friedhelm Meyer auf der Heide ( Heinz Nixdorf Institute & Computer Science, Department University of Paderborn )

Assume a scenario with a set of autonomous mobile robots having initial positions in the plane. Their goal is to move in such a way that they eventually reach a prescribed formation. Such a formation may be a straight line between two given endpoints (short communication chain), a circle or any other geometric pattern, or just one point (gathering problem). In this talk, I consider simple local strategies for such robotic formation problems: the robots are limited to see only robots within a bounded radius; they are memoryless, without common orientation. Thus, their decisions where to move next are solely based on the relative positions of robots within the bounded radius. I will present local strategies for short communication chains and gathering, and present runtime bounds assuming different time models. All previous algorithms with a proven time bound assume global view on the positions of all robots.