Flocking-Segregative Swarming Behaviors using Gibbs Random Fields

Paulo Rezeck¹ and Renato M. Assunção¹ and Luiz Chaimowicz¹ Paulo Rezeck, Renato M. Assunção and Luiz Chaimowicz are with the Department of Computer Science, Universidade Federal de Minas Gerais, Brazil {rezeck,assuncao,chaimo}@dcc.ufmg.br. This work was partially supported by CAPES, CNPq, and Fapemig.

Abstract

This paper presents a novel approach that allows a swarm of heterogeneous robots to produce simultaneously segregative and flocking behaviors using only local sensing. These behaviors have been widely studied in swarm robotics and their combination allows the execution of several complex tasks. Our approach consists of modeling the swarm as a Gibbs Random Field (GRF) and using appropriate potential functions to reach segregation, cohesion and consensus on the velocity of the swarm. Simulations and proof-of-concept experiments using real robots are presented to evaluate the performance of our methodology in comparison to some of the state-of-the-art works that tackle segregative behaviors.

I Introduction

Due to the advances in technology that have enabled the mass production of increasingly smaller robots [1], control methods that yield desired collective behaviors using simple local interactions have received much interest in recent years. Inspired by the emergent behaviors commonly observed in nature, one of the main goals of swarm robotics is to develop such methods in a decentralized and scalable fashion, mainly relying on local sensing and communication capabilities.

In this sense, one of the most fundamental mechanisms a robot swarm must exhibit is the ability of group formation and cohesive navigation [2]. Segregation is a particular type of group formation in which robots with common characteristics are placed together and set apart from other groups [3]. Several applications can benefit from using these behaviors, such as area coverage, surveillance and reconnaissance, transport, foraging, among others.

This work presents a novel stochastic and decentralized approach that allows a swarm of heterogeneous robots to achieve simultaneously segregation and flocking behaviors using only local sensing. To the best of our knowledge, this is the first work to tackle these behaviors together starting from a random initial state and using only local information. Our approach consists of modeling the robot swarm as a Gibbs Random Field (GRF) defining its potential energy as a combination of Coulomb-Buckingham potential and kinetic energy. Such concepts have been extensively used in statistical mechanics and quantum mechanics to model particle interactions, but we revisit them in the swarm robotics context. As a consequence of using GRF and such potentials, besides supporting the segregation and navigation of different groups avoiding collision with obstacles, the approach allows the swarm to reach configurations sufficiently close to the global minimum energy.

Using simulated experiments, we contrast the methodology with a deterministic gradient descent-type algorithm using potential differentials showing that such mechanism is easily trapped at local minima of potential. In addition, we compare our segregative behavior with some of the state-of-the-art approaches and evaluate the flocking behavior in the presence of noise. Real experiments were also performed as a proof-of-concept for our GRF approach.

II Related Work

Most works in swarm robotics usually focus on homogeneous systems, in which all robots have the same characteristics [4]. However, in recent years, there is a growing interest in heterogeneous systems. As a consequence, new types of swarming behaviors have been investigated, such as segregation. One of the first works to deal with this problem was proposed by Groß et al. [5]. The authors presented a control algorithm inspired by a collective phenomenon in which segregation occurs by constantly shaking a mixture of different sizes particles (Brazil Nut effect). This study was later extended by Chen et al. [6] and Joshi et al. [7], when they evaluated and improved performance and presented experiments with real robots.

Another approach to segregate a swarm of heterogeneous robots was presented by Kumar et al. [8]. The authors took inspiration from a biological theory that explains how differences in cell adhesion generate mechanical forces that drive cellular segregation (Differential Adhesion Hypothesis) [9]. This mechanism is modeled with the concept of differential potential, in which robots are subjected to differential artificial potential fields according to their groups. The method’s convergence is guaranteed for two classes, but the swarm may be trapped in local minima when more classes are employed. This approach was later extended in Santos et al. [3, 10] to deal with more than two groups of robots. One limitation is the requirement that robots must have global knowledge about the positions of other robots.

Motivated by the use of differential artificial potential fields, Ferreira Filho and Pimenta [11] proposed a novel controller that differs from the previous ones by using abstractions [12] to represent each group. One advantage of such a controller is that it may not require that all robots receive information from all other robots all the time. More recently, the authors extended this controller to incorporate a collision avoidance scheme that does not interfere with the original segregation controller [13]. In a different work [14], they presented a decentralized control strategy to segregate heterogeneous robot swarms distributed in curves using consensus protocols and heuristics to compute the traveled geodesic distances on curves. This approach assumes that robots know the curve and maintain an underlying fixed communication topology.

Recently, two works assuming minimal and local-only requirements for segregating a swarm of heterogeneous robots have been proposed. Mitrano et al. [15] extended the concept of a minimalistic reactive controller [16] to achieve segregation. They demonstrate that robots with only a ternary sensor and a controller that maps sensor readings to wheel speeds can reach a segregated state. Also, considering local sensing and a memory mechanism supported by communication, Inácio et al. [17] proposed a strategy that combines concepts of Particle Swarm Optimization (PSO) [18] with the Optimal Reciprocal Collision Avoidance (ORCA) [19] to archive segregation.

