11institutetext: Faculty of Computer Science, University of Namur, Belgium
11email<EMAIL_ADDRESS>22institutetext: IRIDIA,
Université Libre de Bruxelles, Brussels, Belgium 22email:
<EMAIL_ADDRESS>
# Controlling Robot Swarm Aggregation through a Minority of Informed Robots

Antoine Sion 11 0000-0002-9901-3906 Andreagiovanni Reina 22
0000-0003-4745-992X Mauro Birattari 22 0000-0003-3309-2194 Elio Tuci 11
0000-0001-7345-671X

###### Abstract

Self-organized aggregation is a well studied behavior in swarm robotics as it
is the pre-condition for the development of more advanced group-level
responses. In this paper, we investigate the design of decentralized
algorithms for a swarm of heterogeneous robots that self-aggregate over
distinct target sites. A previous study has shown that including as part of
the swarm a number of informed robots can steer the dynamic of the aggregation
process to a desirable distribution of the swarm between the available
aggregation sites. We have replicated the results of the previous study using
a simplified approach: we removed constraints related to the communication
protocol of the robots and simplified the control mechanisms regulating the
transitions between states of the probabilistic controller. The results show
that the performances obtained with the previous, more complex, controller can
be replicated with our simplified approach which offers clear advantages in
terms of portability to the physical robots and in terms of flexibility. That
is, our simplified approach can generate self-organized aggregation responses
in a larger set of operating conditions than what can be achieved with the
complex controller.

##  1 Introduction

Swarm robotics can be defined as “the study of how a large number of
relatively simple physically embodied agents can be designed such that a
desired collective behavior emerges from the local interactions among the
agents and between the agents and the environment” [25]. Robot swarms aim to
be robust, flexible and scalable due to their decentralized nature and their
large group size. Brambilla et al. [2] and Schranz et al. [26] give an
overview of the basic collective behaviors that robot swarms can display in
order to achieve complex tasks such as coordinated motion, task allocation,
self-assembly or aggregation, which is studied in this paper. Aggregation is
used to group the swarm in a location—for example, to initiate a collaborative
task that requires physical proximity among the robots. Inspiration for self-
organized aggregation can be found in animals such as bees [29] or cockroaches
[18].

Several approaches have been studied in swarm robotics to achieve aggregation.
A popular method is to control the robots through probabilistic finite-state
machines. Soysal and Şahin [28] analyzed the performance of a three-state
finite-state machine while varying different transitional probabilistic
parameters. Variations of the controller yielded different aggregation
behaviors highlighting the importance of the evaluation metrics used such as
cluster sizes or total distances between robots. Cambier et al. [4] studied
the influence of cultural propagation in an aggregation scenario. Using a
simple finite-state machine with two states, robots communicated with each
other to modify the probabilistic parameters of their controllers. This
behavioral plasticity has ensured adaptability to dynamic environments and
performed better than classical approaches. Simpler methods have also been
proposed to achieve self-organized aggregation as in [16] where the only
sensor available to the robots is a binary sensor informing them on the
presence of another robot in their line of sight. The controller did not
require computation and the parameters were chosen via a grid search. This
approach is validated with successful experiments with 1000 simulated robots
and 40 physical robots. Francesca et al. [14] showed that self-organized
aggregation can be achieved by robots controlled by probabilistic finite-state
machines that are generated automatically.

Artificial evolution has also been used to evolve controllers resulting in
self-organized aggregation [8]. Francesca et al. [15] evolved a neural network
controller to perform self-organized aggregation and showed that the dynamics
of the resulting collective behavior closely matches the one of a biological
model that describes how cockroaches select a resting shelter. Kengyel et al.
[20] studied aggregation in heterogeneous robot swarms where each robot ran
one among four distinct behaviors inspired from aggregation in honeybees. The
number of robots running the alternative behaviors were varied using an
evolutionary algorithm. The results of the simulations show that through the
cooperation of different types of behaviors, the heterogeneous swarm performs
better than its homogeneous equivalent.

In this study, we revisit the methods illustrated in [13] to steer self-
organized aggregation responses with the use of informed robots. Generally
speaking, the use of informed individuals to steer the dynamic process leading
to the group response is a method to guide self-organisation in distributed
systems inspired by behaviors observed in biology. In a seminal study, Couzin
et al. [6] studied the influence of informed individuals in collective
decision making in the context of collective animal motion. The informed
individuals had a preferred direction of motion and biased the collective
decision in that direction. The rest of the swarm did not have any preferred
direction of motion, nor was able to recognise informed individuals as such.
The study shows that the accuracy of the group motion towards the direction
known by the informed agents increases asymptotically as the proportion of
informed individuals increases, and that the larger the group, the smaller the
proportion of informed individuals needed to guide the group with a given
accuracy. A recent study on cockroaches [3] has shown that a minority of
individuals preferring one shelter over the other can influence the population
to reach a consensus for only one site. The technique of using informed
individuals to steer the collective dynamics has already been used in
artificial systems with various types of collective behaviors. For example,
informed individuals have been used in flocking [5, 9, 10] to guide the robot
swarm in the desired direction, in collective decision making [23, 7] to
achieve adaptability, and in self-organized aggregation to differentiate
between multiple sites [12, 13, 11, 17].

In this paper, we replicate the experimental setup originally illustrated in
[13] by showing that equally effective aggregation dynamics can be obtained
with a largely simplified approach. The aggregation response described in [13]
took place in a circular arena with two aggregation sites, the black and the
white site (see Fig. 1a). The goal of the swarm was to distribute the robots
between the two sites in a desired proportion (e.g. 70% of the robots on the
white site and the remaining 30% on the black one) while minimizing the total
proportion of informed robots. Non-informed robots treated both sites in the
same way while informed robots were designed to systematically avoid one of
the sites and to rest on the other. The swarm comprised a certain proportion
of informed robots, among which there were those that selectively rested on
the black site and those that rested only on the white site. The study shows
that the proportion of robots on black/white site at the end of an aggregation
process matches the proportion of informed robots resting only on the
black/white site relative to the number of informed robots in the swarm (see
Sec. 2 for more details). These aggregation dynamics can be achieved using a
relatively low percentage of informed robots in the swarm—roughly 30% for a
swarm of 100 robots.

In [13], the robots were controlled by a probabilistic finite-state machine
illustrated in details in Sec. 2 and depicted in Fig. 1c. In this study, we
question the nature of the mechanisms regulating the transition from state
Stay ($\mathcal{S}$) to state Leave ($\mathcal{L}$), and the type of
communication protocol involved in these mechanisms, by suggesting an
alternative solution that largely simplifies the rule regulating the
transition between these two states for non-informed robots. Following the
“Occam’s razor” principle, the solution we illustrate in this paper can
represent a preferable alternative to the more complex solution proposed in
[13] and can help the porting of the control system to the physical robots.
Moreover, we remove differences both in behavior and in communication
capabilities between informed and non-informed robots that, in our view,
undermine the robustness of the aggregation process. For example, in [13],
non-informed robots rest on an aggregation site if this is already inhabited
by at least one informed robot that signals its presence on the site. Thus, an
aggregation process can only be initiated by informed robots. This can
significantly delay the aggregation process, in particular in those operating
conditions in which the probability that an informed robot finds and rests on
an aggregation site is relatively low. Additionally, this makes the swarm less
robust to the loss of informed robots. In the extreme case of a loss of all
informed robots, there will be no aggregation at all. With our approach,
aggregation dynamics can emerge independently of the presence of informed
robots. This increases the range of group responses that the swarm can
generate without interfering with the effectiveness of the aggregation
dynamics.

##  2 Materials and Methods

|  |
---|---|---
(a) | (b) | (c)
Figure 1: (a) The simulated circular arena with the robots (blue dots) and the
aggregation sites (black and white circles). (b) The Foot-bot robot [1]; image
from www.swarmanoid.org. (c) The probabilistic finite-state machine
controlling the robot behavior composed of three states; $\mathcal{RW}$
(Random Walk), $\mathcal{S}$ (Stay) and $\mathcal{L}$ (Leave).

The experiments are ran using ARGoS [21], which is one of the best-performing
simulators to run physics-based simulations for large-scale robot swarms [22].
The robots operate in a circular environment where the aggregation sites are
circular areas located at equal distance between the center of the arena and
its perimetric wall (Fig. 1a). One site is painted in black, the other in
white; the arena floor is grey. We perform our experiments with a simplified
model of the Foot-bot [1] (see Fig. 1b), a mobile robot that we equip with
three types sensors: a ground sensor, an array of proximity sensors, and the
range-and-bearing sensor. The ground sensor is located on the robot’s
underside, to detect the color of the ground; it returns 1, 0.5, and 0 when a
robot is on a white, grey, and black floor, respectively. The proximity
sensors use infrared (IR) signals to detect obstacles such as other robots or
the arena walls. The range-and-bearing sensor is used by the robots to
exchange simple communication signals when they are located at less than 0.8 m
from each other.

