数理解析研究所講究録
第 833 巻 1993 年 142-152

142

Cooperative Control Algorithms for
Anonymous Mobile Robots
鈴木一郎 (Ichiro Suzuki)
Department of Electrical Engineering and Computer Science
University of Wisconsin–Milwaukee
P.O. Box 784, Milwaukee, WI 53201, U.S.A.

suzuki@cvax.cs.uwm.edu
山下雅史 (Masafumi Yamashita)
広島大学工学部
724 東広島市鏡山町

mak@se.hiroshima-u.ac.jp
Abstract

A system consisting of multiple mobile robots in which the robots can see each otherby their eye sensors but they are not equipped with any communication system, can beviewed as a distributed system in which the components (i.e., robots) can “communicate“
with each other only by means of their moves. We use this system to investigate,
through a case study of a number of problems on the formation of geometric figures in
the plane, the power and limitations of the distributed control method for mobile robots.
In the distributed method, each robot executes a simple algorithm and determines its
movement adaptively based on the observed movement of other robots, so that the
robots as a whole group will achieve the given goal. Each robot is a mobile processor
with an eye sensor which, at every tick of its local clock, observes the positions of all therobots and moves to a new position. The local clocks of the robots are not necessarily
synchronized, and initially, the robots do not have a common x-y coordinate system.
The problems we discuss include (1) converging the robots to a single point, (2) moving
the robots to a single point, (3) agreement on a single point, (4) agreement on the unit
distance, (5) agreement on direction, and (6) leader election. We develop algorithms
for solving some of these problems under various conditions. Some impossibility results
are also presented.

143
1

Introduction