Following the works that rely only on local information, we assume that our robots only use their neighbors’ relative position and velocities to achieve simultaneous segregation and cohesive navigation. However, most of these works only consider collisions with other robots. Our method also allows the robots to avoid collisions with obstacles in the environment, considering that they are equipped with range sensors, such as infrared sensors.

Besides dealing with the segregation problem, our approach also generates a cohesive navigation behavior for the different groups of robots. One of the main challenges in achieving such behavior is reaching a consensus on each part of the group’s velocity as its size increases. In addition to that, the groups must remain segregated while navigating.

One of the earliest and most influential approaches to steer a swarm of homogeneous agents using only local interactions was proposed by Reynolds [20]. This mechanism, called boids, combines three simple rules: separation, cohesion, and alignment. While most works on this subject deal with homogeneous groups, some use heterogeneous robotic swarms to study the flocking of distinct groups. Momen et al. [21] extended the flocking mechanism with heterospecific attraction rules [22] to model different attraction forces between two groups of robots, producing a mixed-species flocking. Ducatelle et al. [23] proposed a mechanism that emerges cooperative self-organized behaviors to solve complex tasks using simple local interactions between the robots of the two different groups. Another study on self-organized flocking explored the concept of Swarm heterogeneity in the sense that robots with more capabilities help others that lack some capabilities in order to yield the desired behavior [24].

Some works tackle the problem of segregated navigation, in which the robots start in a segregated state and have to maintain the segregation during navigation. For example, Santos et al. [25] introduces a novel concept called Virtual Group Velocity Obstacles that combines the concepts of flocking [20] and Velocity Obstacles [26] with abstractions to represent the groups. To improve performance over such approach, Inácio et al. [27] proposed the combination of the Optimal Reciprocal Collision Avoidance algorithm [28] with the concepts of flocking.

Different from these works, our approach simultaneously generates segregation and flocking behaviors. The robots start in a completely random state and, as they move around, they segregate into different groups and keep this segregation while navigating. To the best of our knowledge, this work is the first to present a fully decentralized stochastic controller that performs both behaviors using only local interactions.

Moreover, although our approach produces flocking behaviors, we do not use or extend the mechanism proposed by Reynolds [20]. We model the swarm using dynamic Gibbs Random Fields (GRF), which provide a robust framework for dealing with spatially correlated probabilities. We have been inspired by Tan et al. [29] that used GRF to self-organize homogeneous robots. Besides the use of heterogeneous robots, there are other crucial differences between our work and [29]: we model a continuous movement of the robots in a bounded environment and limit the robots’ maximum velocities, while Tan et al. consider a discrete and a bounded environment and assume lattices as their environment. In addition, we introduce a different potential function that makes all the difference in our approach. In contrast with previous work, we adopt the Coulomb-Buckingham Potential [30] coupled with a Kinetic Energy term to model the robots’ interactions.

III Background

In this section, we overview some concepts about Gibbs Random Fields (GRFs) explaining their properties and why they make sense in a swarm robotics context. A GRF is a probabilistic graphical model that is a particular case of the Markov Random Field (MRF) when the joint probability density of the random variables is strictly positive. GRF models are based on local interactions between neighboring agents. The Markov property is a conditional property that allows one to ignore more distant information as soon as local information is provided. The Hammersley-Clifford theorem establishes the equivalence between a MRF and a GRF [31].

To describe these models succinctly, assume an undirected graph $\mathbf{G}=(\mathbf{V},\mathbf{E})$ with vertices as spatial sites and indexed by $v=1,2,...,\eta$ . A random field on $\mathbf{G}$ is as collection of random variables $\mathbf{X}=\{X_{v}\}_{v\in\mathbf{V}}$ and, for each $v\in\mathbf{V}$ , let $\Lambda_{v}$ be finite set called the phase space for site $v$ that represents where the random variable $X_{v}$ takes it values. An instance of $\mathbf{X}$ establishes a state of the random field $x=\{(x_{1},...,x_{\eta}):x_{v}\in\Lambda_{v},v\in\mathbf{V}\}$ and the product space $\Lambda\triangleq\Lambda_{1}\times...\times\Lambda_{\mathbf{\eta}}$ forms the configuration space.

A neighborhood system on $\mathbf{V}$ is a family $\mathcal{N}=\{\mathcal{N}_{v}\}_{v\in\mathbf{V}}$ , where $\mathcal{N}_{v}\subset\mathbf{V}$ is the set of neighbors for site $v$ satisfying $v/\mathcal{N}_{v}$ and $r\in\mathcal{N}_{v}\Leftrightarrow v\in\mathcal{N}_{r}$ . The neighborhood system induces the configuration of the undirected graph $\mathbf{G}$ by setting an edge $\{v,r\}\in\mathbf{E}$ between $v$ and $r$ if and only if $r\in\mathcal{N}_{v}$ . A set $\mathcal{C}\subset\mathbf{V}$ is called a clique if all elements of $\mathcal{C}$ are neighbors of each other.

Thus, a random field $\mathbf{X}$ is called an MRF concerning the neighborhood system $\mathcal{N}$ if, $\forall v\in\mathbf{V}$ ,

