JAIST Repository
https://dspace.jaist.ac.jp/

Title

Networking Humans, Robots, and Environments:
Self‑Configurable Mobile Robot Swarms: Adaptive
Triangular Mesh Generation

Author(s)Lee, Geunho; Chong, Nak Young

CitationIssue Date

2013

Type

Book

Text version

author

URL

http://hdl.handle.net/10119/11622

RightsThis material is posted here with permission ofBentham Science Publishers. Copyright (C) 2013
Bentham Science Publishers. Geunho Lee and Nak
Young Chong (2013). Self‑Configurable Mobile
Robot Swarms: Adaptive Triangular Mesh
Generation. In Nak Young Chong (Eds.) Networking
Humans, Robots and Environments. Bentham Science
Publishers, pp.59‑75.
http://dx.doi.org/10.2174/97816080573131130101

Description

Japan Advanced Institute of Science and Technology

Self-Configurable Mobile Robot Swarms:
Adaptive Triangular Mesh Generation
Geunho Lee and Nak Young Chong
School of Information Science
Japan Advanced Institute of Science and Technology
Ishikawa, Japan

This material is posted here with permission of Bentham Science Publishers. Copyright (C) 2013 Bentham Science Publishers.
Geunho Lee and Nak Young Chong (2013). Self-Configurable Mobile Robot Swarms: Adaptive Triangular Mesh Generation. In Nak Young Chong (Eds.)
Networking Humans, Robots and Environments. Bentham Science Publishers, pp.59-75. http://dx.doi.org/10.2174/97816080573131130101

A BSTRACT. We address the problem of dispersing a large number of autonomous mobile
robots, for building wireless ad hoc sensor networks performing environmental monitoring and control. For this purpose, we propose the adaptive triangular mesh generation
algorithm that enables robots to generate triangular meshes of various sizes, adapting tochanging environmental conditions. A locally interacting, geometric technique allows eachrobot to generate a triangular mesh with its two neighbor robots. Specifically, we have assumed that robots are not allowed to have any identifiers, any pre-determined leaders orcommon coordinate systems, or any explicit communication. Under such minimal conditions, the positions of the robots were shown to converge to the desired distribution. This
convergence was mathematically proven and also verified through extensive simulations.
Our results indicate that the proposed algorithm can be applied to problems regarding thecoverage of an area of interest by a swarm of mobile sensors.

1. Introduction(a) uniform deployment(b) adaptive deployment

F IGURE 1. Uniform vs. adaptive triangular meshes of mobile robot swarms
With the advance of wireless and mobile networking technologies, much attention has
been paid to the use of large-scale swarms of simple, low-cost mobile robots for many
applications [1] [2]. With the goal of deployment of robot swarms in real environments,
researchers in swarm robotics have recently presented many fundamental coordination approaches such as self-configuration [9] [16], pattern formation [18] [19], flocking [20] [21],and consensus [22] [23]. Based on these coordination approaches, robot swarms are expected to perform a wide variety of real tasks, such as environmental or habitat monitoring [14] [17], exploration [24], search-and-rescue [25], odor localization [26]- [28], and soon.
In particular, for environmental or habitat monitoring, self-configuration of robot swarms
requires a type of collective behavior that allows robots to disperse themselves in a certain
area at a uniform spatial density. Thus, it is essential to properly coordinate the (relative)
positions of robots, and this issue has been widely reported in literature [5]- [15]. Taking
steps to further improve on those previous approaches, this work is aimed at presenting analgorithm to enable robot swarms to configure themselves adaptively in an area of interest2. BACKGROUND

3