A trial starts with the robots randomly placed in the arena following a
uniform distribution, and it terminates after 30,000 s. As in [13], the swarm
of size $N$ is composed of informed robots (in proportion $\rho_{I}$) and non-
informed ones (in proportion $1-\rho_{I}$). During a trial, both informed and
non-informed robots move randomly in the environment at 10
$\nicefrac{{cm}}{{s}}$. Non-informed robots can rest on any aggregation site
as soon as they enter into one of them. Informed robots selectively avoid to
rest on one site and rest only on the other one. There are informed robots for
black—which avoid to rest on the white site, and rest on the black aggregation
site only—and informed robots for white—which avoid to rest on the black site,
and rest on the white site only. Let $N_{sb}$ be the number of informed robots
for black, $N_{sw}$ the number of informed robots for white,
$\rho_{sb}=\frac{N_{sb}}{N_{sb}+N_{sw}}$ the proportion of informed robots for
black relative to the total number of informed robots, and
$\rho_{sw}=1-\rho_{sb}$ the proportion of informed robots for white relative
to the total number of informed robots. Firat et al. [13] demonstrated that,
with a relatively small proportion of informed robots in the swarm
($\rho_{I}\approx 0.3$) and for different values of $\rho_{sb}$ and
$\rho_{sw}$, the number of robots aggregated on the black site is
approximately equal to $N\,\rho_{sb}$, while the number of those aggregated on
the white site is approximately equal to $N\,\rho_{sw}$, for swarms of size
$N=50$ and for $N=100$. Our objective is to replicate this aggregation
dynamics with a largely simplified model illustrated below.

The primary difference between our model and the one introduced in [13]
resides in the way in which the robots communicate while within an aggregation
site. In [13], communication is needed by the robots to count how many
informed robots are resting on the aggregation site within the communication
range. In our model, communication is needed by the robots to count how many
robots (including both informed and non-informed) are resting on the
aggregation site within the communication range. This small difference between
the two models derives from a rather substantial modification of the robots’
communication system which we apply to the original model as illustrated in
[13] to improve the robustness and flexibility of the swarm’s behavior. In
[13], informed robots emits signals (i.e., one bit signal), while non-informed
robots can only receive these signals, they can not emit them. Contrary to
[13], in our model, informed and non-informed robots are functionally
identical with respect to communication; they can both send and receive
signals. This implies that, contrary to [13], in our model communication
signals indicate only the presence of spatially proximal robots within a site
without saying anything about the identity of the signal’s sender (i.e.,
whether it is an informed or a non-informed robot). Therefore, the results of
our study can generalise to application scenarios where the communication is
indirect, i.e., the robots count the neighbors in its view range without the
need of an exchange of messages and without the need of distinguishing between
informed and non-informed robots.

Both in [13] and in our model, the robots are controlled by a probabilistic
finite state-machine (hereafter PFSM, see Fig. 1c), which is updated every 2
seconds and comprises three states: Random Walk ($\mathcal{RW}$), Stay
($\mathcal{S}$), and Leave ($\mathcal{L}$). However, in our model, the rules
that regulate the transition between different states have been modified with
respect to the original implementation as illustrated in [13]. In the
following, we describe the PFSM and we illustrate the modifications we
introduced with respect to [13].

At the beginning of a trial, the robots are in state $\mathcal{RW}$. They
explore the environment while avoiding obstacles with an isotropic random walk
based on straight motion and random rotation. The robots move straight for 5 s
at a speed of 10 $\nicefrac{{cm}}{{s}}$, and turn with turning angles taken
from a wrapped Cauchy distribution [19]. The probability density function is
the following :

$f_{\omega}(\theta,\mu,\rho)=\frac{1}{2\pi}\frac{1-\rho^{2}}{1+\rho^{2}-2\rho\cos(\theta-\mu)},\quad
0<\rho<1,$ (1)

where $\mu$ is the average value of the distribution and $\rho$ the skewness.
With $\rho=0$, the wrapped Cauchy distribution becomes uniform and there is no
correlation between the movement directions before and after a turn. With
$\rho=1$, we have a Dirac distribution and the robot follows a straight line.
Here we take $\rho=0.5$. During this behavior, when the proximity sensors
detect an obstacle (the wall or other robots), the robot stops and turns of an
angle chosen uniformly in the interval $[-\pi,\pi]$. After turning, if there
is no obstruction ahead, the robot resumes its normal random walk otherwise,
it repeats the manoeuvre.

Both in our model and in [13], informed robots systematically transition from
state $\mathcal{RW}$ to the state $\mathcal{S}$ when they enter their
preferred site, otherwise they move randomly. While in $\mathcal{S}$, informed
robots rest on the aggregation site. The condition that triggers the
transition from state $\mathcal{RW}$ to the state $\mathcal{S}$ for non-
informed robots is different in our model with respect to [13]. In particular,
in [13], non-informed robots switch to state $\mathcal{S}$ if, while entering
into an aggregation site, they perceive the presence of informed robots at the
site. Contrary to [13], in our approach, non-informed robots systematically
transition from state $\mathcal{RW}$ to state $\mathcal{S}$ whenever they
enter into an aggregation site regardless of the presence of any other type of
robot at the site. In both studies, when a robot enters an aggregation site,
it continues moving forward for 10 seconds to avoid a congestion of robots on
the perimeter of the site that could eventually hinder other robots from
entering. Then, it rests on the site.

Both in our model and in [13], informed robots never leave the state
$\mathcal{S}$. That is, once an informed robot finds its preferred site, it
never leaves the site. Non-informed robots transition from state $\mathcal{S}$
to state $\mathcal{L}$ with a probability that is computed differently with
respect to [13]. In [13], non-informed robots transition from state
$\mathcal{S}$ to state $\mathcal{L}$ with a probability $P_{Leave}$ computed
as

$P_{Leave}=\begin{cases}e^{-a(k-|n-x|)}&\text{if $n>0$,}\\\ 1&\text{if
$n=0$;}\\\ \end{cases}$ (2)

where $n$ and $x$ are the number of informed robots resting on the site within
communication distance at this moment and at the moment of joining this site,
respectively. Parameters $a$ and $k$ are fixed to $a=2$ and $k=18$. With Eq.
(2), the transition from state $\mathcal{S}$ to state $\mathcal{L}$ is based
on the temporal variation in the number of informed robots perceived at an
aggregation site.

Contrary to [13], in our model the probability $P^{{}^{\prime}}_{Leave}$ that
regulates the transition from state $\mathcal{S}$ to state $\mathcal{L}$ for
non-informed robots is computed as

$P^{{}^{\prime}}_{Leave}=\alpha e^{-\beta n}\;,$ (3)

with $n$ the number of robots (including both informed and non-informed)
within communication distance, $\alpha=0.5$, and $\beta=2.25$111The parameters
$\alpha$ and $\beta$ have been fine-tuned to achieve a symmetry-breaking
behavior in a homogeneous swarm of $N=100$ non-informed robots using the same
arena setup illustrated in [13].. Contrary to [13], $P^{{}^{\prime}}_{Leave}$
relies on the fact that any type of robot in the swarm can broadcast and
perceive communication signals while resting on a site. This transforms
$P^{{}^{\prime}}_{Leave}$ into something that depends on the estimated local
density of (any type of) robots, while in [13] $P_{Leave}$ depends on the
variation in the number of informed robots in the neighborhood. Hence,
$P_{Leave}$ requires the robots to use memory and distinguish between types of
robots, $P^{{}^{\prime}}_{Leave}$ does not.

Both in [13] and in our approach a robot in state $\mathcal{L}$ exits an
aggregation site by moving forward and avoiding obstacles. Once outside the
site, it systematically transitions to state $\mathcal{RW}$.

To summarise, the main differences between the model illustrated in [13] and
our model are the following: (i) in [13] informed robots only emit signals and
non-informed robots only receive signals. In our models, both informed and
non-informed robots send and receive communication signals. (ii) In [13], non-
informed robots rest on a site only if they perceive the presence of informed
robots, and leave a site with a probability that depends on the variation in
the number of perceived informed robots. Hence, it requires memory of the past
and a comparison between the present and the past state. In our model, non-
informed robots systematically rest on an aggregation site, and they leave it
with a probability that is determined by the current local density of robots
(regardless of whether they are informed or non-informed) at the site.
Therefore, our model is reactive and does not require any form of memory. In
the next section, we show that the above mentioned modifications improve the
robustness and the behavioral flexibility of the swarm.

##  3 Results

Table 1: Parameters values Experiment parameters | Values
---|---
Swarm size ($N$) | $\\{50,100\\}$
Proportion of informed robots ($\rho_{I}$) | $\\{0.1,0.2,0.3,0.4,0.5\\}$
Proportion of black informed robots ($\rho_{sb}$) | $\\{0.5,0.6,0.7,0.8,0.9,1\\}$
Arena diameter | 12.9 m (for $N=50$), 19.2 m (for $N=100$)
Aggregation site diameter | 2.8 m (for $N=50$) , 4.0 m (for $N=100$)