\displaystyle{P(X_{v}=x_{v}\text{$|$}(X_{r}=x_{r})_{r\neq v})=P(X_{v}=x_{v}\text{$|$}(X_{r}=x_{r})_{r\in\mathcal{N}_{v}})},

(1)

which indicates that the probability of the site $v$ assuming the state $x_{v}$ given the state of all other sites is equal to the probability of $v$ assuming the same state $x_{v}$ given only the states of neighboring sites. Such a definition reflects the local characteristics of the MRF constrained by the local Markov properties [32]. It is convenient to model robotics swarms, since it implies the conditional independence of information coming from outside a neighborhood system, which supports the requirement of local interactions.

A GRF is a particular application for (1) when the Gibbs measure can represent its joint probability density. A Gibbs measure is a generalization of the canonical ensemble to infinite systems, which gives the probability of the system $\mathbf{X}$ being in the state $x$ . Formally, let us denote a potential $\mathbf{U}$ as a family $\displaystyle{\{U_{A}:A\subset\mathbf{V}\}}$ of functions on the configuration space $\Lambda$ , where $U_{A}:\Lambda\rightarrow\mathbb{R}$ , and $U_{A}(x)$ depends only on $x_{A}\triangleq\{x_{v}:v\in A\}$ . At the end, $U_{A}$ is only a function of the values at the sites contained in the set $A$ , that is $\displaystyle{U_{A}(x)\equiv U_{A}(x_{A})}$ . In this way, given a potential $\mathbf{U}$ , the potential energy $H(x)$ for configuration $x$ is defined as

H(x)=\sum\limits_{A\subset\mathbf{V}}U_{A}(x_{A}).

(2)

By definition [31], if $U_{A}\equiv 0$ whenever $A$ is not a clique or a singleton, $\mathbf{U}$ is called a nearest-neighbor potential. If $U_{A}\equiv 0$ whenever $A$ is not a pair or a singleton, $\mathbf{U}$ is called a pairwise potential. $\mathbf{U}$ is called a pairwise, nearest-neighbor potential if it is both a pairwise potential and a nearest-neighbor potential. In particular, for a pairwise, nearest-neighbor potential $U$ , we can write (2) as

H(x)=\sum\limits_{v\in\mathbf{V}}U_{\{v\}}(x_{v})+\sum\limits_{(v,t)\in\mathbf{V}\times\mathbf{V},t\in\mathcal{N}_{v}}U_{\{v,t\}}(x_{v},x_{t}).

(3)

Finally, a random field $\mathbf{X}$ is called a GRF if,

P(\mathbf{X}=x)=\frac{1}{Z}e^{-\frac{H(x)}{T}},\textrm{ with }Z=\sum\limits_{z}e^{-\frac{H(z)}{T}},

(4)

where $Z$ is the partition function (normalizing constant); $T$ is interpreted as temperature in the context of statistical physics; and $\frac{1}{Z}e^{-\frac{H(x)}{T}}$ is called Gibbs distribution.

Researchers in statistical mechanics and mathematics usually applied the GRF to describe the distribution of system configurations at the thermodynamic equilibrium or measure the probability of such a system yielding the desired state. One of the challenges of directly evaluating (4) is the high cardinality of the configuration space, which makes the computation of $Z$ intractable.

A typical approach to sequential sampling states in a configuration space given a probability function consists of using Markov Chain Monte Carlo (MCMC) methods, such as the Metropolis algorithm [33]. A process to parallelly sample over (4) is described in the next section.

IV Methodology

The general idea of our methodology consists of modeling the configuration of a swarm of heterogeneous robots as a GRF and then sampling velocities for each robot in a decentralized way, which leads the entire swarm to a convergence towards the global minimum of the potential.

IV-A Formalization

Consider a set $\mathcal{R}$ of $\eta$ heterogeneous robots navigating in a bounded region within the two-dimensional Euclidean space¹¹1We assume two-dimensional space for convenience but one can straightforward extend it to three-dimensional space.. The state of the $i$ -th robot at time step $t$ is represented by its pose $\mathbf{q}_{i}^{(t)}$ and velocity²²2From now on, we use the symbol $\mathbf{v}$ to represent robot velocities. $\dot{\mathbf{q}_{i}}^{(t)}=\mathbf{v}_{i}^{(t)}$ , which is bounded by $v_{max}$ , $||\mathbf{v}_{i}^{(t)}||\leq v_{max}$ . In addition, robots are driven by a holonomic kinematic model with motion model $\displaystyle{\mathcal{K}:(\mathbf{q}_{i}^{(t)},\mathbf{v}_{i}^{(t)})\rightarrow(\mathbf{q}_{i}^{(t+1)})}$ . The heterogeneity of the system is modeled by a partition $\tau=\{{\tau}_{1},...,{\tau}_{m}\}$ , with each ${\tau}_{k}\subset\mathcal{R}$ containing exclusively all robots of type $k$ . That is, $\forall(j,k):j\neq k\ \rightarrow{\tau}_{k}\cap{\tau}_{j}=\emptyset$ .