In the last several years, the interest in the distributed control method for multiple mobile
robots has increased considerably among the researchers in the U.S. and $Japan[1,2,3,4$ ,6, 7]. The main idea of the method is to let each robot execute a simple algorithm anddetermine its movement adaptively based on the observed movement of other robots, sothat the robots as a whole group will achieve the given goal. This approach has been shown
to be very promising for the generation of certain patterns and collision avoidance. In theearlier works on distributed robot control, the main emphasis is on the development ofheuristic algorithms for various problems and the presentation of simulation results, and inmany cases, formal discussions on the correctness and performance of the algorithms are
not given [3] [6].
A robot system in which the robots can communicate with each other by radio, forexample, such as a system of radio-controlled vehicles or spaceships, can be considered asa distributed system whose communication topology is a complete graph. Therefore, such
systems can be analyzed using the standard techniques developed in the field of distributed
computing (although such analyses are by no means easy). In this paper, we consider a system consisting of multiple mobile robots in which the robots can see each other by their eye
sensors, but they are not equipped with any communication system. We view this system as
a distributed system in which the components (i.e., robots) can “communicate” with eachother only by means of their moves. Clearly this system is a suitable model for studying
the distributed control method mentioned in the previous paragraph. As the reader might
expect from the assumptions we make about the robots below, the study reveals delicate
interplay of a number of key concepts of distributed computing, such as synchrony and asynchrony, communication, termination detection, self-stabilization, anonymity of processors,
and knowledge (in a casual sense).
A basic problem for such a robot system is to design an algorithm such that, if all therobots execute it individually, then the robots as a whole group will eventually form thegiven geometric figure. The main goal of this paper is to present some theoretical results
related to this problem. The results presented here provide useful insights that will help us
to answer certain fundamental questions, such as whether the given algorithm really solves
the given problem and, for that matter, whether the given problem is solvable at all in astrict sense by a distributed algorithm. This work is a step toward the ultimate goal ofdetermining exactly what class of problems are solvable in a distributed manner.
We assume that each robot is a mobile processor having an eye sensor which, at everytick of its local clock, observes the positions of all the robots (including itself) in terms of its
own local x-y coordinate system and moves to a new position. (The new position need not
be distinct from the current position.) The robot (or the algorithm it uses to compute thenew position) is oblivious if the new position is determined only from the positions of therobots observed at that time instant. Otherwise, it is not oblivious and the new position
may depend also on the observations made in the past. The local clocks of the robots are notnecessarily synchronized, and thus the clock of a robot may tick much more frequently thanthat of some other robots. It is assumed that initially, the robots do not have a common
sense of direction and unit distance, and hence the local x-y coordinate system of a robot
may not be the same as that of another robot. Thus, the robots do not have a common
x-y coordinate system. Finally, we assume that the robots are anonymous, in the sense144
that they all use the same algorithm for determining the next position, and they cannot be
distinguished from their appearances. This implies, for example, that depending on whatmovements are allowed, a robot that observes other robots at two consecutive clock ticks
may not be able to tell which robot has moved to which position between the two ticks.
Under these assumptions, we first consider the problem of converging all the robots
toward a single point. Note that since the robots do not have a common x-y coordinate
system, we cannot simply use an algorithm such as “move toward point $(0,0)$ . For thisproblem, we give an oblivious algorithm that works correctly even if robots are added ordeleted from the system a finite number of times. (For simplicity, in this paper we assume
that a robot can move to its new position instantaneously.) We then discuss the subtletyof the problem by showing how certain minor changes in the algorithm or the assumption
affect the possibility of achieving the goal. Also, we show that the set of geometric figures
realizable by any deterministic algorithm must necessarily include the configuration in which
all robots are located at the same position.
Next, we investigate the problem of letting the robots agree on a common x-y coordinate
system. Clearly, such an agreement can greatly reduce the complexity of subsequent motion
coordination algorithms. The problem consists of three subproblems, agreement on theorigin, agreement on the unit distance, and agreement on the direction of the positive xaxis. We first consider a related problem of moving (instead of converging) two robots to asingle point, and show that this problem can be solved by a nonoblivious algorithm but notby any oblivious algorithm. Since two robots can agree on the origin if they can move toa single point, this result shows that agreement on the origin for two robots is solvable bya nonoblivious algorithm. Moreover, we show that agreement on the origin is solvable by anonoblivious algorithm even for the case $n>2$ , where is the number of robots. We also
show that agreement on the unit distance is solvable by a nonoblivious algorithm if either$n=2$ or $n>2$ and no two robots occupy the same position initially. On the other hand, weshow that agreement on the direction is not solvable even if $n=2$ . This last result showsthat the robots cannot agree on a common x-y coordinate system in general.
Finally, we consider the case in which the robots have a sense of direction (i.e., thedirection of the positive X-axis is the same for all robots). For this case, we show thatthe robots can agree on a common x-y coordinate system, and that the robots can elect aleader provided that no two robots occupy the same position initially. Once a unique leader
is elected, the robots can be moved to form any geometric figure.
As a final note of this section, we remark that if the local clocks are synchronized,then the robots can easily communicate with each other by means of the distances of theirmoves. Therefore, many problems on synchronized robot systems can be reduced to thecorresponding problems on anonymous complete networks, and can be analyzed using thetechniques developed, for example, in [8].
We present necessary definitions and basic assumptions in Section 2. Section 3 discusses
the problem of converging the robots to a point. Agreement on a common coordinate system
is discussed in Section 4. In Section 5 we consider the case in which the robots have a senseof direction. Concluding remarks are found in Section 6.
In this abstract, we present only the key ideas. All the details and the missing proofs
can be found in the full paper.
$n$

145
Definitions and Basic Assumptions