In this section, we compare the performance of swarms of robots controlled by
the PFSM as originally illustrated in [13] and by our modified PFSM presented
in Sec. 2. We evaluate the two approaches in several different conditions
given by all the possible combinations of the parameters’ values listed in
Table 1. In particular, we vary the swarm size ($N$), the proportion of
informed robots in the swarm ($\rho_{I}$), and the proportion of black
($\rho_{sb}$) and white ($\rho_{sw}$) informed robots. As in [13], while
changing the swarm size, the swarm density has been kept constant by changing
the diameter of the arena and of the aggregation sites (see Table 1 for
details).

We recall that the task of the robots is to distribute themselves on each site
in a way that the robots resting on the black and white sites should be equal
to $N\,\rho_{sb}$ and $N\,\rho_{sw}$, respectively, with the proportion of
informed robots $\rho_{I}$ being as small as possible.

|  |  |
---|---|---|---
(a) | (b) | (c) | (d)
|  |  |
(e) | (f) | (g) | (h)
Figure 2: Graphs showing the median over 20 trials of the number of robots on
each site at time $t=30,000$ s (end of trials) for $N=50$ robots (top row) and
$N=100$ robots (bottom row). For our approach the results are shown in (a) and
(e) with reference to the black site, and in (b) and (f) with reference to the
white site. For the approach in [13], the results are shown in (c) and (g)
with reference to the black site, and in (d) and (h) with reference to the
white site. On all graphs, the y-axis refers to the proportion of informed
robots in the swarm ($\rho_{I}$) and the shades of grey refer to the number of
robots at each aggregation site with white indicating zero robots, and black
indicating 50 robots in graphs on top row, and 100 robots in graphs on bottom
row. The x-axis refers to ($\rho_{sb}$) in (a), (c), (e), and (g) and to
($\rho_{sw}$) in (b), (d), (f), and (h).

For each testing condition, and for each approach, we have run 20 trials.
Figure 2 shows, for both approaches, the median over 20 trials of the number
of robots resting on each site at the end of each trial (i.e., at time
$t=30,000$ s) for a swarm of $N=50$ robots (see Fig. 2, graphs in top row) and
for a swarm of $N=100$ robots (see Fig. 2, graphs in bottom row). For our
approach the results are shown in Figs. 2a and 2e with reference to the black
site, and in Figs. 2b and 2f with reference to the white site. For the
approach in [13], the results are shown in Figs. 2c and 2g with reference to
the black site, and in Figs. 2d and 2h with reference to the white site.

With a swarm of $N=50$ robots, both approaches perform relatively well, with
the median of the number of robots resting on the black site increasing for
progressively higher values of $\rho_{sb}$ (see Figs. 2a, and 2c) and
decreasing for progressively lower values of $\rho_{sw}$ (see Figs. 2b and
2d). These trends can be clearly observed, for both approaches, for any values
of $\rho_{I}$, even for the smallest tested value $\rho_{I}=0.1$ (i.e, 10% of
informed robots in the swarm). However, our approach performs better than the
approach in [13] for values of $\rho_{I}>0.3$ and $\rho_{sb}>0.8$. In these
conditions, our results are closer to the target robot distributions than the
results obtained with the approach from [13] (see Figs. 2a, 2b, 2c, and 2d,
top right corners). With a larger swarm size $N=100$, our results are closer
to the target robot distributions for both $\rho_{I}<0.3$ and $\rho_{sb}<0.7$
(see Figs. 2e, 2f, 2g, and 2h, bottom left corners) and for $\rho_{I}>0.3$ and
$\rho_{sb}>0.8$ (see Figs. 2e, 2f, 2g, and 2h, top right corners).

|  |  |
---|---|---|---
(a) | (b) | (c) | (d)
|  |  |
(e) | (f) | (g) | (h)
Figure 3: Graphs showing the interquartile range over 20 trials of the number
of robots on each site at $t=$ 30,000 s (end of trial). See the caption of
Fig. 2 for more details.

Figure 3 shows the interquartile ranges of the number of robots on each site
at $t=30,000$ s for both approaches for a swarm size of $N=50$ (graphs in top
row) and $N=100$ (graphs in bottom row). For low proportions of informed
robots ($\rho_{I}<0.3$), our approach shows a slightly higher variability in
the final distribution of the swarms (Figs. 3a, 3b, 3e, and 3f) than the
approach in [13] (see Figs. 3c, 3d, 3g, and 3h). However, at higher
proportions of informed robots($\rho_{I}>0.3$), the variability is roughly the
same for the two approaches in the majority of the parameter configurations.

With our modified approach, we have run further tests with a swarm entirely
made of non-informed robots (i.e., $\rho_{I}=0$). The removal of informed
robots from the swarm prevents the model illustrated in [13] from generating
robots’ aggregates, as the transition from state random walk $\mathcal{RW}$ to
the state stay $\mathcal{S}$ (i.e., resting on the aggregation site) of non-
informed robots is triggered by the perception of an aggregation site
populated by informed robots. As shown in Fig. 4, in our model, a swarm
without informed robots can break the environmental symmetry by repeatedly
forming a single aggregate on either the black or the white aggregation site.
The median of the number of robots not resting on any site at the end of the
experiment is 4 with an interquartile range of 5. This shows that the
modifications we made to the system as originally illustrated in [13] enlarges
the swarm behavioral repertoire without loss of performance with respect to
the results shown in [13].

Figure 4: Graphs showing the frequency distribution of the number of robots on
each aggregation site, at the end of 50 runs, with each trial lasting $t=$
30,000 s, and without informed robots in the swarm ($\rho_{I}=0$). The swarm
size is $N=100$.

The results of our tests show that our simplified model generates aggregates
that match equally fine or even better than in [13] the expected distributions
of robots on each aggregation site for each tested combination of values of
$\rho_{I}$, $\rho_{sb}$, and $\rho_{sw}$. We show, however, that our approach
generates a slightly higher between-trials variability than the one in [13].
This is due to the fact that when every robot can start the formation of
clusters in the sites, as it is in our approach, clusters composed exclusively
of non-informed robots can also appear. When the proportion of informed robots
is low, the disruptive effect of these types of aggregates on the desired
aggregation dynamics increases as well as with the between trials variability.
We also show that, in the absence of informed robots in the swarm, the robots
break the environmental symmetry by repeatedly generating a single aggregate
on either the black or the white site. Since any aggregation behavior in the
absence of informed robots is precluded to the swarm as modelled in [13], we
conclude that the modifications introduced by us improve the robustness and
the behavioral flexibility of the swarm.

##  4 Conclusions

We proposed a simplified version of an existing aggregation method using
informed individuals in a swarm of robots. We have presented the results of a
comparative study that quantitatively evaluates the effectiveness of two
different algorithms in driving the aggregation dynamics in swarms of
heterogeneous robots made of informed and non-informed robots. The original
approach, illustrated in [13], is based on a finite-state machine controller
by which individual robots only transit from state random walk $\mathcal{RW}$
(corresponding to random diffusion in the environment) to state Stay
$\mathcal{S}$ (corresponding to resting on an aggregation site) when they end
up on an aggregation site populated by informed robots. Moreover, the robots
transit from state Stay $\mathcal{S}$ to state Leave $\mathcal{L}$
(corresponding to leaving the aggregation site) with a probability that
depends on the variation in the perceived number of informed robots at the
site during resting, thus requiring memory, however limited. The functional
characteristics of this finite-state machine are supported by a communication
protocol in which only informed robots can send signals and non-informed
robots can receive signals. We have replicated the study illustrated in [13]
with a simplified finite-state machine controller in which the robots rest on
a site regardless of the presence of informed robots, and they leave the site
with a memoryless probability that depends on the current perceived local
density at the aggregation site of any type of robots. Moreover, we have re-
established a functional equivalence in communication capabilities between
informed and non-informed robots. That is, in our approach, there is no
distinction in communication capabilities between the types of robots, both
can send and receive messages that signal their presence at an aggregation
site. This implementation choice allows the robots to estimate the robot
density in their neighborhood without any need of distinguishing between robot
types. Our comparative tests show that the swarms controlled by our approach
generate aggregation dynamics that are never less performing than [13], and in
some experimental conditions they are closer to the target robot distributions
than the one observed with the approach illustrated in [13]. We showed that,
our approach, contrary to the one introduced in [13], suffers from a slightly
higher between-trials variability in the number of robots resting at each
aggregation site at the end of a trial. We also show that our approach can
generate a larger set of aggregation dynamics than in [13], since in the
absence of informed robots the swarm controlled with our simplified approach
systematically forms a single aggregate in one of the aggregation sites, while
the swarm controlled by the approach in [13] never aggregates. Based on the
“Occam’s razor” principle of parsimony, we claim that due to its simplicity,
effectiveness, and robustness to a larger set of operating conditions, our
approach should be favored over the one introduced in [13] to control the
aggregation dynamics using informed robots.

Future research directions will consider setups with three or more aggregation
sites to verify if, with our approach, the expected distributions of robots at
the aggregation sites are attained in more complex environments. We also plan
to validate the approach illustrated in this paper with the physical robot
Kilobots [24] using the Kilogrid platform [30]. This will allow the study of
the convergence time of the system and the possible speedup of the dynamics
[27].