with varying spatial densities. As illustrated in Fig. 1, robot swarms can explore an unknown area and detect and sense oil or chemical spills across the area. The contaminatedarea should be covered efficiently with mobile robots or sensors to investigate the degree
and extent of contamination as quickly as possible and, if possible, prevent the possible
expansion of the area. Therefore, in this paper, we address the problem of how to enableswarms of autonomous mobile robots to self-adjust their configuration or spatial density to
fit local environmental conditions.
Based on our prior research on swarm configuration [16] [17], we propose an adaptive
triangular mesh generation algorithm that enables robot swarms to explore an area, andto adjust the intervals between neighboring robots autonomously. The main objective isto provide robots with adaptive deployment capabilities to cover an area of interest more
efficiently with variable triangular meshes according to sensed area conditions. This also
can give us a more accurate picture of variations in the conditions of an area. In this chapter,the properties of the proposed algorithm are mathematically explained and the convergenceis proven. We also demonstrated through extensive simulations that a large-scale swarm ofrobots can establish a triangular mesh network, adapting to varying degrees of connection.
The results have been encouraging, and indicate that self-configurable robot swarms canbe deployed for environmental or habitat monitoring.
The rest of this chapter is organized as follows. Section 2 gives a brief description on
the state-of-the-art in the field of robot swarms. Section 3 presents the formal definitionsof the adaptive triangular mesh generation problem. Section 4 describes our approach, its
mathematical properties, and convergence at the equilibrium state. Section 5 summarizes
the results of simulations. Section 6 explains our conclusions.

2. Background
Decentralized control for robot swarms can be broadly classified into global and local
strategies, according to whether sensors have range limits. Global strategies [3] [4] [19]may provide fast, accurate, and efficient deployment, but are technically infeasible, andlack scalability as the number of robots increases. On the other hand, local strategies aremainly based on interactions between individual robots, inspired by nature. Local strategies can further be divided into biological emergence [5] [6], behavior-based [7], and virtual physics-based [8]- [15] approaches. Many of the behavior-based and virtual physicsbased approaches use such physical phenomena as electric charges [8], gravitational forces[9], spring forces [10] [14] [15], potential fields [11], van der Waals forces [12], and othervirtual models [13].
Robot swarm configurations achieved by the above-mentioned local interactions may
result in lattice-type networks. These configurations offer high level coverage and multiple redundant connections, ensuring maximum reliability and flexibility from the standpoint of topology. Depending on whether there are interactions among all robots, the networks can be classified as fully or partially-connected topologies [30]. The fully-connected
topologies have each robot interact with all other robots within a certain range simultaneously. Thus, those approaches might over-constrain individual robots, and frequently leadto deadlocks. However, using the partially-connected topology, robots interact selectively
with other robots, but are connected to all robots. For example, robots may choose to exert
force in a certain direction [14], where this selective interaction helps prevent them frombeing too tightly constrained. Therefore, robots may be able to achieve faster formation
without deadlocks [15].

3. PROBLEM STATEMENT

4

In our earlier work [17], we presented self-configuration of a robot swarm which enables a large number of robots to configure themselves into a 2-dimensional plane with geographic constraints. A locally-interacting geometric technique based on partially-connected
topology provides a unique solution that allows robots to converge to uniform distribution
by forming an equilateral triangle with two neighbors. By collecting this local behavior ofeach robot, a uniformly spaced swarm of robots was organized to cover an environment.
Unlike previous works [5]- [15], our approach first was to construct uniformly spaced equilateral triangles conforming to the borders of an unknown area, when the robot sensors are
subject to range and accuracy limitations. Second, an equilateral triangle lattice is built,
with a partially-connected mesh topology. Among all the possible types of regular polygons, equilateral triangle lattices can reduce the computational burden, and are less influenced by other robots, due to the limited number of neighbors, and are highly scalable. The
proposed local interaction is computationally efficient, since each robot utilizes only position information of two other robots. Our approach eliminates such major assumptions
as robot identifiers, common coordinates, global orientation, and direct communication.
More specifically, robots compute the target positions without requiring memories of pastactions or states, helping to cope with transient errors.

