Distributed algorithms for formation of geometric patterns with many mobile robots

We discuss a method for controlling a group of mobile robots in a distributed manner. The method is distributed in the sense that all robots, or most of the robots in some cases, plan their motion individually based upon the given goal of the group and the observed positions of other robots. We illustrate the method by showing how a large number of robots can form an approximation of a circle, a simple polygon, or a line segment in the plane. We also show how the robots can distribute themselves nearly uniformly within a circle or a convex polygon in the plane. Finally, we show how the robots can be divided into two or more groups. It turns out that in many cases most robots execute an identical, simple algorithm. The performance of the method is demonstrated by simulation. © 1996 John Wiley & Sons, Inc.