Each robot has a circular sensing range of radius $\lambda$ , where it can estimate the relative position and velocity of other robots as well as their type, and also obstacles within the environment. Obstacles are represented as a finite set of points $\displaystyle{\mathcal{O}=\{\mathbf{o}_{1},...,\mathbf{o}_{n}\}}$ . An obstacle detected by the $i$ -th robot consists of a subset of points $\mathcal{O}_{i}\subset\mathcal{O}$ , where $\displaystyle{\mathbf{o}_{j}\in\mathcal{O}_{i}\rightarrow||\mathbf{o}_{j}-\mathbf{q}_{i}||\leq\lambda}$ and $||\mathbf{o}_{j}-\mathbf{q}_{i}||$ is the Euclidean norm between two points.

The neighborhood system for the $i$ -th robot, constrained by the sensing range $\lambda$ , defines a set of robots:

\mathcal{N}_{i}\triangleq\{j\in\mathcal{R}:j\neq i,||\mathbf{q}_{j}-\mathbf{q}_{i}||\leq\lambda\}.

(5)

IV-B Extension of the GRF to swarm robotics

Inspired by the GRF capability in modeling local interactions, here we discuss its concepts in the context of swarm robotics. Following the modeling presented in section III, let us define a graph $\mathbf{G}=(\mathcal{R},\mathbf{E})$ with a set of random variables $\mathbf{X}=\{X_{i}\}_{i\in\mathcal{R}}$ , in which each $X_{i}$ models the random velocity $\mathbf{v}_{i}$ of the $i$ -th robot. A configuration of the system $\mathbf{X}$ is $\displaystyle{\mathbf{x}=\{\mathbf{v}_{1},...,\mathbf{v}_{\eta}\}}$ where $\mathbf{v}_{i}\in\Lambda_{i}$ and represents the velocities performed by each robot.

A neighborhood system on $\mathcal{R}$ , given a configuration space $\mathbf{x}$ , is a family $\displaystyle{\mathcal{N}=\{\mathcal{N}_{i}\}_{i\in\mathcal{R}}}$ , where $\mathcal{N}_{i}\subset\mathcal{R}$ is the set of neighbors defined in (5) and satisfies $i/\mathcal{N}_{i}$ and the symmetry $\displaystyle{j\in\mathcal{N}_{i}\Leftrightarrow i\in\mathcal{N}_{j}}$ . The neighborhood system $\mathcal{N}$ induces the configuration of the graph $\mathbf{G}$ by establishing an edge between each pair $(i,j)$ of robots if and only if $j\in\mathcal{N}_{i}$ .

Until now, our definitions only allow us to calculate the probability of the entire swarm reaching a certain configuration, but what we require here is to sample velocities for each robot given the information about the robots in its neighborhood. Next, we explain how we perform such a procedure in a decentralized way using the Gibbs distribution.

IV-C Parallel Gibbs sampling

Parallel Gibbs sampling implies that all robots are simultaneously updating their velocities based on the configuration $\mathbf{x}$ at time $t$ . Such a method is possible here due to the local nature of the Gibbs potential energy.

Formally, let $t$ denote the temporal index and $\displaystyle{\mathbf{x}^{(t)}=\mathbf{x}=(\mathbf{v}_{1},...,\mathbf{v}_{\eta})}$ be the swarm configuration at time $t$ . Let $\mathbf{Z}_{i}(\mathbf{x})\triangleq\{\mathbf{z}_{i}:||\mathbf{z}_{i}||\leq v_{max}\}$ , where $\mathbf{Z}_{i}(\mathbf{x})\subset\Lambda_{i}$ , be the set of possible velocities for the $i$ -th robot given the configuration $\mathbf{x}^{(t)}$ . Using (4), the $i$ -th robot updates its velocity $\mathbf{v_{i}}^{(t)}=\mathbf{v_{i}}$ to $\mathbf{v_{i}}^{(t+1)}=\mathbf{\bar{v}_{i}}$ with probability

P_{i}(\mathbf{v_{i}},\mathbf{\bar{v}_{i}}|\mathbf{x})=\begin{cases}\frac{e^{-H(\mathbf{\bar{v}_{i}},\mathbf{x}_{\mathcal{R}\setminus i})/T}}{\sum\limits_{\mathbf{z}_{j}\in\mathbf{Z}_{i}(x)}e^{-H(\mathbf{z}_{j},\mathbf{x}_{\mathcal{R}\setminus i})/T}},&\text{ if }\mathbf{\bar{v}_{i}}\in Z_{i}(\mathbf{x})\\ 0,&\text{otherwise}.\end{cases}

(6)

Note that (6) still depends on the global knowledge at the potential energy $H(\cdot,\mathbf{x}_{\mathcal{R}\setminus i})$ . However, if we rewrite (3) as,

\begin{split}H(\cdot,\mathbf{x}_{\mathcal{R}\setminus i})=\left(U_{\{i\}}(\cdot)+\sum\limits_{\forall j\in\mathcal{R}\setminus i}U_{\{j\}}(\mathbf{v}_{j})\right)+\\ \sum\limits_{\forall j\in\mathcal{N}_{i}}U_{\{i,j\}}(\cdot,\mathbf{v_{j}}),\end{split}