### Acknowledgements.

This work was supported by Service Public de Wallonie Recherche under grant n°
2010235 - ARIAC by DIGITALWALLONIA4.AI; by the European Research Council (ERC)
under the European Union’s Horizon 2020 research and innovation programme
(grant agreement No 681872); and by Belgium’s Wallonia-Brussels Federation
through the ARC Advanced Project GbO (Guaranteed by Optimization). A. Reina
and M. Birattari acknowledge the financial support from the Belgian
F.R.S.-FNRS, of which they are Chargé de Recherches and Directeur de
Recherches, respectively.

## References

  * [1] Bonani, M., Longchamp, V., Magnenat, S., Rétornaz, P., Burnier, D., Roulet, G., Vaussard, F., Bleuler, H., Mondada, F.: The MarXbot, a miniature mobile robot opening new perspectives for the collective-robotic research. In: 2010 IEEE/RSJ International Conference on Intelligent Robots and Systems. pp. 4187–4193. IEEE (2010)
  * [2] Brambilla, M., Ferrante, E., Birattari, M., Dorigo, M.: Swarm robotics: a review from the swarm engineering perspective. Swarm Intelligence 7(1), 1–41 (2013). https://doi.org/10.1007/s11721-012-0075-2
  * [3] Calvo Martín, M., Eeckhout, M., Deneubourg, J.L., Nicolis, S.C.: Consensus driven by a minority in heterogenous groups of the cockroach periplaneta americana. iScience 24(7) (2021). https://doi.org/10.1016/j.isci.2021.102723
  * [4] Cambier, N., Albani, D., Frémont, V., Trianni, V., Ferrante, E.: Cultural evolution of probabilistic aggregation in synthetic swarms. Applied Soft Computing 113, 108010 (2021). https://doi.org/10.1016/j.asoc.2021.108010
  * [5] Çelikkanat, H., Şahin, E.: Steering self-organized robot flocks through externally guided individuals. Neural Computing and Applications 19(6), 849–865 (2010). https://doi.org/10.1007/s00521-010-0355-y
  * [6] Couzin, I.D., Krause, J., Franks, N.R., Levin, S.A.: Effective leadership and decision-making in animal groups on the move. Nature 433, 513–516 (2005). https://doi.org/10.1038/nature03236
  * [7] De Masi, G., Prasetyo, J., Zakir, R., Mankovskii, N., Ferrante, E., Tuci, E.: Robot swarm democracy: the importance of informed individuals against zealots. Swarm Intelligence 15(4), 315–338 (2021). https://doi.org/10.1007/s11721-021-00197-3
  * [8] Dorigo, M., Trianni, V., Şahin, E., Groß, R., Labella, T.H., Baldassarre, G., Nolfi, S., Deneubourg, J.L., Mondada, F., Floreano, D., Gambardella, L.M.: Evolving self-organizing behaviors for a swarm-bot. Autonomous Robots 17(2), 223–245 (2004). https://doi.org/10.1023/B:AURO.0000033973.24945.f3
  * [9] Ferrante, E., Turgut, A.E., Huepe, C., Stranieri, A., Pinciroli, C., Dorigo, M.: Self-organized flocking with a mobile robot swarm: a novel motion control method. Adaptive Behavior 20(6), 460–477 (2012). https://doi.org/10.1177/1059712312462248
  * [10] Ferrante, E., Turgut, A.E., Stranieri, A., Pinciroli, C., Birattari, M., Dorigo, M.: A self-adaptive communication strategy for flocking in stationary and non-stationary environments. Natural Computing 13(2), 225–245 (2014). https://doi.org/10.1007/s11047-013-9390-9
  * [11] Firat, Z., Ferrante, E., Cambier, N., Tuci, E.: Self-organised aggregation in swarms of robots with informed robots. In: Fagan, D., Martín-Vide, C., M. O’Neill, M.A. Vega-Rodríguez (eds.) Theory and Practice of Natural Computing. pp. 49–60. Springer (2018). https://doi.org/10.1007/978-3-030-04070-3_4
  * [12] Firat, Z., Ferrante, E., Gillet, Y., Tuci, E.: On self-organised aggregation dynamics in swarms of robots with informed robots. Neural Computing and Applications 32(17), 13825–13841 (2020). https://doi.org/10.1007/s00521-020-04791-0
  * [13] Firat, Z., Ferrante, E., Zakir, R., Prasetyo, J., Tuci, E.: Group-size regulation in self-organized aggregation in robot swarms. In: Dorigo, M., Stützle, T., Blesa, M.J., Blum, C., Hamann, H., Heinrich, M.K., Strobel, V. (eds.) Swarm Intelligence. pp. 315–323. Springer International Publishing, Cham (2020). https://doi.org/10.1007/978-3-030-60376-2_26
  * [14] Francesca, G., Brambilla, M., Brutschy, A., Trianni, V., Birattari, M.: AutoMoDe: A novel approach to the automatic design of control software for robot swarms. Swarm Intelligence 8(2), 89–112 (2014). https://doi.org/10.1007/s11721-014-0092-4
  * [15] Francesca, G., Brambilla, M., Trianni, V., Dorigo, M., Birattari, M.: Analysing an evolved robotic behaviour using a biological model of collegial decision making. In: Ziemke, T., Balkenius, C., Hallam, J. (eds.) From Animals to Animats 12: 12th International Conference on Simulation of Adaptive Behavior, SAB 2012. Lecture Notes in Computer Science, vol. 7426, pp. 381–390. Springer, Berlin, Germany (2012). https://doi.org/10.1007/978-3-642-33093-3_38
  * [16] Gauci, M., Chen, J., Li, W., Dodd, T.J., Groß, R.: Self-organized aggregation without computation. The International Journal of Robotics Research 33(8), 1145–1161 (2014). https://doi.org/10.1177/0278364914525244
  * [17] Gillet, Y., Ferrante, E., Firat, Z., Tuci, E.: Guiding aggregation dynamics in a swarm of agents via informed individuals: an analytical study. In: The 2019 Conference on Artificial Life: A Hybrid of the European Conference on Artificial Life (ECAL) and the International Conference on the Synthesis and Simulation of Living Systems (ALIFE). pp. 590–597. MIT Press (2019). https://doi.org/10.1162/isal_a_00225
  * [18] Jeanson, R., Rivault, C., Deneubourg, J.L., Blanco, S., Fournier, R., Jost, C., Theraulaz, G.: Self-organized aggregation in cockroaches. Animal Behaviour 69(1), 169–180 (2005). https://doi.org/10.1016/j.anbehav.2004.02.009
  * [19] Kato, S., Jones, M.: An extended family of circular distributions related to wrapped cauchy distributions via brownian motion. Bernoulli 19(1), 154–171 (2013), http://www.jstor.org/stable/23525635
  * [20] Kengyel, D., Hamann, H., Zahadat, P., Radspieler, G., Wotawa, F., Schmickl, T.: Potential of heterogeneity in collective behaviors: A case study on heterogeneous swarms. In: Chen, Q., Torroni, P., Villata, S., Hsu, J., Omicini, A. (eds.) PRIMA 2015: Principles and Practice of Multi-Agent Systems. pp. 201–217. Springer International Publishing, Cham (2015)
  * [21] Pinciroli, C., Trianni, V., O’Grady, R., Pini, G., Brutschy, A., Brambilla, M., Mathews, N., Ferrante, E., Di Caro, G., Ducatelle, F., Birattari, M., Gambardella, L.M., Dorigo, M.: ARGoS: a modular, parallel, multi-engine simulator for multi-robot systems. Swarm Intelligence 6(4), 271–295 (2012). https://doi.org/10.1007/s11721-012-0072-5
  * [22] Pitonakova, L., Giuliani, M., Pipe, A., Winfield, A.: Feature and performance comparison of the V-REP, Gazebo and ARGoS robot simulators. In: Giuliani, M., Assaf, T., Giannaccini, M.E. (eds.) Towards Autonomous Robotic Systems. pp. 357–368. Springer International Publishing, Cham (2018). https://doi.org/10.1007/978-3-319-96728-8_30
  * [23] Prasetyo, J., De Masi, G., Ferrante, E.: Collective decision making in dynamic environments. Swarm Intelligence 13(3), 217–243 (2019). https://doi.org/10.1007/s11721-019-00169-8
  * [24] Rubenstein, M., Ahler, C., Hoff, N., Cabrera, A., Nagpal, R.: Kilobot: A low cost robot with scalable operations designed for collective behaviors. Robotics and Autonomous Systems 62(7), 966–975 (2014). https://doi.org/10.1016/j.robot.2013.08.006
  * [25] Şahin, E., Girgin, S., Bayindir, L., Turgut, A.E.: Swarm Robotics, pp. 87–100. Springer Berlin Heidelberg (2008). https://doi.org/10.1007/978-3-540-74089-6_3
  * [26] Schranz, M., Umlauft, M., Sende, M., Elmenreich, W.: Swarm robotic behaviors and current applications. Frontiers in Robotics and AI 7, 36 (2020). https://doi.org/10.3389/frobt.2020.00036
  * [27] Sion, A., Reina, A., Birattari, M., Tuci, E.: Impact of the update time on the aggregation of robotic swarms through informed robots (2022), accepted to the SAB 2022 conference
  * [28] Soysal, O., Şahin, E.: Probabilistic aggregation strategies in swarm robotic systems. In: Proceedings 2005 IEEE Swarm Intelligence Symposium, 2005\. SIS 2005. pp. 325–332 (2005). https://doi.org/10.1109/SIS.2005.1501639
  * [29] Szopek, M., Schmickl, T., Thenius, R., Radspieler, G., Crailsheim, K.: Dynamics of collective decision making of honeybees in complex temperature fields. PLOS ONE 8(10), 1–11 (2013). https://doi.org/10.1371/journal.pone.0076250
  * [30] Valentini, G., Antoun, A., Trabattoni, M., Wiandt, B., Tamura, Y., Hocquard, E., Trianni, V., Dorigo, M.: Kilogrid: a novel experimental environment for the Kilobot robot. Swarm Intelligence 12(3), 245–266 (2018). https://doi.org/10.1007/s11721-018-0155-z