3. Problem Statement
Definition and Notation. We consider a swarm of mobile robots, denoted as r1 , · · · , rn .
It is assumed that all robots are within a swarm network configured by our previously
proposed self-configuration method [16] [17]. Each robot autonomously moves on a 2dimensional plane. They have no leader and no identifiers, do not share any common
coordinate system, and do not retain any memory of past actions. Due to limited sensing range, they can detect the position of other robots only within a certain distance. In
addition, robots do not communicate explicitly with other robots.
Let us consider a robot ri with local coordinates ~rx,i and ~ry,i , as illustrated in Fig.
2-(a). Here, ~ry,i defines the vertical axis of ri ’s coordinate system as its heading direction.
It is straightforward to determine the horizontal axis ~rx,i by rotating the vertical axis 90
degrees counterclockwise. The position of ri is denoted as pi . Note that pi is (0, 0) withrespect to ri ’s local coordinates. The distance between pi of ri and pj of another robot
rj is denoted as dist(pi , pj ). We define a uniform distance du , the predefined desiredinterval between ri and rj . As shown in Fig. 2-(b), ri detects the positions pj , pk , andpl of other robots located within its sensing boundary SB, yielding an observation set ofthe positions Oi (={pj , pk , pl }) with respect to its local coordinates. Next, ri can selecttwo robots rs1 and rs2 within ri ’s SB, which we call the neighbors of ri , and denote theirpositions, {ps1 , ps2 }, as Ni . Given pi and Ni in Fig. 2-(c), the triangular configuration,
denoted by Ti , is defined as a set of three distinct positions {pi , ps1 , ps2 }.
As mentioned above, if robots detect an event such as an oil or chemical spill within
the self-configured network, they attempt to cooperate with each other to cover the area as
efficiently as possible. The gradient in contamination density across the area forces robots
to adjust the intervals between neighboring robots. For a certain point pi occupied by ri
as presented in Fig. 2-(d), the densities are expressed by ki ranging between 0 < ki ≤ 1,
where ki = 0 represents the maximum density and ki = 1 corresponds to zero density.
Moreover, it is assumed that each robot can detect and measure densities for positions
occupied by other robots within SB, yielding a set of the densities Ki corresponding toindividual positions in Oi .

4. SOLUTION APPROACH

5SB

SB (Sensing Boundary)

pj

ri

pk

r
ry ,i

radius of SB

pi

(0,0)

du

ri

r
rx ,i

pl

(a) ri ’s local coordinatesSB(b) observation set Oi
SB

kj

ps2

kk

ps1

ki

ri

pi

kl
(c) triangular configuration Ti(d) density set Ki

F IGURE 2. Illustration of definitions and notations frequently used inthis chapter
Problem Definition. Now, we formally address the ADAPTIVE TRIANGULAR MESH
GENERATION problem as follows.

Given a swarm of mobile robots self-configured in a 2-dimensional plane, how can the
robots form triangular mesh patterns of various sizes adapting to varying environmental
conditions?
Our approach to the above problem enables robots to disperse themselves into equilateral triangular patterns of various sizes, according to changes in environmental conditions within an area of interest. The basic concept behind this approach is to enablerobots to form triangular configurations while changing their suitable distances dependingon locally-sensed information. In other words, given a uniform distance du , three neighboring robots configure an equilateral triangle with a side length proportional to the local
measurement data density.
4. Solution Approach
Regarding our solution approach, this section explains the generation of triangularmeshes adapting to the measurement data densities in the areas occupied by three neighboring robots, provides two important properties of the approach, and shows the convergence
into a desired stable configuration using Lyapunov’s theory.

4. SOLUTION APPROACH

6

A LGORITHM -1 A DAPTIVE T RIANGULAR M ESH G ENERATION
Function ϕtriangular (Oi , Ki )1

ps1 :=

min2

ps2 :=

3

φ := angle between ps1 ps2 and ri ’s local horizontal axisp∈Oi −{pi }[dist(pi , p)]minp∈Oi −{pi ,ps1 }[dist(ps1 , p) + dist(p, pi )]4

pct := (pct,x , pct,y ) // centroid of Ti (= {ps1 , ps2 , pi })

5
6

+ks2
ka := ki +ks1// average contamination density
3du
da := ka × √ // desired interval from pct

7

pti,x := pct,x + da cos(φ + π2 )

89pti,y := pct,y + da sin(φ + π2 )pti := (pti,x , pti,y ) // next target point

3

rs1

rs1

pi

rs2

ri
(a) 1st neighbor selection(b) 2nd neighbor selection

ps1 ps2

ps1

ks1
pct

ks2

pct

pi

ki

pti

da

(c) target point computation

ps2

ri

da

(d) moving to the target

F IGURE 3. Illustration of A LGORITHM -1
Algorithm Description. Here, we describe the adaptive triangular mesh generation
algorithm. As presented in A LGORITHM -1, the algorithm consists of a function ϕtriangularwhose arguments are Oi and Ki at each activation. Each time, ri first observes other robots
within Oi to select the closest neighbor rs1 as illustrated in Fig. 3-(a). If there exist two
or more candidates for rs1 , ri determines rs1 according to the high contamination density.
Secondly, as illustrated in Fig. 3-(b), the second neighbor rs2 within Oi is selected, such

