# Hierarchical Control of Smart Particle Swarms

Vivek Shankar Varadharajan, Sepand Dyanatkar, and Giovanni Beltrame
Varadharajan V. S. and Beltrame G. are with Polytechnique Montréal, 2500 Chem.
de Polytechnique, Montréal, QC H3T 1J4. (email: vivek-
<EMAIL_ADDRESS>giovanni.beltrame@polymtl.ca)Dyanatkar S. is
with The University of British Columbia, 2329 West Mall, Vancouver, BC V6T
1Z4. (email<EMAIL_ADDRESS>
###### Abstract

We present a method for the control of robot swarms which allows the shaping
and the translation of patterns of simple robots (“smart particles”), using
two types of devices. These two types represent a hierarchy: a larger group of
simple, oblivious robots (which we call _the workers_) that is governed by
simple local attraction forces, and a smaller group (the _guides_) with
sufficient mission knowledge to create and maintain a desired pattern by
operating on the local forces of the former. This framework exploits the
knowledge of the guides, which coordinate to shape the workers like smart
particles by changing their interaction parameters. We study the approach with
a large scale simulation experiment in a physics based simulator with up to
1000 robots forming three different patterns. Our experiments reveal that the
approach scales well with increasing robot numbers, and presents little
pattern distortion for a set of target moving shapes. We evaluate the approach
on a physical swarm of robots that use visual inertial odometry to compute
their relative positions and obtain results that are comparable with
simulation. This work lays foundation for designing and coordinating
configurable smart particles, with applications in smart materials and
nanomedicine.

###### Index Terms:

Swarms, Multi-Robot Systems, Hierarchical Swarm Control, Distributed Robot
Systems, Decentralized behavior, Smart Particles.

##  I Introduction

Decentralized behaviors have been increasingly studied in the past two decades
mainly because they have many desirable properties like scalability,
robustness, and flexibility. The study of decentralized behaviors on robots
took initial inspiration from natural swarms of ants and bees [1], which
exhibit complex collective behaviors through simple local interactions. Even
after decades of research, the deployment of collective behavior on robots
that cooperatively perform a real-world task remains challenging. Equipping
robots with swarm intelligence is one of the most promising applications of
artificial intelligence, but it is yet to find its way to solving real-world
problems, and it is considered one of the grand challenges of the decade in
robotics [2]. Robot swarms are generally composed of a team of robots that are
simple and inexpensive, but when working together, they are capable of
performing tasks reserved to more complex and expensive robots. Some
futuristic views on swarm robotics [3] suggest that engineering methods for
heterogeneous, hierarchical self-organization is required in robot swarms to
transition from laboratories to real-world applications. This work is a step
in this direction that leverages self-organization through local interactions
in a two-level robot hierarchy. Hierarchies in robot swarms can be of two
types: information hierarchies and intelligence hierarchies. The former
(information hierarchies) considers identical robots with varying level of
mission-related information: the robots with more information can make better
mission decisions and are placed at the top of the hierarchy. For example,
consider the task of exploring an unknown environment: some robots might have
a better map and are therefore able to make better decisions about where to go
next, placing them at the top of the information hierarchy. Intelligence
hierarchies consider heterogeneous swarms with some robots having higher
sensor and computational capabilities (while others are more limited) that
lead to enhanced intelligence and decision-making, thus placing them at top of
the hierarchy.

Figure 1: The states followed by the guide robots in our system.

Most of the swarm intelligence techniques applied to robot swarms [4, 5, 1]
focus on a single level of hierarchy and employ a uniform behavior across the
swarm. Heterogeneity is generally addressed by assigning task-specific roles
to robots [6, 7] or allowing roles to emerge [8]. Hierarchical approaches to
swarm intelligence have been investigated in the context of particle swarm
optimization [9, 10], but they have received very little attention in
robotics. The shepherding problem [11, 12, 13] considers a 2-level hierarchy
with two types of robots: _sheep_ that need to be herded by robot _dogs_. The
problem considered in this work is comparable with the shepherding problem: we
use smarter _guide_ robots to shape and transport a group of _workers_. The
main difference with shepherding is that our _guides_ (or dogs in the
shepherding analogy) shape and maintain the pattern made by _workers_ (a.k.a.
the sheep) during motion by operating on the rules that govern the workers
swarm.

To shape the swarm, the guides take up certain locations around the workers
and, using a task allocation mechanism [14], they shape the swarm using
virtual potentials. Once a desired shape is attained, the workers are “locked”
in position and translated by the guides using virtual forces. The guides
coordinate with each other by tracking the overall movement of the swarm, the
orientation its members towards the target, as well as the position of the
center of mass of the formation. The guides interact with the workers by
operating on four control parameters: density ($\rho$), field of view ($FoV$),
mode ($M$) and reactive field of view ($RFov$). These parameters are used to
influence the formation and the bonding between the workers. This approach
resembles smart particle design [15] and finds potential applications in smart
materials and targeted drug delivery. Just like smart particles can be
designed to be dynamically programmed to change their attraction forces, a few
intelligent robot guides can order the workers to a desired shape and move
them to a target location by operating on the attractive and repulsive forces
between the workers.

We evaluate our approach of hierarchical swarm control using a physics-based
simulator (ARGoS3 [16]) with varying number of robots (50, 100, 300 and 1000),
drawing three different patterns. We empirically study the convergence time
for shaping and transport of the swarm, as well as the distortion incurred by
the swarm after reaching its target location. We also evaluate our approach
with a small swarm of 6 robots using visual inertial odometry to estimate the
relative position between the robots, without any external positioning system,
obtaining a performance comparable to the simulations.

##  II Related work

Patterns in robot swarms are generally achieved by designing collective
behaviors that emerge as a result of local interactions with neighbors [4].
Some examples of pattern formation are morphogenesis [4], self-assembly [5]
and progressive shape formation [17]. These methods create stable structures
using only local interactions.

Flocking. In some applications, robots are required to move while maintaining
a pattern or formation. This behavior is usually referred to as flocking [18,
19], taking inspiration from the behavior of birds. Flocking is extensively
studied in literature, with hundreds of different approaches [20] inspired
from the basic microscopic model [21] of attraction, repulsion and cohesion.
Methods for flocking vary based on the way the neighbors are selected, for
example, using the $L^{2}$ [22] or Voronoi distance [23]. Flocking has been
applied to aerial [18, 24] and ground robots [22]. However, flocking does not
allow for the creation of arbitrary structures: generally flocks are limited
to maintaining a common heading and inter-robot distance either in unbounded
[24] or bounded spaces [18].

Leader-follower methods. Some approaches use a leader-follower strategy for
flocking, where a few robots act as leaders [25] that share metrics and
positions with the other robots, which in turn use this information to
coordinate their motion. The leader-follower problem is widely studied [26,
27, 28, 29], and we can only take a small representative set from literature
for discussion. Meng et. al. [28] proposed an optimal control technique using
algebraic graph theory for coordinating a group of robots to follow the motion
of the leaders, with focus on controllability and control optimality. The
approach in [28] and [30] uses Hilbert space projection and dynamic
programming. These algorithms are centralized for the leaders and require
access to a global positioning system. In a decentralized setting, with robots
that have limited visibility and communication constraints, Panagou et al.
[29] employ a tractor-trail method to have the followers form a single file
and follow the leader in a known environment with obstacles. Some methods
consider the robots in a leader-follower setting to be virtual springs [31]
that needs to maintain formation. Ji et. al. [32] proposed a two-phase method
that first moves leaders to a fixed goal and then moves the followers within
the convex-hull generated by the leaders position. Most of these methods in
leader-followers are computation intensive, with requirements that increases
with the number of robots, with rare exceptions [31] that rely on local
information and do not suffer from scalability issues.

Shepherding. The leader-follower approach has its natural extension to the
shepherding problem: simple robots (the ‘sheep’) that are herded by one [33]
or a group of robots (the ‘shepherds’) [34]. One common approach to
shepherding is to approximate a cluster of sheep as a circle or ellipse that
needs to be maintained over motion [34, 12, 13] by placing the shepherds
behind or around the sheep herd. The approach in [13] used simple computation
free robots with a single line-of-sight sensor to evolve a shepherding
controller using evolutionary optimization. This approach requires a large
number of shepherds to encircle the sheep to succeed. Strömbom et. al [35]
proposed a two-phase approach that first gathers a group of unwilling agents
into a cluster and moves them to a target location using a simple
attraction/repulsion model. Hu et. al. [11] proposed occlusion-based herding
that places the shepherds in the occluded region to the goal behind the sheep:
this approach decomposes the control input into various contributions of
attraction and repulsion between sheep, and repulsion from shepherds. There is
a wide body of other comparable approaches that use Hilbert space filling and
path planning [36], repulsive force [37] and connected-component labeling
[12]. Many approaches require a reliable communication between the shepherd
and sheep, besides a few that rely on local measurements [13]. Similarly to
flocking, most shepherding approaches do not focus on maintaining a pattern
during the translation to a goal.

We consider a variation to the shepherding problem, with two main differences:
first, we maintain the pattern during movement to the goal. Maintaining the
pattern is important for applications like nanomedicine or smart materials, as
the relative position of the particles might have important functional
implications. Second, the shepherds (the guides in our parlance) have the
ability to change the interaction forces between the sheep (i.e., the
workers), which truly establishes a hierarchical control system on the swarm.

##  III Model and System

Consider a group of $n$ robots with each robot $i$ having the following
dynamics

$\dot{x}_{i}=v_{i},v_{i}=u_{i},i\in R,R=\\{r_{1},...,r_{n}\\}$ (1)

with $x_{i}$, $v_{i}$ and $u_{i}$ $\in\mathbb{R}^{2}$ being the position,
velocity and control input respectively. The relative position ($x_{ij}$) and
velocity ($v_{ij}$) of two robots $i$ and $j$ are $x_{ij}=x_{i}-x_{j}$ and
$v_{ij}=v_{i}-v_{j}$. We define the set of relative inter-agent distances
$D=\\{d_{ij}=\mathinner{\\!\left\lVert
x_{i}-x_{j}\right\rVert}\in\mathbb{R}|i,j=1,...,N,i\neq j\\}$ and the
communication graph formed between the robots as
$\mathcal{G}=(R,E,\textit{W})$ with $R=\\{r_{1},...,r_{n}\\}$ the set of
vertices, $E=\\{e_{ij}|i,j\in N,i\neq j\\}$ the edge set and $W=\\{w_{ij}\in
R_{+}|e_{ij}\in E\\}$ are weights assigned to the edges. Each robot $i\in R$
forms a neighbors set $N_{i}=\\{j\in R|\mathinner{\\!\left\lVert
x_{ij}\right\rVert}\leq d_{com}\\}$ as dictated by $E$, with $d_{com}$
representing the communication range of the robots.

Our swarm has two types of robots: guides and workers, further dividing the
graph vertex set $R$ into $R^{G}$ (vertices corresponding to guides) and
$R^{W}$ (vertices corresponding to workers), with $R^{G}\cap R^{W}=\emptyset$.
The guide robots are assumed to be equipped with sophisticated sensors capable
of performing localization, path planning, traversability estimation, etc. The
worker robots are simple and oblivious, being capable of only communicating
and measuring the relative position $x_{ij}$ of their neighbors. The enhanced
capabilities of the guide robots place them in a leadership role: they
perceive mission goals and provide directives to the worker robots both
indirectly (by moving to a different position) and directly (by ordering a
change to the attractive/repulsive forces among the workers). Just like a
smart material or social insects, the workers perform a task without them
realizing the significance of their individual contribution.

The neighbor set $N_{i}$ of robot $i$ can be divided into guide neighbors
$N^{G}_{i}=N_{i}\cup R^{G}$ and worker neighbors $N^{W}_{i}=N_{i}\cup R^{W}$.
The center of mass of the worker robots is defined as $x^{c}=\frac{1}{\lvert
R^{W}\rvert}\sum_{i\in R^{W}}x_{i}$, and assumes a circular approximation of
the worker cluster. The robots are only capable of measuring relative
positions $x_{ij}$ and hence the center of mass perceived by robot $i$ is
$x^{c}_{i}=\frac{1}{\lvert N^{W}_{i}\rvert}\sum_{i\in N^{W}_{i}}x_{ij}$.

Fig. 1 illustrates the different states of the guide robots. To shape a
cluster of workers, the guides are given $k$ shaping targets, each specified
by an angle ($\theta^{s}$) and a distance ($d^{s}$) with respect to the worker
center of mass ($x^{c}$). Consider the shape angle set
$\Theta^{s}=\\{\theta^{s}_{1},...,\theta^{s}_{k}\\}$ and shape distance set
$D^{s}=\\{d_{1}^{s},...,d^{s}_{k}\\}$. A guide robot $i\in R^{G}$ is assigned
a shaping target $\theta_{i}\in\Theta^{s}$ and $d_{i}^{s}\in D^{s}$ through a
decentralized task allocation mechanism.

To reach its target angle
$\angle{(x_{i}-x^{c})}-\theta^{s}_{i}<\theta_{\delta}$, with $\theta_{\delta}$
being a small tolerance, a guide $i$ follows the edge of the worker cluster.
Upon reaching $\theta_{i}^{s}$, the robots translate to ensure a distance
$d_{i}^{s}$ from the center of mass of the workers cluster, withing a small
tolerance $d_{\delta}$: $d^{s}_{i}-\mathinner{\\!\left\lVert
x^{c}_{i}\right\rVert}<d_{\delta}$. Once a shaping target is reached (both
angle and distance), the guides wait for all the other guides to reach their
respective shape targets using a mechanism called a barrier [38].

Once at their shaping targets, the guides translate to a target distance
$d^{sp}$ from the center of mass of the worker cluster, thus forcing the
workers into the desired shape. We use again a barrier to ensure all the guide
robots have reached their destination, upon which the guides start moving to a
sequence of targets $\mathbb{T}=\\{x_{1},...,x_{n}\\},\forall
x_{i}\in\mathbb{R}^{2}$ maintaining the worker formation obtained through
shaping. A guide interacts with the workers through simple potentials by
changing its position which in turn causes a repulsive action on the workers.
The guides can also manipulate the parameters of the potential fields that
control the workers. These parameters can be propagated across the swarm and
change the workers reactions to the actions of guides. The available
parameters are density ($\rho$), field of view ($FoV$), mode ($M$) and
reactive field of view ($RFov$). Fig. 2 shows the effect of these parameters.

###### Definition 1

Given a graph $\mathcal{G}(t)=(R(t),E(t),\textit{W}(t))$ formed by a group of
robots at time $t$, the robots are said to be in a formation if and only if
the link between $\\{v_{i},v_{j}\\}\in E(t)$ is preserved $\forall
t\in(t_{0},\infty)$. $\textit{W}=d_{ij},w\mathrel{\mathop{\mathchar
58\relax}}E\to\mathbb{R}_{+}$ being the weights of the graph defining the
formation parameters.

The positions of the robots are continuously evolving over time because of
motion. If motion is edge-consistent (i.e. if the distance
$\mathinner{\\!\left\lVert x_{ij}\right\rVert}$ is constant $\forall e_{ij}\in
E$ of a graph $\mathcal{G}$ [39]), we say that the formation is maintained. We
define a graph to be an even-edged graph of distance $d$ if
$\forall\mathinner{\\!\left\lVert x_{ij}\right\rVert}\approx d,\forall
e_{ij}\in E$. The worker robots maintain a even-edged graph with distance
$d_{\rho}$ defined by the current density parameter $\rho$ both in Loose and
Shape mode, and an edge-consistent graph in Rigid mode.

###### Definition 2

The field of view neighbor set is $N^{FoV}_{i}=\\{\forall
j\in\textit{R}^{W}|d_{ij}\leq d_{FoV}\\}$, with $d_{FoV}$ being the field of
view distance and $R^{W}$ being workers set. Similarly, a reactive field of
view neighbor set $N^{RFoV}_{i}=\\{\forall j\in\textit{R}^{G}|d_{ij}\leq
d_{RFoV}\\}$, with $d_{RFoV}$ being the reactive field of view distance and
$R^{G}$ being the guides set.

The field of view distance $d_{FoV}$ is used to control the field of view
neighbor set $N^{FoV}$ and influence the strength of a robots position in a
formation. Reaction distance to a guide robot $d_{RFoV}$ is defined by $RFoV$,
influence the distance at which the workers will start responding to guide
robots. The mode of the worker robots $M\in\\{Loose,Shape,Rigid\\}$ defines
the graph behavior of the worker robots, i.e., maintaining even-edged graph or
edge-consistent graph.

### Hierarchical Organization

We employ an intelligence hierarchy in this study (i.e., robots have different
capability levels). The hierarchical organization of a swarm of robots has
several benefits; it allows the application of simple decentralized methods
based on emergence and task performance that are incapable of simpler robots.
In this study, the guides are the only robots that perceive the mission goals
and can lead the workers. The workers are _smart particles_ and can only sense
and act locally, therefore missing the global view of their mission. Imagine a
nano-medicine application: we have tiny robots with minimal intelligence that
can be guided by larger, more capable robots and _injected_ into locations
inaccessible by the larger robots due to their size. The hierarchy allows for
a smaller number of _expensive_ robots with a global view of the mission,
while most of the workers are _cheaper_ robots that can only sense and act
locally, with limited computation. Even assuming that cost is the only metric
(i.e., smarter robots can still do the task), in one of our examples (fig. 1),
we show a swarm of 1000 _simple_ robots guided by 32 _smarter_ robots.
Optimistically assuming that a cost of $1$ for a simple robot and that a
smarter robot costs $5$, it means the cost of a hierarchical swarm is
$1000+32*5=1160$ compared with an entire smarter robot swarm $1000*5=5000$, or
a $76.8\%$ reduction in cost.

Furthermore, biological systems exhibit various levels of hierarchy. The human
muscular movement starts from the brain and applies a stimulus to muscles
unaware of the global task. The principles behind the hierarchical
organization employed in this work can be related to human biology. A large
swarm of oblivious robots capable of only performing local sensing is guided
through local interactions by the small swarm of coordinating intelligent
robots. This hierarchical organization allows the system to display all three
well-known properties seen in natural swarms: scalability, robustness to
failure, and adaptivity. One of the standard methods in achieving scalability
is to employ a behavior that operates on local interactions; this can be
directly applied in a hierarchically organized swarm.

##  IV Methodology

###  IV-A Worker Swarm

The control parameters that dictate the behavior of the worker robots are
density ($\rho$), field of view ($FoV$), mode ($M$) and reactive field of view
($RFov$). $\rho$ defines the desired inter-robot distance $d_{\rho}$ to
preserve with the neighbors in field of view ($N^{FoV}_{i}$). $d_{RFoV}$ is
the distance at which the robots start reacting to guide robots. The four
control parameters of the worker robots are set by the guide robots using
virtual stigmergy [40], a conflict-free replicated data structure that acts as
a global distributed shared memory for the swarm. Virtual stigmergy uses
gossip-based communication that propagates through the network updating the
local copies of information on the robots, and was shown to converge if a
communication path exists (connected graph).

Figure 2: Illustration of the control parameters used by the worker swarm to
preserve a shape, the control parameters are controlled by the guide robots to
change the properties of the worker robots.

A common method to design a control law for the sheep in shepherding [11] or
flocking [41] is to use artificial potential functions that produce attraction
and repulsion between the robots. Unlike the shepherding problem, we need to
maintain the desired formation during its translation. Potential functions
used in modeling the bonding structure of atomic molecules [42] are some
interesting candidates for enforcing a bond between two robots. We considered
various potentials like Morse potential (used in modeling diatomic molecules),
Lennard-Jones potential (used in modeling rare gases), Buckingham potential
(used in modeling ceramic materials) and the harmonic approximation (used in
modeling crystalline lattice structures) [42]. Morse, Lennard-Jones, and
Buckingham potentials produce uneven attraction and repulsion forces when
applied on robots, for instance produce stronger repulsion and weaker
attraction becomes a problem when these parameters are dynamically configured
by the guide robots. In this work, we choose the harmonic approximation to
define the bonding force between the worker robots. A standardized Harmonic
potential is of the following form $\phi(x)=\frac{1}{2}k(x)^{2}$, we
empirically shape the potential to obtain a desired force response for a given
distance and obtain the potential function:

$\phi(d)=a_{0}+\frac{kd^{3}}{2\lvert d\rvert}$ (2)

with $a_{0}$ and $k$ being design constants. The feedback control contribution
for maintaining the formation between other worker robots within the field of
view ${FoV}$ is $w_{i}$ and the control contribution for producing a repulsive
reaction from the guide robots within the reactive field of view $RFoV$ is
$g_{i}$

$\displaystyle u_{i}$ $\displaystyle=\alpha w_{i}+\beta g_{i}$ (3)
$\displaystyle w_{i}$ $\displaystyle=\frac{1}{\lvert
N^{FoV}_{i}\rvert}\sum_{j\in
N^{FoV}_{i}}\phi(d_{ij}-d_{\rho})\frac{x_{ij}}{\mathinner{\\!\left\lVert
x_{ij}\right\rVert}}$ (4) $\displaystyle g_{i}$ $\displaystyle=\frac{1}{\lvert
N^{RFoV}_{i}\rvert}\sum_{j\in
N^{RFoV}_{i}}\phi^{+}(d_{ij}-d_{\rho})\frac{x_{ij}}{\mathinner{\\!\left\lVert
x_{ij}\right\rVert}}$ (5)

The potential function $\phi(d_{ij}-d_{\rho})$ provides the magnitude and
$\frac{x_{ij}}{\mathinner{\\!\left\lVert x_{ij}\right\rVert}}$ determines the
direction of each $w_{ij}$ and $g_{ij}$ contribution. $\alpha$ and $\beta$ are
design parameters that define the relative importance of maintaining formation
with respect to reacting to the guides in proximity. The function
$\phi^{+}(d)\to\mathbb{R}^{+}$ produces only repulsion mapping to positive
real values if and only if the input domain is $d\in{[}0,\infty{]}$.
Similarly, the function $\phi(d)\to\mathbb{R}$ produces real values when
$d\in{[}-\infty,\infty{]}$. Both functions $\phi^{+}(.)$ and $\phi(.)$ are
Lipschitz continuous and belong to class function $\phi^{+}(.)\in S^{+}$ and
$\phi(.)\in S$. The class functions are defined as
$S^{+}=\\{f\mathrel{\mathop{\mathchar
58\relax}}{[}0,\infty{)}\to\mathbb{R}|f(d)=0,\forall d\geq 0,f(d)>0,\forall
d<0\\}$ and $S=\\{f\mathrel{\mathop{\mathchar
58\relax}}(-\infty,\infty)\to\mathbb{R}|f(d)<0,\forall d>0,f(d)>0,\forall
d<0\\}$. From the class definition and equ. 3, an attraction force exists
between all the robots with distance $d_{ij}>d_{\rho},\forall i,j\in E$ and a
repulsive force acts on the robots with distance $d_{ij}<d_{\rho}$. The
equilibrium point with $u_{i}=0$ is when all the neighboring robots of robot
$i$ are at distance $d_{\rho}$ and with no guide robots within $d_{RFoV}$.

A worker swarm takes one of the three modes: 1. Loose, 2. Shape and 3. Rigid,
each resulting in distinct swarm behavior. In the loose mode, the worker
robots maintain a formation with distance $d_{\rho}$, allowing them to create
new edges when a new robot appears in its neighbor set. The worker robots
behave like a fluid in loose mode. The mode transition from any other mode to
shape formation creates two new sets: a distance lookup set
$D_{i}^{lo}=\\{d_{ij}|d_{ij}<d_{FoV};\forall j\in N_{i}^{FoV}(t)\\}$, lookup
set $N_{i}^{lo}=\\{j|\forall j\in N_{i}^{FoV}(t)\\}$, with $t$ being the time
at mode transition. The worker robots use $D_{i}^{lo}$ in shape mode to
maintain a formation only with the respective robots in $N_{i}^{lo}$ and
remove robots from sets $N_{i}^{lo}$ and $D_{i}^{lo}$ if the distance
$d_{ij}>d_{FoV}$, allows link breakages with robots outside $d_{FoV}$. The
link breakage in a formation allows the worker robot cluster to create a
desired shape, when a guide robot forces itself into the cluster. As in shape
mode, the mode transition to rigid creates the sets $D_{i}^{lo}$ and
$N_{i}^{lo}$, unlike shape mode, the rigid mode does not allow link breakage.
Assuming $d_{com}>d_{\rho}$, worker robots maintain the formation only with
robots in set $N_{i}^{lo}$ and continue to maintain formation with distance
$d_{ij}\in D_{i}^{lo}$ instead of $d_{\rho}$ until the robot is in the
communication range $d_{ij}<d_{com},j\in N_{i}^{lo}$. Rigid mode enforces a
rigid graph to the graph $\mathcal{G}$ formed by the robot group with $E$
being edge-consistent, as defined in [39].

Figure 3: Finite state machine describing the high level guide behavior for
all $i\in R^{G}$. The dotted boxes group the high-level states, inside the box
are the internal sub-states. The diagram shows the standard single shape
objective edge following and shaping procedure in solid black connections.
Additional connections for a multi-shape execution is shown with dotted
connections.

###  IV-B Guide Swarm

The guide swarm is the brains of the whole robot group, controlling the worker
swarm, which is analogous to the muscles that do the work. The guide swarm has
a series of internal information and states, in addition to the workers’
configuration control parameters. Guides are initialized with the overall set
of shaping parameters ($D^{s}$, $\Theta^{s}$ and $d^{sp}$) and movement
targets ($\mathbb{T}$), and are controlled internally by their own state
machine. The set of movement targets $\mathbb{T}$ can be easily obtained using
any standard robotic path planner. Similarly, the shaping parameters could be
obtained by a planner that outputs these parameters for a given shape. The
system is designed in a way that allows for dynamic changes to the shaping
parameters for a multi-shape movement. In this study, we only consider a fixed
parameter set. The parameters for the workers are set through virtual
stigmergy, which also defines the properties of the shape and hence it is
considered to be part of the shape dependent parameters.

Guides have the following high-level states: 1. Task Allocation, 2. Shaping
setup, 3. Shaping, and 4. Movement. The high level state machine of the guides
is depicted in fig. 3. Our depiction continues to assume a single shape set of
shaping parameters, however we show the ability to do multiple shapes in a
single execution with dotted connections. All the state transitions between
the 4 high-level states occur only with an agreement with all the guides. We
use a barrier [38], a decentralized method which holds the state of the robots
in a standby state until all the robots satisfy the conditions for the state
transition. We implemented the barrier using virtual stigmergy, which provides
a tuple space storage.

Task Allocation The multi-robot task allocation problem [43] is a
combinatorial optimization problem requiring heuristics to obtain an
approximate solution in polynomial time. The specific task allocation problem
that we have in our setup is a Single Assignment (SA) problem and can be
solved using auction or consensus. The SA problem used by the guide robots to
assign $t$ to $|R^{G}|$ robots has the form:

$\displaystyle min\sum_{i\in R^{G}}\sum_{j\in\Theta^{s}}c_{ij}(x_{i})a_{ij}$
(6) $\displaystyle st.\sum_{j\in\Theta^{s}}\leq 1,\forall i\in R^{G}\text{ and
}\sum_{i\in R^{G}}\leq 1,\forall j\in\Theta^{s}$

with $c_{ij}=\mathinner{\\!\left\lVert.\right\rVert}$ being the cost function
of assigning task $j$ to robot $i$ and $a_{ij}\in\\{0,1\\}$ being the binary
assignment variable. We used the distance to the task estimated using the
worker center of mass as the cost. We solve the single assignment problem of
equation 6 using the decentralized consensus procedure described in [14].

Shaping setup and Shaping The task of shaping involves the guides separating
from the guide cluster, the robots apply a similar potential in equ. 2 to
separate and reach a distance $d^{ss}$. Guides edge-follow the worker cluster
until the shape angle assigned to them is reached. Algorithm 1 shows the
pseudocode of the edge-following procedure used by the guide robots reach the
shape target angle $\theta^{s}_{i}$. The algorithm is partly inspired from [5]
but differentiates itself by maintaining a recently-followed neighbor list to
escape concave edge areas (otherwise causing with approach in [5]).

Algorithm 1 Edge following algorithm. Current distance (d), current neighbor
($N_{c}$), old neighbor ($N_{o}$), and current edge (E).

1:d=0, $N_{c}$=0, $N_{o}$=0

2:Last_seen = circular_buffer(10)

3:step loop()

4:Yield = false

5:for each j $\in N_{i}$ do

6: if $\angle x_{j}<\frac{\pi}{4}$ and $j\in R^{G}_{i}$ then

7: Yield = true

8: break

9: end if

10: if not in Last_seen and $d_{j}$ $<$ d and $j\in R^{W}_{i}$ then

11: $N_{c}$ = j

12: E = j

13: if $N_{o}$ $\neq$ $N_{c}$ then

14: Last_seen.push_back(j)

15: end if

16: end if

17:end for

18:if not Yield then

19: move_vec$=\perp x_{N_{c}}+(d_{N_{c}}-d^{e})*x_{N_{c}}$

20: goto(move_vec)

21:else

22: goto($[0,0]^{T}$)

23:end if

24:$N_{o}$ = $N_{c}$

The problem of guide robots reaching the assigned shaping target angles
$\theta^{s}$ is solved using algorithm 1. The edge following algorithm loops
through all the neighbors and finds the closest neighbor to edge follow, if
the robot has to yield to a neighbor in front, and updates a list of old
neighbors. The old neighbors list is used to avoid following 10 previously
followed neighbors. The current move_to vector determining the control inputs
for the robot in edge following is computed in line 19. The components of the
current move_vec are the perpendicular vector to the edge following neighbor
averaged with the distance error in maintain the required edge following
distance $d^{e}$.

In shaping, the guide robots are required to perform a motion by forcing
themselves into the worker cluster. The guide robot move in unison at a
certain speed to attain the required shape. The speed of shaping for the guide
robots are defined using a velocity they will adopt during the shaping
process. we define the speed of shaping to be $v^{s}$. Certain formations
require the worker robots to stay behind one another, the shaping with a guide
robot in front is performed by closely monitoring the speed of the guide in
front.

Movement The task of translating in formation is what we define as the
formation shepherding problem. The robots have to preserve the edges $E$ of a
graph $G$ as per definition 1.

###### Problem 1

Given a group of n robots with the capability to measure relative position of
its neighbors $x_{ij}\in\mathbb{R}^{n}$, find a control strategy $f(x_{ij})\to
u_{i}\in\mathbb{R}^{n}$ that will allow them to perform edge-consistent motion
with the graph $\mathbb{G}$ defined by the robot network.

Problem 1 is solved through hierarchical organization of the robot swarm,
guide robots coordinately apply a force on the worker robots in formation to
move them to a target. The coordination between the guide robots happen by
measuring the center of mass of the worker cluster and their angle to the
movement target vector $x_{i}^{g}$. The guide swarm applies the control law
defined by the equ. 7 to solve problem 1.

$\displaystyle u_{i}$
$\displaystyle=\alpha_{g}g_{i}+\beta_{g}c_{i}+\gamma_{g}a_{i}$ (7)
$\displaystyle a_{i}$
$\displaystyle=p(\theta_{i}^{tc})\left(\perp\frac{x^{c}_{i}}{\mathinner{\\!\left\lVert
x^{c}_{i}\right\rVert}}\right)$ (8) $\displaystyle p(\theta)$
$\displaystyle=\begin{cases}-1&,\theta<\pi\textit{ and
}\theta<(\theta_{t}+\pi)\textit{ and not}(\theta<\theta_{t})\\\
1&,(\theta<\pi\textit{ and }\theta<(\theta_{t}+\pi))\textit{ or
}\theta>\theta_{t}\\\ -1&,otherwise\end{cases}$ (9)

with $\theta_{i}^{tc}=\angle(x_{i}^{c}-x_{t})$. The parameters $\alpha_{g}$,
$\beta_{g}$ and $\gamma_{g}$ are design parameters respectively that define
the importance of moving towards the target, conserving the desired center of
mass distance to the workers and maintaining the orientation between the
target and worker center of mass. The control input during the movement phase
has three contributions: 1. contribution to move the robot to the target
$g_{i}$, 2. contribution to maintain a distance from worker center of mass
$c_{i}$, and, 3. contribution to maintain the orientation with worker center
of mass and target $a_{i}$. Both $g_{i}$ and $c_{i}$ use the harmonic function
potential defined in equ. 2 as in equ. 4. Whereas the contribution to maintain
the orientation is performed using equ. 8.

Figure 4: The range of shape configurations simulation used in the
experiments, with varying swarm sizes. The snapshots are taken as the shaping
mode is complete, before the guides transition to movement mode.

Figure 5: The different trajectories undertaken by robots in each shape:
clover on the left, dumbbell in the center and circle on the right. Here we
can already see the motion of the circle is more direct than the others, with
the dumbbell showing noticeable vertical and horizontal distortion en route to
its destination. Figure 6: Time taken by the worker robots to transition from
one state to another. We can see consistently longer and more varying times in
the movement of clover and dumbbell shapes. The task allocation, shaping
setup, and shaping of clovers and dumbbells also appear to be affected by
increasing the swarm size.

###  IV-C Theoretical Analysis

To show that the robots do not collide or diverge from a given formation, we
define the energy of the system $J(x,v)=U(x)+T(v)$, which is a combination of
potential energy $U(x)=\sum_{i\in V}U_{i}(x)$ and kinetic energy
$T(v)=\sum_{i\in V}T_{i}$.

$\displaystyle U_{i}(x)$ $\displaystyle=\frac{1}{2}\sum_{j\in
N^{FoV}_{i}}\int_{d_{ij}}^{d_{\rho}}\phi(x)dx+\sum_{j\in
N^{RFoV}_{i}}\int_{d_{ij}}^{d_{RFov}}\phi^{+}(x)dx$ (10)

The potential energy of a worker robot $U_{i}=U^{W}_{i}+U^{G}_{i},i\in R^{W}$
can be divided in two components $U^{W}_{i}$ and $U^{G}_{i}$. $U^{W}_{i}$ is
the potential energy of robot $i$ due to the force caused by other worker
robots and $U^{G}_{i}$ is potential energy from the force caused by the
guides.

Consider the radius of the robot to be $r<\delta$, with $\delta$ the collision
range. Similarly, consider $d_{FoV}$ the distance at which the link between
two robots in a formation is broken. This means that a robot with only one
neighbor will be disconnected from the formation if this link is broken. Note
that links are broken during shaping to create the desired formation. At
collision the potential energy between agents is
$U^{col}_{ij}=\int_{r}^{\delta}\phi(x)dx$ and the potential energy between two
agents when breaking a link is
$U^{brk}_{ij}=\int_{d_{\rho}}^{d_{FoV}}\phi(x)dx$.

###### Lemma 1

Consider an actuated group of robots from equ. 1 using equ. 3 with potential
$\phi(d_{ij}-d_{\rho})=\phi(d_{ji}-d_{\rho})\in S,\forall i,j\in E$, the
energy of the group is $J(x,v)=U(x)+T(v)$ with potential energy at collision
$U^{col}_{ij}>0,\forall i,j\in E$. The potential energy between the two agents
$U_{ij}=0$ when $d_{ij}=d_{\rho}$. The agent will get to the equilibrium
distance $d_{\rho}$ by applying equ. 4 for all distance $d_{ij}<d_{\rho}$.

###### Proof 1

The potential function $\phi(d_{ji}-d_{\rho})$ is strictly positive when
$d_{\delta}<d_{ij}<d_{\rho}$, because $\phi\in S$. The potential energy of the
system follows $U^{col}_{ij}>U_{ij},\forall d_{ij}>d_{\delta}$ and hence the
robot is repelled to $d_{\rho}$, avoiding a collision. The potential energy of
two robots is $U_{ij}=0$, because
$\phi(d_{ij}-d_{\rho})=\phi(d_{ji}-d_{\rho}),\forall i,j\in E$.

Applying lemma 1 to the case $d_{\rho}>d_{ij}<d_{FoV}$ results in a potential
energy $U_{ij}<U^{brk}_{ij}$ when applying equ. 4. Therefore, robot $i$ and
$j$ will be attracted towards one another. Note that $U_{ij}<0,\forall
d_{ij}>d_{\rho}$.

###### Lemma 2

Consider a group of actuated robots using the control law in equ. 1 and
applying the potential in equ. 2. The potential energy $U^{G}_{i}>U^{W}_{i}$
when there is at least one guide robot $j$ with $d_{ij}<d_{RFoV}$.

###### Proof 2

Applying the potential function $\phi(d_{ij}-d_{\rho})$ with $d_{ij}=d_{\rho}$
gives $\phi=0$ according to the class function $S$ and $\phi\in S$, hence
$U^{W}_{i}$ = 0. As in the previous proof, any two given robots are driven to
the equilibrium of the potentials, i.e. $d_{ij}=d_{\rho}$, whenever
$d_{ij}>d_{\rho}$. When a guide robot $j$ is within the reaction distance
($d_{RFoV}$) of robot $i$, then the potential $\phi^{+}$ is applied to the
guide robot’s force contribution $U^{G}_{i}>0$ because $\phi^{+}$ is strictly
positive for all distance $d<0$. Therefore, with at least one worker $j$ with
$d_{ij}<d_{RFoV}$, the potential energy $U^{W}_{i}>0$ with
$U^{G}_{i}>U^{W}_{i}$.

###### Lemma 3

Consider the same group of actuated robots using the control law in equ. 1. We
saw in lemma 1 that the workers do not collide and in lemma equ. 2 that the
potential from the guides allows shaping. Additionally, the control law also
ensures that the guides do not collide with or cause collisions within the
worker swarm, regardless of mode.

###### Proof 3

The guide approaches and interacts with workers using the control law from
equ. 7. The workers repel with equ. 5 but also try to maintain a safe distance
with equ. 4. Using lemma 2, workers repel the guides at stability
$U^{G}_{i}>U^{W}_{i}$ imposes a risk of collision with $\exists j\in
R^{W},d_{ij}\leq d_{\delta}$ as the worker move closer. If guide $i$ follows
equ. 7, $c_{i}$ continues increasing as it approaches the worker COM
$x_{i}^{c}$. As it does, the attracting $g_{i}$ and $a_{i}$ terms remain
stable, diminish, or remain zero from the inherent motion in direction of
$x_{t}$ and $\theta_{i}^{tc}$. The $c_{i}$ potential following equ. 2 is
quadratically increasing as $d\to 0$, and thus $c_{i}>g_{i}+a_{i}$. Hence, the
guide is repelled and cannot collide with or cause collisions within the
worker swarm.

According to lemma 2, whenever a worker robot is in the reactive field of a
guide robot, the force exerted on the worker by the guide is greater than that
of another worker, thus allowing the guide robots to manipulate the worker
swarm. These manipulations and other motions occur without collisions, as
shown in lemmas 1 and 3.

##  V Experiments

We evaluate our approach both in simulation and with real robots. We
implemented our approach using Buzz [44] an extensible domain-specific
programming language for robot swarms. We open-source our implementation and
other analysis for use by the community (will be released after review). We
used the Khepera IV robot model in simulation. Real experiments were conducted
with custom, modified Khepera IV robots equipped with an Intel RealSense T265
111https://www.intelrealsense.com/tracking-camera-t265/ and an Nvidia Jetson
TX1 (some robots in the worker class were using a Raspberry Pi 4) as their on-
board computer. Robots in simulation used a situated communication [45] model
and the real robots used batman-adv
222https://www.kernel.org/doc/html/v4.16/networking/batman-adv.html a layer
two ad-hoc networking protocol (IBSS) to communicate. Custom application layer
software based on UDP used the underlying neighbors discovered in layer 2 by
batman-adv to broadcast information. Situated communication in the real robots
was realized by creating data packets pairs with [position, data]. The robots
receiving a new communication broadcast used the positional information and
computes a relative distance and angle to its neighbor.

Simulation Simulation experiments were performed using a physics-based
simulator, ARGoS3 [16]. Simulation configuration used during our experiments
were: number of worker robots $N\in\\{$50, 100, 300$\\}$ and three different
shapes $Shape\in\\{$Clover, Dumbbell, Circle$\\}$ (see fig. 4). The case with
$50$, $100$ and $300$ worker robots had $4$, $8$ and $16$ guide robots
respectively for both clover and dumbbell shapes. The circle formation case
used $9$ guides for both $50$ and $100$, and $17$ guides for the $300$ worker
case. A different number of dog robots for circle formation was used mainly
because of the configuration involved; a lower number of robots do not provide
the enclosure required to move the worker robots in this formation. Each
experimental configuration was repeated 30 times with random robot
initializations using a uniform distribution of parameters a and b as shown in
table I. Experiments with 1000 worker robots case were performed only for the
clover shape using 32 guides, and were repeated 30 times as well. The design
parameters used in the experiments are shown in table I. Fig. 4 show a
consistent shape for all three formations used in the experiments and plots
the actual position of the robots at the end of shaping. As seen in the fig. 4
and fig. 5 the robots were able to form a consistent formation and move to a
target placed at 10 meters from the start location for all three shapes.

TABLE I: Experimental parameters

| Design
---
$k$ | 0.02
$a_{0}$ | 0

| Experimental
---
$a$ | $\frac{\sqrt{(0.9155*N)/0.1}}{2}+4$
$b$ | $-a$
$d_{\rho}$ | 0.8 m
$d_{\delta}$ | 0.45 m
$\theta_{\delta}$ | 0.01 rad
$FOV$ | 1 m
$RFOV$ | 0.7 m
$d^{e}$ | 95

The performance metrics used to study and compare the various formations are
time taken by guide state (as shown by fig. 6) and the distortion incurred
during motion (as shown in fig. 7). Distortion metric $\Upsilon$ was computed
using:

$\displaystyle\Upsilon=\frac{1}{N}\sum_{i\in R_{W}}\sum_{j\in R_{W},j\neq
i}\mathinner{\\!\left\lVert
x_{i}(t_{s})-x_{j}(t_{s})\right\rVert}-\mathinner{\\!\left\lVert
x_{i}(t_{f})-x_{j}(t_{f})\right\rVert}$ (11)

with $t_{s}$ being the time at shaping and $t_{f}$ being the time at reaching
the target. The purpose of the distortion metric is to quantify the final
deformation of the formation as a result of motion. The distortion metric
records the average difference in relative position between the swarm after
shaping and the swarm at its final location. The distortion metric is
normalized with the largest value from all the configurations, to obtain a
value in the range of $[0,1]$. The primary rationale behind the normalization
is to obtain a comparative metric of the shape deformation across various
configurations used in the study. A value of 0 is a perfect displacement with
no distortion (i.e., no relative change in distances between the robots) and 1
is the worst distortion seen in the current formation. The distortion metric
can be also viewed as the relative change in position of a robot with respect
to the worst case encountered in the experimental configuration.

As seen in fig. 6, the time taken for the simulations is grouped by Task
Allocation for guide robots to select shaping targets, shaping setup to locate
the worker flock and edge-follow to the target, shaping to create a desired
formation with the worker and moving the desired formation to a target. Task
allocation phase has a monotonic increase in time with number of robots and
does not vary with configurations, since it is a function of number of robots
and available tasks. In particular, the mean time take was about 4s, 18s, 22s,
45s and 48s for 4, 8, 9, 16 and 17 guide robots respectively. Shaping setup
and Shaping exhibit a similar pattern because of these steps being
configuration dependent, for instance, reaching a certain angular alignment
through edge following requires a similar amount of time. Shaping setup on an
average took 260s, 350s and 650s for $50$, $100$ and $300$ worker cases in
both clover and dumbbell shape. In case of circle formation, shaping setup
took 315s, 374s and 621s for the three different worker cases respectively.
Movement on the other hand has its own dynamics for different shapes with
various number of workers and hence exhibits different trends for different
shapes. Clover shape with $50$, $100$ and $300$ robots took $17171s$, $16101s$
and $15073s$ respectively. The circle shape took the least amount of time
w.r.t other shapes because the robots required a lower number of corrective
moves to maintain formation and spent more time moving towards the target.

The distortion metric results in fig. 7 compare the distortions incurred from
motion. The clover shape encountered the least distortion for all three cases
($50$, $100$ and $300$ workers), mainly because the guide robots are
positioned well into the formation acting as pillars of the formation. There
is a steady increase in distortion when adding additional robots, which is
expected due to the summation used in equ. 11 of the distance error that
accumulates with more robots. The overall average distortion for the clover
shape stayed below 0.3. The dumbbell shape on the other hand had the worst
level of distortion due to the two ends without guides, which could swing
freely and deformed significantly. Even with a lower number of worker robots,
limited numbers of guide robots are unable to steadily hold the two sides of
the dumbbell in place. In particular, the dumbbell had an average relative
distortion of 0.78, 0.69 and 0.51 for $50$, $100$ and $300$ robots. The circle
had a steady increase in distortion, $0.25$, $0.4$ and $0.75$ on average for
$50$, $100$ and $300$ robots.

Figure 7: Distortion incurred by the swarm in different states, according to
the metric defined in equ. 11 and section $V$. Here we see how the dumbbell is
particularly subject to distortion with smaller worker and guide swarms,
although distortion decreases with larger worker swarms. On the other hand,
the circle and clover shapes seem to have greater distortion with increasing
worker swarm size.

Figure 8: Trajectory for shaping and translating a swarm of 6 real robots.
Left: simulation; middle: real robots; right: the time taken for the
operation. Slightly different actuation and forces affecting the real robot
dynamics make for a smoother set of trajectories simulation, albeit subject to
minor drift.

Real robots We used 6 Khepera IV robots with 4 as workers and 2 guides. We
used a simple square like shape to be formed by the robots. The robots were
able to task allocate, preform the shaping setup to reach the provided shaping
targets and move to a target of about 1m in formation. Fig. 8 left shows the
trajectory of the robots for a similar shape in simulation, middle, the
trajectory of the real robots and the right, shows the time taken to reach the
target in formation. The robots took about 240s with real robots and 247s in
simulation. The simulation results are comparable to the real robots.

##  VI Conclusion

We propose a hierarchical approach to control a swarm of robots that form
shapes and translate in formation with two types of robots: a large group of
simple robots (workers) and a small swarm of intelligent robots (guides). The
process of decision-making for formation and translation to targets is
performed by the guides, and workers act as the muscle in forming shapes with
no knowledge of the overall task. The interactions of the swarms are designed
to be simple and local through virtual potential fields that depend on the
relative position of the robots. This approach relies on the knowledge of the
guide swarm, which coordinates to obtain the desired shape of the worker
swarm, like smart particles. The interaction properties of the worker swarm
are dynamically adapted by the guide swarm, leveraging its additional sensing
and knowledge. The approach scales well with increasing number of robots
forming similar shapes. We evaluated the approach on a small swarm of robots
in a realistic setting that use visual inertial odometry to compute relative
positions, with no additional external setup for position estimation. The
prototype framework implemented in this work lays the foundation for
hierarchically self-organizing swarms that could be one day be used for
targeted drug delivery and cancer treatment using nanomedicine.

## References

  * [1] M. Dorigo, G. Theraulaz, and V. Trianni, “Swarm robotics: Past, present, and future,” _Proceedings of the IEEE_ , vol. 109, no. 7, pp. 1152–1165, 2021\.
  * [2] G. Z. Yang, J. Bellingham, P. E. Dupont, P. Fischer, L. Floridi, R. Full, N. Jacobstein, V. Kumar, M. McNutt, R. Merrifield, B. J. Nelson, B. Scassellati, M. Taddeo, R. Taylor, M. Veloso, Z. L. Wang, and R. Wood, “The grand challenges of science robotics,” _Science Robotics_ , vol. 3, no. 14, 2018.
  * [3] M. Dorigo, G. Theraulaz, and V. Trianni, “Reflections on the future of swarm robotics,” _Science Robotics_ , vol. 5, no. 49, pp. 9–12, 2020.
  * [4] I. Slavkov, D. Carrillo-Zapata, N. Carranza, X. Diego, F. Jansson, J. A. Kaandorp, S. Hauert, and J. Sharpe, “Morphogenesis in Robot Swarms,” _Accepted for publication on Science Robotics. Available on Dec 19, 2018_ , vol. 3, no. 24, pp. 1–17, 2018.
  * [5] M. Rubenstein, A. Cornejo, and R. Nagpal, “Programmable self-assembly in a thousand-robot swarm,” _Science_ , vol. 345, no. 6198, pp. 795–799, 2014\. [Online]. Available: https://science.sciencemag.org/content/345/6198/795
  * [6] C. Pinciroli and G. Beltrame, “Swarm-Oriented Programming of Distributed Robot Networks,” _Computer_ , vol. 49, no. 12, pp. 32–41, 2016.
  * [7] M. Dorigo, D. Floreano, L. M. Gambardella, F. Mondada, S. Nolfi, T. Baaboura, M. Birattari, M. Bonani, M. Brambilla, A. Brutschy _et al._ , “Swarmanoid: a novel concept for the study of heterogeneous robotic swarms,” _IEEE Robotics & Automation Magazine_, vol. 20, no. 4, pp. 60–71, 2013.
  * [8] A. Prorok, M. A. Hsieh, and V. Kumar, “The impact of diversity on optimal control policies for heterogeneous robot swarms,” _IEEE Transactions on Robotics_ , vol. 33, no. 2, pp. 346–358, 2017.
  * [9] M. Scheutz, “Real-time hierarchical swarms for rapid adaptive multi-level pattern detection and tracking,” in _2007 IEEE Swarm Intelligence Symposium_. IEEE, 2007, pp. 234–241.
  * [10] H. Chen, Y. Zhu, K. Hu, and X. He, “Hierarchical swarm model: a new approach to optimization,” _Discrete Dynamics in Nature and Society_ , vol. 2010, 2010\.
  * [11] J. Hu, A. E. Turgut, T. Krajník, B. Lennox, and F. Arvin, “Occlusion-based coordination protocol design for autonomous robotic shepherding tasks,” _IEEE Transactions on Cognitive and Developmental Systems_ , 2020.
  * [12] S. Razali, N. F. Shamsudin, M. Osman, Q. Meng, and S.-H. Yang, “Flock identification using connected components labeling for multi-robot shepherding,” in _2013 International Conference on Soft Computing and Pattern Recognition (SoCPaR)_. IEEE, 2013, pp. 298–303.
  * [13] A. Özdemir, M. Gauci, and R. Groß, “Shepherding with robots that do not compute,” in _ECAL 2017, the Fourteenth European Conference on Artificial Life_. MIT Press, 2017, pp. 332–339.
  * [14] V. S. Varadharajan, D. St-Onge, B. Adams, and G. Beltrame, “Swarm relays: Distributed self-healing ground-and-air connectivity chains,” _IEEE Robotics and Automation Letters_ , vol. 5, no. 4, pp. 5347–5354, 2020.
  * [15] C. Huang, G. Yang, Q. Ha, J. Meng, and S. Wang, “Multifunctional “smart” particles engineered from live immunocytes: toward capture and release of cancer cells,” _Advanced Materials_ , vol. 27, no. 2, pp. 310–313, 2015\.
  * [16] C. Pinciroli, V. Trianni, R. O’Grady, G. Pini, A. Brutschy, M. Brambilla, N. Mathews, E. Ferrante, G. Di Caro, F. Ducatelle _et al._ , “Argos: a modular, parallel, multi-engine simulator for multi-robot systems,” _Swarm intelligence_ , vol. 6, no. 4, pp. 271–295, 2012.
  * [17] G. Li, D. St-Onge, C. Pinciroli, A. Gasparri, E. Garone, and G. Beltrame, “Decentralized progressive shape formation with robot swarms,” _Autonomous Robots_ , vol. 43, no. 6, pp. 1505–1521, 2019. [Online]. Available: https://doi.org/10.1007/s10514-018-9807-5
  * [18] G. Vásárhelyi, C. Virágh, G. Somorjai, T. Nepusz, A. E. Eiben, and T. Vicsek, “Optimized flocking of autonomous drones in confined environments,” _Science Robotics_ , vol. 3, no. 20, pp. 1–14, 2018.
  * [19] R. P. Ramos, S. M. Oliveira, S. M. Vieira, and A. L. Christensen, “Evolving flocking in embodied agents based on local and global application of reynolds’ rules,” _Plos one_ , vol. 14, no. 10, p. e0224376, 2019.
  * [20] B. T. Fine and D. A. Shell, “Unifying microscopic flocking motion models for virtual, robotic, and biological flock members,” _Autonomous Robots_ , vol. 35, no. 2, pp. 195–219, 2013.
  * [21] C. W. Reynolds, “Flocks, herds and schools: A distributed behavioral model,” in _Proceedings of the 14th annual conference on Computer graphics and interactive techniques_ , 1987, pp. 25–34.
  * [22] F. Gökçe and E. Şahin, “To flock or not to flock: the pros and cons of flocking in long-range” migration” of mobile robot swarms,” in _Proceedings of The 8th International Conference on Autonomous Agents and Multiagent Systems-Volume 1_ , 2009, pp. 65–72.
  * [23] V. Gazi and K. M. Passino, “Stability of a one-dimensional discrete-time asynchronous swarm,” _IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics)_ , vol. 35, no. 4, pp. 834–841, 2005.
  * [24] S. Hauert, S. Leven, M. Varga, F. Ruini, A. Cangelosi, J.-C. Zufferey, and D. Floreano, “Reynolds flocking in reality with fixed-wing robots: communication range vs. maximum turning rate,” in _2011 IEEE/RSJ international conference on intelligent robots and systems_. IEEE, 2011, pp. 5015–5020.
  * [25] D. V. Dimarogonas, M. Egerstedt, and K. J. Kyriakopoulos, “A leader-based containment control strategy for multiple unicycles,” in _Proceedings of the 45th IEEE Conference on Decision and Control_. IEEE, 2006, pp. 5968–5973.
  * [26] R. Tron, J. Thomas, G. Loianno, K. Daniilidis, and V. Kumar, “Bearing-only formation control with auxiliary distance measurements, leaders, and collision avoidance,” in _2016 IEEE 55th Conference on Decision and Control (CDC)_. IEEE, 2016, pp. 1806–1813.
  * [27] L. Consolini, F. Morbidi, D. Prattichizzo, and M. Tosques, “Leader–follower formation control of nonholonomic mobile robots with input constraints,” _Automatica_ , vol. 44, no. 5, pp. 1343–1349, 2008.
  * [28] M. Ji, A. Muhammad, and M. Egerstedt, “Leader-based multi-agent coordination: Controllability and optimal control,” in _2006 American Control Conference_. IEEE, 2006, pp. 6–pp.
  * [29] D. Panagou and V. Kumar, “Cooperative visibility maintenance for leader–follower formations in obstacle environments,” _IEEE Transactions on Robotics_ , vol. 30, no. 4, pp. 831–844, 2014.
  * [30] S. Björkenstam, M. Ji, M. B. Egerstedt, and C. F. Martin, “Leader-based multi-agent coordination through hybrid optimal control.” Georgia Institute of Technology, 2006.
  * [31] J. Wiech, V. A. Eremeyev, and I. Giorgio, “Virtual spring damper method for nonholonomic robotic swarm self-organization and leader following,” 2018.
  * [32] M. Ji, G. Ferrari-Trecate, M. Egerstedt, and A. Buffa, “Containment control in mobile networks,” _IEEE Transactions on Automatic Control_ , vol. 53, no. 8, pp. 1972–1975, 2008.
  * [33] H. Hoshi, I. Iimura, S. Nakayama, Y. Moriyama, and K. Ishibashi, “Robustness of herding algorithm with a single shepherd regarding agents’ moving speeds,” _Journal of Signal Processing_ , vol. 22, no. 6, pp. 327–335, 2018\.
  * [34] L. Chaimowicz and V. Kumar, “Aerial shepherds: Coordination among uavs and swarms of robots,” in _Distributed Autonomous Robotic Systems 6_. Springer, 2007, pp. 243–252.
  * [35] D. Strömbom, R. P. Mann, A. M. Wilson, S. Hailes, A. J. Morton, D. J. Sumpter, and A. J. King, “Solving the shepherding problem: heuristics for herding autonomous, interacting agents,” _Journal of the royal society interface_ , vol. 11, no. 100, p. 20140719, 2014.
  * [36] N. K. Long, M. Garratt, K. Sammut, D. Sgarioto, and H. A. Abbass, “Shepherding autonomous goal-focused swarms in unknown environments using hilbert space-filling paths,” _Shepherding UxVs for Human-Swarm Teaming: An Artificial Intelligence Approach to Unmanned X Vehicles_ , pp. 31–50, 2021.
  * [37] M. Kubo, M. Tashiro, H. Sato, and A. Yamaguchi, “Herd guidance by multiple sheepdog agents with repulsive force,” _Artificial Life and Robotics_ , pp. 1–12, 2022.
  * [38] D. St-Onge, V. S. Varadharajan, I. Švogor, and G. Beltrame, “From design to deployment: decentralized coordination of heterogeneous robotic teams,” _Frontiers in Robotics and AI_ , vol. 7, p. 51, 2020.
  * [39] M. Mesbahi and M. Egerstedt, _Graph theoretic methods in multiagent networks_. Princeton University Press, 2010\.
  * [40] C. Pinciroli, A. Lee-Brown, and G. Beltrame, “A tuple space for data sharing in robot swarms,” in _Proceedings of the 9th EAI International Conference on Bio-inspired Information and Communications Technologies (formerly BIONETICS)_ , 2016, pp. 287–294.
  * [41] H. T. Zhang, C. Zhai, and Z. Chen, “A general alignment repulsion algorithm for flocking of multi-agent systems,” _IEEE Transactions on Automatic Control_ , vol. 56, no. 2, pp. 430–435, 2011.
  * [42] S. J. Stuart, A. B. Tutein, and J. A. Harrison, “A reactive potential for hydrocarbons with intermolecular interactions,” _The Journal of chemical physics_ , vol. 112, no. 14, pp. 6472–6486, 2000.
  * [43] G. A. Korsah, A. Stentz, and M. B. Dias, “A comprehensive taxonomy for multi-robot task allocation,” _The International Journal of Robotics Research_ , vol. 32, no. 12, pp. 1495–1512, 2013.
  * [44] C. Pinciroli and G. Beltrame, “Buzz: An extensible programming language for heterogeneous swarm robotics,” in _2016 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_. IEEE, 2016, pp. 3794–3800.
  * [45] K. Støy, “Using situated communication in distributed autonomous mobile robotics.” in _SCAI_ , vol. 1. Citeseer, 2001, pp. 44–52.