$\displaystyle\leq\|x_{t}-x^{\star}\|\sqrt{2\underset{z\sim\mu_{t}}{\operatorname{\mathbb{E}}}\big{[}L(z)^{2}\big{]}\Big{(}\underset{z\sim\mu_{t}}{\operatorname{\mathbb{E}}}\big{[}\|g_{x^{\star}}(z)\|^{2}\big{]}+\underset{z\sim\mu_{t}}{\operatorname{\mathbb{E}}}\big{[}\|g_{x_{t}}(z)-g_{x^{\star}}(z)\|^{2}\big{]}\Big{)}}$
$\displaystyle\leq\|x_{t}-x^{\star}\|\sqrt{2\underset{z\sim\mu_{t}}{\operatorname{\mathbb{E}}}\big{[}L(z)^{2}\big{]}\Big{(}\underset{z\sim\mu_{t}}{\operatorname{\mathbb{E}}}\big{[}\|g_{x^{\star}}(z)\|^{2}\big{]}+\|x_{t}-x^{\star}\|^{2}\cdot\underset{z\sim\mu_{t}}{\operatorname{\mathbb{E}}}\big{[}L(z)^{2}\big{]}\Big{)}}$
$\displaystyle\to 0,$

where we used Hölder’s inequality, condition 2 of the lemma, and (40).

To complete the proof, it now suffices to show
${\operatorname{\mathbb{E}}}_{z\sim\mu_{t}}\big{[}g_{x^{\star}}(z)g_{x^{\star}}(z)^{\top}\big{]}\rightarrow\Sigma$.
To this end, we define the step-like function
$\varphi_{q}\colon{\mathbf{R}}\rightarrow{\mathbf{R}}$ for any
$q\in{\mathbf{R}}$ by setting

$\varphi_{q}(x)=\begin{cases}1&\text{if }x\leq q,\\\ -x+q+1&\text{if }q\leq
x\leq q+1,\\\ 0&\text{if }q+1\leq x.\end{cases}$

Fix a constant $\delta>0$. Then we have the decomposition

$\displaystyle\underset{z\sim\mu_{t}}{\operatorname{\mathbb{E}}}\big{[}g_{x^{\star}}(z)$
$\displaystyle g_{x^{\star}}(z)^{\top}\big{]}-\Sigma$
$\displaystyle=\underset{z\sim\mu_{t}}{\operatorname{\mathbb{E}}}\big{[}g_{x^{\star}}(z)g_{x^{\star}}(z)^{\top}\big{]}-\underset{z\sim\mu^{\star}}{\operatorname{\mathbb{E}}}\big{[}g_{x^{\star}}(z)g_{x^{\star}}(z)^{\top}\big{]}$
$\displaystyle=\underbrace{\underset{z\sim\mathcal{D}_{x_{t}}}{\operatorname{\mathbb{E}}}\big{[}\big{(}1-\varphi_{N_{\delta}}(\|g_{x^{\star}}(z)\|)\big{)}g_{x^{\star}}(z)g_{x^{\star}}(z)^{\top}\big{]}-\underset{z\sim\mu^{\star}}{\operatorname{\mathbb{E}}}\big{[}\big{(}1-\varphi_{N_{\delta}}(\|g_{x^{\star}}(z)\|)\big{)}g_{x^{\star}}(z)g_{x^{\star}}(z)^{\top}\big{]}}_{A_{t}}$
$\displaystyle\hskip
31.2982pt+\underbrace{\underset{z\sim\mu_{t}}{\operatorname{\mathbb{E}}}\big{[}\varphi_{N_{\delta}}(\|g_{x^{\star}}(z)\|)g_{x^{\star}}(z)g_{x^{\star}}(z)^{\top}\big{]}-\underset{z\sim\mu^{\star}}{\operatorname{\mathbb{E}}}\big{[}\varphi_{N_{\delta}}(\|g_{x^{\star}}(z)\|)g_{x^{\star}}(z)g_{x^{\star}}(z)^{\top}\big{]}}_{B_{t}},$

where $N_{\delta}$ comes from condition 1 of the lemma. We bound $A_{t}$ using
the triangle inequality:

$\displaystyle\|A_{t}\|_{\text{op}}$
$\displaystyle\leq\left\|\underset{z\sim\mu_{t}}{\operatorname{\mathbb{E}}}\big{[}\big{(}1-\varphi_{N_{\delta}}(\|g_{x^{\star}}(z)\|)\big{)}g_{x^{\star}}(z)g_{x^{\star}}(z)^{\top}\big{]}\right\|_{\text{op}}+\left\|\underset{z\sim\mu^{\star}}{\operatorname{\mathbb{E}}}\big{[}\big{(}1-\varphi_{N_{\delta}}(\|g_{x^{\star}}(z)\|)\big{)}g_{x^{\star}}(z)g_{x^{\star}}(z)^{\top}\big{]}\right\|_{\text{op}}$
$\displaystyle\leq\underset{z\sim\mu_{t}}{\operatorname{\mathbb{E}}}\big{[}\|g_{x^{\star}}(z)\|^{2}\mathbf{1}\\{\|g_{x^{\star}}(z)\|\geq
N_{\delta}\\}\big{]}+\underset{z\sim\mu^{\star}}{\operatorname{\mathbb{E}}}\big{[}\|g_{x^{\star}}(z)\|^{2}\mathbf{1}\\{\|g_{x^{\star}}(z)\|\geq
N_{\delta}\\}\big{]}$

and therefore

$\limsup_{t\to\infty}\|A_{t}\|_{\text{op}}\leq 2\delta.$

In order to bound $B_{t}$, we first define the map
$h(z)=\varphi_{N_{\delta}}(\|g_{x^{\star}}(z)\|)g_{x^{\star}}(z)g_{x^{\star}}(z)^{\top}$
and note

$B_{t}=\underset{z\sim\mu_{t}}{\operatorname{\mathbb{E}}}{\big{[}h(z)\big{]}}-\underset{z\sim\mu^{\star}}{\operatorname{\mathbb{E}}}\big{[}h(z)\big{]}.$

Observe that we can rewrite $h=\Phi\circ g_{x^{\star}}$, where
$\Phi(w)=\varphi_{N_{\delta}}(\|w\|)ww^{\top}$. Clearly $\Phi$ is Lipschitz
continuous on any compact set and zero outside of a ball of radius
$N_{\delta}+1$ around the origin. Therefore $\Phi$ is globally Lipschitz.
Since $g_{x^{\star}}$ is $\beta$-Lipschitz by the second assumption of the
lemma, we conclude that $h$ is globally Lipschitz with a constant $C<\infty$
that depends only on $N_{\delta}$ and $\beta$. Therefore, we deduce

$\displaystyle\|B_{t}\|_{\text{op}}$
$\displaystyle=\left\|\underset{z\sim\mu_{t}}{\operatorname{\mathbb{E}}}\big{[}h(z)\big{]}-\underset{z\sim\mu^{\star}}{\operatorname{\mathbb{E}}}\big{[}h(z)\big{]}\right\|_{\text{op}}$
$\displaystyle=\sup_{\|u\|,\|v\|\leq
1}\left\\{\underset{z\sim\mu_{t}}{\operatorname{\mathbb{E}}}\big{[}u^{\top}h(z)v\big{]}-\underset{z\sim\mu^{\star}}{\operatorname{\mathbb{E}}}\big{[}u^{\top}h(z)v\big{]}\right\\}$
$\displaystyle\leq C\cdot W_{1}(\mu_{t},\mu^{\star})\to 0,$

where the inequality follows from the fact that the map $z\mapsto
u^{\top}h(z)v$ is $C$-Lipschitz. Hence

