SWARM 2015: The First International Symposium on
Swarm Behavior and Bio-Inspired Robotics
October 28-30, Kyoto, Japan

Swarm Robotic Network Using Lévy Flight in Target Detection Problem
Yoshiaki Katada1† , Akihiro Nishiguchi1, Kazuya Moriwaki1 and Ryosuke Watakabe1
1

Department of Electrical and Electronic Engineering, Setsunan University, Osaka, Japan(Tel: +81-72-839-9148; E-mail: katada @ ele.setsunan.ac.jp)

Abstract: One approach in swarm robotics is homogeneous system which is embedded with sensing, computing, mobileand communication components. In this study, a target detection problem, which is one of navigation problems, wasemployed. Once a robot detects a target, robots immediately communicate with a base station via intermediate relay
robots due to the multi-hop transmission of wireless communication. Therefore, this control task is completed withconnectivity of the network. In a target detection problem, we must improve the performance of exploration as well as
connectivity of the network. This study investigates the performances of the two kinds of random walk algorithm innavigation while loosely ensuring connectivity of the robotic network based on our previous study.
Keywords: Swarm Robotics, Lévy Flight, Wireless Sensor Networks, Target Detection Problem

1. INTRODUCTION

to the base station via WSN.
Our research group investigated communication range
and the number of robots required for a SR network toachieve connectivity based on percolation theory[6-8] incomputer simulation [9]. According to the results obtained in [9], we conduct a series of real experiments inthis work. Also, we must consider the performance of exploration as well as connectivity of the SR network in atarget detection problem. Therefore, we improve exploration strategies to enhance the performance.
In this paper, we employ a Brownian random
walk, which employs the constant step size, and Lévy
flight[10], which employs the step size following Lévy
probability distribution, in order to investigate the effectof the step size of the random walk and the number ofrobots in a target detection problem. Addition to this, theswarm robotic behavior emerged from each random walkare analyzed.
As a related work, Sutantyo et al. [11] studied the effect of Lévy flight on a target detection problem by real
underwater swarm robots. Their experimental environment is an aquarium with size 2.5 m × 2.5 m × 1.5
m. Their control task is to aggregate around targets after
a robot detects a target and attracts other robots. They
employed the firefly optimization algorithm with Lévy
flight to generate the “attractive” and “random” behavior of the robots. They employed the blue-light intensity
as communication. Thus, they neither used explicit verbal communication nor ensured the connectivity between
the robots. Moreover, they did not assume communication with the outside of the swarm robots after detecting atarget. The control task of them is different from the oneof our study and their environment is much smaller thanours described later.
The paper is organized as follows. The next section
shows the structure of the mobile robots. Section 3 explains two random walks. Section 4 describes the controller of the robots and how to implement random walkand Lévy flight in the controller, respectively. Section 5shows the setting and results in real experiments. Section
6 discusses the results. Conclusions are given in the last

Swarm Robotics (SR) [1][2] have attracted much research interest in recent years. Generally, the tasks in
SR are difficult or inefficient for a single robot to copewith. Thus, SR and multi-robot systems overlap eachother. Sahin [3] enumerated several criteria1 for distinguishing swarm robotics as follows:• autonomy: Each robot should be physically embodied
and situated.
• redundancy: Group sizes accepted as swarms is 10 to20.
• scalability: SR system should be able to operate undera wide range of group sizes.
• simplicity: Each robot should employ cheap design,that is, the structure of a robot would be simple and thecost for it would be cheap.
• homogeneity: SR system should be composed of homogeneous individuals. This enhances the above 2nd and3rd criterion.
Following the last criterion, homogeneous controllers forindividuals are desirable for SR systems. Additionally,
this approach does not assume the existence of an explicit
leader in swarm robots due to the above criteria. This results in that a collective behavior emerges from the local
interactions among robots and between the robots and theenvironment. Therefore, SR systems are required for that
individuals show various behaviors through interactions
although the individuals are homogeneous.
The typical control tasks in SR are navigation, aggregation, formation and transport requiring distributed collective strategies [2]. In this paper, we copes with a target
detection problem, which is one of navigation problems.
In this control task, several robots can communicate witheach other via wireless sensor networks (WSN)[4][5] dueto the multi-hop transmission to achieve collective exploration. As soon as a robot detects a target, the informationis sent from the robot to the base station via intermediate
relay robots. Therefore, all robots should be “connected”† Yoshiaki Katada is the presenter of this paper.
1 Sahin [3] claimed that these criteria should be used as a measure of thedegree of SR in a particular study.

Ⓒ SWARM 2015 All Rights Reserved.

310

