Journal of Robotics, Networking and Artificial Life, Vol. 2, No. 3 (December 2015), 157-161

Probability of mixing up the nearest neighbor robot under target enclosure by robot
swarm
Masao Kubo

Computer Science, National Defense Academy of Japan, Yokosuka, Kanagawa, Japan
Hiroshi Sato

Computer Science, National Defense Academy of Japan, Yokosuka, Kanagawa, Japan
Akihiro Yamaguchi

Department of Information and Systems Engineering, Fukuoka Institute of Technology Fukuoka, Japan
Eugene Kitamura

Computer Science, National Defense Academy of Japan, Yokosuka, Kanagawa, Japan
Akira Namatame

Computer Science, National Defense Academy of Japan, Yokosuka, Kanagawa, Japan
E-mail: {masaok ,hsato ,ed12005, nama}@nda.ac.jp, aki@fit.ac.jp

Abstract

This paper analyzes conditions in which a robotic swarm with a simplest communication device can succeed
to enclose a target. The robots have to know directions to their each nearest neighbors. Each robot has asame signal emitter like a torch and they can observe the sum of the intensity of their torches. We analyze theprobability to the mistake of the direction when a robot adopts the direction of the strongest intensity of thesignal as the direction of the nearest neighbor because we expect this approach makes the robot swarm more
simple and scalable. The computer simulations show the case of the success.

Keywords: target enclosure, swarm robotics, low cost robot design, collective intelligence

1. Introduction
This paper analyzes conditions in which a robotic
swarm with a simplest communication device cansucceed to enclose a target. The swarm is equippedwith a same limited transmission range signal
emitter. This communication system could make alarge robot swam cheaper and scalable. On the otherhand, it suffers a lower performance because they

Published by Atlantis Press
Copyright: the authors
157

Journal of Robotics, Networking and Artificial Life, Vol. 2, No. 3 (December 2015), 157-161

Masao Kubo, Hiroshi Sato, Akihiro Yamaguchi, Eugene Kitamura, Akira Namatame

could not observe any correct information. In thispaper, this low cost robot design concept is applied
to a robot swarm to enclose a target.
The target enclosure task is useful for monitoringof disaster sites. We focused on the study ofTakayama et al.3. In their model, each robot needs
information of directions to only one neighbor and toits target. Recently, a research used a hybrid systemtheory and showed that robots controlled by thismethod which references the nearest neighbor canalso enclose a target1.
In making a cheap and scalable component for arobot swarm a limited range homogeneous signal
emitter is focused. We call it the torch system. For
example, Kilobot2 has the same small LED emitter as
a communication device and a flock of 1000 Kilobots
can form a large shape. However, the transmission
range of their LED light is about 6 robot length.
Swarmbot4 proposes that the robot having ahomogeneous light can collect the sufficient numberof robots to solve a task. Each robot has the samecolor lights around its body. The intensity of lightbecomes strong as the number of robots increase. If
the intensity of light is too strong a robot will not join
the group.

Fig.1
Model of Takyama's
algorithm: α,β.

Fig.2
Diffusionlight of torchofThe advantage of this torch system is its highprocurability. The very limited transmission range
provides less interference of communication.
Therefore, emitters which use the same signal band
can be installed into many robots. Also, its smallenergy consumption is an advantage. The smaller thecommunication range, the smaller the energy
consumption.

In this paper, we examine a robotic swarm withtorch system for the target enclosing task. We adopt
Takayama’s work for the control scheme of robot but
the referencing robot is different in this work. We
propose the most powerful signal direction to be thedirection of the referencing robot. We call this the“MOPS” direction. In this paper, we show that theproposed robotic swarm can enclose a target
successfully by computer simulation. We discuss theprobability of mixing up the nearest neighbor robot
under the target enclosure task by robot swarm.

Fig.3

The most powerful signal (MOPS) direction

2. Takayama's target enclosing modelFirstly, Takayama's target enclosing model isexplained. On a two-dimensional plane, let there be
only one target O at the origin and n robots. Robots
are numbered counterclockwise as P1,..,Pn, and ri is
the position vector of the robot Pi.
To achieve this task, Takayama et al.3 proposed thefollowing model. Each robot determines its control
input, speed vi, and angular velocity ωi using two
aspects of angular information: relative angles withrespect to the target and an anterior neighboring
robot, denoted as αi and βi, respectively. As a result,rotational movement occurs with a central focus on
the target.
(1)
v = fβi

ωi =ivi− k cos(α i )r(2)where the parameters r , k, and f>0 as specified
beforehand. Pi+1 is the robot to which Pi refers, and r

Published by Atlantis Press
Copyright: the authors
158

Journal of Robotics, Networking and Artificial Life, Vol. 2, No. 3 (December 2015), 157-161

Probability of mixing up

