## Oct 20 2000:

A presentation based on
"Distributed anonymous mobile robots:
formation of geometric patterns," by
Suzuki, I. and Yamashita, M.
*SIAM Journal on Computing* (1999) **28**,4, pp. 1347-63

Speaker: David Goggin, ICS, UC Irvine

Consider a system of multiple mobile robots in which each robot,
at infinitely many unpredictable time instants, observes the positions of
all the robots and moves to a new position determined by the given
algorithm. The robots are anonymous in the sense that they all execute the
same algorithm and they cannot be distinguished by their appearances.
Initially they do not have a common x-y coordinate system. Such a system
can be viewed as a distributed system of anonymous mobile processes in
which the processes (i.e., robots) can "communicate" with each other only
by means of their moves. In this paper we investigate a number of
formation problems of geometric patterns in the plane by the robots.
Specifically, we present algorithms for converging the robots to a single
point and moving the robots to a single point in finite steps. We also
characterize the class of geometric patterns that the robots can form in
terms of their initial configuration. Some impossibility results are also
presented.