to the recommendation in [13]. Fig. 2 shows Eq. (1) with
γ = 1.0 and α = 1.2 over the step size range 1 ≤ d ≤ 30.

section.

2. SETUP FOR SWARM MOBILEROBOTS

4. CONTROLLER

Differential wheeled robots (Fig. 1) were used in thisexperiment. The robot’s diameter and height are approximately 170 mm and 75 mm, respectively. The robot isequipped with four infrared distance sensors located at its
front for measuring the distance to other robots and walls,
and two infrared sensors located at both ends of the bodyfor detecting a target. The maximum detection rangesof the former infrared sensor and the latter infrared sensor are 300 mm and 200 mm, respectively. The robot’s
processor is the Arduino microcontroller, which gets sensory inputs and outputs signals to control two wheels
through motor drivers. The robot is equipped with wireless devices, XBee. XBees, based on ZigBee wirelessstandard, can compose wireless ad hoc networks, where
nodes can communicate with each other via multi-hop
path. A XBee equipped with each robot is set as a routerof the network. As a target, an infrared-emitting ball is
employed to make handling easy, which is the official
ball for RoboCup Junior [12]. Its infrared rays are distinguishable from those emitted by the distance sensor
described above due to the different wavelength.

4.1. Design methods in SR
Controllers in SR are required to enhance the criteria described in Sec. 1. Thus, the methods to design
such controllers can be classified into two categories:
behavior-based design and automatic design [2]. The
both methods are based on the interaction between robots
and environment. The former develops controllers byhand and the latter does by soft computing. Reinforcement learning (RL) and evolutionary robotics (ER) arerepresentative of automatic design. Currently, RL and
ER are useful in simulated environment. However, it isdifficult to ensure consistent behavior of robots in realenvironment with the one obtained in simulated environment [15-19]. Therefore, most researchers aiming at realrobots in SR employ the behavior-based design.
Subsumption architecture (SSA) proposed by Brooks[20]is a representative of behavior-based design. In behaviorbased design for SR, individual behavior of swarm robots
is adjusted iteratively based on the interaction among therobots and between the robots and environment [2]. As
a format to describe such individual behavior, finite statemachines are often used. On the other hand, augmented
finite state machine is used to describe modules in a control layer for SSA explained in the next subsection. According to these, we employ SSA as a format to describe
behavior of individuals which compose swarm robotic
network.

3. RANDOM WALKS
In this study, we cope with a navigation task. We assume that robots have no prior knowledge of the environment. In these scenarios, random walks are general
exploration strategies. A random walk with a constantstep size is well known. On the other hand, Lévy flightis a random walk whose step size varies according to aLévy probability distribution [10]. It is reported in [13]that Lévy flight is useful for the environment where targets are distributed sparsely and randomly.
Lévy probability distribution for a step size can be approximated in the following [14]:p(d) ≃ γd−α4.2. Layer Structure of SSA
Fig. 3 shows a layer structure of SSA implemented inthis swarm robots. The SSA to achieve the control task
in this study is composed of the following three layers:transmission, obstacle avoidance and target exploration.
A capital I in Fig. 3 indicates inhibition by which a lower
layer is inhibited when an upper layer is activated [20].
Each layer is composed of some modules connected toeach other.
Behavior of each layer can be explained as the following; In the target exploration layer, the explore module(1)

where d is a step size, γ is the scaling factor and α is aparameter varying the shape of the probability distribution. In this study, we set γ to 1.0 and α to 1.2 according

avg
1
PDF: p(d)

0.8
0.6
0.4
0.2
0
5

Fig. 1 Setup for swarm mobile robots

10

15 20
d [step]

25

Fig. 2 Lévy probability distribution

311

30

distance sensor

obstacle avoidance layer
detectobstacle(a)RN(2)turn right(b)RN(6)㻵
turn lefttarget exploration layer

explorebase station

stop

㻵

forwardmotorstargetdetectingsensortransmission layertransmit
message㼟

detecttargetturn rightmove forward

turn leftturn(c)LF(6)Fig. 3 Layer structure of SSA

Fig. 4 Transition between move-forward phase and rotate
phase in navigation

sends messages to one of the following three modules:
forward, turn right and turn left, where forward means
moving forward and turn right (left) rotating clockwise(counter clockwise) at the position. In the obstacle avoidance layer, the detect obstacle module sends messages toeither turn right or turn left according to the sensory inputs from distance sensors described in Sec. 2, in order
to avoid the obstacles which the robot faces. In the transmission layer, the detect target module sends messages tothe transmit messages module and the stop module when
the sensory inputs from the infrared sensors for detecting
a target are beyond a threshold. The transmit messages
module transmits messages to the base station via intermediate relay robots. The stop module sends messages to
its own motors to stop them.