(7)

one may note that the second term inside the parenthesis is constant for the $i$ -th robot, which lets us reduce the form for $H(\mathbf{\bar{v}_{i}},\mathbf{x}_{\mathcal{R}\setminus i})$ and $H(\mathbf{z_{i}},\mathbf{x}_{\mathcal{R}\setminus i})$ in (6). This shows the local nature of the Gibbs potential energy and implies that we do not require the knowledge of the entire swarm to sample velocities for the $i$ -th robot, but only information about its neighbors $\mathcal{N}_{i}$ . Thus, we can rewrite (6) as

P_{i}(\mathbf{v_{i}},\mathbf{\bar{v}_{i}}|\mathbf{x})=\frac{e^{-\left(U_{\{i\}}(\mathbf{\bar{v}_{i}})+\sum\limits_{\forall j\in\mathcal{N}_{i}}U_{\{i,j\}}(\mathbf{\bar{v}_{i}},\mathbf{v_{j}})\right)T^{-1}}}{\sum\limits_{\mathbf{z_{i}}\in\mathbf{Z}_{i}(x)}e^{-\left(U_{\{i\}}(\mathbf{z_{i}})+\sum\limits_{\forall j\in\mathcal{N}_{i}}U_{\{i,j\}}(\mathbf{z_{i}},\mathbf{v_{j}})\right)T^{-1}}},

(8)

where $\mathbf{\bar{v}_{i}}\in\mathbf{Z}_{i}(\mathbf{x})$ .

IV-D Potential energy

Here we propose combining two potential functions into the potential energy $H(\cdot)$ to achieve simultaneous segregative-flocking behaviors of the swarm.

IV-D1 Coulomb-Buckingham potential

The Coulomb-Buckingham potential [30] is a combination of the Lennard-Jones potential with the Coulomb potential used to describe the interaction among particles considering their charges. We took advantage of such a mechanism to model the swarm’s heterogeneity by setting the particle charges. The formula for the interaction is

\Phi(r)=\varepsilon\left({\frac{6}{\alpha-6}}e^{\alpha}\left(1-{\frac{r}{r_{0}}}\right)-{\frac{\alpha}{\alpha-6}}\left({\frac{r_{0}}{r}}\right)^{6}\right)+\frac{c_{i}c_{j}}{4\pi\varepsilon_{0}r},

(9)

where $r=||\mathbf{q}_{j}-\mathbf{q}_{i}||$ is the euclidean distance between the particles $i$ and $j$ ; $\varepsilon$ is the depth of the minimum energy; $r_{0}$ is the minimum energy distance; $\alpha$ is a free dimensionless parameter; $c_{i}$ and $c_{j}$ are the charges of the particles $i$ and $j$ ; and $\varepsilon_{0}$ is an electric constant.

We define the interaction among the $i$ -th and $j$ -th robots by replacing the product $c_{i}c_{j}$ by the following function,

C(i,j)=\left(2\leavevmode\nobreak\ \mathbb{1}((i,j)\in\tau_{k})-1\right)|c_{i}c_{j}|,

(10)

where $\mathbb{1}(\cdot)$ denotes the indicator function. In this way $C(i,j)$ will be positive if the $i$ -th and $j$ -th robots belong to the same group $\tau_{k}$ and negative otherwise. Fig. 1 illustrates the Coulomb-Buckingham potential.

Refer to caption — Figure 1: The Coulomb-Buckingham potential function. It depends on the distance $r$ among the $i$ -th and $j$ -th robots and a function $C(i,j)$ that produces attractive or repulsive behaviors depending on the heterogeneity among them.

IV-D2 Kinetic energy

We assume classical mechanics to compute the kinetic energy produced by relative velocities of the $i$ -th robot neighbors. Let $\mathbf{V}_{i}$ define the resultant of the relative velocities among all neighbors within the same partition of the $i$ -th robot. The kinetic energy $\mathbf{E_{k}}$ relative to the $i$ -th robot is:

\mathbf{V}_{i}=\sum\limits_{\forall j\in\mathcal{N}_{i}\land(i,j)\in\tau_{k}}\mathbf{v}_{j},\ \ \ \mathbf{E_{k}}(\mathbf{V}_{i})=\frac{1}{2}m(\mathbf{V}_{i}\cdot\mathbf{V}_{i}),

(11)

where $m$ is the cumulative mass of the group.

IV-D3 Combination

We combine the Coulomb-Buckingham potential and the kinetic energy to define the potential energy $H(\mathbf{\bar{v}}_{i},\mathbf{x}_{\mathcal{R}\setminus i})$ . Here, the individual potential $U_{\{i\}}(\mathbf{\bar{v}_{i}})$ represents an obstacle avoidance factor defined by

\begin{split}U_{\{i\}}(\mathbf{\bar{v}_{i}})=\sum\limits_{\forall j\in\mathcal{O}_{i}}\Phi(||\mathcal{K}(\mathbf{q}_{i},\bar{\mathbf{v}_{i}})-\mathbf{o_{j}}||),\end{split}

(12)

