SWARM 2021: The 4th International Symposium on Swarm Behavior and Bio-Inspired Robotics

Swarm Robots Using A New Lévy Walk
Generator in Targets Exploration
Yoshiaki Katada1
Setsunan University, Osaka, Japan,
katada @ setsunan.ac.jp,
WWW home page: http://www.setsunan.ac.jp/~katada/

Abstract. This study tackles the task for swarm robotics where robots
explore the environment to detect many targets. When a robot detects
a target, the robot must be connected with a base station via intermediate relay robots for wireless communication. In our previous results, we
conﬁrmed that Lévy walk outperformed the usual random walk for exploration strategy in real robot experiments. This paper investigated theperformance of a new Lévy walk generator, which is recently proposedin biology, for the targets exploration problem on robotics through a series of computer simulations and compared the performance with thosefor the Lévy walk generator employed in our previous work. The results
suggest that the search of the new Lévy walk is robust for uniformly andnon-uniformly distributed targets and outperforms the previous one.
Keywords: swarm robotics, Lévy walk, navigation, mobile robots

1

Introduction

Swarm Robotics (SR) [1–3] have attracted much research interest in recent years.
Generally, the tasks in SR are diﬃcult or ineﬃcient for a single robot to copewith. Thus, you ﬁnd overlap between SR and multi-robot systems. Şahin [4]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 to 20. Scalability: SR system should be
able to operate under a wide range of group sizes. Simplicity: Each robot should
employ cheap design, that is, the structure of a robot would be simple and also
the cost of it would be cheap. Homogeneity: SR system should be composedof homogeneous individuals. This enhances the above 2nd and 3rd criterion.
According to the last criterion, homogeneous controllers for individuals are desirable for SR systems. Additionally, this approach does not assume the existenceof an explicit leader in swarm robots due to the above criteria. This results inthat a collective behavior emerges from the local interactions among robots andbetween the robots and the environment. Therefore, it is required for SR systems
1

Şahin [4] claimed that these criteria should be used as a measure of the degree of
SR in a particular study.

© SWARM 2021 All Rights Reserved114

that individuals in swarm show various behaviors through interactions although
the individuals are homogeneous.
The typical control tasks in SR are navigation, aggregation, formation, transport, and decision-making, requiring distributed collective strategies [2, 7]. In
this paper, we copes with a target detection problem, which is one of navigation
problems. In this control task, several robots can communicate with each othervia wireless communication networks (WCN) [5, 6] due to the multi-hop transmission to achieve collective exploration. As soon as a robot detects a target,
the information is sent from the robot to the base station via intermediate relay robots. Therefore, all robots should be “connected” to the base station via
WCN.
Our research group investigated communication range and the number ofrobots required for a SR network to achieve connectivity based on percolation
theory in computer simulation [8]. According to the results obtained in [8], we
conducted a series of real experiments [9]. Also, we must consider the performance of exploration as well as connectivity of the SR network in a target detection problem. Therefore, we improve exploration strategies to enhance theperformance.
In a target detection problem which we cope with, we assume that robots haveno prior knowledge of the environment. In these scenarios, a random walk seems
to be appropriate for exploration strategy. It has been reported in the literature[10, 11] that some species show a speciﬁc random walk, Lévy walk [12], whenprey are sparsely and randomly distributed. This condition might correspondto a target detection problem. In our previous works[13], we conducted a seriesof real experiments on a target detection problem by swarm robotic networkin order to investigate the eﬀect of the step size of the random walk and thenumber of robots. We conﬁrmed that Lévy walk outperformed the usual random
walk for exploration strategy in real robot experiments. In computer simulation[14], we investigated which probability distribution for Lévy walk shows best
performance in a many targets detection problem varying its parameters andconﬁrmed that the probability distribution which adopted in [13] was best. Lévy
walk is often discussed based on probability distribution in literature. Recently,
Abe [15] proposed a new Lévy walk model based on nonlinear dynamics, andobserved the movement trajectories of a species of animal, and then found outthat those are consistent with his model.
This paper investigated the search performance of a Lévy walk generator
based on nonlinear dynamics in a many targets detection problem varying theparameters for experimental setting and compared the performance with thoseobtained in our previous work through a series of computer simulations. The
paper is organized as follows. The next section explains the two kinds of Lévy
walk. Sect. 3 shows the structure of the simulated mobile robots. Sect. 4 describes
the controller of the robots and how to implement Lévy walk in the controller,
respectively. Sect. 5 conducts a series of computer simulations in order to investigate the performance of the two kinds of Lévy walk. Conclusions are given in
the last section.

