SWARM 2017: The 2nd International Symposium on
Swarm Behavior and Bio-Inspired Robotics
October 29-November 1, Kyoto, Japan

Automatic Design Method of Probabilistic Finite State Machine
Using PSO for Swarm Robots Aggregation
Yoshiaki Katada1†
1Department of Electrical and Electronic Engineering, Setsunan University, Osaka, Japan(Tel: +81-72-839-9148; E-mail: katada @ ele.setsunan.ac.jp)

Abstract: This paper proposes to use evolutionary computations to design probabilistic finite state machine for thecontroller on an aggregation problem of swarm robotics. This problem formulated as an optimization problem was solvedby the PSOs. Several computer simulations were conducted to investigate the validity of the proposed method. The results
obtained in this paper show to us that the proposed method is useful for the aggregation problem and the best optimized
controllers are interpretable. This would be transferable to real swarm robots problems.
Keywords: Evolutionary Swarm Robotics, Aggregation, Probabilistic Finite State Machine.

1. INTRODUCTION

sign collective behavior is larger than those to design single robot behavior because the interactions are so complex among robots and between the robots and the environment.
In automatic design methods, there are two categories:
reinforcement learning and evolutionary robotics. In reinforcement learning (RL), an agent aims at building
value functions in the process of learning while getting
rewards from the environment. Such optimality is guaranteed based on Markovian decision process, e.g., Qlearning. The existence of other robots may violate suchan assumption. From the viewpoint of a search problem,
RL is considered as a single point search. The ability tosearch the optimal solution is not so high.
In evolutionary robotics[4], evolutionary computation(EC) is generally applied to design artificial neural networks (ANNs) as a controller of a robot. In the caseof SR [1], an evolved controller is commonly used foreach individual robot or the controller for each robot isdesigned individually in the context of cooperative coevolution. The best evolved neural controller may show
good performance on robot control tasks in simulated environment. However, such controllers suffer from the gap
between simulated and real environment when the controllers are transferred to real environment[5-9]. This isdue to uncertainty derived from real environment: noise,complexity and nonlinear dynamics of ANNs. When we
adjust parameters of ANN due to such uncertainty, we
find it hard to interpret the collective behavior emerged
from the best evolved neural controller.
In order to overcome these problems, we propose touse probabilistic finite state machines instead of ANNsfor the controller on a swarm robot control task in thecontext of ER. That is, we apply evolutionary computations to design a probabilistic finite state machine for theswarm robot controller. Such automatic design of probabilistic finite state machines would decrease the effort ofthe design of collective behavior for swarm robot drastically.
The paper is organized as follows. The next section
describes an EC, particle swarm optimization applied todesign the PFSMs. Section 3 describes probabilistic finite

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 those interactions although the individuals are homogeneous.
Following the taxonomies proposed by Brambilla[2],we have the most common design methods to develop
swarm robotics systems: behavior-based design and automatic design. In behavior-based design methods, there
are further three categories: subsumption architecture
design method, probabilistic finite state machine design
method, virtual physics-based design method and others.
On behavior-based design methods, such swarm robotics
systems are developed by hand of the designer until thedesired collective behavior is obtained. Such effort to de† 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 2017 All Rights Reserved.

63

state machine adopted in a swarm robots control problem. Section 4 defines the swarm robot control problem,
aggregation[10-12], where the probabilistic finite statemachines designed by the PSO are evaluated. Section
5 gives the results of our computer simulations. Conclusions are given in the last section.

machine with probabilistic transitions. Brambilla[2] classified those controllers as probabilistic finite state machines (PFSMs). There are several variants of the PFSMs
employed in swarm robotics 2 .
In the PFSMs employed in SR, we set several states
for an individual robot. Let S = {S1 , S2 , · · · , Sm } bea finite set of m states. Each state may correspond to amodule[16], a primitive of the domain ontology[17] or abasic behavior[11]. A state transits to the next state with aprobability (Fig. 1). We can describe those probabilities
as a state transition probability matrix. This is defined asfollows:

2. PARTICLE SWARM OPTIMIZATION(PSO)
Kennedy and Eberhart [13] introduced particle swarm
optimization (PSO) that was based on social behavior offish schooling or bird flocking. The PSOs have been applied to various fields so far due to the search performance and the simplicity of their algorithms.
The optimization problems solved by the PSOs in thispaper are formulated as follows:Pm∑= {pij ∈ ℜ | 0 ≤ pij ≤ 1,

pij = 1,(5)j=1i, j ∈ {1, 2, · · · , m}},min f (x),(1)
xwhere x = (x1 , x2 , · · · , xL )T ∈ RL .
In the PSOs, a solution in the search space is called,“particle”. All the particles in a population have their own
positions and velocities. At each iteration, particles are
updated. The update method of positions and velocities
in the PSO is as follows:

where P ∈ ℜ
is a matrix in which each entry pij isthe transition probability from state i to state j.
m×m

p33

p22
p32

S3

p23

S2

p13
k+1
k
vij
= w · vij
+ c1 · rand() · (pbestij − xkij )+c2 · rand() · (gbestj − xkij ),k+1
xk+1= xkij + vij
,
ij

p21

(2)

p31

S1

p12

(3)
p11

where rand() is a random number between [0, 1], w, c1
and c2 are weight factors for the terms. xkij is the j-thvariable in the position vector of the i-th particle at iteraktion k, vij
is the j-th variable in the velocity vector of thei-th particle. pbestij is the j-th variable in the best position visited so far by the i-th particle and gbestj is thej-th variable in the best position visited so far by all theparticles. Each particle is evaluated by the objective function f (·) to be optimized. The update method in Eq.(2)is called, “inertia weight model (IWM)”, which is employed in this paper.
w, c1 and c2 are parameters to tune for good performance of the PSO. The several methods to tune those parameters have been proposed. In this paper, linearly decreasing inertia weight method (LDIWM) was employed
as well as IWM. In LDIWM, w is not constant but timevarying according to the increase of iterations:
wmax − wmin× k,
(4)
w(k) = wmax −kmax
where wmax and wmin are the upper and lower bounds
of inertia weight, and kmax is the maximum number of
iterations.

Fig. 1 State transition diagram of the PFSM
3.2. Automatic design of the PFSM
The PFSM is optimized as the design variables inan optimization problem by the PSO. The optimization
problem is formulated as follows:minsubject tof (pij ),(6)
0 ≤ pij ≤ 1, i, j = 1, 2, · · · , m, (7)m∑pij = 1, i = 1, 2, · · · , m.
(8)
j=1

According to Eq. (5), |P | = m × m. Thus, the numberof design variables is m × m. In the process of the PSO,
initial particles x0 s are generated in the range [0, 1]. According to Eqs. (2) and (3) for k > 0, xk s would violate
the constraints, Eqs. (7) or (8). Thus, we must consider
these two constraints in order not to leave xk unfeasible.
These constraints can be replaced with the following
constraints.

3. PROBABILISTIC FINITE STATEMACHINE (PFSM)

0 ≤ pij ,pij ≤ 1 ∩3.1. Definition of the PFSM
There are many literatures in swarm robotics employing a controller to be considered as a class of finite state

(9)
m
∑

pij = 1,

i, j = 1, 2, · · · , m. (10)j=1
2 We need discussions whether those are the PFSMs anywhere.

64In order for pij to satisfy Eq. (9), we apply mirroring to
pij as follows:{−pij : if pij < 0p′ij =(11)
pij : otherwize.
p′ij is kept in the design variables for next update. After
that, to satisfy Eq. (10), we normalize p′ij as follows:
p′ij
p′′ij = ∑m

′ .
j=1 pij(12)

p′′ij is used only for evaluations of the objective functions
and is not kept in the design variables for next update.

4. SWARM ROBOT CONTROLPROBLEM AND THE OBJECTIVE
FORMULA

Fig. 2 Setup for swarm mobile robots

Swarm robot control problem in this paper is set tobe aggregation[10] where robots aggregate to an arbitrary
position as closely as possible from their initial positions.
Aggregation is considered to be a building block for applications so that the task of aggregation is often used asa case study [11][12].
In this paper, two performance measures were employed according to the reference[12]: dispersion metric and cluster metric. The dispersion metric to be minimized is as follows:N
1 ∑ (t)f1 = 2||p − p(t) ||2 ,4r i=1 iFig. 3 Distance sensor configurations: (left) sensors forother robots, (right) sensors for obstacles
3 (right)), and four distance sensors located at the frontof the body for detecting other robots (Fig. 3 (left)). The
maximum detection ranges of the former sensor and thelatter sensor are 300 mm and 5 m, respectively.
The simulated environment is a square arena withwalls (Fig. 4). The length of the wall was set at 10 m.
At the beginning of each trial, swarm robots were always placed at the same initial position at random orientations. One trial ends when 30, 000 steps (300 sec) are
performed. We conducted 10 independent runs varying
initial orientations.
Open Dynamics Engine (ODE) [15] was employed inorder to consider dynamics of robots and the interaction