and $\forall j\in\mathcal{O}_{i}:C(i,j)>0$ .

The nearest-neighbor potential establishes a segregative-flocking factor formulated as

\begin{split}\sum\limits_{\forall j\in\mathcal{N}_{i}}U_{\{i,j\}}(\mathbf{\bar{v}_{i}},\mathbf{v_{j}})=\sum\limits_{\forall j\in\mathcal{N}_{i}}\Phi(||\mathcal{K}(\mathbf{q}_{i},\bar{\mathbf{v}_{i}})-\mathcal{K}(\mathbf{q}_{j},{\mathbf{v}_{j}})||)+\\ \mathbf{E_{k}}(\mathbf{V}_{i})+\mathbf{E_{k}}(v_{max}-\bar{\mathbf{v}_{i}}),\end{split}

(13)

where the first term defines the attraction and repulsion among two robots and the second one is the relative velocity of the neighbors. Since we compute the kinetic energy using relative velocities, when $\mathbf{E_{k}}(\mathbf{V}_{i})\rightarrow 0$ , there is a duality on the behavior produced by the robots. More specifically, one may not differentiate if the robots are stationary or moving with the same velocities. To avoid such duality, we added a third term to force the $i$ -th robot to reach its maximum speed.

IV-E Sampling algorithm

Finally, given the probability function (8) and the potential energy defined by combination of (12) and (13) one may use a MCMC algorithm to sample velocities for the $i$ -th robot. In this work, we use the Metropolis-Hastings algorithm [34] for sampling the velocities.

V Experiments and Results

To evaluate the performance of our approach, we conduct a series of simulated experiments. We first analyze the segregative behavior by measuring the method’s performance for different configurations and comparing the results with other methods from the literature. Then, to analyze the flocking capabilities, we evaluate the velocity consensus and the cohesion among the robots when there is noise in the sensor. Finally, we performed experiments with real robots as a proof-of-concept to show the feasibility of our approach in real scenarios. Fig. 2 shows snapshots illustrating the simultaneous flocking segregative behavior produced by our methodology. A video of the experiments is available at Youtube³³3https://youtu.be/KooNGIStWlM and the source code at Github⁴⁴4https://github.com/verlab/2021-icra-grf-swarm.

V-A Segregation Analysis

To evaluate the segregative behavior considering only local information, we compare the convergence rate of our approach against the one presented by Mitrano et al. [15] and Inácio et al. [17]. We consider the work proposed by Santos et al. [10] as a baseline since it assumes global knowledge about the positions of other robots leading to a fast convergence rate. We also contrast our methodology with a deterministic gradient descent approach using potential differentials to show that such mechanism may be easily trapped at local minima.

The experiments consisted of $100$ runs of each approach with a maximum of $20000$ iterations. A random initial state is generated for each run, but it is the same for all approaches. At each iteration, the robot can move a maximum of $0.02$ meters in a square area of $10$ by $10$ meters with the walls being considered obstacles. We varied the number of robots and the number of heterogeneous groups to evaluate each approach’s performance. As a metric, we compute the total amount of clusters formed by robots of the same type and the number of iterations necessary to reach it. Here, two robots of the same type are considered to be in the same cluster if their relative distance is less than $0.3$ meters – the robot radius is $0.07$ meters. The sensing range is set to $0.5$ meters ( $\lambda=0.5$ ) Fig. 3 shows the mean and the $99\%$ confidence interval comparing one with the other approaches.

Analyzing the segregation using the number of formed clusters, we can see that all approaches executed relatively well for a small number of groups, even for an increasing number of robots per group (Fig. 3(a), top). The exception is the Gradient-Descent method, which gets trapped in local minima and cannot reach a segregated state. When the number of groups increases, our approach significantly outperforms the others, with a performance close to the baseline which uses global information (Fig. 3(b), top). When there is a large number of groups, robots usually get trapped by other groups and cannot reach a segregated state. By relying on the stochastic nature of the GRF, our approach can handle these situations better.

Regarding the performance in terms of the number of iterations to reach segregation, we can see that the methods have a similar performance on average when increasing the number of robots. However, all of them are significantly slower than the baseline, which uses global information (Fig. 3(a), bottom). When we vary the number of groups, we can see that Inácio et al. have a better performance (Fig. 3(b), bottom). However there may be a caveat, specially for $|\tau|=30$ : our metric considers the number of iterations spent until reaching the minimum number of clusters. As previously mentioned, Inácio’s method does not reach the minimum number of clusters on several occasions. So, it may be converging faster but to a sub-optimal configuration. On the other hand, our method may take longer due to its stochastic nature, but has a much better success rate.

V-B Flocking Analysis

