Spatial segregative behaviors in robotic swarms using differential potentials

Abstract

Segregative behaviors, in which individuals with common characteristics are placed together and set apart from other groups, are commonly found in nature. In swarm robotics, these behaviors can be important in different tasks that require a heterogeneous group of robots to be divided in homogeneous sets according to their physical (sensors, actuators) or logical (algorithms) capabilities. In this paper, we propose a controller that can spatially segregate a swarm of robots in two specific ways: clusters and concentric rings. By segregation, we mean that the swarm is partitioned in groups, with similar robots belonging to a same group, and these groups are spatially separated from each other. We achieve this by adapting and extending the differential potential concept, an abstraction of the mechanism by which cells achieve segregation. We present stability analysis and perform simulated experiments in 2D and 3D spaces in order to show the robustness of the proposed controller. Experiments with a limited number of real robots are also presented as a proof of concept. Results show that our approach allows a swarm of heterogeneous robots to segregate in a stable, compact, and collision-free fashion.

1 Introduction

Robotic swarms are systems composed of a large number of robots that usually rely on self-organized behaviors in order to solve complex problems. Such systems have been receiving significant attention in recent years due to current advances in technology, which are allowing the mass production of increasingly smaller robots. Şahin (2005) defines swarm robotics as the study and implementation of methods that allow a large number of simple, physically embodied agents to achieve a desired collective behavior in a robust, flexible, and scalable manner. In a wide range of applications, these three properties provide key advantages such as low-cost distributed sensing, reduced chances of complete system failures, better workload distribution, and massive task parallelization.

Research in swarm robotics usually focuses on homogeneous systems, in which all robots have the same physical characteristics (Dudek et al. 1996). However, several applications require the use of heterogeneous teams of agents in order to complete a given task, as sometimes it is not possible to integrate all of the required sensing and actuation capabilities in a single robot. One example of a heterogeneous swarm is the swarmanoid robotic system (Dorigo et al. 2013), which comprises three distinct types of robots: foot-bots, a differential drive unit; hand-bots, an agent that can climb structures and manipulate objects; and eye-bots, an indoor flying robot. Swarm systems such as swarmanoid may be especially useful in search and rescue missions, surveillance and perimeter protection scenarios, cooperative transportation of objects, among other applications.

In some scenarios, heterogeneous robots must be able to organize themselves in a specific manner so as to complete their assignments. For example, supply gathering robots may need to form teams that can maximize the throughput of a particular resource. A possible strategy would be to sort agents according to their specialization, in such a way that gatherers of the same resource stay in the same team. We can say that such system shows a segregative behavior, that is, the sorting process leads dissimilar robots into distinct teams.

Segregation is a natural phenomenon that is commonly used as a sorting mechanism by several biological systems. For example, ants sort their brood into annular patterns where distinct broods tend to be placed at particular annuli (Franks and Sendova-Franks 1992); odors can impact the spatial distribution of several species of cockroaches, whose larvae prefer their own strain odor to that of another (Ame et al. 2004); and the Law of Segregation from classic genetics explains trait inheritance as a process by which two genes separate from each other during gamete formation, leading them to appear in different gametes of the offspring (Ridley 2003). Another important example is embryogenesis, in which cells segregate into distinct regions whose characteristics allow a particular type of tissue to be generated (Eduard and Wilkinson 2012). Phenomena such as these have been extensively studied by biologists, but few robotics researchers have used them as inspiration for developing control strategies in swarm robotics.

In this paper, we present a controller that is able to sort a heterogeneous swarm of robots into homogeneous teams according to the characteristics of each robot. We refer to this sorting behavior as segregation and provide two distinct forms thereof: cluster segregation, in which similar robots form cohesive clusters, and dissimilar ones are separated from each other; and radial segregation, in which robots must form a joint, concentric annular formation that sorts unalike robots into different rings and like robots into a same ring (see Fig. 1). In order to validate the proposed controller, we employ a formal stability analysis and present simulations in 2D and 3D spaces. Furthermore, experiments using a limited number of real robots are provided as proof-of-concept of our methodology.

We believe that the use of large groups composed of robots of different types, with different sensors, different mobility capabilities, different actuators, etc., might be beneficial to several real applications that require flexibility of the swarm. In such scenario, as discussed by Ferreira Filho and Pimenta (2019a), it may be important to have swarms endowed with the ability of autonomously exhibiting segregation behaviors. Segregation can be seen as a collective behavior which allows for the formation of certain interesting geometric patterns such as clusters and rings. Executing a certain type of segregation behavior can be then an important intermediary step in the solution of complex tasks which are commonly tackled by considering hierarchical approaches where different software layers solve different sub-problems of the complete task. A high-level layer could be responsible for solving multi-robot task allocation problems (Gerkey and Matarić 2004) with the aim of assigning robots of different types to groups so as to maximize performance. On the other hand, a low-level layer could be responsible for coordinating each group in the execution of each assigned task such as object manipulation, perimeter surveillance, and environment exploration. In this context, a middle layer responsible for segregating the groups can also be necessary. For example, in scenarios where the agents of a specific group need to exchange a large amount of data before the execution of the assigned task, it is clear the advantage of creating spatial clusters formed by agents of the same group before sending the data. It is more efficient for the robots to communicate with other robots if they are close to each other. At the same time, interference is avoided if the robots of a group are separated from robots of other groups. This clearly motivates the application of cluster segregation behaviors as an intermediary step. Concerning radial segregation behaviors, in which different groups are deployed at circles of different radius values, it is possible to imagine its application in scenarios of perimeter surveillance with the objective of protecting certain regions of the environment from incoming invaders as presented in (Bajaj and Bopardikar 2019). Considering swarms composed of robots that move at different speeds, faster robots could be assigned to surveil outer circles, while slower robots could be assigned to surveil inner circles.

Fig. 1

The two behaviors displayed by our controller in a system consisting of 50 robots with two types

This paper is organized as follows: We discuss related work on swarm controllers and segregative behaviors in Sect. 2. Our methodology is presented in Sect. 3, and experimental results in both simulated and real scenarios are detailed in Sect. 4. Finally, we close this paper with our conclusions and directions for future work in Sect. 5.

2 Related work

Inspired by the collective motion of flocks, herds, and schools, Reynolds (1987) presented one of the most influential algorithms for simulating the movement of a swarm of agents, known as the boids model. Three simple steering behaviors are applied to each agent in the system, with regard to its surrounding neighbors: separation, which avoids collisions; alignment, which steers agents toward their average heading; and cohesion, which moves agents toward their average positions. In every iteration, each agent computes and weighs all rules according to user-specified parameters, and the result is applied as a steering input. Reif and Wang (1999) provided a generalization of these steering rules in their social potential field method, an extension for multi-agent systems of the well-known artificial potential fields technique (Khatib 1985), which is commonly used in robotics for obstacle avoidance. In this framework, pairwise potential functions are defined among robots according to some desired behavior for the whole swarm, and control rules are then formulated based on the gradient of these functions. Thus, robots are controlled as if they were particles moving in a vector field.