4. SOLUTION APPROACH

7

that the total distance from the position ps1 of rs1 to pi passing through ps2 is minimized.
Similarly, if there are two or more candidates for rs2 , ri selects rs2 occupied in the areawith higher density of contamination. Then, as illustrated in Fig. 3-(c), ri measures theangle φ between the line ps1 ps2 connecting two neighbors and the horizontal axis of theobserving ri ’s coordinate system. Thirdly, the centroid pct in Ti (△pi ps1 ps2 ) is computed.
Moreover, based on ki , ks1 , and ks2 at each position occupied by ri , rs1 , and rs2 , ri finds
the local average density ka in Ti through the computation of (ki + ks1 √+ ks2 )/3. Then,from pct , ri calculates an appropriate interval as follows: da = ka × du / 3. Utilizing daand φ, ri calculates its target point pti = (pti,x , pti,y ) located on the same line as the previously calculated interval from pct and perpendicular to ps1 ps2 . Finally, ri moves toward
pti as illustrated in Fig. 3-(d). By repeating this process, ri can form a triangular meshdepending on the contamination densities.

Mathematical Properties. Let’s consider a triangle (whose centroid is pct ) △pi ps1 ps2(or Ti ) configured from the three positions occupied by ri , rs1 , and rs2 . By A LGORITHM 1 above, at time
√ t, ri in Ti (t) finds the next target point pti of which the line segment
pct pti is ka du / 3 in length and is perpendicular to ps1 ps2 in Fig. 3-(c). In other words, at
t + 1, the height of △pti ps1 ps2 is the straight line through pti and perpendicular to ps1 ps2 .
Similarly, since rs1 and rs2 also execute the same algorithm, it is easily seen that pct at t
is the orthocenter H at t + 1.
In Fig. 4, we denote pi , ps1 , and ps2 for simplicity as A, B, and C, respectively. The
lengths of lines AB, AC, and BC are denoted as c, b, and a, respectively. The points P ,Q, and R are the foot of the perpendiculars from the vertices C, B, and A to the vectors−−→ −→−−→
AB, AC, and BC, respectively. The angles ∠CAB, ∠ABC, and ∠BCA are denoted asα, β, and γ, respectively. Moreover, H is the orthocenter of △ABC. Moreover, H is theorthocenter of △ABC (Since pct and H exist in the same location under A LGORITHM -1,
we also use only H instead of pct ).

ps2 (C )

γ

b

Q

a
R

pct

α

(H )

β

pi

P

( A)

ps1
(B)

c
F IGURE 4. Illustrating the derivation of ri ’s position vector toward H

4. SOLUTION APPROACH

8