To evaluate the effectiveness of our approach in producing flocking behaviors, we carried out some experiments and analyzed them regarding the average distance (cohesion) and consensus speed between robots of the same type. The robustness of our method is assessed by adding Gaussian noise $\epsilon$ to the sensor model so that the relative position and velocity estimates are not reliable. Here, we perform $100$ runs with a maximum of $20000$ iterations. We assume $|\tau_{m}|=30$ robots into $|\tau|=5$ heterogeneous groups and sensing range $\lambda=0.5$ meters. The robots start each run in a random initial state and perform both segregation and flocking within an environment of 10 by 10 meters at a maximum speed of $v_{max}=1.0$ meters per second. Noise in the sensor model ranges from $\epsilon=\{0\%,2\%,6\%,10\%\}$ for both relative position and velocity. A noise of $\epsilon=10\%$ implies an error of up to $10\%\lambda=0.05$ meters in position and $10\%v_{max}=0.10$ meters per seconds in speed. Fig. 4 shows the mean and the $95\%$ confidence interval evaluating the impact that such a noise causes in our methodology.

As expected, increasing noise in the sensor model significantly impacts the velocity consensus. We observed that up to $\epsilon=6\%$ , the swarm is able to maintain the flocking-segregative behavior for the experiments’ configuration. When $\epsilon=10\%$ , we notice the velocity consensus degrading and, consequently, the flocking behavior does not converge. However, even with the noise we can segregate the swarm to the minimal number of clusters most of the times for a sufficiently large number of iterations.

V-C Real robots

To evaluate the feasibility of our approach in a real environment, we performed proof-of-concept experiments using five e-puck robots [35]. The robots receive velocity commands from a remote server executing ROS. Given that our robots do not have any sensor that allows them to estimate the relative position and velocity of neighboring robots, we emulate such a sensor using the Optitrack motion capture system [36].

Here we consider the bounded environment as a square area of 2 by 2 meters restricted by walls. We set the sensing distance to $\lambda=0.3$ , and as we have only a few robots, we evaluate cases where we have one or two groups. That is one group with five robots and two groups with two and three robots each. Fig. 5 shows the performance of our approach using real robots. We can see that the robots can reach segregation and also keep the flocking behavior, but with some noise in the velocity consensus due to the uncertainties observed in real settings.

VI Conclusion and Future Work

This paper presented a novel decentralized approach that allows a swarm of heterogeneous robots to achieve simultaneously segregation and flocking behaviors using only local sensing. We compared the segregative behavior with some state-of-the-art approaches and evaluated the flocking behavior in simulated and real scenarios. Results showed that our methodology can segregate a group of heterogeneous robots while keeping cohesive navigation around the environment.

In future work, we intend to equip our robots with distance and bearing sensors and temporally combine their information to locally estimate the neighboring robots’ velocity and position. Moreover, there are several opportunities for future studies and applications using the GRF framework. In particular, we intend to investigate the possibility of performing more complex tasks, such as transport and shape-formation.

References