sition from the move-forward phase to the move-forward
phase is possible. In this case, the average step size iseffectively 2. In RN(6), a step size is set to 6 in the moveforward phase and the transition between the two phases
occurs at 100% in order to compare the performance ofLévy flight.
4.3.2. Lévy FlightLévy flight employs the move-forward phase and therotation phase as random walk does. A step size in the
move-forward phase is determined according to a Lévy
probability distribution described in Sec. 3. The transition between the two phases occurs at 100%. In thisstudy, the maximum step size is set to 30 based on the
results in the preliminary experiment. Thus, the average
step size is effectively 6. We write LF(6) as an abbreviation of Lévy flight in the reminder of this paper.

4.3. Implementation of exploration strategies
In the reminder of this paper, a random walk with aconstant step size is simply called “random walk” to distinguish from Lévy flight. These strategies are implemented in the target exploration layer. The details aredescribed in the following subsections.

5. EXPERIMENT

4.3.1. Random Walk
For random walk, the direction of a move for each stepis determined at random while the step size of a move isconstant. For the differential wheeled robots used in thisstudy, it is difficult to move forward with a constant step
size and to rotate in the predetermined direction simultaneously. Therefore, the whole steps are divided into
the move-forward phase and the rotation phase (Fig. 4).
In the move-forward phase, a robot moves forward driving two wheels (corresponding to the forward module inFig. 3). One step in the move-forward phase is set to
6 seconds according to the results in the preliminary experiment. In the rotation phase, a robot determines the
direction of rotation and selects an angle of rotation randomly from {45, 90, 135} degree. Then, a robot rotates
until the selected angle is achieved (the turn right or turnleft module in Fig. 3). In the reminder of this paper, wewrite RN(*) as an abbreviation of random walk, where“*” in parentheses indicates the average step size.
The move-forward phase and the rotation phase are
implemented as follows; In RN(2), a step size is set to 1 in
the move-forward phase and the phase to be executed is
selected randomly at each step (Fig. 4(a)). Thus, the tran-

5.1. Experimental Environment
We conducted a series of real experiments in the corridor on the 6th floor in the 1st building in Neyagawa
campus of Setsunan University (the yellow part in Fig.
5). There are some class rooms adjacent to this corridor.
Thus, the environment is surrounded by walls2 . A target (an infrared-emitting ball described in Sec. 2) was
placed at the lower left corner in Fig. 5. At the upper
right corner, a wireless base station was placed. The basestation is a laptop with the same XBee as those equippedwith swarm robots. The XBee equipped with the basestation is set as a coordinator. At the beginning of eachtrial, swarm robots were always placed at the same initial
position, the lower right corner, next to the base station
at random orientations (Fig 5). In this environment, thebase station and the robot located near the target can not
be in line-of-sight communication because the distance
between the base station and the target is longer than thecommunication range of the XBee.
2 We assume that the doors of the rooms are closed during the experi-

ment.

312

70.4m

6.3m
B

2.4m
8.4m

100

3.7m

6.0m

80

6.1m
Success rate [%]

6.1m

T
82.8m

Fig. 5 Experimental setup for target detection problem(B: base station, T: target)

N=10
N=15
N=20

60
40
20

5.2. Setting of Real Experiments

0
RN(2)

In this control task, swarm robots explore the environment, detect a target located so far (around 80 m) fromthe base station as not in line-of-sight communication andsend a message to the base station via intermediate relay robots. Therefore, all robots should be “connected”
to the base station via swarm robotic network mentioned
in Sec. 1. It was found in the preliminary experimentthat the XBee in the environment can communicate withother XBee longer than the indoor communication range
calculated by the specifications. It is around 54 m. Thus,
the distance of the communication range relative to thelonger direction of the environment is 54/82.8 ≃ 0.65.
This results in that the number of robots required for a
SR network to achieve connectivity in a square space isfrom 20 to 34 following to the recommendation in [9].
However, connectivity in the rectangular space would beachieved by a smaller number of robots because a squarespace is assumed in the reference[9]. Thus, we conducted a series of real experiments varying the numberof robots N ∈ {10, 15, 20}. One trial ends either when
the base station receives the message from the robot detecting a target 3 or when 1800 sec (30 min.) are performed without receiving the message. As a controller ofthe swarm robot, the SSAs described in Sec 4 were employed varying the exploration strategy in the target exploration layer: random walk (RN(2), RN(6)) and Lévy
flight (LF(6)). We conducted 10 independent runs foreach experiment.

RN(6)Exploration strategy

