The MathNet Korea
Information Center for Mathematical Science

논문검색

Information Center for Mathematical Science

논문검색

SIAM Journal on Computing
( Vol. 28 NO.4 / (1999))
Distributed Anonymous Mobile Robots: Formation of Geometric Patterns
Ichiro Suzuki, Masafumi Yamashita,
Pages. 1347-1363
Abstract Consider a system of multiple mobile robots in which each robot, at infinitely
many unpredictable time instants, observes that 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.
Contents 1. Introduction
2. Definitions and basic assumptions
3. Convergence and formation problems for a point
4. Achievable geometric patterns
5. Concluding remarks
5.1. Agreement on a common $x-y$ coordinate system
5.2. Issues of fault tolerance
5.3. Time complexity
5.4. Other open problems
Key words distributed algorithms, anonymous robots, mobile robots, multiagent systems, formation of geometric patterns
Mathmatical Subject Classification 68Q99