$\limsup_{t\rightarrow\infty}\left\|\underset{z\sim\mu_{t}}{\operatorname{\mathbb{E}}}\big{[}g_{x^{\star}}(z)g_{x^{\star}}(z)^{\top}\big{]}-\Sigma\right\|_{\text{op}}\leq\limsup_{t\rightarrow\infty}\big{(}\|A_{t}\|_{\text{op}}+\|B_{t}\|_{\text{op}}\big{)}\leq
2\delta.$

Since $\delta>0$ is arbitrary, we have
${\operatorname{\mathbb{E}}}_{z\sim\mu_{t}}\big{[}g_{x^{\star}}(z)g_{x^{\star}}(z)^{\top}\big{]}\rightarrow\Sigma$,
as claimed. ∎

Finally, we record two lemmas about products and quotients of Lipschitz
functions.

######  Lemma E.4.

Let $\mathcal{K}$ be a metric space and suppose that
$f\colon\mathcal{K}\rightarrow\mathbf{R}^{n\times q}$ and
$g\colon\mathcal{K}\rightarrow\mathbf{R}^{q\times m}$ are bounded and
Lipschitz. Then the product $fg\colon\mathcal{K}\rightarrow\mathbf{R}^{n\times
m}$ is Lipschitz.

###### Proof.

Let $L_{f}$ and $L_{g}$ be the Lipschitz constants of $f$ and $g$ with respect
to the operator norm $\|\cdot\|$. Then for all $x,y\in\mathcal{K}$, we have

$\displaystyle\|f(x)g(x)-f(y)g(y)\|$
$\displaystyle\leq\|f(x)(g(x)-g(y))\|+\|(f(x)-f(y))g(y)\|$
$\displaystyle\leq\sup_{z\in\mathcal{K}}\|f(z)\|\cdot\|g(x)-g(y)\|+\|f(x)-f(y)\|\cdot\sup_{z\in\mathcal{K}}\|g(z)\|$
$\displaystyle\leq\left(L_{g}\cdot\sup_{z\in\mathcal{K}}\|f(z)\|+L_{f}\cdot\sup_{z\in\mathcal{K}}\|g(z)\|\right)\cdot
d_{\mathcal{K}}(x,y).$

Since $f$ and $g$ are bounded, this demonstrates that $fg$ is Lipschitz. ∎

######  Lemma E.5.

Let $\mathcal{K}\subset{\mathbf{R}}^{m}$ be a compact set and suppose that
$f\colon\mathcal{K}\rightarrow{\mathbf{R}}^{n}$ and
$g\colon\mathcal{K}\rightarrow{\mathbf{R}}\setminus\\{0\\}$ are $C^{1}$-smooth
with Lipschitz Jacobians. Then $f/g$ is $C^{1}$-smooth with Lipschitz
Jacobian.

###### Proof.

Since $f$ and $g$ are $C^{1}$-smooth, it follows immediately from the quotient
rule that $f/g$ is $C^{1}$-smooth with Jacobian given by

$\nabla(f/g)=(1/g)(\nabla f)-(f/g^{2})(\nabla g)^{\top}.$ (41)

By assumption, $\nabla f$ and $\nabla g$ are Lipschitz, and they are bounded
by the compactness of $\mathcal{K}$. Further, the functions $1/g$ and
$f/g^{2}$ are $C^{1}$-smooth, so they are locally Lipschitz by the mean value
theorem; hence $1/g$ and $f/g^{2}$ are Lipschitz and bounded by the
compactness of $\mathcal{K}$. Thus, (41) and Lemma E.4 show that $\nabla(f/g)$
is the difference of two Lipschitz maps. Therefore $\nabla(f/g)$ is Lipschitz.
∎


T2ALinuxBiolinumT-TLFLibertinusSans-TLF

# On the Origins of Objects by Means of Careful Selection

Yegor Bugayenko  0000-0001-6370-0678<EMAIL_ADDRESS>HuaweiRussiaMoscow

###### Abstract.

We introduce a taxonomy of objects for EO programming language. This taxonomy
is designed with a few principles in mind: non-redundancy, simplicity, and so
on. The taxonomy is supposed to be used as a navigation map by EO programmers.
It may also be helpful as a guideline for designers of other object-oriented
languages or libraries for them.

Object-Oriented Programming

††ccs: Object-Oriented Programming

##  1\. Introduction

Each object-oriented programming language offers its own set of objects,
classes, types, functions, constants, traits, templates, and so on, which
programmers can use off-the-shelf to model their specific use cases:
‘‘Development Kit’’ in Java, ‘‘Standard Library’’ in C++, Python, Swift, Rust,
and Ruby, ‘‘.NET Standard’’ in C#, ‘‘Built-in Objects’’ in JavaScript, and so
on.

Each Standard Library (SL) freely defines its own principles of abstraction.
For example, to get an absolute value of a numeric object x in Java, one has
to call a static method of another class Math.abs(x), while in Ruby it would
be a property of the same object x.abs. For example, in Java, an attempt to
get a value from a hash map by a key will produce null in case of its absence,
while in C++ it will return an empty iterator. There are many similar examples
demonstrating the absence of common ground between SLs.

As a humble attempt to create such a common ground for the world of objects,
we suggest our own taxonomy of objects for EO111https://www.eolang.org, a
strictly formal (kudasov2021, 7) object-oriented programming language with an
intentionally reduced feature set (bugayenko2021eolang, 1). All objects are
grouped as such:

  * •

Primitives (Section 3)

  * •

Array (Section 4)

  * •

Error handling (Section 5)

  * •

Flow control abstractions (Section 6)

  * •

Non-standard bit-width numbers (Section 7)

  * •

Memory abstractions (Section 8)

  * •

Math functions and algorithms (Section 9)

  * •

String manipulations (Section 10)

  * •

Collections (Section 11)

  * •

I/O Streams (Section 12)

  * •

File System abstractions (Section 13)

  * •

Net Sockets (Section 14)

  * •

HTTP request and response (Section 15)

  * •

Synchronization in multi-threading (Section 16)

An object in EO is either a composition of other objects or an atom, which is
a foreign function interface to a lower-level runtime such as, for example,
JVM or Assembly. In this paper, we denote atoms by a star, for example:
$\star$times.

Everywhere in the paper we use dark blue color to highlight an object when
it’s mentioned for the first time.

In this paper222LaTeX sources of this paper are maintained in objectionary/on-
the-origin-of-objects GitHub repository, the rendered version is  0.3.0. we
don’t provide exact specification of each object, in order to avoid conflicts
with their exact definitions in Objectionary333https://www.objectionary.com.

##  2\. Principles

We adhere to a few principles:

  * •

We tend to minimize the global scope, keeping the number of global objects to
the absolute possible minimum.

  * •

Wherever possible, objects must be implemented in EO, instead of being atoms.

  * •

There should be no functionality implemented two or more times in the entire
taxonomy.

  * •

Object names must not be abbreviated and must constitute an English sentence
when being used through dot notation, for example: x.times.y > z means ‘‘$x$
times $y$ is $z$.’’ There are a few exceptions though, like eq, seq, lt, and a
few others.

In case of any runtime error, an object is supposed to ‘‘return’’ an error
object, with message attribute present (as string) and @ attribute absent.

##  3\. Primitives

There are five primitive data objects described below. All of them have
$\star$as-bytes attribute, which is an abstraction of their representation as
a sequence of bytes. All primitives also have as-hash attribute, which, being
an int, is their own implementation of a hash function. They also have eq
attribute, which is TRUE if the primitive is equal to another object, through
the use of ^.as-bytes.eq.

###  3.1. Bytes

The center of the taxonomy is bytes data object, which is an abstraction of an
sequence of bytes. The sequence can either be empty or contain an
theoretically unlimited number of bytes. A byte is a unit of information that
consists of eight adjacent binary digits (bits), each of which consists of a 0
or 1. In EO syntax a sequence of bytes is denoted as either \-- (double dash)
for an empty one or as a concatenation of xx-, where xx is a hexadecimal
representation of a byte.

The object bytes has these four attributes, to turn itself into one of four
primitive data objects: $\star$as-int, $\star$as-bool, $\star$as-float, and
$\star$as-string. The attribute $\star$as-int expects the size of the sequence
to be less or equal to eight. The attribute $\star$as-bool is FALSE only if
all bytes equal to zero. The attribute $\star$as-float expects exactly eight
bytes.

There are also attributes for bitwise operations: $\star$and, $\star$or,
$\star$xor, $\star$not, $\star$left, and $\star$right.

The object also has attribute $\star$eq for comparing itself with another
sequence of bytes.

The attribute $\star$size is the total number of bytes in the sequence.

The attribute $\star$slice represents a sub-sequence inside the current one.

The attribute $\star$concat is a new sequence, which is a concatenation of two
byte sequences: the current and the provided one.

###  3.2. Int

The object int is an eight-bytes abstraction of a two’s complement signed
integer in a big-endian order.

The attribute $\star$plus is a summary of this number and another int. The
attribute minus is a subtraction of another int from this number. The
attributes $\star$times and $\star$div are a multiplication and a division of
this number and another int. The attribute neg is the same number with a
different sign.