LF(6)Fig. 6 Success rate for each exploration strategy

were small time delays. From these results, we can saythat connectivity was achieved when or not when the task
was completed.

6. DISCUSSION
In the previous section, we confirmed that the successrate of LF(6) was extremely high. In this section, we investigate those results from the view point of features ofLévy flight described in Sec. 3.
Fig. 7 is a sketch map of the environment divided into
four areas (further from the base station in the order ofA, B, C and D). For each area, we calculated the average
number of robots in all the runs just when one trial ended.
These results are shown in Fig. 8. For RN(2), nearly 40
percent of the robots stayed in Area A (blue) and only
about 10 percent of the robots reached Area C (gray) andD (red) (Fig. 8(a)). Thus, it was difficult for the robots
to get out of the vicinity of the initial positions and go
far away from there. Actually, there is an elevator hall in
Area A and the boundary between Area A and B forms abottleneck. For RN(6) and LF(6), from 20 to 40 percentof the robots reached Area C and D (Figs. 8(b) and 8(c)).
Considering the low success rate of RN(2), a large step
size is favorable to get out of Area A and B.
The following is a comparison between RN(6) andLF(6). In RN(6), from 10 to 20 percent of the robots
stayed in Area A while in LF(6), from 30 to 40 percent of
the robots stayed in Area A. However, we have confirmed
the connectivity in Sec. 5.3. In Fig. 8, we can not findthe reason why LF(6) outperformed RN(6).
Next, we observed the behavior of the robots with
RN(6). Although less than 10 percent of the robots
reached Area D, it took a lot of time to reach there. What
was worse, robots passed by the target without detecting
it due to the relatively large constant step size even though
they reached the vicinity of the target. For LF(6), it took
less time to reach Area D than for RN(6) and robots detected a target in the vicinity of it due to the small forward
movements and the turns following them. This would be
the reason why LF(6) outperformed RN(6).

5.3. Experimental Results
Table 1 shows the time for detecting the target foreach exploration strategy varying the number of robots.
In the table, “—” indicates the trial where the task was
not achieved and “average” indicates the average time ofeach successful trial. Additionally, Fig. 6 shows the success rate for each exploration strategy. The success rate
is higher in the order of RN(2), RN(6) and LF(6) except
for RN(2) with N = 10. Here, the success rate of LF(6)is especially high. Moreover, the time to detect the target for LF(6) is shorter than those for RN(2) and RN(6)in almost all the trials for the same N . For LF(6), we
confirmed that the times are not significantly different for
N s. When one trial ends, the base station sends a message to stop all the robots. At that time, we confirmedthat all the robots stopped each trial even though there
3 In the reminder of this paper, the robot’s detecting a target is synonymous with that the base station receives the message from the robot.

313

Table 1 Time for detecting the target
algorithm
number of robots
trial 1
trial 2
trial 3
trial 4
trial 5trial 6
trial 7
trial 8
trial 9trial 10average [s]

10
—
—
1537
—
—
—
—
—
1676
—
1606

RN(2)
15
—
1328
—
—
—
—
—
—
—
—
1328

20
—
—
—
—
—
—
—
—
—
1690
1690

10
—
—
—
—
—
—
1594
—
—
—
1594

RN(6)
15
1446
—
—
—
—
1558
1536
—
1537
1708
1557

20
928
1336
—
—
—
—
—
—
—
1352
1205

D

C

B

Distribution of the robots [%]100

AFig. 7 Environment divided into four areas

7. CONCLUSIONSIn this paper, we conducted a series of real experiments on a target detection problem by swarm robotic
network in order to investigate the effect of the step sizeof the random walk and the number of robots. We confirmed that the variable step size according to a Lévy
probability distribution, that is, Lévy flight is useful foran exploration strategy in the target detection problem.
Additionally, for Lévy flight the times detecting the target
are not significantly different for the number of robots ensuring the connectivity of the robotic network. In this experimental environment, a prerequisite for achieving thetask was getting out of the vicinity of the initial positions
while a few robots stayed there to ensure the connectivityof the robotic network at the end of the trial. This seems
like foraging behavior of insects in which the elevator hallaround the initial positions is a nest and the target is food.
In this experimental setup, we do not assume the existence of explicit mechanism to maintain the connectivityof the network, that is, the cooperation among the robots.
However, such behaviors were emerged from the interaction between the environment surrounded by the walls
and enough number of robots.
In future works, we will add the functions to estimate
a position of the target after detecting the target and to
make swarm robots home to the base station. Addition tothis, we will expand our approach to the open space, thatis, environment unsurrounded by walls or outdoor.

80