[1] Marc Z Miskin, Alejandro J Cortese, Kyle Dorsey, Edward P Esposito, Michael F Reynolds, Qingkun Liu, Michael Cao, David A Muller, Paul L McEuen, and Itai Cohen. Electronically integrated, mass-manufactured, microscopic robots. Nature, 584(7822):557–561, 2020.
[2] Manuele Brambilla, Eliseo Ferrante, Mauro Birattari, and Marco Dorigo. Swarm robotics: a review from the swarm engineering perspective. Swarm Intelligence, 7(1):1–41, 2013.
[3] Vinicius G. Santos, Luciano C. A. Pimenta, and Luiz Chaimowicz. Segregation of multiple heterogeneous units in a robotic swarm. In 2014 IEEE International Conference on Robotics and Automation (ICRA), pages 1112–1117. IEEE, 2014.
[4] Gregory Dudek, Michael RM Jenkin, Evangelos Milios, and David Wilkes. A taxonomy for multi-agent robotics. Autonomous Robots, 3(4):375–397, 1996.
[5] Roderich Groß, Stéphane Magnenat, and Francesco Mondada. Segregation in swarms of mobile robots based on the brazil nut effect. In 2009 IEEE/RSJ International Conference on Intelligent Robots and Systems, pages 4349–4356. IEEE, 2009.
[6] Jianing Chen, Melvin Gauci, Michael J Price, and Roderich Groß. Segregation in swarms of e-puck robots based on the brazil nut effect. In Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems-Volume 1, pages 163–170, 2012.
[7] Devwrat Joshi, Masahiro Shimizu, and Koh Hosoda. Segregation and flow of modules in a robot swarm utilising the brazil nut effect. In 2019 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pages 4080–4085. IEEE, 2019.
[8] Manish Kumar, Devendra P Garg, and Vijay Kumar. Segregation of heterogeneous units in a swarm of robotic agents. IEEE transactions on automatic control, 55(3):743–748, 2010.
[9] Malcolm S Steinberg. Reconstruction of tissues by dissociated cells. Science, 141(3579):401–408, 1963.
[10] Vinicius G. Santos, Anderson G. Pires, Reza J. Alitappeh, Paulo A. .F Rezeck, Luciano C. A. Pimenta, Douglas G. Macharet, and Luiz Chaimowicz. Spatial segregative behaviors in robotic swarms using differential potentials. Swarm Intelligence, pages 1–26, 2020.
[11] BF Edson Filho and Luciano CA Pimenta. Segregating multiple groups of heterogeneous units in robot swarms using abstractions. In 2015 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pages 401–406. IEEE, 2015.
[12] Calin Belta and Vijay Kumar. Abstraction and control for groups of robots. IEEE Transactions on robotics, 20(5):865–875, 2004.
[13] Edson B Ferreira-Filho and Luciano CA Pimenta. Abstraction based approach for segregation in heterogeneous robotic swarms. Robotics and Autonomous Systems, 122:103295, 2019.
[14] Edson B Ferreira Filho and Luciano CA Pimenta. Segregation of heterogeneous swarms of robots in curves. In 2020 IEEE International Conference on Robotics and Automation (ICRA), pages 7173–7179. IEEE, 2020.
[15] Peter Mitrano, Jordan Burklund, Michael Giancola, and Carlo Pinciroli. A minimalistic approach to segregation in robot swarms. In 2019 International Symposium on Multi-Robot and Multi-Agent Systems (MRS), pages 105–111. IEEE, 2019.
[16] David St-Onge, Carlo Pinciroli, and Giovanni Beltrame. Circle formation with computation-free robots shows emergent behavioural structure. In 2018 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pages 5344–5349. IEEE, 2018.
[17] Fabrício R Inácio, Douglas G Macharet, and Luiz Chaimowicz. Pso-based strategy for the segregation of heterogeneous robotic swarms. Journal of Computational Science, 31:86–94, 2019.
[18] Russell Eberhart and James Kennedy. A new optimizer using particle swarm theory. In Micro Machine and Human Science, 1995. MHS’95., Proceedings of the Sixth International Symposium on, pages 39–43. IEEE, 1995.
[19] Jur van den Berg, Stephen J. Guy, Ming Lin, and Dinesh Manocha. Reciprocal n-Body Collision Avoidance, pages 3–19. Springer Berlin Heidelberg, 2011.
[20] Craig W Reynolds. Flocks, herds and schools: A distributed behavioral model. In Proceedings of the 14th annual conference on Computer graphics and interactive techniques, pages 25–34, 1987.
[21] Sifat Momen, Bala P Amavasai, and Nazmul H Siddique. Mixed species flocking for heterogeneous robotic swarms. In EUROCON 2007-The International Conference on” Computer as a Tool”, pages 2329–2336. IEEE, 2007.
[22] Mikko Mönkkönen, Pekka Helle, and Kimmo Soppela. Numerical and behavioural responses of migrant passerines to experimental manipulation of resident tits (parus spp.): heterospecific attraction in northern breeding bird communites? Oecologia, 85(2):218–225, 1990.
[23] Frederick Ducatelle, Gianni A Di Caro, Carlo Pinciroli, and Luca M Gambardella. Self-organized cooperation between robotic swarms. Swarm Intelligence, 5(2):73, 2011.
[24] Alessandro Stranieri, Eliseo Ferrante, Ali Emre Turgut, Vito Trianni, Carlo Pinciroli, Mauro Birattari, and Marco Dorigo. Self-organized flocking with an heterogeneous mobile robot swarm. In ECAL, pages 789–796, 2011.
[25] Vinicius Graciano Santos, Mario FM Campos, and Luiz Chaimowicz. On segregative behaviors using flocking and velocity obstacles. In Distributed Autonomous Robotic Systems, pages 121–133. Springer, 2014.
[26] Paolo Fiorini and Zvi Shiller. Motion planning in dynamic environments using velocity obstacles. The International Journal of Robotics Research, 17(7):760–772, 1998.
[27] Fabrício R Inácio, Douglas G Macharet, and Luiz Chaimowicz. United we move: Decentralized segregated robotic swarm navigation. In Distributed Autonomous Robotic Systems, pages 313–326. Springer, 2018.
[28] Jur Van Den Berg, Stephen J Guy, Ming Lin, and Dinesh Manocha. Reciprocal n-body collision avoidance. In Robotics research, pages 3–19. Springer, 2011.
[29] Xiaobo Tan, Wei Xi, and John S Baras. Decentralized coordination of autonomous swarms using parallel gibbs sampling. Automatica, 46(12):2068–2076, 2010.
[30] Richard A Buckingham. The classical equation of state of gaseous helium, neon and argon. Proceedings of the Royal Society of London. Series A. Mathematical and Physical Sciences, 168(933):264–283, 1938.
[31] Ross Kindermann. Markov random fields and their applications. American mathematical society, 1980.
[32] Daphne Koller and Nir Friedman. Probabilistic graphical models: principles and techniques. MIT press, 2009.
[33] W Keith Hastings. Monte carlo sampling methods using markov chains and their applications. 1970.
[34] Peter H Peskun. Optimum monte-carlo sampling using markov chains. Biometrika, 60(3):607–612, 1973.
[35] Francesco Mondada, Michael Bonani, Xavier Raemy, James Pugh, Christopher Cianci, Adam Klaptocz, Stephane Magnenat, Jean-Christophe Zufferey, Dario Floreano, and Alcherio Martinoli. The e-puck, a robot designed for education in engineering. In Proceedings of the 9th conference on autonomous robot systems and competitions, volume 1, pages 59–65. IPCB: Instituto Politécnico de Castelo Branco, 2009.
[36] NaturalPoint. Motion capture systems. http://optitrack.com. Accessed: 2019-09-02.