is the expected distance to the target. In Takayama etal.'s model, the i-th robot refers to the i+1-th robot,
and the n-th robot refers to the first robot P1.

3.1. Torch
Every agent has a same torch and it can turn on/off
its torch. The maximum intensity of all the torch issame and known beforehand. We suppose that thespeed of propagation of the signal of the torch is so
fast that an agent can observe the signal immediately.
As shown in Fig.2 during the flight of the signal, thepower of the signal is attenuated. The signal
propagation function p(d) is described as follows.

γ (d / L ) (d / L) 2
d>Lp(d) = 1otherwiseFig.4The location of agents when they enclose thetarget completely (|N| = 8). △ indicates the reference
agent and ○ means its neighbor agents.

2.1. Nearest neighboring robot as thereference
Ref.1 examined a different reference robot scheme inwhich each robot considers its nearest neighboring
robot as its reference robot. Each robot controls itself as described in equation 1 and 2, but it chooses
its nearest neighbor as its reference robot. Thissystem has higher scalability because the individualrobots need not be identified to observe the nearest
robot.
3. The proposed reference model: the mostpowerful signal direction model, MOPS
model

We propose an alternative robotic swarm for thetarget enclosure task. Each robot carries the torchwith the same specification. Additionally we proposea most powerful direction of their signal is used as
the direction of the referencing robot. First, weexplain the torch which the robots have.

(3)

where d is the distance from the emitter, L is thelength of an agent, γ is the attenuation coefficientper L. The equation 3 represents the spherical
diffusion of a light. An agent closer to an emitter
receives a stronger signal. Target enclosing modelwith MOPS direction reference model
We explain the procedure of receiving a signal in theproposed method.
Agent Pi uses the most powerful signal directioninstead of the angle from Pi to Pj (=βi). Also, we callthe angle β'i. Fig.3 shows this angle. Now, we suppose
agent Pi has several signal receivers. We call it sensor
primitive. The direction of k-th sensor primitive spk
is θk. If |θk–θij |≦θs/2, the sensor primitive spk
can sense the signal of Pj. We call θs a visible rangeof sensor primitive. The power of sensor primitive
spk, sk is

Sk = ∑ p(d i,m )(4)where di,m is the distance between Pm and Pi and p is
the signal propagation function in eq.3. β'i is thesubstitution of βi.
(5)β ′i = ∠v i Piθ arg max skk

4. Analysis of the proposed directionreference model

In this section, we describe the result of analysis of
the proposed MOPS reference model. In this section,
we clarify that it is possible for a set of adequate
sensor primitives to detect the nearest neighbor agent

Published by Atlantis Press
Copyright: the authors
159

Journal of Robotics, Networking and Artificial Life, Vol. 2, No. 3 (December 2015), 157-161

Masao Kubo, Hiroshi Sato, Akihiro Yamaguchi, Eugene Kitamura, Akira Namatame

if the locational variance of the neighbor robots issmall.
4.1. Definition of this target enclosing task
The following 2 conditions are defined for a
successful target enclosing. For any agent Pi, the first
condition is that the distance between Pi and thetarget at O is equal to r . The second condition is thatfor any agent Pi the ∠PiOPj = 2π/|N| where Pj is thenearest neighbor agent of Pi.
Now, we suppose that an agent, i = 0 is at (ri,θi) =( r ,0). We call the agent with i = 0 the reference
agent. Also other agents are called the neighbor
agents. When they enclose the target successfully, thelocations of the neighbor agents are (ri,θi)= ( r , iCθ),Cθ=2π/|N|, i=1,...,|N|−1. We call these locations
regular locations. Even if the reference agent moves
while the other agents enclose the target, the relative
position of the reference agent to the other agents
remain the same. The distance to a neighbor agent i, i= 1,...,|N|−1 isd i = 2r 2 (1− cos(iCθ )).

(6)

Therefore,(7)d i=1 = d i= N −1 < d i≠0,1, N −1

We think of 2 nearest neighbor agents for thereference agent when they enclose the target.

circumferential displacement from its regularposition. We assume that the displacements ∆ri , ∆θ ifollow the normal distributions having average 0 andvariance σ r2i , σ θ2i respectively. Also, we assume thatthe fluctuation of signal power at the reference agent
follows a normal distribution having σ i . In this case,the average of power of the signal at the reference
agent is Ai, and its distribution σ 2 i . is2 2σ ri + ki,2θ + σ θ2i
σ 2 i = K i Σ i K iT = ki,r(11)where Σ i = diag(σ r2i ,σ θ2i )The deviation of the signal at the reference agent
can be calculated if |N| and σ ri , σ θ i are known. We
suppose that Is means the set of agents which are invisible range of sensor primitive s. The average ps
and the standard deviation Ms of signal at thereference agent are described as follows.
ps = ∑ A j ,M s =j∈I s∑ s 2jj∈I s(12)Fig.5