LF(6)
15
650
634
—
1328
1634
1083
1072
1279
1392
815
1099

10
1585
1666
—
1405
891
1031
1248
1135
1148
950
1229

20
931
1140
—
1017
949
1167
1428
—
1117
997
1093

D
C
B
A

60
40
20
0
10

15
Number of robots

20(a)RN(2)Distribution of the robots [%]

100
80

D
C
B
A

60
40
20
0
10

15

20

Number of robots(b)RN(6)Distribution of the robots [%]

100
80

D
C
B
A

60
40
20
0
10

15

20

Number of robots(c)LF(6)Fig. 8 Distribution of the robots in each region for thenumber of robots

314

REFERENCES

ing Mobile Robots in Simulated and Real Environments”, Artificial Life 2, pp.417–434, 1995.
[18] D. Keymeulen, M. Iwata, K. Konaka, R. Suzuki, Y.
Kuniyoshi and T. Higuchi, “Off-line Mode-free andOn-line Model-based Evolution for Tracking Navigation Using Evolvable Hardware”, In Proceedingsof the First European Workshop on Evolutionary
Robotics, Springer-Verlag, 1998.
[19] Y. Katada and K. Ohkura, “An Update Method ofComputer Simulation for Evolutionary Robotics”,
Intelligent Autonomous Systems 9 (IAS-9), pp.357–
364, 2006.
[20] R. Brooks, “A Robust Layered Control System for a
Mobile Robot”, IEEE Journal of Robotics and Automation, Vol.2, No.1, pp.14–23, 1986.

[1] V. Trianni, Evolutionary Swarm Robotics, SpringerVerlag 2008.
[2] M. Brambilla, E. Ferrante, M. Birattari and
M. Dorigo, “Swarm Robotics: A Review fromthe Swarm Engineering Perspective,” Swarm Intelligence, Vol.7, No.1, pp.1-41, 2013.
[3] E. Sahin, “Swarm Robotics: From Sources of Inspiration to Domains of Application,” Lecture Notes
in Computer Science, Volume 3342/2005, pp.10-20,
2005.
[4] J. Li, L.L.H. Andrew, C.H. Foh, M. Zukerman and
C. Hsiao-Hwa, “Connectivity, Coverage and Placement in Wireless Sensor Networks,” Sensors, Vol.9,
No.10, pp.7664-7693, 2009.
[5] A. Ghosha and S.K. Das, “Coverage and connectivity issues in wireless sensor networks: A survey,”
Pervasive and Mobile Computing, volume 4, issue
3, pp.303-334, 2008.
[6] D. Stauffer and A. Aharony, Introduction To Percolation Theory: Revised Second Edition, CRC Press,
1994.
[7] E.N. Gilbert, “Random Plane Networks,” J. Soc. Indust. Appl. Math, Vol. 9, No. 4, pp.533-543, 1961.
[8] G.E. Pike and C.H. Seager, “Percolation and Conductivity: A Computer Study. I,” Phys. Rev. B, volume 10, issue 4, pp.1421-1434, 1974.
[9] Y. Katada, “Connectivity of Swarm Robot Networks for Communication Range and the Numberof Robots Based on Percolation Theory”, Proceedings of the 2014 IEEE/SICE International Symposium on System Integration, pp. 93–98, 2014.
[10] P. Lévy, Theorie de l’Addition des Veriables
Aleatoires, Gauthier-Villars, 1937.
[11] D. Sutantyo, P. Levi, C. Möslinger and M. Read,“Collective-Adaptive Lévy Flight for Underwater
Multi-Robot Exploration,” In Proceedings of 2013
IEEE International Conference on Mechatronics
and Automation, pp.456–462, 2013.
[12] http://www.robocupjunior.jp/rule/2014rule/[13] H. Koyama and A. Namatame, “Comparison of efficiency of Random walk based search and Levy
flight search”, Information Processing Society ofJapan, Technical Reports (20), pp. 19–24, 2008 (inJapanese).
[14] C-Y. Lee and X. Yao, “Evolutionary Programming
Using Mutations Based on the Lévy Probability
Distribution”, IEEE Transactions on Evolutionary
Computation, Vol. 8, pp. 1–13, 2004.
[15] R. A. Brooks, “Artificial Life and Real Robots”, In
Proceedings of the First European Conference on
Artificial Life, pp.3–10, 1992.
[16] N. Jakobi, “Half-baked Ad-hoc and Noisy: Minimal
Simulation for Evolutionary Robotics”, In Proceedings of the Fourth European Conference on Artificial Life, pp.348–357, 1997.
[17] O. Miglino, H. H. Lund and D. Nolfi, “Evolv-

315