2. (Many of the results given in the
We consider robots in 2-dimensional Euclidean space
paper also hold for robots in 3-dimensional Euclidean space.) We fix an $x-y$ coordinate
system and specify the position of a robot as a pair $(x,y)$ of real numbers using $Z$ . It is
assumed, however, that is used only for specifying the positions of robots and the robots
have no information on $Z$ .
A robot is modeled as a mobile processor with sufficiently large memory space, an
artificial eye sensor, and a local clock . It can see and locate other robots in its visibility
range with respect to its local $x-y$ coordinate system , and also move to any position
specified as coordinates of . The coordinate system
is local to , in the sense that two
may
have
different
local
coordinate
systems. We denote by
robotsthe clock readingof. at real time . (The robots have no access to real time.) We assume that for any$c_{r}(t)<c_{r}(t^{/})$ if $t<t’$ , and that for any non-negative integer, therereal times and$c_{r}(t)=k$. The clocks are said to be synchronized if there
exists a real time such thatis a constant integer such that for any and $t-c_{r}(t)=d$ holds. Otherwise, they aresaid to be asynchronous, and many different degrees of $aes_{\sim}vnchrony$ can be defined. If thelocal clocks are synchronized and the number of robots never changes, then for simplicity,
we may assume that when robot is initialized, the clock reading of is .
Let be the set of all possible configurations (i.e., contents) of the memory of a robot. Let be the set of real numbers. An algorithm for is a function from to the set, such thatis the set of possible next positions of (given in termsof subsets ofof ) when the memory configuration of is . If
is a singleton for each , thenis said to be deterministic. Otherwise, randomly selects fromits next position (andthere),
and
hence
a
moves
is randomized algorithm. Note that the identifier is not anargument of .
Letbe the set of the positions of all robots, including itself, given in terms of .
shows the positions of the robots from the viewpoint of robot . We naturally
Tbat is,assume that knows its current position with respect to. Note that may be able to, since cannot see those robots that are outside
obtain only a partial information on
its visibility range. (But we assume that all robots have the same eye sensor.) So we letdenote the set of the positions of all robots that are visible from . For
example, if can see only those objects that are within distance , then $viz(P_{r})$ contains
the positions of those robots that are within distance from . To simplify the discussion,in this paper, we assume that has unlimited visibility, and hence $viz(P_{r})=P_{r}$ . We
assume that observes the positions of other robots every time its local clock reaches aninteger value, and that only those positions that have been observed can be used as datafor determining the possible next positions of . This means that the robots never observe,
for example, the velocity of other robots.
From the preceding discussion, the behavior of robot is given as follows. Here,is afixed (common) initial configuration of the memory of a robot.
$E^{2}$

$Z$

$Z$

$r$

$c_{r}$$Z_{r}$$Z_{r}$$Z_{r}$$r$$c_{r}(t)$$t$$c_{r}$$t$$k$$t^{/},$$t$$c_{r}$

$d$

$t,$

$r$

$r$

$R$

$r$

$0$

$c_{r}$$I$$\mathcal{I}$$r$$R^{2}$$\mathcal{I}$$\psi$$\psi(I)$

$r$

$I$

$r$

$Z_{\tau}.$$I$$\psi(I)$$\psi$$\psi(I)$$r$$\psi$$r$$\psi$$P_{r}$$r$$Z_{\tau}$$P_{r}$$r$$Z_{r}$$r$$P_{r}$$r$$r$$viz(P_{r})\subseteq P_{r}$$r$$\delta$$r$$\delta$

$r$

$r$

$r$

$r$