The attribute $\star$lt is a bool object TRUE if it’s ‘‘less than’’ another
int and FALSE otherwise. Attributes gt, lte, and gte are ‘‘greater than,’’
‘‘less than or equal,’’ and ‘‘greater than or equal’’ comparisons
respectively.

Integers with a different bit-width are explained in Section 7. All other
manipulations with integers can be done in their decorators. Some of them are
explained in Section 9.

###  3.3. Bool

The object bool is a one-bit abstraction of a Boolean value. Its $\star$as-
bytes is either 00- or 01-.

There are two pre-defined objects TRUE and FALSE.

The attribute not is a Boolean inversion. Attributes and, or, xor are logical
conjunction, disjunction, and exclusive disjunction of the object itself with
an a array of other Boolean values; they use $\star$and, $\star$or, and
$\star$xor from ^.as-bytes respectively.

The attribute $\star$if is a branching mechanism, expecting three arguments: a
condition as bool, a ‘‘positive’’ object, and a ‘‘negative’’ object. When
being dataized, the object $\star$if first dataizes the condition and then,
according to the result obtained, either dataizes the positive object or the
negative one, returning the result as a result of its own dataization. Both
positive and negative objects must be copies of the same abstract object. This
code give a title to a random number:

QQ.io.stdout QQ.txt.sprintf "Coin toss: if. QQ.math.random.pseudo.gte 0.5
"heads" "tail"

The attribute $\star$while is an iterating mechanism, expecting two
attributes: a condition as bool and an abstract object with one free
attribute. When being dataized, the object $\star$while first dataizes the
condition and then either stops if it is FALSE or dataizes the abstract object
with an int equal to the number of the iterating cycle. This code makes a few
attempts to find a random number that is smaller than 0.1:

while. QQ.math.random.pseudo.gte 0.1 [i] QQ.io.stdout > @ QQ.txt.sprintf
"Attempt #

###  3.4. Float

The object float is an abstraction of a floating point number, which takes
eight bytes and fills them up according to the format suggested by (ieee754,
5).

The attribute $\star$plus is a summary of this number and another float. The
attribute minus is a subtraction of another float from this number. The
attributes $\star$times and $\star$div are a multiplication and a division of
this number and another float. The attribute neg is the same number with a
different sign.

The attribute $\star$lt is a bool object TRUE if it’s ‘‘less than’’ another
float and FALSE otherwise. Attributes gt, lte, and gte are ‘‘greater than,’’
‘‘less than or equal,’’ and ‘‘greater than or equal’’ comparisons
respectively.

Floating-point numbers with a different bit-width are explained in Section 7.
All other manipulations with floating-point numbers can be done in their
decorators. Some of them are explained in Section 9.

###  3.5. String

The object string is an abstraction of a piece of Unicode text in UTF-8
encoding, according to (unicode, 6). UTF-8 uses one byte for the first 128
code points, and up to 4 bytes for other characters.

The attribute $\star$slice takes a piece of a string as another string. The
attribute $\star$length is a total count of characters in the string.

Strings in other encodings, such as UTF-16 or CP1251, may be implemented
through direct manipulations with bytes.

All other manipulations with strings are explained in Section 10.

##  4\. Array

The object array is an abstraction of an immutable sequence of objects. For
example, this code represents a two-dimensional array x of numbers and
strings:

* > x * "green" 0x0D1 * "red" 0xF21 * "blue" 0x11C

The attribute $\star$with is a new array with all elements from the current
array and a new element added to the end of it.

The attribute $\star$at is the $i$-th element of the array.

The attribute $\star$length is the total amount of elements in the array.

All other manipulations with arrays can be implemented in their decorators.
Some of them are explained in Section 11.

##  5\. Error Handling

Here we define objects that help handle errors and exceptional situations.

The object $\star$error causes program termination at the first attempt to
dataize it. It encapsulates any other object, which can play the role of an
exception that is floating to the upper level:

[x] > d if. x.eq 0 error "Can’t divide by zero" 42.div x

The object $\star$try enables catching of $\star$error objects and extracting
exceptions from them. For example, the following code prints "division by
zero" and then "finally":

try [] 42.div 0 > @ [e] QQ.io.stdout > @ e [] QQ.io.stdout > @ "finally"

##  6\. Flow Control

Here we define objects that help control dataization flow.

The object $\star$seq is an abstraction of sequence of objects to be dataized
sequentially. For example, this code prints one message to the console and
then terminates the program due to the inability to dataize the division by
zero in the middle:

seq QQ.io.stdout "Hello, world! 42.div 0 QQ.io.stdout "Bye!"

The object $\star$goto enables forward and backward ‘‘jumps’’ either
immediately finishing dataization or restarting it. For example, this code
won’t print a message to the console if x is equal to zero:

goto [g] seq > @ if. > y x.eq 0 g.forward 0 42.div x QQ.io.stdout
QQ.txt.sprintf "42/x =

In this example, the number will be read from the console again, if it’s equal
to zero:

goto [g] seq > @ as-int. > x QQ.txt.parsed QQ.io.stdin if. x.eq 0 g.backward
QQ.io.stdout QQ.txt.sprintf "Number

The object switch is an abstraction of a multi-case branching that
encapsulates $(k,v)$ pairs and the dataization result is equal to $v$ of the
first pair where $k$ is TRUE, while the last pair is the one to be used if no
other pairs match:

QQ.io.stdout switch * password.eq "swordfish" "password is correct!" *
password.eq "" "empty password is not allowed" * FALSE "password is wrong"

##  7\. Digits

Here we define objects that represent numbers with smaller or larger bitwise
width comparing with the default 64-bits convention. All objects presented in
this Section belong to QQ.digits package.

Objects int8, int16, int32, and int128 are decorators of bytes with a
predefined size. They implement the same numeric operations as int. Objects
float16, float32, and float128 are also decorators of bytes, implementing the
same operations as float.

##  8\. Memory

Here we define objects that manage memory.

The object $\star$memory is an abstraction of a read-write memory capable of
storing one of five primitive data objects mentioned in Section 3. The
attribute $\star$write implements writing operation, while the object
$\star$memory itself decorates the data object stored in it. This code writes
a number into memory and then reads it back and prints:

memory 0 > m seq m.write 42 QQ.io.stdout QQ.txt.sprintf "Memory contains

The object $\star$cage is similar to $\star$memory, but it can store any
object, not only five primitives. The use of $\star$cage is strongly
discouraged. The following code stores a ‘‘book’’ in a $\star$cage, then
retrieves it back, and prints one of its attribute:

[] > book title > "Object Thinking" author > "David West" cage 0 > c seq
c.write book QQ.io.stdout QQ.txt.sprintf "Title is

The object ram is an abstraction of a random-access memory of certain size. It
behaves like bytes, but has an additional attribute $\star$write. In this
example, one kilobyte of memory with random data is allocated when a copy of
ram is created, a non-copying slice s of 13 bytes is made starting with the
200-th byte, data is written into it, then a non-copying sub-slice is created
of only five bytes, and finally a string is read back and "Hello" is printed:

ram 1024 > r seq write. r.slice 200 13 > s "Hello, world!".as-bytes
QQ.io.stdout as-string. s.slice 0 5

The object heap encapsulates a copy of ram and is an abstraction of a memory
management as it exists in (posix, 4). There are two attributes malloc and
free, which allocate and free memory blocks respectively. An allocation of a
memory block creates a copy of heap.pointer object, which is a decorator of
int with two additional attributes write and read. In this code, 13 bytes are
allocated, a string is stored into them, then read and printed, and then the
bytes are freed:

heap (ram 1024) > h seq h.malloc > p p.write "Hello, world!" QQ.io.stdout
(p.read 13).as-string h.free p

##  9\. Math

Here we define objects that represent math functions and algorithms. All
objects in this Section belong to QQ.math package.

The object random is a abstraction of a random float between zero and one
inclusively. It has an additional attribute $\star$pseudo that makes random
with a pseudorandom seed.

The object angle is a decorator of float. It assumes that the angle is in
radians and has the following attributes for trigonometric functions: sine,
cosine, and tangent. There are attributes as-degrees and as-radians for
switching from radians to degrees and backwards.

The object number is a decorator of int and float with the following
additional attributes:

  * •

abs

: absolute value of itself ($|\rho|$)

  * •

ceil

: round itself up

  * •

floor

: round itself down

  * •

ln

: natural logarithm ($\ln\rho$)

  * •

log

: logarithm ($\log_{x}\rho$)

  * •

max

: the greater of itself and another number

  * •

min

: the smaller of itself and another number

  * •

power

: itself raised to the power ($\rho^{x}$)

  * •

signum

: the sign of itself

  * •

sqrt

: square root of itself ($\sqrt{\rho}$)

##  10\. Strings

All objects presented in this Section belong to QQ.txt package.

The object sscanf encapsulates a format string and a content string. It
behaves like an array of scanned data objects. For example, this code parses a
hexadecimal number from the console:

at. QQ.txt.sscanf "QQ.io.stdin 0

The object sprintf builds a string according to the format provided and
compliant with (posix, 4, Chapter 5 ), for example:

QQ.txt.sprintf "Hi, "Jeff" 3.14

The object text is a decorator of a string, it has the following attributes:

  * •

contains

: checks whether it contains $x$

  * •

ends-with

: checks whether it ends with $x$

  * •

index-of

: finds the first occurence of a sub-string

  * •

join

: joins an array with this one as a glue

  * •

lower-case

: makes it lower case

  * •

last-index-of

: finds the last occurence of a sub-string

  * •

left-trim

: removes leading spaces

  * •

replace

: finds and replaces a sub-string

  * •

right-trim

: removes trailing spaces

  * •

split

: breaks it into an array of strings

  * •

starts-with

: checks whether it starts with $x$

  * •

trim

: removes both leading and trailing spaces

  * •

upper-case

: makes it upper case

The object regex is an abstraction of a regular expression, in accordance with
(posix, 4, Part 2 ) (Extended Regular Expressions) and full support of
Unicode. The attribute match is a split of the string into parts:

QQ.txt.regex "/(и([^]+))/i" > r r.match > m "Из искры возгорится пламя" eq. m
* * "Из" 0 * "И" * "з" 1 * * " " * "искры" 3 * "и" * "скры" 4 * * " возгор" *
"ится" 15 * "и" "тся" 16 * * " пламя"

##  11\. Collections

Here we discuss abstractions of lists, maps, sets, and other ‘‘collections.’’
All objects presented in this Section belong to QQ.collections package.

###  11.1. List

The object list is a decorator of array.

The attribute is-empty is TRUE if the length of the array is zero.

The attribute eq is TRUE if each element of the array is equal to the
corresponding element of another array and the lengths of both arrays are the
same.

The attribute without is a new array with the $i$-th element removed.

The attributes each, reduced, found, filtered, and mapped are respectively
similar to forEach, reduce, find, reduce, and map methods of Array object in
JavaScript (EcmaScript, 2). A few ‘‘twin’’ attributes eachi, reducedi,
filteredi, foundi, and mappedi are semantically the same, but with an extra
int argument as a counter of a cycle.

The attribute slice is a part of the array.

The attribute sorted is a new array with elements sorted using given
comparison abstract object with two free attributes.

The attribute reversed is a new array with elements positioned in a reverse
order.

###  11.2. Map

The object map is a decorator of array of pairs $(k,v)$. The map ensures that
all $k$ are always unique. It is expected that each $k$ has as-hash attribute
that behaves as int.

The attributes with, without, found, and foundi are reimplemented in map.

###  11.3. Set

The object set is a decorator of array. The set ensures that all elements in
the array are always unique. It is expected that each $k$ has as-hash
attribute that behaves as int.

The attributes with, without, found, and foundi are reimplemented in set.

###  11.4. Mutable Arrays

The objects array-list and linked-list are the abstractions of mutable lists
that behave like array. They have three additional attributes: inject,
replace, and extract. They encapsulate $\star$cage object.

##  12\. I/O Streams

Here we define manipulations with input and output streams. All objects
presented in this Section belong to QQ.io package.

It is expected that an input stream has the following interface:

[] > input data > @ [max-count] > read /input [] > close

It is expected that an output stream has the following interface:

[] > output [bytes-to-write] > write /input [] > close

The object $\star$stdout is an ‘‘output’’ that prints a string to the standard
output stream, while the object $\star$stderr is an ‘‘output’’ that prints to
the standard error stream.

The object $\star$stdin is an abstraction of a string currently available in
the standard input stream until the EOL character ( \n) and is an ‘‘input.’’
If there is no string in the stream, the object blocks dataization and waits.
This code endlessly reads strings from the console and immediately prints them
back:

TRUE.while [i] QQ.io.stdout > @ QQ.io.stdin

The object $\star$bytes-as-input is an ‘‘input’’ made from bytes.

The object $\star$memory-as-output is an ‘‘output’’ directed towards a copy of
memory.

The object $\star$copied is channel between an ‘‘input’’ and an ‘‘output,’’
which moves all available bytes from the former to the latter when being
dataized. For example, this code write a text to a temporary file:

QQ.io.copied QQ.io.bytes-as-input as-bytes. "Hello, world!" as-output.
QQ.fs.file "/tmp/foo.txt" "w+"

The object content is a string representation of the entire content of an
‘‘input.’’

##  13\. File System

Here we define manipulations with files and directories. All objects presented
in this Section belong to QQ.fs package.

The object file is an abstraction of a file and is a decorator of string,
which is the path of the file. The attribute $\star$exists is TRUE if the file
exists. The attribute $\star$is-dir is TRUE if the file is a directory. The
attribute $\star$touch makes sure the file exists. The attribute $\star$rm
removes the file. The attribute $\star$mv renames or moves the file to a new
place. The attribute $\star$size is the size of the file in bytes. The
attribute $\star$as-output is an output stream for this file, while the
attribute $\star$as-input is an input stream.

The object directory is an abstraction of a directory. The attribute mkdir
creates the directory with all its parent directories. The attribute rm-rf
deletes the directory recursively with all its subdirectories. The attribute
walk finds files in the directory using glob pattern matching. The attribute
tmpfile is a temporary file in the directory.

The object $\star$tmpdir is a system directory of temporary files.

The object path is a decorator of a string and is a path of a file. The
attribute $\star$resolve is a new path with a suffix appended to the current
one. The attribute $\star$dir-name is the name of the directory in the path.
The attribute $\star$ext-name is the extension in the path. The attribute
$\star$base-name is the name of the file in the path.

##  14\. Sockets

Here we define objects used for both server-side and client-side TCP sockets
in accordance with (posix, 4). All objects presented in this Section belong to
QQ.net package.

The object socket is an abstraction of a TCP socket. The attribute
$\star$connect establishes a connection and makes a copy of the socket object.
Then, its attributes $\star$as-input and $\star$as-output may be used for
reading from the socket and for writing to it. For example, this code opens a
connection to the 80th TCP port of google.com and then reads the entire stream
as a Unicode string:

connect. > s QQ.net.socket "google.com" 80 QQ.io.stdout QQ.io.content s.as-
input s.close

The attribute $\star$listen makes a copy of the socket and establishes a
server connection. Then, the attribute $\star$accept can be used to wait for
an incoming connection and then make a copy when it arrives. For example, this
code binds to the 8080th port on a ‘‘localhost’’ and when a connection
arrives, prints a message into it:

listen. > s QQ.net.socket "127.0.0.1" 8080 QQ.io.copied QQ.io.bytes-as-input
"Hello, world!".as-bytes s.accept.as-output s.close

The attribute $\star$close terminates the connection and makes the closed
$\star$socket object impossible to use anymore.

##  15\. HTTP

Here we define objects used for parsing and printing of HTTP requests and
responses in accordance with (rfc2616, 3). All objects presented in this
Section belong to QQ.http package.

The objects http-request and http-response are abstractions of HTTP request
and response respectively. They have attributes that help building them; they
both have as-string attribute to turn them into a string:

http-request .with-method ’GET’ .with-address ’/index.html’ .with-header
’Accept-Encoding’ ’utf-8’ .with-cookie ’Session-Id’ ’8F09A4E438C’ .with-
content-type ’plain/text’ .as-string > r

They both have from-string attribute to create objects from a string. They
also have attributes that represent the pieces, which request and response are
built of:

http-response.from-string "…" > r r.status r.header ’Content-Type’ r.cookie
’Session-Id’

##  16\. Synchronization

Here we define objects used for explicit synchronization between threads. All
objects presented in this Section belong to QQ.sync package.

The object semaphore is a counting semaphore with two attributes:
$\star$capture and $\star$release.

The object atomic-memory is a synchronized decorator of memory with a binary
semaphore encapsulated.

## References

  * (1) Yegor Bugayenko  ‘‘EOLANG and $\varphi$-calculus’’, 2021  arXiv:2111.13384 [cs.PL]
  * (2) ECMA  ‘‘Standard ECMA-262 — ECMAScript Language Specification’’, 2011
  * (3) Roy Fielding et al.  ‘‘RFC2616: Hypertext Transfer Protocol — HTTP/1.1’’  RFC Editor, 1999
  * (4) IEEE 1003.1  ‘‘IEEE Standard for Information Technology—Portable Operating System Interface (POSIX${}^{\text{TM}}$) Base Specifications’’  In _IEEE Std 1003.1-2017 (Revision of IEEE Std 1003.1-2008)_ , 2018  DOI: 10.1109/IEEESTD.2018.8277153
  * (5) IEEE 754  ‘‘IEEE Standard for Floating-Point Arithmetic’’  In _IEEE Std 754-2019 (Revision of IEEE 754-2008)_ , 2019  DOI: 10.1109/IEEESTD.2019.8766229
  * (6) ISO 10646  ‘‘Information Technology — Universal Coded Character Set (UCS)’’  In _ISO/IEC 10646:2020_ , 2020
  * (7) Nikolai Kudasov et al.  ‘‘$\varphi$-calculus: a purely object-oriented calculus of decorated objects’’, 2022  arXiv:2204.07454 [cs.PL]