115

2

Lévy Walk

A random walk with a constant step size is well known as Brownian walks. On
the other hand, Lévy walk is a random walk whose step size varies according
to a power-law distribution. This section introduces the two kinds of lévy walk
generators employed in this study.
2.1

Lévy Walk Based On Probability

Lévy probability distribution [12] for a step size, w, is formulated as follows:
Lα,γ (w) =∫1 ∞−γqαecos(wq)dq, γ > 0, w ∈ R
π 0

(1)

where γ is the scaling factor and α (0 < α < 2) is a parameter varying the shapeof the probability distribution.
Lévy probability distribution for a step size can be approximated in thefollowing [16]:L(w) ∝ w−α(2)According to the recommendation in [13, 17], we deﬁne it as follows:
L(w) ≡ w−1.2(3)

Probability distribution

Fig. 1 shows Equation (3) truncated over the range 1 ≤ w ≤ 30. On the manytargets detection problem[14], we compared the performance of Equation (3)with those of the other formulations of Lévy probability distribution through aseries of computer simulations and conﬁrmed that Equation (3) shows the best
performance in the robot control problem. Thus, we employ Equation (3) as aLévy walk based on probability distribution in this study.

1
0.8
0.6
0.4
0.2
0
5

10

15

20

25

Step size
Fig. 1. Lévy probability distribution

116

30

2.2

Lévy Walk Based On Nonlinear Dynamics

Recently, Abe [15] developed a model of simple, deterministic, and nonlinear system where Lévy walks emerging near a critical point, and discussed its characteristics relating to biological systems. This model is attractive from the robotics
point of view because it would be easy to implement it for a mobile robot for
the following reasons;– The process for generation of Lévy walk is deterministic, except that only
the initial states are randomly determined. We do not have to implement
any probability distribution for Lévy walk although it is sometimes hard towrite a source code with it.
– The computational cost is low for generation of Lévy walk.
– The physical meaning of the model is interpretable for mobile robot locomotion. This is mentioned later.
– The move phase and rotate phase go together. This can be easily implemented and does not require any control unit.
The mathematical formulation is as follows;
The nonlinear system has two internal states, xt , yt ∈ [0, 1]. These internal
states are updated in the following way:
xt+1 = (1 − ϵ)f (xt ) + ϵf (yt )(4)

yt+1 = (1 − ϵ)f (yt ) + ϵf (xt ),(5)