$I_{0}$$r$[Behavior of robot ]$r$;
Wait until the clock reading ofrepeat$/*start$ Move $Action^{*}/$$I$$:=I_{0}$$c_{r}$

becomes an integer ;
$s$

146
be the positions of the robots at local time ;$I:=I\cup\{(p, s)|p\in viz(P_{r})\}$ ;;Randomly select an element fromMove to ;$:=s+1$ ;$/*End$ Move $Action^{*}/$
reaches the value ;Wait until
until forever.

Let$P_{r}$$s$$\psi(I)$

$q$

$q$

$s$

$s$

$c_{r}$

The assignment $:=I\cup\{(p, s)|p\in viz(P_{r})\}$ means that robot stores information
obtained at local time with tag , in order to distinguish it from the information
obtained at different times. Note that the robots are anonymous in the following sense: (1)and function are common to all robots, (2) the identifier ofthe initial configuration
robot is not an argument of , and (3) $viz(P_{r})$ contains only the positions of robots (butnot their identities).
For the sake of simplicity, we assume that a robot can move to any position instantaneously. In other words, we assume that the time necessary for executing a move action, aseries of instructions between two comments (Start Move Action” and “End move Action”,
is negligibly small compared with one unit time of each local clock, and that whenever arobot observes, all robots have already reached their destinations and are stationary.
Because of the assumption for local clock , the execution of move actions of robots
is fair. Every robot executes its move action infinitely many times. Finally, note that if
synchronized clocks are available, by definition, all robots move simultaneously.
Let be a predicate over the set of multisets of points which is invariant under any
motion (i.e., rotation and parallel transformation) and similarity. In what follows, predicatesover multisets we will discuss in this paper are assumed to satisfy the above condition. Letbe such a predicate. We are interested in designing algorithms (functions)such that,for example, the robot obeying
converge to points (with respect to coordinate system$Z)$ such that predicate
holds, no matter where the robots are initially distributed. Since
robots never can perceive the absolute coordinate system $Z$ , all we can expect for algorithms
is to form a figure which is similar to the goal figure. The restriction for predicates wasintroduced because of this reason.
This framework permits us to add $and/or$ remove robots dynamically. Although we will
not state it explicitly, all algorithms we will discuss in this paper correctly work (after small
modifications for some algorithms), even if the number of robots changes dynamically.
Algorithms having this property can be seen as self-stabilizing algorithms, which solve
problems in spite of any transient failures. Finally, throughout this paper, we reserve
symbol for denoting the number of robots.
$I$

$r$

$viz(P_{r})$

$s$

$s$

$I_{0}$$\psi$$r$$\psi$$r$$c_{r}$

$r$

$\pi$

$\psi$$\pi$$\psi$

$\pi$

$n$

3

Convterging to a Point

The convergence problem for a predicate is the problem of designing an algorithm suchthat the robots obeying the algorithm converge to points for which holds, regardless of
their initial distribution. Define a predicate
as $\pi_{point}(p_{1}, \ldots,p_{n})=true$ iff $p_{i}=p_{j}$for any $1\leq i,j\leq n,$ $2\leq n$ . In this section we discuss the convergence problem for,which we call POINT. That is, POINT is the problem of converging all the robots to asingle point. The aim of this section is not only to propose algorithms for POINT, but also
$\pi$

$\pi$

$\pi_{point}$$\pi_{point}$

147
to discuss relations between additional assumptions we can make and possible algorithms.
We also discuss a limitation of deterministic algorithms.
be the current positions of robots with respect to . Although may not occupyLetthe origin of , it can be assumed that is at the origin, without loss of generality.
First of all, let us propose a deterministic algorithm for solving POINT. Let $P$ andbe a set of points and a farthest point in $P$ from the origin, respectively. Define a function
Since we assume that a robot is at the origin
as $\psi_{point}(P)=\{p/2\}$ for any
always moves to the midpoint of a farthest
executingof its coordinate system
robots and itself. Notice that the next position of such is determined only from the current), regardless of the rest of the history that
positionsof the robots (with respect todoes not include time information.) Such an
might have observed. (Notice also thatalgorithm is said to be oblivious. All algorithms we will discuss in this section are oblivious
deterministic.
$Z_{r}$$P_{r}$$Z_{r}$

$r$

$r$

$p$

$P^{1}$$\psi_{point}$$Z_{r},$$r$$\psi_{point}$

$r$

$r$

$I$

$Z_{r}$$P_{r}$$P_{r}$$r$

Theorem 1 Function$\psi_{point}$

corrrectly solves problem POINT.

Suppose we use point instead of $p/2$ as the next position. Consider the case of two
robots. If their clocks are synchronized, then the two robots simply exchange their positions
and never converge to a point. In fact, using an argument similar to that in the proof of
Theorem 1, we can prove the following theorem. Let $\psi_{point1}(P)=\{p/b\}$ for any $P$ , whereis a constant real number.
$p$

$b$

Corollary 1 2 Function$\psi_{point1}$

correctly solves problem POINT iff $b>1$ .

As another possible candidate for a POINT algorithm, one may choose function
is a point which is uniquely determined from the positions of robots, indepen$=q$ , whereof , such as the center of gravity. It is easy to see
dently of how they look from the viewthat by using an argument similar to that in the proof of Theorem 1, one can show that thisnew algorithm solves problem POINT, in this particular case of the center of gravity. Notethat if the local clocks are synchronized, then it can solve problem POINT very efficiently
since all robots simultaneously move to the center of gravity in the first move. However, it
is not clear whether or not
can solve POINT more efficiently thanin general
positions.
more
information
on
the
robot
using
, where is a nearest point in $P$ from the origin (except the
Function
points at the origin), seems to be a better algorithm than
, since finding a nearest
always moves a robot torobot should be easier than finding a farthest one. Note thatthe midpoint of the nearest robot (except those at the same point) and itself. Unfortunately,
andcannot solve POINT. To see this, consider the case of four robots(resp.
initially distributed in such a way thatandand ) occupy close positions.
(resp.
Suppose that none of them move at the same time. Then, robots
andandconverge to a point, which is unachievable within a finite time. Hence,cannotsolve POINT.
The next theorem states that any problem solvable by a deterministic algorithm is.
actually solvable by an algorithm for POINT, such as$\psi_{point2}(P_{r})$$q$$P_{r}$$r$$\psi_{point2}$$\psi_{poi\tau\iota t}$$\psi_{p\dot{\alpha}\cdot,\iota t3}(P)=q/2$$q$$\psi_{poir\iota.t}$$\psi_{point3}$$\psi_{poi\tau\iota t3}$$r_{1},$ $r_{2},$ $r_{3}$$r_{1}$$r_{2}$$r_{4}$$r_{4}$$r_{3}$$r_{1}$$r_{4})$$r_{3}$$r_{2}$$\psi_{point3}$$\psi_{point}$

1Since an algorithm is a function from to the set of subsets of , strictly speaking,must bedefined as $\psi_{z)oint}(I)=\{p/2\}$ for any . Here, is a farthest point in from the origin, and $P=\{p|(p, s)\in$, where is the integer such that $(q, t)$ does not exist in for any and $t(>s)$ .
2The corollary is partially suggested by Saito[5].
$R^{2}$$\mathcal{I}$

$I$

$I\}$

$s$

$P$

$p$

$I$

$q$

$\psi_{poi,,t}$148
Theorem 2 Let be a predicate which is invariant under any motion and simila rity. Then
there is a dete rministic algorithm for solving the convergence problem for if and only if
for any $P,$ $\pi_{point}(P)$ implies $\pi(P)$ .
$\pi$

$\pi$

The proof of Theorem 2 uses the fact that “clones” remain indistinguishable forever,where two robots and are clones of each other if they share a coordinate system incommon (i.e., $Z_{r}=Z_{s}$ ), their local clocks always show the same value (i.e., $c_{r}=c_{s}$ )after they are initialized, and both their initial positions and the times at which they are
initialized, respectively, are the same. In what follows, we assume that no clones exist.
$r$

4

$s$

Agreeing on a Coordinate System

In the previous section, we investigated oblivious algorithms for POINT. Although oblivious
algorithms are useful (because they are easy to understand and to analyze), they have also
apparent drawbacks caused by the fact (actually the definition) that the robots cannot communicate with each other, since some common concepts (e.g., how large the unit distanceis, which direction north means, and so on) are inevitable for communication, but remembering the concepts requires memory. This section investigates the problem of obtaining acommon coordinate system. Assuming that robots share a coordinate system in common,roughly speaking, robots can be named in terms of their coordinates, and a special leader
robot can be elected (if it is necessary) who controls all other robots. The fact is, however,that agreeing on a coordinate system is not possible in general. The problem of agreeing
on a coordinate system consists of the following three agreement problems; agreeing on theorigin, agreeing on the direction, and agreeing on the unit distance. We, therefore, examine
which ones of these are difficult. Through the investigation, we will learn what kind ofknowledge is essential to have a common coordinate system. We also explain a limitationof oblivious algorithms.

4.1

Agreeing on the Origin

Recall that an algorithm is said to solve POINT if the robots obeying converge to apoint from any initial distribution. This definition does not require that the process finishes, for example, does not assure that the robots willin finite steps. In fact, algorithm
move to a single point in finite steps. In this subsection we first consider the problem of truly
moving two robots to a single point in finite steps. We call this problem RENDEZVOUS.
We have the following negative result.
$\psi$$\psi$$\psi_{p\sigma int}$

Theorem 3 There is no oblivious algorithm to solve problem RENDEZVOUS.

On the other hand, we can show that there is an algorithm $\psi_{rendezvous}$ which is not
oblivious for solving RENDEZVOUS. Instead of describing \mbox{\boldmath $\psi$}rendezvous using mathematicalnotations, we explain the behavior of a robot executing it.
: When a robot wakes up for the first time, if it finds out that the
Algorithm
two robots reside at the same point, then there is nothing to do. Otherwise, if they occupy
different points, it transforms its coordinate systems
in such a way that (1) its position) becomes its origin(with respect toand (2) the position (with respect to ) of the$\psi_{re\tau\iota dezvous}$$r$$Z_{r}$$Z_{r}$$0_{r}$$Z_{r}$

149
other robot becomes $(0, a)$ for some real number $a>0$ . Then it moves one unit distance) towards its right to $(1, 0)$ .
(with respect toIt then continues to move one unit distance in the same direction on the $X$ -axis, whenever it wakes up until it observes that the position of changes for the second time.
If the trajectory of the first change of $s’ s$ position which observes is parallel with $r’ s$$X$ -axis, then it moves to $(0, a/2)$ ; otherwise, it moves to the intersection of $r’ sX$ -axis andthe line which includes the trajectory of .
$s$

$Z_{r}$

$s$

$r$

$s$

Theorem 4 Function$\psi_{rendezv\sigma us}$$\square$correctly solves problem RENDEZ $VO$ US.

Note that in $\psi_{rendezvous}$ , both robots know the point at which they will meet before
actually meeting each other there. (This is not true for the algorithms in the previous
section.) Thus $\psi_{rendezvms}$ almost solves the problem of agreeing on the origin, which wecall ORIGIN, for two robots. Here, we say “almost,” since if initially the two robots areat the same point , then neither of them ever moves, and hence neither of them will everbe convinced that the other robot has already woken up and recognized this situation.
Therefore, the robots will never be convinced that they have agreed on . To remove thissmall flaw, we may modify the instruction for this case as follows: If a robot finds that it
occupies the same point as the other robot when it wakes up at local time for the firsttime, then it moves to (1, t) with respect to its coordinate system, and restarts the algorithm. Since we assume that clones do not exist, it is easy to see that the two robots
never move to the same point infinitely many times. So we obtain:
$p$

$p$

$t$

$\psi_{e\tau\iota dezv\sigma t\iota s}$

Theorem 5 Problem ORIGIN is solvable, provided $n=2$ .

$\square$Now, we propose an algorithm
for ORIGIN for the case $n>2$ . Let $P$ be the setof the initial positions of the robots. The algorithm assumes that the robots are located at
distinct points. So we first transform any given initial distribution (in which two or morerobots may occupy the same point) into one in which this condition is satisfied. This canbe done by an algorithm
given below. Although we execute
before.
as preprocessing, confusion between the two algorithms never occurs. Algorithm
is an extension of the scattering process of $\psi_{rendezvous}$ we explained immediately before
Theorem 5.
$\psi_{origin}$$\psi_{scatter}$$\psi_{scatter}$$\psi_{origin}$$\psi_{scatte}.,$: Let
be the current positions of robots observes. Hence, always
Algorithm
resides at its origin. When wakes up, if no other robots are located at the origin, then it
stays there until all robots are located at distinct points. If there is at least one other robot
located at the origin, then it moves to $(a/4, a/4t)$ (with respect to) and repeats thisprocedure from the beginning. Here $a>0$ is the minimum distance between two positions
in , and is the current local time.
$\psi_{scatte7}.$$P_{r}$

$r$

$r$

$r$

$Z_{7}$$\square$$t$$P_{7}$

It is easy to check that in finite time, each robot occupies a distinct point, since no clones
exist.
Another technical difficulty is that in general, a robot cannot determine, given thepositions of the robots observed at two time instants
and , which robot has moved towhich point between
and . We overcome this problem by imposing a bound on the
maximum distance that any robot can move while another robot sleeps, so that the robot
at point at timemust be at the point closest to at time . Specifically, let $a_{r}>0$$t_{1}$$t_{1}$$p$$t_{1}$$t_{2}$$t_{2}$$p$$t_{2}$

150
be the minimum distance between two robots, when robot wakes up for the first time.
in the -th move. Here, $\epsilon>0$ is a
Then we allow to move at most distance(small) constant chosen by the algorithm. This restriction assures the above property, since-neighborhood of its initial position. Then any robot can correctly
remains inside the
which
robot
has
moved to which position even if it sleeps for a long time period.
recognize
Of course, this technique cannot be used in an algorithm in which a robot needs to moveover a long distance.
$r$

$k$

$a_{r}\epsilon/2^{k}$

$r$

$r$

$a_{r}\epsilon$: Let
be the initial distribution of robots, and let $CH(P)$ be the
Algorithm
convex hull of . It is assumed that the parameter mentioned above is chosen in sucha way that the farthest neighbor relation among vertex points of $CH(P)$ does not changeby their moves. When a robot wakes up for the first time, it decides . Next, it moves
towards a farthest robot from , if is located at a vertex point of $CH(P)$ ; otherwise, it
moves along the line perpendicular to the line connecting and . Let
be the direction
moves.
It then continues to move keeping the directionunchanged, until it observes that theposition of each robot changes at least twice.
knows the trajectoryThen,of $s’ s$ first move for each robot . We identify the
trajectory with the line including it, and let $L=\{l_{s}\}$ . Further let
be the envelop
Now, it chooses the center of gravity of the vertex points which define
polygon ofas
the (common) origin.
$P$$\psi_{origin}$$P$$\epsilon$$r$$a_{r}$

$r$

$s$

$r$

$r$

$s$

$d_{r}$$r$$d_{r}$$p_{s}$

$r$

$s$

$E$

$L^{3}$$E$$\square$

Theorem 6 Algorithm$\psi_{origin}$solves ORIGIN, provided $n>2$ .

Hence, we can conclude that ORIGIN is solvable.

Corollary 2 Problem ORIGIN iS solvable

4.2

口Agreeing on the Unit Distance

We call the problem of agreeing on the unit distance UNITDIST. First, using an algorithm
similar to \mbox{\boldmath $\psi$}rendezvous’ we can show the next theorem.

Theorem 7 UNITDIST is solvable, provided $n=2$ .

For the case $n>2$ , consider algorithm
given below. Again, it is assumed that
we usebefore executing \mbox{\boldmath $\psi$}unitdist so that no two robots are located at the same pointin .
$\psi_{unitdist}$$\psi_{scatter}$

$P$

: Let
Algorithm
be the initial distribution of robots, and let $CH(P)$ be theconvex hull of . It is assumed that the parameter is chosen in such a way that the set ofvertex points of the convex hull of the current positions of robots does not change by theirmove. When a robot wakes up for the first time, it decides . Then it moves towards
a farthest robot from , if is not a robot located at a vertex point of $CH(P)$ . If is arobot located at a vertex point of $CH(P)$ , then moves along the line perpendicular tothe bisector of the angle at . Let
be the direction moves.
$P$$\psi_{ur\iota itdist}$$P$$\epsilon$

$r$

$s$

$a_{r}$

$r$

$r$

$r$

$v$

$r$

$d_{r}$$v$$r$

3The envelope polygon of a set of lines is the polygon consisting of the finite length segments thatbound the infinite faces of the arrangement defined by .
$L$

$L$

151
unchanged, until it observes that theIt then continues to move keeping the direction
position of each robot changes at least twice.
of $s’ s$ first move for each robot . We identify theThen, knows the trajectory
trajectory with the line including it, and let $L=\{l_{s}\}$ . Let $E$ be the envelop polygon of .
Now, it chooses the shortest edge in $E$ as the (common) unit distance.
$d_{r}$$1_{s}$

$r$

$s$

$L$

$\square$

Theorem 8 Algorithm$\psi_{unitdist}$solves UNITDIS , provided $n>2$ .
$T$Hence, we can conclude that UNITDIST is solvable.

Corollary 3 Problem UNITDIST is solvable.

4.3$\square$Agreeing on Direction

This subsection shows that the third agreement problem of agreeing on direction is unsolvable in general. Let us call this problem DIRECTION.
Theorem 9 There is no algorithm for solving DIRECTION, even in the case of $n=2$ .

It is worth emphasizing that DIRECTION is unsolvable even if the local clocks aresynchronized. On the other hand, the other two agreement problems are trivially solvable
if the local clocks are synchronized.

Robots with a Sense of Direction

5

In this section, first we show that if the robots have a common sense of direction, thenthey can agree on a common coordinate system. As before, we assume that no two robots
occupy the same position in the initial distribution. It is easy to verify that the following
algorithm achieves this goal.

Algorithm $\psi_{coordinate}$ : When a robot wakes up, it moves one unit distance (with respect) to the east, and repeatedly does so until it observes that the position of each robot
tohas changed at least twice. Then knows the trajectories of $s’ s$ first move for each robot, and since
are parallel to each other, chooses the minimum distance $>0$ between any
two trajectories as the common unit distance, and the northern-most line as the common$X$ -axis.
Next, moves one unit distance to the north, and repeatedly does so, until it again
observes that the position of each robot has changed at least twice. Then, knows theof $s’ s$ first northbound move for each robot , and it chooses the easterntrajectories
most line as the common -axis.
$r$$Z_{r}$$r$$\ell_{s}$$\ell_{s}s$

$s$

$r$

$r$

$r$

$h_{s}$$s$$Y$$\square$Once the robots agree on a common coordinate system, they can elect a leader using
any suitable lexicographic ordering of their initial positions. (Recall that we may assume
that no two robots have the same initial position.) Here, a robot whose initial position is$(a, b)$ can communicate the values
and to other robots by moving along line $y=b$ first.
and then along line $x=a$ . This idea is similar to that in
Let be any predicate. The formation problem for is the problem of designing analgorithm such that the robots obeying the algorithm will eventually reach some points for
$a$

$b$

$\psi_{coordinate}$

$\pi$

$\pi$

152
holds in finite steps. For example, RENDEZVOUS is the formation problem for
for $n=2$ . By definition, if the formation problem for a predicate is solvable, so is
the convergence problem for the same predicate. Since the leader can compute the final
positions of all the robots that satisfy any given predicate and then communicate them tothe other robots using its movement by a technique similar to the one used in’
we obtain the following theorem.
which

$\pi$

$\pi_{point}$$\psi_{co\sigma’\cdot diate}\eta$Theorem 10 For any predicate
a sense of direction.

$\pi$, the formation problem for$\pi$

is solvable, if robots have

Corollary 4 The problems of forming a circle and a line segment are both solvable, if robots
have a sense of direction.

6

Concluding Remarks

We regarded a robot system as a distributed system in which components can communicate
with only by means of their moves, and investigated the possibility and impossibility ofsolving some of the problems related to the formation of geometric figures in the plane.
Our study indicates that the assumptions we make on the knowledge and capabilities of therobots can affect the difficulty of solving the given problem in a subtle way. We are currently
conducting a similar investigation on randomized algorithms and for the 3-dimensional case.
The results will be reported in a future paper.

References[1] R. Brooks, “Micro-brains for micro-brawn: Autonomous microrobots,” Proc. IEEE
Micro Robotics and Teleoperators Workshop, Hyannis, MA, November 1987.

[2] A. Flynn, “Gnat robots (and how they will change robotics),” Proc. IEEE Micro
Robotics and Teleoperators Workshop, Hyannis, MA, November 1987.
[3] K. Fujimura, “Model of reactive planning for multiple mobile agents,” Proc. IEEE Int.
Conf. on Robotics and Automation, Sacramento, CA, June 1991, pp. 1503-1509.
[4] T. Fukuda and S. Nakagawa, “Approach to the dynamically reconfigurable robot systems,” Journal of Intelligent and Robotics Systems 1, 1988, pp. 55-72.

[5] Y. Saito, private communication, 1992.
[6] K. Sugihara and I. Suzuki, “Distributed motion coordination of multiple mobile
robots,” Proceedings of the 5th IEEE International Symposium on Intelligent Control,
Philadelphia, Pennsylvania, September 1990, pp. 138-143.
[7] J. Wang and G. Beni, “Cellular robotic systems: Self-organizing robots and kinetic
pattern generation,” Proc. of the 1988 IEEE International Workshop on Intelligent
Robots and Systems, Tokyo, Japan, 1988, pp. 139-144.

[8] Yamashita, M., and Kameda, T., “Computing on anonymous networks,” Proc. 7th$ACM$ Symposium on Principles of Distributed Computing, 1988, 117-130.