The idea of driving the motion of multiple robots as if they were particles subject to the action of artificial forces was explored in the work of Spears et al. (2004). The proposed framework was entitled “physicomimetics” in which, different from other works, the artificial forces were used to generate “way points” for the robots instead of directly providing the robot control inputs. Under this approach, homogeneous groups of robots were able to form lattices, perform goal tracking, obstacle avoidance, surveillance, and perimeter defense tasks. Another interesting example inspired by laws of physics is the work of Pimenta et al. (2013), in which robots are controlled using a fluid dynamics model. Basically, the whole swarm behaves as a fluid, of which every robot represents a portion, and Smoothed Particle Hydrodynamics, a numerical method frequently used to simulate fluids, is employed so as to derive decentralized control laws for the swarm.

These works have been widely used as foundations to several control strategies and applications in swarm robotics. Some examples include, but are not limited to: pattern formation (Hsieh et al. 2008; Coppola et al. 2019), leader-follower strategies (Leonard and Fiorelli 2001; Tanner et al. 2004), shepherding (Lien et al. 2004), congestion control (Marcolino et al. 2017) and flocking (Olfati-Saber 2006; Tanner et al. 2007).

Another type of approach considers a mathematical model of synchronizing oscillators able to move in the environment (Iwasa et al. 2010; Starnini et al. 2016), a representation for self-organizing groups of individuals found in nature. The elements of such systems were then called ‘swarmalators’ by O’Keeffe et al. (2017), an intuitive name for systems that mix swarming and synchronization. The phase and spatial dynamics of such systems result from a location-dependent synchronization and phase-dependent aggregation, respectively. However, such two-way space-phase coupling is difficult to find in real-world systems (O’Keeffe et al. 2018). This approach is also another example of strategy that considers the composition of pairwise attractive and repulsive virtual forces acting on the agents. In robotic swarms, this is indeed an effective strategy to generate patterns and gives rise to interesting emergent behaviors. Differently from most works in robotics literature, in this case the attractive and repulsive forces are functions not only of the relative displacement of agents but also of the third state variable called phase. The dynamics of this third variable is also dependent on the relative displacement giving rise to a coupled system. This is quite interesting as it allows for the coupling between swarming and synchronization behaviors. For such systems, different stationary and non-stationary states are observed depending on the values of the model parameters. Among the collective states swarmalators can exhibit, the splintered phase wave can be seen as a segregative behavior, as a set of clusters of robots with the same phase are formed. However, it is important to emphasize this is a non-stationary state where agents keep moving even after convergence and according to O’Keeffe et al. (2017), it is not clear yet what determines the exact number of clusters that will be formed. As discussed by O’Keeffe and Bettstetter (2019), the theoretical works developed in this field are mainly concerned with the problem of finding which spatiotemporal patterns will emerge given the mathematical swarmalator model. Just recently, real-world implementation of these models has been undertaken and some of the theoretical patterns have been also observed in real robots (Barciś et al. 2019). The results on swarmalators provide evidence that the application of these models in robotics is promising and may pave the way for the solution of complex tasks. This will become possible when future research provides the tools that will enable one to design a model given an arbitrary desired spatiotemporal pattern to be formed. A comprehensive review of swarmalators is presented in (O’Keeffe and Bettstetter 2019).

In this work, we consider a potential field-based approach, which relies only on the difference of positions and its derivatives, without the need of considering any kind of internal state dynamics for the agents (phase) as in the case of swarmalators. Potential fields are well established and have proven their efficacy in a large body of real-world scenarios in the last decades. Besides its intrinsic robustness and its low computational cost, it has also another appealing feature which is the possibility of considering the associated potential function in the process of construction of a Lyapunov function to be used in stability analysis. Being able to successfully apply Lyapunov theorems, or extensions such as LaSalle’s theorems, in such analysis depends highly on the ability to find such a function, which might be very tricky for general nonlinear systems. In robotic systems this process can be facilitated when considering potential field-based controllers. In this work, we benefit from this important feature allowing us to prove convergence to invariant sets and collision-free motion in segregation tasks for swarms composed of agents with double integrator dynamics.

None of the previously cited works presented strategies dedicated to induce segregation behaviors in heterogeneous groups of robots. On the subject of segregation in swarm robotics, research has been mostly focused on using it as a mechanism by which robots sort a set of objects (e.g., see Deneubourg et al. (1991)). Few authors have specifically studied segregation in heterogeneous swarms in a similar sense as we do. One example is Groß et al. (2009), which presented a motor schema that allowed robots to organize into annular structures. Their work was based on the Brazil Nut Effect, a convection phenomenon by which a mixture of granular material subjected to vibrations ends up with its largest particles close to the surface (Rosato et al. 1987). The authors designed a distributed controller that considered robots as grains of different sizes, and local interactions among neighbors made “larger” agents move outward. Despite the interesting results, their controller relies on randomized input and requires all robots to share a common target in order to simulate vibrational and gravitational forces, respectively. This behavior was demonstrated with swarms of physical e-puck robots by Chen et al. (2012a). Also inspired by this convection phenomenon, de la Croix and Egerstedt (2013) devised a weighted consensus protocol in which similar robots had the same weight and were subjected to an external control signal that separated the system into a desired number of clusters. Nevertheless, this signal must come from a centralized source, which may hinder the scalability of the system in real scenarios.

Ferreira Filho and Pimenta (2015) introduced an approach to swarm cluster segregation based on hierarchical abstractions, which are virtual structures that embody the pose and shape of a team of robots (Tan and Lewis 1996). Abstractions were modeled as circles, and control equations were derived to separate these circles so that robots belonging to the same group stay inside the same circle. The authors presented stability and convergence proofs of segregation, but their method was not collision-free, and a practical implementation may require a centralized unit that broadcasts inputs for all abstractions or a networked consensus algorithm to be employed among robots. This approach was extended in Ferreira Filho and Pimenta (2019a) in which a collision avoidance scheme based on the solution of an optimization problem which does not interfere in the solution of the segregation problem is incorporated in the method.

Decentralized radial segregation was also tackled by these authors. In Ferreira Filho and Pimenta (2019b), they present a method based on the use of consensus protocols and some heuristics to find where the segregation is going to take place and the correct radius for each group. Although the method is able to run in a decentralized way, it assumes the maintenance of an underlying fixed communication topology during the execution of the task.

In Edwards et al. (2016), the swarm segregation was formulated as a convex optimization problem, which results in provably correct segregation, however, relying on global knowledge. More recently, St-Onge et al. (2018) proposed a minimalistic reactive approach based on local information to obtain a circular behavior, concept that was later used in (Mitrano et al. 2019) to achieve segregation. Also considering local information only, Inácio et al. (2019) presented an evolutionary-based strategy that combines concepts of the particle swarm optimization (PSO) with the optimal reciprocal collision avoidance (ORCA) algorithm to keep groups segregated as they navigate.