where ϵ ∈ [0.0, 0.5] is the coupling strength between x and y, and f is a nonlinear
function.
A tent map was employed as the nonlinear function f in [15].
{x/r(x < r)f (x) =
(1 − x)/(1 − r) (x ≥ r),
where r is a parameter of the tent map. An agent movement is determined by
the above internal states as follows;∆θ = c(xt − yt )(6)

θt+1 = θt + ∆θ
Xt+1 = Xt + cos θt

(7)
(8)

Yt+1 = Yt + sin θt ,(9)where, c is set to π/ max |xt − yt |, and θ, X and Y are the orientation andposition of the agent. Thus, the speed of the agent is 1 per time step. The
reference [15] reported that the dynamics of Equation (7) change drasticallywith the parameter, ϵ; The dynamics shows a Brownian random walk when
ϵ is small, Lévy walk when ϵ is near a critical point, and constantly straightmovement when ϵ is above the critical point. At a critical point, ϵ = 0.22 whenr = 0.7.

117

3

Simulated swarm robot and environment

According to our previous work using the swarm mobile robots [13], the settingof computer simulations was as follows. Diﬀerential wheeled robots (Fig. 2(a))
were used in this experiment. The robot’s diameter and height are 0.17 [m]and 0.075 [m], respectively. The robot is equipped with four distance sensors
located at the front of the body for measuring the distance to other robots andwalls, and two sensors located at both ends of the body for detecting targets(Fig. 2(b)). The maximum detection ranges of the former distance sensor andthe latter sensor are 0.3 [m] and 0.2 [m], respectively. The robots are assumed tobe equipped with wireless devices, which can compose wireless ad hoc networks
and communicate with each other via multi-hop path.

(a) Diﬀerential wheeled robots(b) Ray of the distance sensors (dash line) andthe target detection sensors (dot-dash line)

Fig. 2. Set up for computer simulation: swarm robot

The simulated environment is a square arena with walls (Fig. 3). The lengthof the wall was set to 20 [m]. At the lower left corner, a wireless base station
was placed. The communication range of the wireless device was set to 20 [m].
The connectivity of the wireless communication network is checked based ongeometric model [6, 8]. At the beginning of each trial, swarm robots were always
placed 1 [m] apart at the same initial position, the lower left corner, next tothe base station at random orientations (Fig. 3(e)). The cylindrical objects wereplaced as targets. The radius of the cylinder is 0.11 [m] and the height is 0.22[m]. Targets were uniformly or non-uniformly distributed over the arena. The
number of targets was set at T ∈ {84, 168, 336}.
Open Dynamics Engine (ODE) [18] was employed in order to consider dynamics of robots and the interaction between robots and environment.

118

(a) T = 84, uniform(b) T = 84, non-uniform(c) T = 168, uniform(d) T = 168, non-uniform

Targets

RobotsBase station(e) T = 336, uniform
Fig. 3. Set up for computer simulation: distribution of targets

119

4

Controller

4.1

Subsumption Architecture

detecttargetstop

distance sensor

obstacle avoidance layer
detectobstaclebase stationtransmission layertransmit
message㼟turn right㻵turn lefttarget exploration layer

Fig. 4. Layer structure of SSA

120

motorstargetdetectingsensorSubsumption architecture (SSA) [19] is employed as a format to describe individuals’ behavior of the swarm robotic network according to the setting of ourprevious work [13]. Fig. 4 shows a layer structure of SSA implemented in thisswarm robots. The SSA to achieve the control task in this study comprises thefollowing three layers: transmission, obstacle avoidance and target exploration. A
capital I in a circle in Fig. 4 indicates inhibition by which a lower layer is inhibited when an upper layer is activated. Each layer is composed of some modules
connected to each other.
The behavior of each layer can be explained as follows. In the transmission
layer, the detect target module sends messages to the transmit messages moduleand the stop module when the sensory inputs from the sensors for detecting targets 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. In the obstacle avoidance layer, the detectobstacle module sends messages to either turn right module or turn left module
according to the sensory inputs from distance sensors described in Sect. 3, inorder to avoid the obstacles which the robot faces. In the target exploration
layer, Lévy walk (Sect. 2) is implemented. The details are described in the next
subsection.

4.2

Implementation of Lévy walk in the SSA

Lévy Walk Based On Nonlinear Dynamics (LWnd ) Lévy walk based on
nonlinear dynamics can be easily implemented as mentioned in Sect.2.2, especially for the diﬀerential wheeled robots. In the model of the diﬀerential wheeled
robots based on ODE (Sect.3), the angular velocities of the wheels are controlled
for behavior control. Therefore, the angular velocities are determined as follows;
vr = ωmax · x(10)vl = ωmax · y,(11)

where vr and vl are the angular velocities for right and left wheels, ωmax is the
maximum angular velocity of the wheel, and x, y are determined according toEquations (4) and (5), respectively. This leads the orientation of a robot on kinematics, which is identiﬁed with Equation (6). Therefore, the trajectories would
follow the dynamics of Equations (7)-(9) without the calculation of Equation(6). The internal states (Equation(4)(5)) are updated every 0.5 [s]. The target
exploration layer for Lévy walk based on nonlinear dynamics can be describedin Fig. 5.

drive right motor
explore㻵target exploration layer

drive left motor

Fig. 5. Details of the target exploration layer for LWnd

Lévy Walk Based On Probability (LWprob ) In the target exploration layer
for Lévy walk based on probability described in Sect. 2.1, the explore module
sends messages to one of the following three modules: forward, turn right andturn left, where forward means moving forward and turn right (left) rotating
clockwise (counter clockwise) at the position (Fig.6). In each module, the rotational direction of the right and left wheels are set, respectively. The angularvelocity in the forward module is set at a constant value, which is the same asωmax for LWnd . The angular velocity in the turn right and turn left modules is
set at 65 percent of ωmax .
For the diﬀerential wheeled robots assumed to be used in this study, it isdiﬃcult to simultaneously move forward with a regular step size and rotate in thepredetermined direction. Therefore, the whole steps are divided into the rotation
phase and the move-forward phase (Fig. 7). The transition between them occurs
at 100%. In the rotation phase, a robot randomly determines the direction of121rotation and randomly selects an angle of rotation from {45, 90, 135} degree.
Then, a robot rotates until reaches the desired angle (the turn right or turn left
module in Fig. 4). In the move-forward phase, a robot moves forward driving
two wheels (corresponding to the forward module in Fig. 4). The execution timein the move-forward phase is a random value w according to a Lévy probability
distribution(Equation (3)) multiplied by w0 , where w0 is the minimum movement
time and set at 6 [s] according to the previous experiment [13].

forwardexplore㻵turn righttarget exploration layer

turn left

Fig. 6. Details of the target exploration layer for LWprob

move forward

turnFig. 7. Transition between move phase and rotate phase for LWprob

5

Computer Simulation

5.1

Setting of computer simulations

A series of computer simulations have been conducted varying the number ofrobots N ∈ {5, 10, 15, 20} and the target distribution described in Sect. 3. One
trial ends when 360, 000 steps (3600 sec) are performed. This experiment investigated the performance of Lévy walks, LWnd and LWprob described in Sect.4,
formulating target detection rate as T (t)/T , where T (t) is the number of targets
detected by swarm robots at t time step. We conducted 50 independent runsvarying the initial orientations of the robots. All results were averaged over 50
runs.

122

5.2

Experimental results

Fig. 8 shows the average detection rate at each time step for LWnd and LWprob
with N and T , respectively. The ﬁnal detection rate converged to 100 % for all
the N except for N = 5. For LWnd , no signiﬁcant diﬀerences of the detection
rate in the search process (we call this a search speed in the reminder of thispaper) for each N were observed among the distribution of targets (Fig.8(a),8(c), 8(e) and 8(g)). The speed becomes faster with the increase of N for eachtarget distribution.
Meanwhile, the speeds for non-uniform were smaller than those for uniform
for LWprob for each N (Fig.8(b), 8(d), 8(f) and 8(h)). Increasing N had the sameeﬀect for the target distribution.
LWnd outperformed LWprob for each N , especially when targets were nonuniformly distributed. One reason for this would be that LWnd does not divide
the whole steps of movement into the rotation phase and the move-forward
phase. The robots according to LWnd always move.

6

Conclusions

This paper investigated the search performance of the two kinds of Lévy walkin the many targets detection problem varying the number of robots and thetarget distribution through a series of computer simulations. The results suggestthat LWnd outperformed LWprob in this experiment. LWnd can generate Lévy
walk without dividing the whole steps of movement into the rotation phase andthe move-forward phase. Therefore, it is predictable that the search speed for
LWnd is faster than the one for LWprob . Moreover, no signiﬁcant diﬀerences ofthe speed for LWnd were observed between for uniform target distributions andnon-uniform ones. I cannot still ﬁgure out this reason.
As I mentioned in Sect.2 and 3, LWnd can be easily implemented for robotic
control due to its mechanism. Future work will investigate the performance ofLévy walk based on nonlinear dynamics in real robot experiments.

123

T=84, uniform
T=168, uniform
T=336, uniform
T=84, non-uniform
T=168, non-uniform
0100000200000Ditection rate

Detection rate

1
0.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0

1
0.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0

300000T=84, uniform
T=168, uniform
T=336, uniform
T=84, non-uniform
T=168, non-uniform
0100000Step

T=84, uniform
T=168, uniform
T=336, uniform
T=84, non-uniform
T=168, non-uniform
0100000200000

1
0.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0

300000T=84, uniform
T=168, uniform
T=336, uniform
T=84, non-uniform
T=168, non-uniform
0100000

Step

100000200000Ditection rate

Detection rate

1
0.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0

300000T=84, uniform
T=168, uniform
T=336, uniform
T=84, non-uniform
T=168, non-uniform
0100000

Step

100000200000300000Detection rate

Detection rate

300000(f) LWprob for N = 15

T=84, uniform
T=168, uniform
T=336, uniform
T=84, non-uniform
T=168, non-uniform
0200000Step(e) LWnd for N = 15
1
0.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0

300000(d) LWprob for N = 10

T=84, uniform
T=168, uniform
T=336, uniform
T=84, non-uniform
T=168, non-uniform
0200000Step(c) LWnd for N = 10
1
0.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0

300000(b) LWprob for N = 5

Ditection rate

Detection rate(a) LWnd for N = 5
1
0.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0

200000
Step

1
0.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0

T=84, uniform
T=168, uniform
T=336, uniform
T=84, non-uniform
T=168, non-uniform
0100000Step

200000Step(g) LWnd for N = 20(h) LWprob for N = 20

Fig. 8. Average detection rate for each time step

124

300000References
1. V. Trianni, Evolutionary Swarm Robotics, Springer-Verlag, 2008.
2. M. Brambilla, E. Ferrante, M. Birattari, M. Dorigo, “Swarm Robotics: A Review
from the Swarm Engineering Perspective,” Swarm Intelligence, Vol.7, No.1, pp.1–41,
2013.
3. H. Hamann, Swarm Robotics: A Formal Approach, Springer, 2018.
4. E. Şahin, “Swarm Robotics: From Sources of Inspiration to Domains of Application,” Lecture Notes in Computer Science, Vol.3342, pp.10–20, 2005.
5. A. Ghosha, S. Das, “Coverage and Connectivity Issues in Wireless Sensor Networks:
A Survey,” Pervasive and Mobile Computing, Vol.4, No.3, pp.303-334, 2008.
6. J. Li, L. Andrew, C. Foh, M. Zukerman, C. Hsiao-Hwa, “Connectivity, Coverageand Placement in Wireless Sensor Networks,” Sensors, Vol.9, No.10, pp.7664-7693,
2009.
7. L. Bayindir, “A review of swarm robotics tasks,” Neurocomputing, Vol. 172, pp.292–
321, 2016.
8. Y. Katada, “Connectivity of Swarm Robot Networks for Communication Rangeand the Number of Robots Based on Percolation Theory”, Proceedings of the 2014
IEEE/SICE International Symposium on System Integration, pp. 93–98, 2014.
9. Y. Katada, K. Kogo, “Development of the Shortest Path Display System Using
Swarm LED Indicators Based on Signal Strength of Wireless Communication”, Proceedings of the 2017 IEEE/SICE International Symposium on System Integration,
2017.
10. G. Viswanathan, V. Afanasyev, S. Buldyrev, E. Murphy, P. Prince, H. Stanley,“Lévy Flight Search Patterns of Wandering Albatrosses”, Nature, Vol.381, pp.413–
415, 1996.
11. N. Humphries, H. Weimerskirch, N. Queiroz, E. Southall, D. Sims, “Foraging
Success of Biological Lévy Flights Recorded in Situ”, Proceedings of the National
Academy of Sciences of the United States of America, Vol.109, No.19, pp.7169–7174,
2012.
12. P. Lévy, Theorie de l’Addition des Veriables Aleatoires, Gauthier-Villars, 1937.
13. Y. Katada, A. Nishiguchi, K. Moriwaki, R. Watakabe, “Swarm Robotic Network
Using Lévy Flight in Target Detection Problem”, Artificial Life and Robotics, Vol.21,
No.3, pp.295–301, 2016.
14. Y. Katada, “Swarm Robotic Network Using Lv́y Flight for Exploration –Computer
Simulation for Sweeping”, Transactions of the Society of Instrument and Control
Engineers, Vol.54, No.1, pp.22–30, 2018 (Japanese).
15. M. Abe, “Functional Advantages of Lévy Walks Emerging near A Critical Point”,
Proceedings of the National Academy of Sciences, National Academy of Sciences,
117(39), pp.24336–24344, 2020.
16. C-Y. Lee, X. Yao, “Evolutionary Programming Using Mutations Based on theLévy Probability Distribution”, IEEE Transactions on Evolutionary Computation,
Vol. 8, pp. 1–13, 2004.
17. H. Koyama, A. Namatame, “Comparison of Eﬃciency of Random Walk Based
Search And Levy Flight Search”, Information Processing Society of Japan, Technical
Reports (20), pp. 19–24, 2008 (in Japanese).
18. Open Dynamics Engine (ODE), “http://ode.org/”
19. R. Brooks, “A Robust Layered Control System for a Mobile Robot”, IEEE Journalof Robotics and Automation, Vol.2, No.1, pp.14–23, 1986.

125