(13)
(t)

where r is the radius of a robot, pi is the position of thei-th robot at time t, p(t) is the center of the positions of
all the robots.
The cluster metric is as follows:
number of robots in the largest cluster at time t
c=
,(14)
N
where a cluster is defined as a maximal connected subgraph, where two robots are adjacent if the distance between the centers of them is less than 4r.
Thus, the 2nd objective function to be minimized is asfollows:
1
.
(15)
f2 =
c
The objective functions are evaluated when t is the final
time step in a trial.

5. COMPUTER SIMULATION
5.1. Setting of computer simulations
5.1.1. Simulated swarm robot and environment
According to the previous experiment using the swarm
mobile robots [14], the setting of computer simulations
was as follows. 10 differential wheeled robots (Fig. 2)
were used in this experiment. The robot’s diameter andheight are approximately D = 170 mm and H = 75mm, respectively. The robot is equipped with four infrared distance sensors located at the front of the bodyfor measuring the distance to other robots and walls (Fig.

Fig. 4 Set up for computer simulation: Initially, swarm
robots are always placed at the center.

65

avoidance module becomes active.
– If the controller detects no obstacles, the random walkmodule becomes active.
In the random walk module, the whole steps are divided into the rotation phase and the move-forward phase[14]. In the rotation phase, the controller determines
the direction of rotation and selects an angle of rotation
randomly from {45, 90, 135} degree. Then, a robot rotates until reaches the desired angle. In the move-forward
phase, a robot moves forward driving two wheels. Its one
step is set in two way: constant and Gaussian. For constant random walk, one step is set at 0.1 sec due to thatthe physics is updated at a rate of 10 times per control cycle. For Gaussian random walk, one step is determinedaccording to Gaussian distribution.

between robots and environment.
5.1.2. Controller
Fig. 5 shows the controller employed in this experiment. This takes its inspiration from the reference [11].
This controller is composed of the PFSM, a random walkmodule, an avoidance module, approach module and stop
module. In the PFSM (Fig.6), we have three states:{Approach, Wait, Repel}. Thus, m = 3 and |P | = 9.
• W ait: the robot stops immediately.
• Approach:– If the controller detects other robots, the robot approaches to the detected robots. When the distance between the robots is less than the threshold3 , the state transits to W ait to stop the robot.
– If the controller detects not a robot but obstacles, theavoidance module becomes active.
– If the controller detects neither robot or obstacle, therandom walk module becomes active.
• Repel:– If the controller detects other robots or obstacles, the5.1.3. Setting of the PSO
Computer simulations were conducted using particlesof size 20. The number of design variables was L = 9
mentioned above. The PSO was employed to design the
PFSM parameters. The parameters of the PSO adopted
in this experiment are as follows: c1 = 2.0, c2 = 2.0,
w = 0.5 in Eq.(2) for IWM and c1 = 2.0, c2 = 2.0,
wmin = 0.4, wmax = 0.9 in Eq.(4) for LDIWM. Eachrun lasted 200 iterations. We conducted 10 independentruns for each condition. All results were averaged over
10 runs.
We conduct two types of optimization problem;- single objective optimization (single obj) We employeda single objective function, f1 , in Eq.(13).
-two objective optimization (two obj) In addition to f1 ,we employed f2 in Eq.(15) in order to decrease the number of clusters. For this multiobjective optimization, weapplied Lexicographic ordering[18] where f2 has priority over f1 ; When f2 (P ) < f2 (P ′ ) or f2 (P ) > f2 (P ′ ),f1 is not evaluated. When f2 (P ) = f2 (P ′ ), f1 (P )and f1 (P ′ ) are compared for updating the position in thememory of the PSO. This priority considers the discreteness of f2 .

Wait

3 The threshold value was set to D mentioned in Section 5.1.1.

stopforward㻵turn rightturn left

approach layer

motorsapproachrobot
distance
sensorApproachstop layer

obstacle
distance
sensorRepel

turn right
avoidance㻵turn left

avoidance layer

forwardrandomwalk㻵turn right

exploration layer

turn left

5.2. Experimental Results
5.2.1. Objective function values
Figs. 7(a) and 7(b) show the best objective function
values of f1 for each iteration for single obj and two obj,
respectively. The IWM shows good performance regardless of the type of random walk. The LDIWM for Gaussian random walk shows the worst performance among
them. The objective function values in Fig. 7(a) were
better than those in in Fig. 7(b) for each condition.
Fig. 7(b) shows non-elitism, that is, the objective function values can not keep their best values in the previous
iteration. This is due to Lexicographic ordering where f2
has priority over f1 . Fig. 7(c) shows the best objectivefunction values of f2 for each iteration for two obj. The
same tendencies were observed as those in Fig. 7(a). The
differences among the conditions were small at the last
iteration. No condition was found where f2 converges to
1. This means that the swarm robots did not aggregate
into a single cluster.

Fig. 5 Subsumption architecture[16] with the PFSM

p33

p22
p32

Repel

Wait

p23
p13
p21

p31

Approach

p12

p11
Fig. 6 State transition diagram of the PFSM for aggregation66

2

Dispersion [x10 ]Table 1 Performance of the controllers obtained by the
IWM for constant random walk

12
11
10
9
8
7
6
5
4
3

iwm, const
iwm, gaussldiwm, const
ldiwm, gaussmetricstatistics
single obj
two obj

best
139
123

100

150

worst
0.1
0.3

0.21

(a)f1 for single objective optimization

12
11
10
9
8
7
6
5
4
3

c
avg
0.31
0.58

best
0.8
0.9

0.0

200

Iterations

2

worst
2515
2505

0.22
50

Dispersion [x10 ]

f1
avg
674
927

Repel

Wait

1.0
0.002
0.0
Approach

0.57
iwm, const
iwm, gaussldiwm, const
ldiwm, gauss
50

100
Iterations

150

0.004

0.993
(a)For single objective optimization

200

0.12

(b)f1 for two objective optimization

0.45
0.32

1/MaxClusterRatio

4

Repel

iwm, const
iwm, gaussldiwm, const
ldiwm, gauss

3

0.01

Wait

0.04
0.54

2

0.56

Approach

0.12

0.84

1
50

100
Iterations

150

200
(b)For two objective optimization(c)f2 for two objective optimization

Fig. 7 Objective function values for each iteration

Fig. 8 State transition diagram of the best optimized
PFSM

5.2.2. Performance of the best optimized controller
In this section, we investigate the performance of thebest optimized controllers obtained in the previous section. The IWM for constant random walk shows the best
performance for single obj and two obj. Table 1 shows theperformance in 50 trials on the dispersion (f1 in Eq.(13))
and the ratio of the number of robots in the largest cluster (c in Eq.(14)). The controller designed in single obj
shows smaller dispersion than the one designed in two
obj. The controller designed in two obj tends to form thebigger cluster while it keeps relatively large dispersion.

Figs. 8(a) and 8(b) show the state transition diagramof the best optimized PFSMs for single obj and two obj,
respectively. Each PFSM has its unique characteristics;
In the PFSM for dense aggregation (Fig. 8(a)), Wait always transits to Repel. This means an instant start even if
a state transits to Wait. Thus, swarm robots approach toeach other most of the time and they rarely repel. In the
PFSM for a large cluster (Fig. 8(b)), a state sometimes
transits to Wait. Wait transits to Approach or itself. Thistendency might give the ability to form larger clusters.
These tendencies are also confirmed in the trajectories

67

is interpretable. This means that the PFSM would betransferable to real environment and readjustable after its
transfer. Future work will investigate these potential abilities of the propose method in real robot experiments. In
literature, there are several swarm robotics control tasks
where the controller with the PFSM is employed. I would
like to apply the proposed method to those control tasks.

REFERENCES[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. Şahin, “Swarm Robotics: From Sources of Inspiration to Domains of Application,” Lecture Notes in
Computer Science, Volume 3342/2005, pp.10–20,
2005.
[4] S. Nolfi and D. Floreano: Evolutionary Robotics:
The Biology, Intelligence, and Technology of SelfOrganizing Machines, MIT Press, 2000.
[5] R. A. Brooks, “Artificial Life and Real Robots”, In
Proceedings of the First European Conference on
Artificial Life, pp.3–10, 1992.
[6] 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.
[7] O. Miglino, H. H. Lund and D. Nolfi, “Evolving Mobile Robots in Simulated and Real Environments”, Artificial Life 2, pp.417–434, 1995.
[8] 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.
[9] Y. Katada and K. Ohkura, “An Update Method ofComputer Simulation for Evolutionary Robotics”,
Intelligent Autonomous Systems 9 (IAS-9), pp. 357–
364, 2006.
[10] S. Garnier, C. Jost, R. Jeanson, J. Gautrais, M.
Asadpour, G. Caprari, G. Theraulaz, “Aggregation
Behaviour as a Source of Collective Decision in aGroup of Cockroach-like-robots”, In Lecture notes
in Computer Science: Vol. 3630. Advances in Artificial Life, Springer, pp. 169–178, 2005.
[11] O. Soysal, E. Bahçeci, E. Şahin, “Aggregation in
Swarm Robotic Systems: Evolution and Probabilistic Control”, Turkish Journal of Electrical Engineering and Computer Sciences, Vol. 15, No. 2, pp. 199–
225, 2007.
[12] M. Gauci, J. Chen, W. Li, T. J. Dodd, R. Groß,“Self-Organised Aggregation without Computation”, The International Journal of Robotics Research, Vol. 33, No. 9, pp. 1145–1161, 2014.
[13] J. Kennedy and R. C. Eberhart, “Particle swarm op-(a)For single objective optimization(b)For two objective optimization

Fig. 9 Trajectories of the swarm robots with the best optimized PFSM: Gray points show the initial positionsof the robots.

of the swarm robots. Fig. 9(a) shows the trajectories ofthe swarm robots with the PFSM in Fig. 8(a). The robots
frequently moved around to approach the other robots.
On the contrary, the robots with the PFSM in Fig. 8(b)stayed at a certain place as well as moved around.

6. CONCLUSIONSThis paper proposed to design a probabilistic finite
state machine for a swarm robot controller on an aggregation problem by using the PSO. Several computer simulations were conducted to investigate the validity of the
proposed method. The results obtained in this paper showthat the proposed method is useful for the aggregation
problem. The collective behavior of the swarm reflected
the characteristics of the best optimized PFSMs.
The two objective functions employed in this paper are
not in the relationship of trade-off which is found in general multi-objective optimization problems. Those objectives can coincide because a single cluster brings small
dispersion. In near future, another PSO can be applied togenerate selection pressure towards the Pareto front.
As confirmed in Section 5, the best optimized PFSM

68

timization”, In Proceedings of IEEE International
Conference on Neural Networks, pp. 1942–1948,
1995.
[14] Y. Katada, A. Nishiguchi, K. Moriwaki and R.
Watakabe, “Swarm Robotic Network Using Levy
Flight in Target Detection Problem”, Artificial Lifeand Robotics, Volume 21, Issue 3, pp. 295–301,
2016.
[15] Open Dynamics Engine (ODE), http://ode.org/.
[16] 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.
[17] R. Pfeifer and C. Scheier, Understanding Intelligence, MIT Press, 1999.
[18] C. A.C. Coello, G. T. Pulido and M. S. Lechuga,“Handling Multiple Objectives with Particle Swarm
Optimization”, IEEE Transactions on Evolutionary
Computation, Vol. 8, No. 3, pp. 256–279, 2004.

69