A superset behavior of segregation is splitting: when a large, coherent cluster of agents separates into two or more smaller clusters, without regarding any intrinsic characteristic of each robot. In this context, Chen et al. (2012b) employed artificial forces having distinct effective ranges to control splitting as well as merging behaviors in a homogeneous system. More precisely, they used a long-range, attractive force; a short-range, repulsive force; and an intermediate-range, Gaussian-shaped, repulsive force. By tuning the magnitude of the intermediate-range repulsion, they achieved splitting or merging behaviors for the whole swarm. In another work, Zhao et al. (2011) provided decentralized density-based controllers for swarms of robots, and they observed that a segregative behavior emerged when applying their control method on a homogeneous swarm, i.e., robots were split into subgroups that formed circular patterns after reaching equilibrium. These circular arrangements changed from multiple ring-like patterns to a single ring when decreasing the reference density of the system. Unfortunately, the authors indicated that a mathematical explanation for such behavior is still open. Altogether, in both of these works, there is no straightforward manner of selecting which robots must be segregated, since the authors considered the swarm to be homogeneous. Also, as a side note, Zhao et al. (2011) classified the behavior of their controller as being segregative, but we consider that it actually is a splitting behavior, because segregation occurs when the split is due to differences in an intrinsic characteristic that is shared among agents.

To some extent, another problem related to segregation is stationary clustering: when robots are spatially assembled into different groups by relying on communication, but not movement. One such approach is by Di Caro et al. (2012), who introduced a token-based communication protocol that relies on spatial awareness. Each robot uses a local ad hoc network to propagate messages containing tokens that represent the density of robots in its surrounding area, and a load-balancing protocol transports tokens among robots so that after convergence agents can be split into two groups: those that hold tokens and those that do not. This approach was later extended to handle clustering into more than two groups (Cruz et al. 2015).

In biological theory, the Differential Adhesion Hypothesis (DAH) (Steinberg 1963) states that differences in cell adhesion generate mechanical forces that drive cellular segregation. In other words, a cell population experience stronger cohesive forces when among similar cells than when among dissimilar ones, and this imbalance is responsible for the segregative behavior (Eduard and Wilkinson 2012). Based on the DAH, Kumar et al. (2010) proposed that robots should experience different magnitudes of potential while interacting with different agents so as to achieve segregation, namely the differential potential concept. They devised a controller that was able to segregate a swarm comprising of two types of robots into two distinct clusters in a smooth and concise fashion.

By following the DAH approach proposed by Kumar et al. (2010), we introduced a modified version of their controller that is able to handle segregation of a heterogeneous swarm into multiple clusters (Santos et al. 2014). Moreover, stability results and collision avoidance guarantees were provided. In spite of the efficacy of both approaches, only numerical simulations were provided in the papers, and implementations on real robots were not presented. Thus, in comparison with our previous work (Santos et al. 2014), in this paper we present further extensions of our controller, novel metrics for measuring segregation, an improved discussion and analysis of the proposed method, including some of its limitations, and new simulations as well as experiments with real robots.

3 Methodology

We consider a set of fully actuated, heterogeneous mobile agents whose dynamics are given by the following double integrator:

$$\begin{aligned} {\dot{q}}_i = v_i \text { and } {\dot{v}}_i = u_i \quad i \in \varUpsilon = \{1,2,\dots ,n\}, \end{aligned}$$

(1)

in which $q_i \in {\mathbb {R}}^p$, $v_i \in {\mathbb {R}}^p$, and $u_i \in {\mathbb {R}}^p$ are the position, velocity, and control input of robot i, respectively $(p \ge 2)$. The heterogeneity of the system is modeled by a partition $\tau = \{\tau _1,\tau _2,\dots ,\tau _m \}$, with each $\tau _k \subset \varUpsilon$ containing all agents of type k. We assume that $\forall j,k: \, j \ne k \rightarrow \tau _j \cap \tau _k = \emptyset$ and $\forall j,k:|\tau _j|{\approx }|\tau _k|$, i.e., each robot is uniquely assigned to a single type and the partition sizes are balanced¹.

Our goal is to sort robots of different types into m distinct groups so that each group contains only similar agents. This task can be done by our controller in two distinct ways: cluster segregation and radial segregation. In the former, robots belonging to a particular $\tau _k$ must be cohesively grouped into a single cluster while being split from other agents. In the latter, the whole swarm must form a joint, concentric annular formation in which robots of $\tau _k$ must belong to a same ring, while agents of different types must belong to different ones.

3.1 Control law

Given a heterogeneous system with type partition $\tau$ on n mobile agents, whose dynamics are described by (1), we propose the following control law:

$$\begin{aligned} u_i = - \sum _{j \ne i} \nabla _{q_i} U_{ij}(\Vert q_{ij}\Vert ) - \sum _{j \ne i} (v_i - v_j), \end{aligned}$$

(2)

in which $U_{ij}(\Vert q_{ij}\Vert )$ is an artificial potential function that rules the interaction between agents i and j, $\Vert q_{ij}\Vert$ is the Euclidean norm of the vector $q_i - q_j$, and $\nabla _{q_i}$ is the gradient with respect to the coordinates of agent i. The first term in (2) represents the interactions of robot i with all other agents, and the second term forces robots to match their velocities. The artificial potential field $U_{ij}:{\mathbb {R}} \rightarrow {\mathbb {R}}_{>0}$ is a function of the relative distance between a pair of agents, i.e.,

$$\begin{aligned} U_{ij}(\Vert q_{ij}\Vert ) = \alpha \left( \frac{1}{2} (\Vert q_{ij}\Vert - d_{ij})^2 + \ln {\Vert q_{ij}\Vert } + \frac{d_{ij}}{\Vert q_{ij}\Vert }\right) , \end{aligned}$$

(3)

in which $\alpha \in {\mathbb {R}}_{>0}$ is a scalar control gain, and $d_{ij} \in {\mathbb {R}}_{>0}$ is a parameter that controls the segregative behavior between i and j, as discussed in the next paragraph. The initial conditions and dynamics of the system exclude all situations where (3) is undefined. In other words, if there are no collisions at the initial state, then the system is collision-free throughout all time steps (see Proposition 2). Moreover, an important assumption in these equations is that each robot is capable of computing its distance $q_{ij}$ and relative velocities to all other robots. In Sect. 4 we present experiments relaxing this assumption.

We apply the differential potential concept (Kumar et al. 2010) to control the robots, i.e., pairs of dissimilar agents must experience different magnitudes of potential than pairs of similar agents. We accomplish this by specifying $d_{ij}$ according to the following definition:

$$\begin{aligned} d_{ij} = {\left\{ \begin{array}{ll} d_{AA}^{(k)},& \text {if } i \in \tau _k \text { and } j \in \tau _k \\ d_{AB},& \text {if } i \in \tau _k \text { and } j \not \in \tau _k \end{array}\right. }, \end{aligned}$$

(4)

where $d_{AA}^{(k)}$ is a particular constant for each $\tau _k$. We state by (4) that interactions among similar robots of type k are ruled by $d_{AA}^{(k)}$, while interactions among robots of different types are ruled by $d_{AB}$. The system achieves two distinct behaviors according to the values of these constants as shown in Table 1.

Table 1 Constraints on the parameter $d_{ij}$ for achieving cluster and radial segregation

We show in Fig. 2a a plot of the artificial potential function $U_{ij}(\Vert q_{ij}\Vert )$, whose minimum is located at $\Vert q_{ij}\Vert = d_{ij}$, and display the possible interaction forces between a pair of robots in Fig. 2b. The latter actually depicts the scalar part of the gradient

$$\begin{aligned} \nabla U_{ij}(\Vert q_{ij}\Vert ) = \alpha \left( \Vert q_{ij}\Vert - d_{ij} + \frac{1}{\Vert q_{ij}\Vert } - \frac{d_{ij}}{\Vert q_{ij}\Vert ^2}\right) \frac{q_{ij}}{\Vert q_{ij}\Vert }, \end{aligned}$$

(5)

of which we ignore the normalized vector term $q_{ij}/\Vert q_{ij}\Vert$. It is easy to see that when $d_{AA}^{(k)} < d_{AB}$, at any given distance, forces among agents of similar types are greater than those among different types, and the opposite is true for $d_{AA}^{(k)} > d_{AB}$. Therefore, our controller effectively implements some of the key ideas in Steinberg’s differential adhesion model (Steinberg 1963) for cellular segregation.

Fig. 2

Plot of the potential field $U_{ij}(\Vert q_{ij}\Vert )$ and its underlying forces given $d_{AA}^{(1)}=2$, $d_{AB}=5$, and $d_{AA}^{(2)}=8$

3.2 Controller analysis

In this section, we analyze the convergence and some properties of the multi-agent system when using the proposed control law. Let $V({\mathbf {q}},{\mathbf {v}})$ be the Lyapunov function

$$\begin{aligned} V({\mathbf {q}},{\mathbf {v}}) = U({\mathbf {q}}) + \frac{1}{2} {\mathbf {v}}^\intercal {\mathbf {v}}, \end{aligned}$$

(6)

in which ${\mathbf {q}} \in {\mathbb {R}}^{np}$ and ${\mathbf {v}} \in {\mathbb {R}}^{np}$ are stacked vectors whose components are the positions and velocities of all robots, respectively, and $U({\mathbf {q}}): {\mathbb {R}}^{np} \rightarrow {\mathbb {R}}_{>0}$ is the collective artificial potential function, which can be written as follows:

$$\begin{aligned} U({\mathbf {q}})&= \frac{1}{2} \sum _{\tau _k \in \tau } \sum _{i \in \tau _k} \sum _{j \in \tau _k, j \ne i} U_{ij}(\Vert q_{ij}\Vert )\nonumber \\&+ \frac{1}{2} \sum _{\tau _k \in \tau } \sum _{i \in \tau _k} \sum _{j \in \varUpsilon \setminus \tau _k} U_{ij}(\Vert q_{ij}\Vert ). \end{aligned}$$

(7)

With this definition, we can model the collective dynamics of the system by

$$\begin{aligned} \dot{{\mathbf {q}}}&= {\mathbf {v}} \end{aligned}$$

(8)

$$\begin{aligned} \dot{{\mathbf {v}}}&= -\nabla U({\mathbf {q}}) - {\hat{L}}({\mathbf {q}}){\mathbf {v}}, \end{aligned}$$

(9)

in which ${\hat{L}}({\mathbf {q}}) = L({\mathbf {q}}) \otimes I_p$ is the Kronecker product of the system’s Laplacian matrix $L({\mathbf {q}})$ and the $p \times p$ identity matrix $I_p$ (please refer to (Olfati-Saber 2006) for a thorough description of (9)).

Proposition 1

The collective artificial potential function $U({\mathbf {q}})$ is strictly convex if $\forall i,j: d_{ij} > \frac{\sqrt{3}}{9}$.

Proof

The second derivative of $U_{ij}(\Vert q_{ij}\Vert )$ with respect to $\Vert q_{ij}\Vert$ is given by

$$\begin{aligned} U^{''}_{ij}(\Vert q_{ij}\Vert ) = \alpha \left( 1 -\frac{1}{\Vert q_{ij}\Vert ^2} + \frac{2d_{ij}}{\Vert q_{ij}\Vert ^3}\right) , \end{aligned}$$

(10)

of which $\Vert q_{ij}\Vert = 3d_{ij}$ is a minimum. By evaluating $U^{''}_{ij}$ at this particular inter-agent distance, we have

$$\begin{aligned} U^{''}_{ij}(3d_{ij}) = \alpha \left( 1 - \frac{1}{27d^{2}_{ij}}\right) , \end{aligned}$$

(11)

which is positive for $d_{ij} > \frac{\sqrt{3}}{9}$. Hence, given this constraint, $U_{ij}(\Vert q_{ij}\Vert )$ is strictly convex on $(0, \infty )$. The same is also true for $U({\mathbf {q}})$ in its respective domain because the set of convex functions is closed under addition. $\square$

Proposition 2

Assuming that the adjacency graph of the swarm system is complete at all times, and that $\forall i,j: d_{ij} > \frac{\sqrt{3}}{9}$, for any initial condition that belongs to the level set $\varOmega _C = \{({\mathbf {q}},{\mathbf {v}}) \mid V({\mathbf {q}},{\mathbf {v}}) \le C\}$, with $C > 0$, a heterogeneous system with type partition $\tau$ on n mobile agents, whose dynamics and control laws are, respectively, given by (1) and (2), asymptotically converges to the largest invariant set in $\varOmega _I = \{({\mathbf {q}},{\mathbf {v}}) \in \varOmega _C \mid {\dot{V}}({\mathbf {q}}, {\mathbf {v}}) = 0\}$, without any inter-agent collisions. At this largest invariant set, the velocity of each agent is bounded, all velocities match, and the system’s collective potential reaches a global minimum.

Proof

We aim to demonstrate that ${\dot{V}}({\mathbf {q}},{\mathbf {v}}) \le 0$ so as to apply LaSalle’s Invariance Principle in order to show stability. Thus, we can differentiate $V({\mathbf {q}}, {\mathbf {v}})$ with respect to time and then substitute (8) and (9) as follows:

$$\begin{aligned} {\dot{V}}({\mathbf {q}},{\mathbf {v}})&= \dot{{\mathbf {q}}}^\intercal \nabla U({\mathbf {q}}) + {\mathbf {v}}^\intercal \dot{{\mathbf {v}}} \nonumber \\&= {\mathbf {v}}^\intercal \nabla U({\mathbf {q}}) + {\mathbf {v}}^\intercal (-\nabla U({\mathbf {q}}) - {\hat{L}}({\mathbf {q}}){\mathbf {v}}) \nonumber \\&= - {\mathbf {v}}^\intercal {\hat{L}}({\mathbf {q}}){\mathbf {v}} \nonumber \\&= -\frac{1}{2}\sum _i\sum _j\Vert {\mathbf {v}}_i - {\mathbf {v}}_j\Vert ^2 \le 0. \end{aligned}$$

(12)

The last step in (12) holds because the system’s adjacency graph is complete (Olfati-Saber 2006). Therefore, using LaSalle’s Invariance Principle, all initial conditions that lie on $\varOmega _C$ will lead the system to the largest invariant set in $\varOmega _I$, in which ${\dot{V}}({\mathbf {q}},{\mathbf {v}}) = 0$.

During convergence to this largest invariant set, assume that robots i and j collide (i.e., $\Vert {\mathbf {q}}_{ij}\Vert = 0$). We see by (3) and (7) that this would take $U({\mathbf {q}}) \rightarrow \infty$, which contradicts the facts that $V({\mathbf {q}}, {\mathbf {v}}) \le C$ and ${\dot{V}}({\mathbf {q}}, {\mathbf {v}}) \le 0$. Hence, the system is collision-free. Furthermore, by applying $V({\mathbf {q}}, {\mathbf {v}}) \le C$ into (6), we can conclude that ${\mathbf {v}}^\intercal {\mathbf {v}} \le 2C$, leading to $\Vert {\mathbf {v}}\Vert \le \sqrt{2C}$. Consequently, all individual velocities are bounded by $\sqrt{2C}$ as well.

At the largest invariant set in $\varOmega _I$, we showed that ${\dot{V}}({\mathbf {q}},{\mathbf {v}}) = 0$, which, in conjunction with (12), entails that all velocities must match (i.e., $\forall i,j: {\mathbf {v}}_i = {\mathbf {v}}_j$), because this is the only scenario in which (12) can be equal to zero. Matching velocities imply that inter-agent distances remain constant (i.e., $\forall i,j: \dot{{\mathbf {q}}}_{ij} = {\mathbf {0}}$), and by differentiating (7) with respect to time we find

$$\begin{aligned} {\dot{U}}({\mathbf {q}})&= \frac{1}{2} \sum _{\tau _k \in \tau } \sum _{i \in \tau _k} \sum _{j \in \tau _k, j \ne i} \dot{{\mathbf {q}}}_{ij}^\intercal \nabla _{{\mathbf {q}}_{ij}} U_{ij}(\Vert {\mathbf {q}}_{ij}\Vert ) \nonumber \\&+ \frac{1}{2} \sum _{\tau _k \in \tau } \sum _{i \in \tau _k} \sum _{j \in \varUpsilon \setminus \tau _k} \dot{{\mathbf {q}}}_{ij}^\intercal \nabla _{{\mathbf {q}}_{ij}} U_{ij}(\Vert {\mathbf {q}}_{ij}\Vert ) = 0, \end{aligned}$$

(13)

which allows us to conclude that $U({\mathbf {q}})$ is constant at the steady state. Moreover, matching velocities also indicate that ${\hat{L}}({\mathbf {q}}){\mathbf {v}} = {\mathbf {0}}$, which reduces (9) to

$$\begin{aligned} \dot{{\mathbf {v}}} = -\nabla U({\mathbf {q}}). \end{aligned}$$

(14)

Therefore, $\nabla U({\mathbf {q}})$ must be the zero vector, as otherwise the collective potential would reach a lower value instead of being constant. This implies that the system has reached a local minimum of $U({\mathbf {q}})$, and velocities must not change. By Proposition 1, the system actually reaches a global minimum because all local minima of a convex function in an open, convex set are always global extrema. $\square$

Proposition 2 demonstrates that our controller is not hindered by local minima, a common problem in potential-based control strategies, especially in motion planning scenarios (Choset et al. 2005). Notice that this does not indicate that the system is always segregated at the steady state. Instead, it shows that the collective potential energy of the swarm is completely minimized.

We now present two distinct metrics for evaluating the convergence of the system into a segregated state in a quantitative sense. The metric for cluster segregation is based on the intersection area of convex hulls, and the metric for radial segregation relies on a discrete counting procedure.

3.3 Cluster segregation metric

We evaluate our metric by computing the pairwise intersection area between the convex hulls of the robots according to their type partition. That is, the convex hull of all robots of type k is computed and intersected with each other. Formally, metric $M_\text {clu}({\mathbf {q}}, \tau )$ is given by

$$\begin{aligned} {M_\text {clu}({\mathbf {q}}, \tau ) = } \sum _{\tau _k \in \tau }\sum _{\tau _l \in \tau , l \ne k} A \left( CH(\bigcup _{i \in \tau _k} q_i) \bigcap CH(\bigcup _{j \in \tau _l} q_j) \right) , \end{aligned}$$

(15)

in which A(Q) and CH(Q) denote the area and the convex hull of set Q, respectively. We have chosen this metric because the convex hull can be used as a simple and well-defined shape representation of a cluster. This means that cluster segregation occurs when there is no overlap among clusters. Thus, we say that the system is fully segregated when $M_\text {clu}({\mathbf {q}}, \tau )$ approaches zero.

3.4 Radial segregation metric

In order to measure radial segregation, we adapt the metric proposed by Groß et al. (2009) to suit the conditions of our system. Their metric requires robots to segregate around a stationary point $c \in {\mathbb {R}}^p$, and, as this is not the case in our controller, we must simply define this particular point as being the centroid of the swarm,

$$\begin{aligned} c = \frac{1}{n}\sum _{i \in \varUpsilon } q_i, \end{aligned}$$

(16)

which can be shown to be a stationary point of the swarm (Gazi and Passino 2011). Accordingly, we denote the radial segregation metric as

$$\begin{aligned} M_\text {rad}({\mathbf {q}}, \tau ) = \frac{1}{n^2}\sum _{i \in \varUpsilon } \sum _ {j \in \varUpsilon } \epsilon _{ij}({\mathbf {q}}, \tau ), \end{aligned}$$

(17)

in which $\epsilon _{ij}({\mathbf {q}}, \tau )$ is the radial segregation error between a pair of robots, given by

$$\begin{aligned} \epsilon _{ij}({\mathbf {q}}, \tau ) = {\left\{ \begin{array}{ll} 1, & i \in \tau _k, j \in \tau _l, k \ne l,\\ & d_{AA}^{(k)}< d_{AA}^{(l)}, \Vert q_i - c\Vert \ge \Vert q_j - c\Vert \\ 1, & i \in \tau _k, j \in \tau _l , k \ne l,\\ & d_{AA}^{(k)} > d_{AA}^{(l)}, \Vert q_i - c\Vert < \Vert q_j - c\Vert \\ 0, & \text {otherwise} \end{array}\right. }. \end{aligned}$$

(18)

Equation (17) counts the number of robots outside the correct spherical shells according to the values of each $d_{AA}^{(k)}$ and normalizes the result into the unit interval. Therefore, in order to minimize (17), given $d_{AA}^{(k)} < d_{AA}^{(l)}$, robots belonging to $\tau _k$ must be inside an inner shell, whereas robots belonging to $\tau _l$ must be inside an outer shell. In this manner, robots are radially segregated when $M_\text {rad}({\mathbf {q}}, \tau )$ approaches zero.

4 Experiments

In order to analyze our controller under both metrics, we performed an extensive sequence of 2D numerical simulations in a swarm system consisting of 150 robots and a varying number of robot types (5, 10, and 15 distinct types). Experiments considering noise in the robot sensing model and also relaxing the complete graph assumption were also performed. At the outset of every experiment, all velocities were set to zero, robots were positioned according to a two-dimensional uniform distribution, and a minimum distance constraint was maintained among agents to avoid collisions at the initial state. We also developed 3D numerical simulations and evaluated our metrics accordingly. Finally, additional experiments using real robots were performed in a controlled environment as proof-of-concept. A video of the experiments is available at https://youtu.be/jb3DD0mgGEE.

4.1 Cluster segregation

In our numerical simulations of cluster segregation, we set $\forall k : d^{(k)}_{AA} = 2$, $d_{AB} = 5$, and $\alpha =1$ for all tests. We present in Fig. 3a the mean and the $95\%$ confidence interval of metric $M_\text {clu}({\mathbf {q}}, \tau )$ among 100 experiments given the aforementioned initial conditions. In all cases, it is easy to see that both the mean and the confidence interval approach zero as the number of iterations increases. Likewise, experiments comprising fewer types of robots tend to converge to a segregated state faster than those comprising more types. Such result is expected, since using a large number of types results in few robots per cluster, lowering the magnitude of the resultant force acting on a robot toward its respective cluster.

Fig. 3

Mean values of $M_\text {clu}({\mathbf {q}},\tau )$ and $M_\text {rad}({\mathbf {q}}, \tau )$ for 100 experiments with cluster and radial segregation, respectively, with a varying number of robot types. Dashed lines represent a $95\%$ confidence interval

We composed in Fig. 4 a series of snapshots from particular instances of our experiments. We can see that similar robots form clusters whose sizes grow as other agents join them. Moreover, interesting symmetric patterns can be observed at the stable state. When running these experiments, we also noticed two particular behaviors that are not explicit in the snapshots: large clusters usually move to the outskirts of the whole swarm, and adjacent clusters comprised of different robots form corridor-like structures, which were used by agents of a third type to move at higher speeds toward their own cluster. Both behaviors contributed to an overall opening of free space, whereby smaller clusters took advantage to increase their size by joining with lone robots or other small clusters.

Fig. 4

Snapshots of numerical simulations of cluster segregation using 150 robots and a varying number of heterogeneous types in 2D. The type of each robot is represented by a different color. In each sequence, the left and right images represent the initial and final configuration, respectively

These experiments were performed with balanced groups. We also made experiments with unbalanced groups and, in some experiments in which the size of one group is less or equal to 20% the size of the others, we reached equilibrium states in which the smaller groups are not segregated. Normally these situations happen when the robots of the smaller groups reach a symmetrical configuration in which their attractive force is annulled by the repulsive force of the other groups. It means that the minimum of the collective potential is reached without converging to a configuration of segregation. Figure 5 shows snapshots of two scenarios with unbalanced groups. In Fig. 5a, we have four groups with 30 robots and one group with 5. While the large groups segregate, robots of the smaller group stay outside and do not segregate (notice the purple robots close to the coordinates $(-4,2), (-2,-4)$ and $(4,-2))$. Another example is shown in Fig. 5b, with eight groups of 20 robots each and two with 4 robots (notice the purple and pink robots close to the coordinates $(-3,2), (-3,-4)$ and $(4,-3))$. In these simulations, we set $\forall k : d^{(k)}_{AA} = 4$ and $d_{AB} = 5$.

Fig. 5

Scenarios with unbalanced groups. We can see that the robots of the smaller groups stay at the borders and are not able to segregate

Due to situations like these, we have the restriction that group sizes should be balanced. Possible alternatives to cope with this problem will be discussed in Sect. 5.

4.2 Radial segregation

In our simulations of radial segregation, $d_{AB}$ was set to 7.5, and each value for $d_{AA}^{(k)}$ was linearly increased in steps of five units, starting from $d_{AA}^{(1)} = 5$, and the initial conditions were set in the same manner as before. We present in Fig. 3b the mean and the $95\%$ confidence interval of $M_\text {rad}({\mathbf {q}},\tau )$ among 100 experiments. In all cases, the mean and the confidence interval approached zero as the iterations increased, as expected.

Figure 6 contains another series of snapshots from this particular set of experiments. In every sequence, the leftmost and rightmost images show the initial and final states, correspondingly, and the latter also depicts circles as visual aid so that the radial segregation among robots can be more easily observed. Through a visual inspection, we can see that robots entered into an annular, segregated formation whose radius depends on $d_{AA}^{(k)}$, of which the innermost and outermost group of robots have the lowest and highest value, i.e., $d_{AA}^{(1)}$ and $d_{AA}^{(m)}$, respectively. Furthermore, if the number of robots per type ($|\tau _k|$) is sufficiently low when compared to the radius of the annular formation, then the latter degenerates into a perfect circular shape.

Fig. 6

Snapshots of numerical simulations of radial segregation using 150 robots and a varying number of heterogeneous types in 2D. The type of each robot is represented by a different color. In each sequence, the left and right images represent the initial and final configuration, respectively. The rightmost image also displays circles fitted to the convex hull of each set of types to provide visual aid

4.3 Noise in the sensor model

As mentioned in Sect. 3, we assume that the adjacency graph is complete, i.e., each robot can measure its distance $\Vert q_{ij}\Vert$ to all the other robots in the swarm. To relax this assumption a little, we performed some simulations adding noise to these measurements. Basically, we set a maximum error percentage $\xi$ and added Gaussian noise $N(q_{ij}, \sigma )$ to the sensor inputs by setting the variance $\sigma$ to one-third of the maximum noise. That allows the random model to obtain 99.7% of precision according to the 68–95–99.7 rule. We conduct the experiments with different values of $\xi$, specifically: $0\%, 1\%, 5\%, 10\%,$ and $20\%$ maximum errors.

Figure 7a shows the mean and the 95% confidence interval of the metric $M_\text {clu}({\mathbf {q}},\tau )$ over 100 experiments using 150 robots, 5 agents types, for different values of $\xi$. The results show that the sensor noise does not affect the segregative behavior, since $M_\text {clu}({\mathbf {q}},\tau )$ approaches zero as the experiment evolves, similarly to the behavior observed in the experiments without noise. The differences among the various values of $\xi$ are very small and can be seen through the zoom in the figure. But it is interesting to note in Fig. 7b that the control input $\sum _i{||u_i||}$ does not approach zero for larger values of $\xi$, implying that the robots will keep moving even in a segregated state due to the noisy measurements. This can be minimized by adjusting the damping term in the control input. We also perform these experiments with radial segregation and the results are similar.

Fig. 7

Mean values of metric $M_\text {clu}({\mathbf {q}},\tau )$ and the sum of control inputs of all robots $\sum _i{||u_i||}$ for 100 experiments with a varying of the sensor noise. Dashed lines represent a $95\%$ confidence interval

4.4 Local perception

We know that the assumption of a complete adjacency graph can be hard to enforce considering large swarms. Thus, besides the evaluation of the method with the addition of noise in the sensor model, it is important to relax even more the assumption that each robot is capable of measuring its distance and relative velocities to every other robot in the swarm, and study the performance of the method considering that each robot can only detect other robots within a certain neighborhood.

Basically, without detecting the other robots, specially robots within the same group/type, there will be multiple clusters with robots of the same type, since they will not attract themselves without knowing the existence of each other.

To evaluate this, we performed a series of simulations varying the perception radius r and observing the performance of the algorithm. We considered 150 robots belonging to 5 different types in a experimental area of 80x80 squared meters. The values of $d_{AA}^{(k)}$ and $d_{AB}$ were set, respectively, to 2 and 8 and we vary the perception radius r from 4 to 24 meters with 2 meter intervals. For each value of r we performed 100 repetitions with robots starting at random positions.

The graph of Fig. 8a shows the number of formed clusters. Since we have 5 different types, we would expect to have the robots segregated in 5 different groups. But observing the graph, we see that this only happens for values of r greater than 8. Another way of analyzing this is to observe the average distance between robots of the same type and of different types, as shown in Fig. 8b. We would expect these distances to converge to the desired values of $d_{AA}^{(k)}$ and $d_{AB}$ (2 and 8 respectively), but this only happens in all repetitions for values of r greater than 8.

Fig. 8

Number of formed clusters and average distances among robots when varying the perception radius r. Robots are only segregated for values of r greater than 8

Figure 9 shows snapshots of the final configurations of the robots in simulations with the sensing radius set to 4, 6, 10 and 24 m. The small circles represent the robots and the large circles their sensing areas. We can notice that in the first two snapshots ($r=4$ and $r=6$) robots are not segregated and there are multiple clusters with robots of the same types.

Fig. 9

Snapshots of the final robot configurations for simulations with different sensing radius represented by the large circles. With smaller sensing radius the algorithm is not able to completely segregate the swarm, as shown in a and b

Hence, we can see that while we may not need a strict complete adjacency graph, it is necessary at least a large perception radius so robots can be able to detect their peers and segregate. A possible solution to overcome this problem is to explore control laws that directly model local sensing and communication into their methodologies, as will be discussed in Sect. 5.

4.5 Simulations in 3D

We have executed simulations in 3D space and evaluated our metrics in this extended workspace. Figure 10 contains two images of the final configurations of a particular experiment comprising 150 robots and 5 agent types. Initial conditions were chosen exactly as in the 2D simulations. The controller was able to achieve both cluster and radial segregation according to the chosen values of the parameter $d_{ij}$, and robots have displayed the same overall behavior as of their 2D counterparts. Particularly, we have noticed that it is easier for robots to segregate in this scenario because of the additional degree of freedom, which allows agents to maneuver in new directions. Thus, in the 3D case, it is unusual to find lone robots wandering toward their cluster/shell in later iterations.

We also ran a set of 100 experiments in 3D space and computed the mean and confidence interval under both of our metrics. The results are very similar to those already presented in Fig. 3, i.e., both statistics converge to zero as the iterations increase. The plots of such results are purposefully omitted in this paper because they do not provide any more insights either on the capabilities or on the flaws of our control equations.

Fig. 10

Examples of the final segregation state in simulated 3D experiments

4.6 Real robots

To evaluate the feasibility of our controller in a real environment, we performed experiments using nine e-puck robots (Mondada et al. 2009). These experiments are interesting to validate the performance of our approach in the presence of external noise such as sensing and actuation errors.

Each e-puck is a small-sized, differential wheeled platform equipped with a camera, a ring of 8 IR sensors, and a bluetooth interface that allows local communication among robots as well as receiving control input from a remote computer (see Fig. 11a). An overhead camera system and a set of fiduciary markers were used for estimating the position and orientation of each robot, providing global localization. At the software level, we employed the ROS framework (Quigley et al. 2009) for tracking the pose of all robots and sending their respective velocity inputs.

Fig. 11

a E-puck robot used during experiments. The depicted marker is used for localization. b The differential drive model used to control the robots

As mentioned, the e-puck is a differential drive platform and thus is subject to a non-holonomic constraint. However, our controller, as specified in (2), is suitable only for fully actuated robots. To address this issue, we follow the same strategy presented by Pimenta et al. (2013). Let $(x_i, y_i, \theta _i)$ be the pose of an e-puck robot, first, we compute the integral of (2), with respect to time, so as to find a corresponding velocity vector

$$\begin{aligned} \begin{bmatrix} {\dot{x}}_i \\ {\dot{y}}_i \\ \end{bmatrix} = \int u_i dt, \end{aligned}$$

(19)

in which ${\dot{x}}_i$ and ${\dot{y}}_i$ are the desired velocity coordinates with respect to a global frame. Second, we use this vector as an input in a static feedback linearization scheme (Desai et al. 1998), which gives us both linear $(v_i)$ and angular $(\omega _i)$ speeds as proper inputs for the differential drive model of the e-puck robot.

$$\begin{aligned} \begin{bmatrix} v_i \\ \omega _i \\ \end{bmatrix}= \begin{bmatrix} \cos (\theta _i) & \sin (\theta _i) \\ \frac{-\sin (\theta _i)}{\delta } & \frac{\cos (\theta _i)}{\delta } \\ \end{bmatrix} \begin{bmatrix} {\dot{x}}_i \\ {\dot{y}}_i \\ \end{bmatrix} \end{aligned}$$

(20)

Equation (20) requires the specification of the parameter $\delta > 0$, which is a constant that corresponds to an offset from the reference point $(x_i, y_i)$ (see Fig. 11b).

In our experiments, we employed nine robots divided in three balanced groups, which represent three distinct types of robots. For cluster segregation, we set the parameters $\alpha =0.5$, $d_{AB} = 0.5$, and $\forall k : d^{(k)}_{AA} = 0.2$. For radial segregation, these constants were set to $\alpha =1.2$, $d_{AB}= 0.35$, and $d_{AA}^{(k)}$ was increased in steps of 0.25, starting at $d_{AA}^{(1)} = 0.25$.

The trajectories of all robots in both experiments, from the initial to the stable configuration, are presented in Fig. 12. These trajectories are depicted as dashed lines that connect the starting and ending positions, which are represented by a circle and a square, respectively. We also provide visual aid by providing simple overlaid shapes that indicate the final configuration of the clusters in Fig. 12a and the radial formation in Fig. 12b. Moreover, we evaluated both of our metrics while running our real implementation, and the outcomes are shown in Fig. 13. Based on these results, it is clear that the system was able to reach segregation in these two instances.

Fig. 12

The complete trajectories performed by nine e-puck robots in both segregation experiments considering three agent types

Fig. 13

The metric values for the e-puck experiments. a $M_\text {clu}({\mathbf {q}}, \tau )$ (Eq. 15) and b $M_\text {rad}({\mathbf {q}}, \tau )$ (Eq. 17)

Fig. 14

Snapshots along the execution of the experiments considering nine e-puck robots and three different agent types

Snapshots of the experiments can be seen in Fig. 14. The initial and final configuration of the system are displayed in the leftmost and rightmost images, respectively. As all e-puck robots are visually similar in these pictures, we distinguish their different types (i.e., the partition $\tau$) by overlaying simple shapes that indicate which robots belong to a same group.

4.7 Aggregation and mixed behaviors

Another interesting aspect of our control equations is that robots are able to display other behaviors besides cluster and radial segregation. For instance, we can aggregate the whole swarm if the constraints required to achieve cluster segregation (see Table 1) are written in a different form, i.e.,

$$\begin{aligned} d_{AB} < d_{AA}^{(1)} = d_{AA}^{(2)} = \dots = d_{AA}^{(m)}. \end{aligned}$$

(21)

In this manner, as every $d_{AA}^{(k)}$ is larger than $d_{AB}$, forces between robots of different types will be stronger than forces between same-type agents, which is the exact opposite of the differential potential concept. Interestingly enough, this leads robots to aggregate together instead of segregating. We display in Fig. 15a an example of a stable state where robots are aggregated. Note that for any particular robot, most of its nearest neighbors belong to a different type than its own.

We also can employ cluster and radial segregation together in the same system by defining other constraints on the parameters $d_{AA}^{(k)}$ and $d_{AB}$. For example, consider a system composed of four types of robots and let the constraints be

$$\begin{aligned} d_{AA}^{(1)} = d_{AA}^{(2)}< d_{AB} \;\text { and }\; d_{AB}< d_{AA}^{(3)} < d_{AA}^{(4)}. \end{aligned}$$

(22)

The first part of (22) forces robots of type 1 and 2 to segregate in clusters, while the second part makes robots of type 3 and 4 segregate radially, as shown in Fig. 15b (robots of type 4 form the outermost ring because $d_{AA}^{(4)} > d_{AA}^{(3)}$).

Fig. 15

Other examples of behaviors displayed by our controller when different constraints other than those in Table 1 are used

5 Conclusion

In this paper, we proposed a controller that is able to display distinct segregative behaviors when applied to a system comprising multiple heterogeneous mobile robots. This was accomplished by generalizing our previous work (Santos et al. 2014) based on the differential potential concept, an abstraction of the mechanisms by which biological systems achieve segregation. In our method, robots experience different magnitudes of potential when interacting with other agents. More specifically, similar robots adjust their interaction forces according to their particular type, whereas dissimilar robots have a fixed parameter that rules their interactions. We also presented novel metrics for measuring segregation, an improved discussion and analysis of the proposed method, including some of its limitations, and new simulations as well as experiments with real robots

We mathematically showed the stability and convergence properties of the proposed method. In our proofs we demonstrated that the swarm system converges asymptotically to an invariant set which is associated with the minimum of the collective potential. A current limitation of our investigation is in the fact that we cannot always say that this minimum is obtained only when the system is segregated. Results showed that our controller is effective in achieving segregation into clusters and in a radial sense. In all the experiments with balanced groups and tuning parameters defined as proposed in this paper, it was possible to verify cluster and radial segregation as desired. We also suggested that our approach is able to mix these distinct behaviors as well as display the opposite behavior of segregation, that is, aggregation, by just tuning constants $d_{AA}$ and $d_{AB}$ in our control equations. Therefore, investigating how the continuous change in those parameters and the variation of the difference among the groups in terms of number of robots impact the invariant set and consequently the geometric patterns described by the system when the collective potential reaches its minimum is an interesting topic for future investigation. This future investigation will then allow us to say what other segregative and non-segregative behaviors can be exhibited with this method. It is also important to mention that the absence of inter-robot collisions is mathematically guaranteed in our approach.

In spite of the positive results, our controller can still be improved. For instance, we assumed that robots are capable of measuring their relative displacements and velocities to all the other robots, as we require the adjacency graph of the system to be complete. We understand that this assumption may be difficult to enforce in general swarm applications, so we performed some experiments relaxing this assumption. These experiments showed that robots of the same type may form multiple clusters if they are unaware of the other groups, which may happen in scenarios with local sensing. To cope with this problem, we think it would be interesting to explore control laws that directly model local sensing and communication into their methodologies. This type of strategy was considered, for example, in Ferreira Filho and Pimenta (2019b) by applying consensus-based distributed controllers and some local information exchange-based heuristics to solve radial segregation. Nonetheless, in this case it is still necessary to guarantee connectivity of the robotic network.

The requirement of balanced type partitions may also hinder the applicability of our method in general scenarios. As discussed in Sect. 4, the method may not work in scenarios with unbalanced groups due to the fact that the minimum of the potential might be reached without having reached segregation. A possible solution that we want to explore in future work is the use of weighted potential functions to counterbalance the asymmetry of the forces in the system.

Besides these two limitations, there are still some points that should be addressed for the application of this methodology in more general scenarios. While our proof of concept experiments showed the feasibility of our method using real robots, we relied on an overhead camera to estimate the distance among the robots. To perform this estimation locally, robots should have some kind of range sensor, such as an infrared, and maybe a camera to identify the robot types. The e-puck has these sensors, but their resolution and processing capacity are not sufficient for this task². We believe that with the advances in sensor and computing technologies, even simple robots will be able to do this kind of processing inexpensively in the near future.

Moreover, our methodology does not consider the presence of obstacles. Obstacle avoidance would require other repulsive forces that in conjunction with the segregative potentials could lead to local minima scenarios, for example, when the segregative forces are annulled by the repulsive forces from the obstacles in a non-segregated state. To cope with obstacles, we believe that it would be necessary to augment the controllers with some kind of high level planner or coordination mechanisms, similarly to the approach proposed in Marcolino and Chaimowicz (2005).

By exploring these issues, we think that a further extension of our methodology could be applicable to more general settings related to the segregation problem in swarm robotics.