The probability with which a farther neighbor isrecognized as a closer neighbor.

4.2. Fluctuation of signal power caused bydisplacement of neighbor agentsThe signal power of neighbor agent i at the reference
agent can be approximated by Taylor expansion. It is
described as follows.

4.3. Limit of variance of signal under which an

Si = Ai + K i ∆ i , Ai = γ d i / L L2 d 2 i , K i = [k i,r , k i,θ ]We assume that there are 2 sensor primitives s1, s2 of
the reference agent. Each sensor primitive observes
one of the nearest neighbor agents in equation 7. Also
visible ranges of s1 and s2 are so narrow that it
receives signal from only one of the nearest neighboragents, namely, |Is1| = |Is2| = 1.

(8)

dik i,r = −( 2Lγ L r )(1 − cos(iC ))(r 2 loγ(γ )(cos(iC ) − 1) + Ld )i(9)ki,θ = −( 2Lγ L r 2 ) sin(iC )(r 2 loγ(γ )(cos(iC ) − 1) + Ld )

(10)

θd i5

θ

did i5θθTiwhere ∆ i = [∆ri ,∆θ i ] . ∆ri is a displacement along
the target direction from its regular position, ∆θ i is aagent can detect the nearest neighbor
agentsNow, we suppose that a small displacement at thenearest neighbor agents occurs while all of theagents move. We assume that the difference ofdistance between the 2 nearest neighbor agents is ∆.

Published by Atlantis Press
Copyright: the authors
160

Journal of Robotics, Networking and Artificial Life, Vol. 2, No. 3 (December 2015), 157-161

Probability of mixing up

In this case, the condition for the reference agent tochoose a sensor primitive correctly for observing thecloser agent can be deduced by using the 3- σ rule.
ps1 − kM >ps1 + ps2
2(13)where ps1 ≥ ps2 and k is a positive constant. Here k=3

for the rest of this paper.

the nearest neighbor is an important information forthis task. We can expect that if the fluctuation of anagent is sufficiently small and the gap of distance
between the nearest and the second nearest neighbor
agent (∆) is given, the agent can select the correct
sensor primitive which observes the nearest neighbor
agent.

Therefore, if the standard deviation of the sensor
primitive M is smaller than M Limit , the reference
agent can almost certainly select the correct sensor
primitive. M Limit is described as follows.
M ≤ M Limit =p(d1 ) − p(d1 + ∆)2k(14)M Limit is changed by signal’s attenuation coefficientγ. Fig.6 illustrates M and M Limit while γ changes. M
with σ θ i = 0.5, 1 and 2 degree are illustrated by lines
with markers +, ○, and □ respectively .|N|=8, r=10m. σ ri =0.1m.
The variance of signal power at the reference
agent becomes smaller as the σ θ i becomes small.

The solid and dashed lines represent M Limit with∆=1m and 2m respectively. In order to detect thedifference in distance of ∆m between the nearest
agents with high certainty, the variation of thereceived signal M must be smaller than M Limit lines.
For example, Fig.6 shows that even if the nearest
neighbor agent’s location is distributed σ θ i =0.5
degrees, the reference agent can detect 1m difference
between the 2 nearest agents for any γ. On the otherhand, the reference agent cannot detect suchdifference if the nearest neighbor agent’s location
is distributed σ θ i =1 and 2 degrees.
By this experiment, we expect that if the σ θ i issufficiently small, the reference agent that is ∆ closer
than the 2nd nearest neighbor agent can be selectedby the sensor primitive with the strongest intensity
signal.
5. Conclusions

In this paper, we examine a robotic swarm with thetorch system, which is a simple communication
device, for the target enclosing task. The direction ofFig.6Limit of variance of signal under which an agent candetect the nearest neighbor agents

References
1. M. Kubo, H. Sato, T.Yoshimura, A.Yamaguchi, T. Tanaka,“Multiple targets enclosure by robotic swarm”,
Robotics and Autonomous Systems 62,1294–1304(2014)
2. M.Rubenstein, C.Ahler, N.Hoff, A.Cabrera, R.Nagpal,“Kilobot: A low cost robot with scalable operations
designed for collective behaviors”, Robotics andAutonomous Systems, 62, 996-975,(2014).
3. Y. Takayama, S. Yamamoto, T. Takimoto, “DistributedFormation Control of a Nonholonomic Multiagent
System for Target-enclosing Operations”, Proceedingsof 9th SICE System Integration Division Annual
Conference, SY0015, 679-680(2008)
4. F. Ducatelle, A. Fö rster, G. D. Caro, and L. Gambardella,“New task allocation methods for robotic swarms”, 9thIEEE/RAS Conference on Autonomous Robot Systems
and Competitions,(2009).

Published by Atlantis Press
Copyright: the authors
161