−−→
−→
−−→
Since AB and AC are linearly independent, AH can be defined as
−−→
−−→
−→
(1)
AH = xAB + y AC,−→−→α−AB, thewhere x and y are scaling coefficients. Since we can easily see that AP = b coscfollowing relation holds:−−→ −−→ −→
−→
−→
α −
P H = AH − AP = (x − b cos)AB + y AC.
c
−−→
−−→
Thus, the inner product between P H and AB can be expressed as follows:−−→ −−→
b cos α 2P H · AB = (x −)c + (bc cos α)y = 0.
c
Similarly, the following equation holds:−−→ −→
c cos α 2)b = 0.
(3)
QH · AC = (bc cos α)x + (y −bNow, using (2) and (3), the following simultaneous equations can be obtained:
(2)

(4)

cx − (b cos α)y= b cos α(c cos α)x + by

= c cos α.

By solving (4), we can obtain the coefficient x as follows:α(b−c cos α).
x = b cosbc
sin2 αUsing the cosine formula (b = c cos α + a cos γ), x is expressed as follows:
α cos γx = a cos.
c sin2 αIn addition, by utilizing the sine formula ( sina α = sinc γ ), x is rewritten as the following
equation:
α cos γx = cos
sin α sin γ .

Thus, if we do not consider the case of a right triangle, it is straightforward to rewrite x as
the following equation:
(5)

x=

1
tan β
=
.
tan α tan γ
tan α tan β tan γ

Similarly, the coefficient y can be represented as follows:
(6)

y=

tan γ
.
tan α tan β tan γ

Using the addition theorems of the trigonometric function, we can obtain the following
result:tan α tan β tan γ = tan α + tan β + tan γ.
Thus, (5) and (6) are rewritten as follows:
x =

tan β
tan α+tan β+tan γ

y

tan γ
tan α+tan β+tan γ .

(7)=With respect to a reference point O, (1) can be rewritten as follows:−−→ −−→ −→−−→ −→−−→ −→
AH = OH − OA = x(OB − OA) + y(OC − OA).

4. SOLUTION APPROACH

9−−→
Now OH can be represented in the following form:
−−→
−→
−−→
−−→
(8)
OH = (1 − x − y)OA + xOB + y OC.
−−→
Substituting (7) into (8), finally, OH is given by
−−→
−−→
−→
−−→ tan αOA + tan β OB + tan γ OC
OH =
.
(9)
tan α + tan β + tan γ

target pointof rs1

OH

(0,0)

r
rx ,i

ri ry,ips1
pct (= H )

r

pti

ps2
target pointof rs 2F IGURE 5. Illustrating two important properties: pct and position vector
Under the adaptive triangular mesh generation algorithm, there are two mathematicalproperties. First, pti is determined with pct in Ti (t) at t used as H at t + 1. Moreover,ri uses pct at t as a basis to generate Ti (t + 1) with dr from pct to pti at t + 1 (see Fig.
−−→
3-(c)). Secondly, since pct and H between t and t + 1 remain unchanged, OH in (9) is the
position vector toward pct with respect to the origin of ri ’s local coordinates as illustrated
in Fig. 5.
Motion Control. Under the adaptive triangular mesh generation algorithm, three neighboring robots attempt to cooperatively configure themselves into an equilateral triangle,
adapting to the density of contamination. As presented in Fig. 6, let’s consider the circumscribed an equilateral triangle △pti ps1 ps2 configured from three positions occupied by ri ,durs1 , and rs2 where the center is pct and the radius is da (= ka × √) in length. From the3
triangular configuration and the two mathematical properties above, we design the motionof ri by controlling the distance di from pct and the internal angle θi between pct pti andpct ps2 .
First, di in Fig. 6 is controlled by the following equation:(10)d˙i (t) = −a(di (t) − da ),where a is a positive constant. Indeed, the solution of (10) is obtained as follows:di (t) = |di (0)|e−at + da .
The solution converges exponentially to da as t approaches infinity. Secondly, θi is controlled by the following equation:(11)θ̇i (t) = k(θs1 (t) + θs2 (t) − 2θi (t)),

4. SOLUTION APPROACH

10

ps2

ps1

θ s2
θi

ri

di

θ s1

pct

da
pti

F IGURE 6. Motion control of a robot by the algorithm

where k is a positive number. Using the features of a triangle whose total external angles
is 2π, (11) can be rewritten as(12)2θ̇i (t) = k ′ ( π − θi (t)),
3where k ′ is 3k. Similarly, the solution of (12) is obtained as follows:′θi (t) = |θi (0)|e−k t + 32 π.

The soultion converges exponentially to 23 π as t approaches infinity. Note that (10) and(12) imply that the trajectory of ri converges to an equilibrium state [da 32 π]T . From Fig.
6, this also implies that the equilibrium for θi is defined as θi = θs1 since △pti pct ps1 and△pti pct ps2 are eventually congruent [16]. In order to show the convergence into the state[di (t) θi (t)]T , we will take advantage of stability based on Lyapunov’s theory [31]. The
convergence into the desired stable configuration is one that minimizes the energy level ofthe scalar function. Consider the following scalar function:(13)

fi (di , θi , θs1 ) =11(di − da )2 + (θs1 − θi )2 .
2
2This scalar function is always positive definite except when di 6= da and θi 6= θs1 . The
derivative of the scalar function is given as follows:f˙i = −(di − da )2 − (θs1 − θi )2 ,which is negative definite. The scalar function is radially unbounded, since it tends toinfinity as ||[di (t) θi (t)]T || → ∞. Therefore, the equilibrium state is asymptotically stable,
implying that ri reaches a vertex of the stable triangle.

5. SIMULATION RESULTS AND DISCUSSION11

Now we show the convergence of the algorithm for n robots. The n-order scalarfunction F is defined asnXfi (di , θi , θs1 ).
(14)
F=
i=1

It is straightforward to verify that F is positive definite and Ḟ is negative definite. F isradially unbounded, since it tends to infinity as t approaches infinity. Consequently, nrobots move toward the equilibrium state.
5. Simulation Results and Discussion

F IGURE 7. Simulation result for the whole deployment of 100 robots((a)∼(c): uniform configuration [16], (d)∼(i): adaptive configuration
with increasing center density of 0.7)
In this section, we describe simulations of filling an area of interest with a swarm ofrobots in order to show the validity of our proposed algorithm. In these simulations, we
represent the area of varying contamination density as a colored circle that will be sparsely
or densely populated with robots.

5. SIMULATION RESULTS AND DISCUSSION(a) uniform configuration

12(b) adaptive configuration

F IGURE 8. Adaptive triangular mesh generation with geographic borders(a) center density: 0.9(b) center density: 0.8(c) center density: 0.7(d) center density: 0.6

F IGURE 9. Simulation results according to varying contamination densities
First, in order to assist in understanding the self-configuration of robot swarms from an
initial distribution, Fig. 7 presents snapshots for the simulation result by 100 robots. Fromthe initial distribution in Fig. 7-(a), the robots configured themselves in the 2-dimensional
plane (see Fig. 7-(c)). After constructing an equilateral triangle network, we investigated5. SIMULATION RESULTS AND DISCUSSION

13

how they adapt their triangular mesh network according to the assigned contamination
densities. The snapshots from Fig. 7-(d) to (i) show that robots could generate adaptive
triangular meshes based on ka and da . If the series of snapshots are carefully observed, thenumber of robots within the area of interest, represented by a red circle, increases. In detail,it is initially observed in Fig. 7-(d) that there are 7 robots within the area. By executing
the adaptive triangular mesh generation algorithm repeatedly, the number of robots locatedin that area rises to 17 robots in the final distribution (see Fig. 7-(i)). Compared with Fig.
7-(c), the overall size of the final distribution was reduced. Similarly, Fig. 8 shows theresult from another simulation with geographical borders [17].
Secondly, Fig. 9 shows the results from simulations with four different degrees ofcenter density. In the figure, the number of robots within the circle increases in proportion
to the degree of density. Similarly, the size of the swarm in its final converged shape varies
according to the center density. Higher densities forced the robots to decrease the intervals
between neighboring robots.
Thirdly, we performed simulations for multiple varying densities in a single swarm.
Figs. 10-(a) and (b) show the results for two identical center densities. Although the swarm
was spilt into two smaller groups, robots could adaptively configure themselves near thearea. Figs. 10-(c) and (d) present the results when the center contamination densities vary:
0.7 on the left hand side and 0.9 on the right hand side. The higher center contamination
density area is more densely populated. In Figs. 10-(e) and (f), the simulation was performed for three different center contamination densities in a swarm: 0.9, 0.7, and 0.8 fromleft to right. Robots could adapt the interval between each other according to the varying
contamination densities, which is similar to previous simulations. Thus the overall size ofthe swarm also varies accordingly.
Three main features highlight our adaptive triangular mesh generation as follows.
First, the approach enables the swarm of robots to deploy themselves while adapting tocontamination densities. More specially, we proposed motion control to form equilateraltriangles with a appropriate intervals depending on the density. Secondly, the triangle lattice is built based on a partially-connected mesh topology since each robot locally interacts
with its selected neighbors. Among all the possible types of regular polygons, the triangle
element is easy to construct and highly scalable as the number of robots increases. Thirdly,
our approach eliminates major assumptions such as robot identifiers, common coordinates,
global orientation, specific leaders, and direct communication. Robots calculate their target position without having to remember past actions or states, which makes it easier tocope with transient error.
We believe that our algorithm works well under real world conditions, but several
issues remain to be addressed. Our approach relies on the assumption that robots cansense the positions of neighboring robots and contamination densities within SB. Practically speaking, it is difficult to precisely measure the positions of other robots using infrared [9] [29] or sonar sensors [19], and to detect the contamination densities. When directcommunications are employed, it is possible to exchange information about densities. So,
as our future work, (to further facilitate implementation of the proposed method in a realenvironment,) robot swarms exchanging information are expected to be effectively applied
to such deployment. Robots, however, still require a priori knowledge, such as individual
identifiers or global coordinates. Direct communication may also involve difficulties suchas limited bandwidth, range, and interference. These important engineering issues are left
for future work.

6. CONCLUSIONS

14(a) 2 identical densities(b) adaptive deployment(c) 2 different densities(d) adaptive deployment(e) 3 different densities(f) adaptive deployment

F IGURE 10. Simulation results for varying local contamination densities
6. Conclusions
The adaptive triangular mesh generation problem was addressed to disperse a swarmof mobile robots which can adapt to the degree of contamination in a target area. There
were several major assumptions underlying our proposed approach to this problem: no
robot identifiers, no common coordinates or global orientation, and no direct communication. Robots computed their target positions without requiring memories of past actions orstates. Under such conditions, the proposed adaptive mesh generation algorithm enables a

6. CONCLUSIONS

15

large-scale swarm of robots to configure themselves into triangular patterns, while changing the uniform interval according to the contamination densities that can be detected by
sensors. We took advantage of the fact that, among all the possible types of n-polygons,
the triangle is highly scalable, and less influenced by the number of neighboring robots. To
form the triangular pattern, robots were allowed to interact with only two selected neighbors at each time. By collecting such a local behavior of each robot, a swarm of robots
arranged in triangular meshes was self-configured into the area of varying degrees of thelocal density. The properties of the algorithm were shown mathematically, and also verified
through extensive simulations. Finally, we expect that the proposed approach can be used
as a simple and effective way to deploy mobile sensor networks for coverage of unknown
areas of interest.

Bibliography[1] Choset, H., “Coverage for robotics-a survey of recent results”. Annals of Mathematics and Artificial Intelligence 31(1-4):113-126 (2001).
[2] Cortes, J., Martinez, S., Karatas, T., and Bullo, F., “Coverage control for mobile sensing networks”. IEEE
Transactions on Robotics and Automation 20(2):243-255 (2004).
[3] Suzuki, I. and Yamashita, M., “Distributed anonymous mobile robots: formation of geometric patterns”.
SIAM Journal of Computing, 28(4):1347-1363 (1999).
[4] Cao, Z., Tan, M., Wang, S., Fan, Y., and Zhang, B., “The optimization research of formation control for
multiple mobile robots”. Proc. 4th World Cong. Intelligent Control and Automation, pp.1270-1274 (2002).
[5] Ikemoto, Y., Hasegawa, Y., Fukuda, T., and Matsuda, K., “Graduated spatial pattern formation of robot
group”. Information Sciences 171(4):431-445 (2005).
[6] Shimizu, M., Mori, T., and Ishiguro, A., “A development of a modular robot that enables adaptive reconfiguration”. Proc. IEEE/RSJ Int. Conf. Intelligent Robots and Systems, pp.174-179 (2006).
[7] Balch, T. and Hybinette, M., “Social potentials for scalable multi-robot formations”. Proc. IEEE Int. Conf.
Robotics and Automation, pp.73-80 (2000).
[8] Howard, A., Mataric, M.J., and Sukhatme, G.S., “Mobile sensor network deployment using potential fields:
a distributed, scalable solution to the area coverage problem”. Proc. 6th Int. Symp. Distributed Autonomous
Robotic Systems, pp.299-308 (2002).
[9] Spears, W., Spears, D., Hamann, J., and Heil, R., “Distributed, physics-based control of swarms of vehicles”.
Autonomous Robots 17(2-3):137-162 (2004).
[10] Fujibayashi, K., Murata, S., Sugawara, K., and Yamamura, M., “Self-organizing formation algorithm foractive elements”. Proc. 21st IEEE Symp. Reliable Distributed Systems, pp.416-421 (2002).
[11] Reif, J. and Wang, H., “Social potential fields: a distributed behavioral control for autonomous robots”.
Robotics and Autonomous Systems 27(3):171-194 (1999).
[12] Zheng, Y.F. and Chen, W., “Mobile robot team forming for crystallization of protein”. Autononomous
Robots 23(1):69-78 (2007).
[13] Martison, E. and Payton, D. “Lattice formation in mobile autonomous sensor arrays” in Swarm Robotics(LNCS). Sahin, E. and Spears, W.M. (eds.), 3342:98-111, Springer, (2005).
[14] McLurkin, J. and Smith, J., “Distributed algorithms for dispersion in indoor environments using a swarmof autonomous mobile robots”. Proc. 7th Int. Symp. Distributed Autonomous Robotic Systems, pp.831-840(2004).
[15] Shucker, B., Murphey, T.D., and Bennett, J.K., “Convergence-preserving switching for topology-dependent
decentralized systems”. IEEE Transactions on Robotics 24(6):1405-1415 (2008).
[16] Lee, G. and Chong, N.Y., “A geometric approach to deploying robot swarms”. Annals of Mathematics andArtificial Intelligence 52(2-4):257-280 (2008).
[17] Lee, G. and Chong, N.Y., “Self-configurable mobile robot swarms with hole repair capability”. Proc.
IEEE/RSJ Int. Conf. Intelligent Robots and Systems, pp.1403-1408 (2008).
[18] Fredslund, J. and Mataric, M.J., “A general algorithm for robot formations using local sensing and minimalcommunication”. IEEE Transactions on Robotics and Automation 18(5):837-846 (2002).
[19] Lee, G. and Chong, N.Y., “Decentralized formation control for small-scale robot teams with anonymity”.
Mechatronics 19(1):85-105 (2009).
[20] Folino, G. and Spezzano, G., “An adaptive flocking algorithm for spatial clustering” in Parallel Problem
Solving from Nature - PPSN VII (LNCS). Goos, G., Hartmanis, J., and Leeuwen, J.V. (eds.), 2439:924-933,
Springer,(2002).
[21] Lee, G. and Chong, N.Y., “Adaptive flocking of robot swarms: algorithms and properties”. IEICE Transactions on Communications E91-B(9):2848-2855 (2008).
[22] Fax, J.A. and Murray, R.M., “Information flow and cooperative control of vehicle formations”. IEEE Transactions on Automatic Control 49(9):1465-1476 (2004).
16

BIBLIOGRAPHY

17[23] Olfati-Saber, R. and Murray, R.M., “Consensus problems in networks of agents with switching topology
and time-delays”. IEEE Transactions on Automatic Control 49(9):1520-1533 (2004).
[24] Burgard, W., Moors, M., Stachniss C., and Schneider, F., “Coordinated multi-robot exploration”. IEEE
Transactions on Robotics and Automation 20(3):120-145 (2005).
[25] Mondada, F., Pettinaro, G.C., Guignard, A., Kwee, I., Floreano, D., Deneubourg, J.-L., Nolfi, S., Gambardella, L.M., and Dorigo, M., “Swarm-bot: a new distributed robotic concept”. Autonomous Robots
17(2-3):193-221 (2004).
[26] Jatmiko, W., Sekiyama, K., and Fukuda, T., “A particle swarm-based mobile sensor network for odor source
localization in a dynamic environment” in Distributed Autonomous Robotic Systems 7. Gini, M. and Voyles,
R. (eds.), Springer Japan, pp.71-80 (2007).
[27] Jung, B. and Sukhatme, G.S., “Tracking targets using multiple robots: the effect of environment occlusion”.
Autonomous Robots 13(3):191-205 (2002).
[28] Krishnanand, K.N., Amruth, P., and Guruprasad, M.H., “Glowworm-inspired robot swarm for simultaneous
taxis towards multiple radiation sources”. Proc. IEEE Int. Conf. Robotics and Automation, pp.958- 963(2006).
[29] Lee, G., Yoon, S., Chong, N.Y., and Christensen, H., “Self-configuring robot swarms with dual rotating
infrared sensors”. Proc. IEEE/RSJ Int. Conf. Intelligent Robots and Systems, pp.4357-4362 (2009).
[30] Ghosh, S., Basu, K., and Das, S.K., “An architecture for next-generation radio access networks”. IEEE
Network 19(5):35-42 (2005).
[31] Slotine, J.E. and Li, W., Applied nonlinear control. Prentice-Hall (1991).