# Resource Constrained Semantic Segmentation for Waste Sorting

Cascina Elisa
Politecnico di Torino
<EMAIL_ADDRESS>
Pellegrino Andrea
Politecnico di Torino
<EMAIL_ADDRESS>
Tozzi Lorenzo
Politecnico di Torino
<EMAIL_ADDRESS>

###### Abstract

This work addresses the need for efficient waste sorting strategies in
Materials Recovery Facilities to minimize the environmental impact of rising
waste. We propose resource-constrained semantic segmentation models for
segmenting recyclable waste in industrial settings. Our goal is to develop
models that fit within a 10MB memory constraint, suitable for edge
applications with limited processing capacity. We perform the experiments on
three networks: ICNet, BiSeNet (Xception39 backbone), and ENet. Given the
aforementioned limitation, we implement quantization and pruning techniques on
the broader nets, achieving positive results while marginally impacting the
Mean IoU metric. Furthermore, we propose a combination of Focal and Lovász
loss that addresses the implicit class imbalance resulting in better
performance compared with the Cross-entropy loss function.

GitHub repository

##  1 Introduction

The exponential growth of the global population has resulted in a significant
increase in waste production. To tackle this challenge, it is essential to
develop efficient strategies for Materials Recovery Facilities, as they play a
vital role in the recycling process. These strategies should focus on
improving the detection of recyclable waste and minimizing negative
environmental consequences.

Koskinopoulou _et al_. [1] introduced the task of segmenting waste that could
be useful for waste sorting. Figure 1 shows the qualitative performance by
Mask RCNN. However, Mask RCNN models are generally large and have a high
number of training parameters. So, to achieve real-time waste segmentation
performance, the model should be computationally efficient.

Figure 1: Example of semantic segmentation model result [1]

In this work, we focus on developing resource-constrained semantic
segmentation models specifically designed for waste-sorting applications in
industrial settings. The primary objective of this work was to deploy tiny
semantic segmentation models capable of fitting within a memory constraint of
10MB with significant mIOU. This design makes them suitable for edge
applications utilizing smart cameras with limited onboard processing capacity.

The contribution of this work can be summarized in three folds: Firstly, we
select three resource-efficient semantic segmentation network architectures
for experimentation, namely: ICNet [2], BiSeNet (with Xception39 backbone) [3,
4] and ENet [5]. We chose the models above as they show significant
performance on semantic segmentation tasks and have great potential for
adaptation in resource-constrained environments. Next, we train the models
using an augmented dataset with various loss functions to improve performance.
We address the class imbalance problem by introducing the models on a plethora
of losses: Focal [6], Dice [7], Class-balanced focal [8], as well as the
combination of Focal and Lovász[9]. Finally, we ensure parameter efficiency of
our model while preserving mIoU results by performing model pruning [10, 11]
and quantization [12, 13, 14, 15] techniques. Moreover, given the relatively
compact nature of ENet, we opted to augment its dimensions by modifying the
sizes of both the encoder and decoder to enhance standard ENet performances
while respecting the memory constraint.

##  2 Related Work

Our research builds upon the work by Koskinopoulou _et al_. [1], which
introduces an integrated robotic system designed to sort recyclable materials.
This system comprises two principal components: a robotic manipulator for
physically segregating waste into distinct bins based on material type and a
vision-based module dedicated to material detection and categorization. The
materials are Aluminium, Paper, Bottle, and Nylon.

Our study further elaborates on the aspect of vision-based detection. To
accurately categorize recyclables based on their material type in an
autonomous recovery system, they chose Convolutional Neural Networks (CNNs),
the most cost-effective option. The study focuses on instance segmentation to
identify and label multiple objects within waste images. To accomplish this,
the Mask Regional CNN network was employed due to its success in similar
tasks. Mask R-CNN offers a scalable method for categorizing recyclables across
numerous classes.

The study considers various factors to optimize performances, including tuning
training parameters, dataset size, learning steps per epoch, and entation
techniques. Multiple versions of the Mask R-CNN model (Net 1 to Net 4) are
examined, each with its strengths and limitations. Net 1 and Net 2, both
trained with smaller datasets, had limitations and poor performance when
applied to the waste images. Meanwhile, Net 3 showed significant improvement
and could be used in real-world applications. Net 4, which incorporates
entation and extended training, outperforms other versions when tested on the
final images.

A key element of their research involves the development of a tailored open-
source dataset, an indispensable resource for training our neural networks.
Notably, the available open-source datasets for public utilization, namely
TrashNet [16], and Taco [17], are confined to outdoor waste classification
scenarios. These datasets do not sufficiently address the inherent
complexities of industrial demanding environments. On the contrary, the paper
by Koskinopoulou _et al_.; embraces an inverse methodology geared toward
automating the annotation process of addressing diverse problem entanglements.
Firstly, the mask that indicates each region of interest was assigned as an
image annotation. In the second step, translation, rotation, and scaling were
randomly applied to the image and the mask. Finally, pairs of objects from the
previous stage, with their respective masks, were randomly chosen and
positioned over new images with colorful backgrounds to develop complex
problem instances (as shown in Figure 2).

Figure 2: Dataset images with new colorful backgrounds [1]

##  3 Design choices

In this section, we will discuss our most significant intuitions and design
preferences that allow us to attain our goals.

###  3.1 Models

We present a concise overview of the main characteristics of the three neural
networks employed in this work:

  * •

ENet (Efficient Neural Network): It is designed to perform semantic
segmentation while being lightweight in terms of computing resources, with a
size of $\sim$1.5MB and $\sim$360,000 parameters. ENet utilizes innovative
architectural features. Among them, spatial pooling is used to downsample
feature maps efficiently. Moreover, the network’s architecture consists of an
initial convolutional layer, followed by several encoder and decoder blocks,
with each block featuring bottleneck modules. Skip connections are employed to
amalgamate feature maps from different layers, capturing low-level and high-
level features. [5]

  * •

BiSeNet V2 (Bilateral Segmentation Network): It is characterized by a two-
branch network structure consisting of a detail branch and a semantic branch.
It uses the Xception39 pre-trained model as a backbone. The details branch is
responsible for extracting spatial information, which is low-level
information, while the semantic branch is designed to capture high-level
semantics. Then, it is followed by an aggregation layer and a segmentation
head. This design strikes a balance between accuracy and efficiency. BiSeNet
is known for its relatively compact model size (with a weight of $\sim$14MB
and $\sim$5.2 million of parameters) compared to some other semantic
segmentation networks. [4]

  * •

ICNet (Image Cascade Network): It is tailored for high-quality real-time
semantic segmentation, even though it comes with a larger model size as a
trade-off, with a dimension of $\sim$190MB and $\sim$48 millions of
parameters. It employs a cascade of multiple branches to process input images
at various scales, enabling it to capture both fine and coarse details in
segmentation tasks. It incorporates a pyramid structure, efficiently capturing
multi-scale features. Additionally, ICNet produces a hierarchical segmentation
map with multiple resolution levels, which proves advantageous for delineating
objects in various contexts. The cascade architecture enables multi-scale
processing, allowing it to effectively handle objects of varying sizes. [2]

####  3.1.1 Custom ENet

In the context of ENet, adjustments were made to the dimensions of specific
layers in both the encoder and decoder. These changes were made possible by
the model’s size, which allowed for the addition and modification of layers
without exceeding the 10MB limit. Specifically, we expanded the network’s
architecture adding a downsampling layer with the objective of achieving an
output size of 256 x 32 x 32 for every bottleneck layer in stages 2 and 3,
instead of the original configuration of 128 × 64 × 64. We will refer to this
modified model as Custom ENet.

All the characteristics of the employed networks are summarised in Table 1
(FLOPS stands for floating point operations per second).

Net | Size (MB) | FLOPS | # Parameters
---|---|---|---
Enet | 1.45 | 11.88 | 363,132
Custom Enet | 5.45 | 13.42 | 1,363,168
BiSeNet | 13.38 | 74.89 | 5,188,485
ICNet | 189.96 | 99.35 | 47,489,184
Table 1: Employed models main characteristics

###  3.2 Loss functions

In semantic segmentation, a loss function is a critical component used to
measure the dissimilarities between predicted pixel-wise class labels and
ground truth labels in an image. Deep learning models are prone to bias
towards the majority class. In the context of semantic segmentation, the
background class (i.e. everything that is not part of the object of interest)
often constitutes the majority class. This bias may lead the model to allocate
excessive attention to the background, resulting in inaccurate segmentation of
the foreground objects. We implement three losses to address this problem:

  * •

Focal loss: It’s a function that introduces a modulation factor (regulated
with a hyperparameter $\gamma$) into the Cross-entropy loss function, aimed at
concentrating the learning process on challenging misclassifications.
Essentially, it is a Cross-entropy loss that adapts its weighting dynamically.
As the model gains more confidence in correctly classifying an example, this
scaling factor progressively diminishes toward zero. In simpler terms, this
factor automatically reduces the impact of straightforward examples during
training and swiftly directs the model’s attention to the more difficult
instances.[6]

  * •

Class-balanced focal loss: This is a re-weighting scheme based on the
effective number of samples within each class to recalibrate the focal loss
function. The effective number reflects the idea that as the number of samples
increases, the incremental benefit of a newly added image diminishes. It
essentially represents the coverage of the data samples in representing the
class in a feature space.[8]

  * •

Dice loss: Dice loss attaches similar importance to false positives and false
negatives, dynamically adjusting weights to deemphasize easy-negative
examples. [7]

Moreover, we utilize additional loss functions in order to enhance
performance:

  * •

Lovász loss: Its primary objective is to promote the alignment of the
predicted class with ground truth masks, leading to an improved mIoU value.
[18]

  * •

Focal-Lovász loss: Firstly introduced in [9], we aim to combine the benefits
of both loss functions.

###  3.3 Pruning and Quantisation

These two techniques are implemented to attain our objective of creating a
lightweight model.

####  3.3.1 Pruning

Pruning is a neural network technique used to reduce the size and complexity
of the network by selectively removing certain connections (weights) while
trying to preserve the network’s performance. It works by creating a pruning
mask for each layer of the model. The pruning mask determines which parameters
should be pruned, so setting the values of the pruned connections or
parameters to zero. [10, 11] Pruning techniques can be categorized into two
main types: unstructured (i.e. deleting individual parameters without their
respective structure) and structured pruning (i.e. removing entire structures
of parameters). We present an explanation of the methods employed:

  * •

Random Unstructured Pruning: During the pruning process, a certain percentage
of weights are selected randomly and assigned a value of zero. This
effectively eliminates those connections from the network, reducing its size
and complexity.

  * •

L1 Unstructured Pruning: It encourages sparsity in the neural network by
zeroing out the weights tensors with the lowest L1-norm.

  * •

Random Structured Pruning: It randomly removes entire neuron channels or
filters from the neural network.

  * •

Ln Structured Pruning: This pruning method, where n indicates the order of the
norm, is an extension of L1 Pruning with a structured method. It encourages
entire units to become exactly zero, according to their norms.

####  3.3.2 Quantisation

Quantization is a technique for performing computations and storing tensors at
lower bit-widths than floating point precision. A quantized model executes
some or all of the operations on tensors with reduced precision rather than
full precision (floating point) values. $N$ float32 values are mapped to lower
precision numbers that can be represented by $N$ uint8 values and 2 more
single values: a float32 scale factor and an int32 zero_point value. In this
way, a float32 number can be reconstructed as

$val_{float32}=(val_{uint8}-zero\\_point)\times scale$

This process can lead up to a 4x reduction in memory size. [13]

Quantization can be classified into Dynamic and Static. Dynamic quantization
adapts the zero_point and scale factors on the fly, making it powerful but
computationally expensive. Static quantization, on the other hand, has fixed
parameters for every input. Among the static quantization approaches, we
examine two of them:

  * •

Post-Training Quantisation: It involves quantizing a pre-trained model after
it has already been trained at high precision. This approach is simpler but
may require fine-tuning to recover some performance lost due to quantization.

  * •

Quantisation-Aware Training: It minimizes the impact of quantization on model
accuracy. During training, the model is exposed to quantized values, and
gradients are computed accordingly. This helps the model adapt to the lower-
precision representation while maintaining performance.

In our work, we employ PTQ (Post-Training Quantisation) because it enables us
to achieve a satisfactory reduction in model size.

##  4 Experimental Results

In this section, we present and analyze the experimental results obtained
during the evaluation of our previously proposed methods. In each of our
experimental setup, we employed the hyperparameters as detailed in the Table
2. We will only showcase the “optimal” results, defined by the criteria of
achieving a high mIoU value while preserving minimal variance in the final
epochs; this ensures the model’s robustness towards the end of the training
process. Throughout the training, certain transformations such as scaling,
random cropping, and random horizontal flips (with a 0.5 probability of
occurring) are applied to the training dataset. Unless otherwise specified,
the neural networks were trained for 100 epochs with the Cross-entropy loss.

Parameters | Values
---|---
Learning rate (LR) | {$5e^{-4},\,5e^{-5},\,5e^{-6}$}
Learning Rate decay ($LR_{D}$) | {$None,0.995$}
Step LR decay ($Step_{LR}$) | {$None,\,20,\,25,\,30,\,50$}
Table 2: Hyperparameters used in training

###  4.1 Binary segmentation

Our first step was to train the segmentation networks to give a pixel-wise
prediction for the waste area, specifically distinguishing between background
and objects.

The optimal hyperparameter configurations have been outlined in Table 3. As
expected, BiSeNet and ICNet outperform Enet, primarily due to disparities in
model complexity and size.

Net | LR | $LR_{D}$ | $Step_{LR}$ | mIoU
---|---|---|---|---
Enet | $5e^{-6}$ | None | None | 0.780
BiSeNet | $5e^{-6}$ | None | None | 0.848
ICNet | $5e^{-5}$ | None | None | 0.830
Table 3: Binary segmentation experimental results

###  4.2 Instance segmentation

Differently from the previous phase, our objective here is to categorize the
waste materials into one of four possible labels: aluminum, paper, bottle, or
nylon. As shown in Table 4, compared to binary segmentation, there is a
decrease in the mIoU as we now need to identify both objects against the
background and classify them into material classes. It’s worth noting that
Aluminum is consistently recognized. Regarding the nets, the performance of
ENet and BiSeNet is comparable, while ICNet is the top-performing model.

Alongside Table 4, we provide an analysis of the experimental training process
in Figures 3,4 and 5. A first consideration is that Aluminium, recognized
since the first epochs, has demonstrated remarkable stability over the
training process; this behavior can be explained by the repetitive shape of
aluminum objects (mainly cans) and the reflectivity property of the material.
At the outset, the recognition of the Bottle class faces initial challenges
when compared to the other classes. In each scenario, Paper consistently
exhibits as the least performing. Nylon, on the other hand, exhibits higher
variance in performance, but interestingly, it emerges as the second-best
performer in our analysis. As we observe the training process, we notice that
there is an equilibrium point reached after a certain number of epochs, i.e.
model converges to the optimal result. A remarkable observation is that
BiSeNet, when lower learning rates are used, slowly converges to the final
mIoU value without significant fluctuations.

Net | LR | $LR_{D}$ | $Step_{LR}$ | # Epochs | Aluminium | Paper | Bottle | Nylon | mIoU
---|---|---|---|---|---|---|---|---|---
Enet | $5e^{-4}$ | 0.995 | 25 | 150 | 0.988 | 0.569 | 0.618 | 0.668 | 0.682
BiSeNet | $5e^{-6}$ | None | None | 150 | 0.989 | 0.565 | 0.588 | 0.676 | 0.679
ICNet | $5e^{-4}$ | 0.995 | 50 | 150 | 0.99 | 0.619 | 0.676 | 0.679 | 0.733
Table 4: Instance segmentation experimental results Figure 3: ENet validation:
mIoU over epochs Figure 4: BiSeNet validation: mIoU over epochs Figure 5:
ICNet validation: mIoU over epochs

####  4.2.1 Custom ENet

Table 5 presents the results of our custom ENet implementation. It’s
noteworthy that despite being trained for a shorter duration, it converges to
results that are on par with the standard ENet. However, under the same
configuration (1), it fails to surpass the performance of the standard one.
Additionally, even in the best-case scenario (2), the results do not meet
expectations.

Net | LR | $LR_{D}$ | $Step_{LR}$ | # Epochs | Aluminium | Paper | Bottle | Nylon | mIoU
---|---|---|---|---|---|---|---|---|---
Enet | $5e^{-4}$ | 0.995 | 25 | 150 | 0.988 | 0.569 | 0.618 | 0.668 | 0.682
Custom ENet (1) | $5e^{-4}$ | 0.995 | 25 | 100 | 0.987 | 0.548 | 0.586 | 0.653 | 0.667
Custom ENet (2) | $5e^{-4}$ | None | None | 100 | 0.986 | 0.56 | 0.603 | 0.628 | 0.679
Table 5: Instance segmentation experimental results of ENet and Custom ENet

####  4.2.2 Data Augmentation

In this particular scenario, we aim to introduce additional transformations
during the training process: random vertical flips (RVF) and color jittering
(RCJ, i.e. light changes in brightness, contrast, saturation, and hue of the
image). These alterations were applied respectively with probability 0.5 and
0.25.

In Table 6, we present the results for the three models employing combinations
of the aforementioned transformations (referred to as AT for brevity).
Overall, the extra entation proved to be unsatisfactory, yielding outcomes
that were inferior to those of the previous models.

Net | AT | LR | $LR_{D}$ | $Step_{LR}$ | Aluminium | Paper | Bottle | Nylon | mIoU
---|---|---|---|---|---|---|---|---|---
Enet | RVF + RCJ | $5e^{-4}$ | None | None | 0.983 | 0.454 | 0.433 | 0.588 | 0.569
BiSeNet | RVF + RCJ | $5e^{-6}$ | None | None | 0.983 | 0.445 | 0.406 | 0.580 | 0.556
ICNet | RVF + RCJ | $5e^{-5}$ | None | None | 0.982 | 0.433 | 0.340 | 0.556 | 0.540
Enet | RVF | $5e^{-4}$ | 0.995 | 30 | 0.983 | 0.484 | 0.456 | 0.533 | 0.583
BiSeNet | RVF | $5e^{-6}$ | 0.995 | 30 | 0.983 | 0.459 | 0.419 | 0.598 | 0.574
ICNet | RVF | $5e^{-4}$ | 0.995 | 30 | 0.982 | 0.490 | 0.414 | 0.555 | 0.567
Table 6: Data Augmentation experimental results

###  4.3 Loss Functions

In the following section, we explore the use of various Loss Functions, a
critical aspect of our experimental framework. We will present the results of
our experiments, shedding light on the impact of these loss functions on the
models’ performance, when changing from the standard one (the Cross-entropy)
that was employed in all previous experiments. Notice that all the results
reported for the Focal loss refer to an implementation with hyperparameter
$\gamma=2$ (we also tried 1 and 5, but 2 was the best one).

Table 7 presents the results for each network trained with different loss
functions. Notably, ENet consistently outperforms the others, with a specific
mention going to the Class-balanced Focal and the Focal-Lovász losses, which
yield a mIoU increase of 4.11% and 7.48%, respectively.

BiSeNet also demonstrates improved performance with certain loss functions
when compared to Cross-entropy. Remarkably, the Lovász and Dice losses stand
out, leading to improvements of up to nearly 6%.

In contrast, ICNet experiences a notable decline in performance.

Net | Loss | LR | $LR_{D}$ | $Step_{LR}$ | Aluminium | Paper | Bottle | Nylon | mIoU
---|---|---|---|---|---|---|---|---|---
Enet | Focal | $5e^{-4}$ | 0.995 | 25 | 0.987 | 0.612 | 0.653 | 0.524 | 0.680
BiSeNet | Focal | $5e^{-6}$ | None | None | 0.987 | 0.557 | 0.486 | 0.682 | 0.642
ICNet | Focal | $5e^{-4}$ | 0.995 | 50 | 0.988 | 0.441 | 0.616 | 0.666 | 0.663
Enet | Lovász | $5e^{-4}$ | 0.995 | 25 | 0.988 | 0.605 | 0.629 | 0.656 | 0.689
BiSeNet | Lovász | $5e^{-6}$ | None | None | 0.989 | 0.591 | 0.618 | 0.689 | 0.702
ICNet | Lovász | $5e^{-4}$ | 0.995 | 50 | 0.986 | 0.607 | 0.634 | 0.544 | 0.676
Enet | Dice | $5e^{-4}$ | 0.995 | 25 | 0.984 | 0.546 | 0.514 | 0.535 | 0.600
BiSeNet | Dice | $5e^{-6}$ | None | None | 0.989 | 0.599 | 0.632 | 0.697 | 0.718
ICNet | Dice | $5e^{-4}$ | 0.995 | 50 | 0.987 | 0.604 | 0.644 | 0.606 | 0.686
Enet | CBFL | $5e^{-4}$ | 0.995 | 25 | 0.989 | 0.598 | 0.653 | 0.682 | 0.710
BiSeNet | CBFL | $5e^{-6}$ | None | None | 0.988 | 0.542 | 0.546 | 0.613 | 0.642
ICNet | CBFL | $5e^{-4}$ | 0.995 | 50 | 0.985 | 0.349 | 0.621 | 0.710 | 0.662
Enet | Focal-Lovász | $5e^{-4}$ | 0.995 | 25 | 0.99 | 0.60 | 0.682 | 0.734 | 0.733
BiSeNet | Focal-Lovász | $5e^{-6}$ | None | None | 0.989 | 0.582 | 0.584 | 0.67 | 0.685
ICNet | Focal-Lovász | $5e^{-4}$ | 0.995 | 50 | 0.988 | 0.532 | 0.663 | 0.638 | 0.693
Table 7: Loss functions experimental results

###  4.4 Pruning and Quantisation

In the pursuit of reducing the size of the models, we explore the employment
of pruning and quantization techniques, keeping in mind the strict memory
constraint of 10MB. It’s worth noting that ENet, being inherently lightweight
in terms of computational resources ($\sim$1.5MB), does not necessitate size
reduction. Conversely, given that BiSeNet has an approximate size of 14MB,
applying quantization or pruning alone suffices. Finally, given that ICNet is
highly computationally demanding, with an estimated size of around 190MB, it
requires both pruning and quantization to meet the specified constraints.

The two models selected for pruning and quantization are the ones with the
highest mIoU values shown in Tables 4 and 7.

####  4.4.1 Pruning

We tried the aforementioned methods (Paragraph 3.3) and it came out that only
the L1 unstructured achieves acceptable results. The implementation of pruning
in PyTorch includes the hyperparameter ”amount” that refers to the proportion
of the network’s parameters to be pruned, leading to an equal reduction in the
model size. The outcomes of these experiments are depicted in Table 8.

Regarding the ICNet, it’s important to note that in order to respect the 10MB
constraint, it is necessary to use a pruning amount of at least 0.95
(corresponding to a size of 9.73MB). However, this adjustment results in a
substantial degradation in performance, with the highest achievable mIoU
standing at only 0.196 under these conditions. Conversely, employing a low
value for amount results in a favorable trade-off between parameter size and
the final mIoU metric, albeit not adhering to the memory constraint.

It’s important to note that BiSeNet not only respects the 10MB limitation but
also demonstrates that even though the higher amount value, it has a smaller
decrease in mIoU compared to ICNet.

Net | Amount | Aluminium | Paper | Bottle | Nylon | mIoU | Size (MB) |  $\Delta$mIoU %
---|---|---|---|---|---|---|---|---
BiSeNet | 0.3 | 0.988 | 0.566 | 0.614 | 0.675 | 0.688 | 9.38 | -4.18%
ICNet | 0.95 | 0.967 | 0.0 | 0.0 | 0.0 | 0.196 | 9.73 | -73.26%
ICNet | 0.2 | 0.988 | 0.585 | 0.604 | 0.622 | 0.690 | 152.1 | -5.91%
ICNet | 0.15 | 0.989 | 0.604 | 0.647 | 0.679 | 0.718 | 161.48 | -2.04%
Table 8: Pruning experimental results

####  4.4.2 Quantisation

Post-training quantization was applied to both BiSeNet and ICNet. At the
outset, an attempt was made to employ Dynamic quantization, but it proved to
be ineffective in the model. This is because PyTorch’s implementation only
affects Linear and Recurrent layers, which are absent in the ICNet
architecture. The results of these experiments are presented in Table 9.

BiSeNet demonstrates impressive outcomes when quantization is applied. The
model size is reduced by over 75%, and remarkably, this reduction has minimal
impact on performance, as evidenced by a mere 1.53% decrease in mIoU.

Quantization on ICNet proved to be highly effective, reducing its size by more
than half with only a 1% decrease in mIoU value.

Net | Aluminium | Paper | Bottle | Nylon | mIoU | Size (MB) |  $\Delta$mIoU % |  $\Delta$Size %
---|---|---|---|---|---|---|---|---
BiSeNet | 0.989 | 0.602 | 0.614 | 0.689 | 0.707 | 3.21 | -1.53% | -76.02%
ICNet | 0.990 | 0.609 | 0.653 | 0.697 | 0.725 | 90.69 | -1.09% | -52.25%
Table 9: Quantisation experimental results

####  4.4.3 Pruning + Quantisation

As ICNet still did not meet the memory constraint, we attempted to combine
Pruning and Quantisation: we applied quantization on the pruned model obtained
with different values of amount (0.2, 0.4, and 0.6). Contrary to our initial
expectations, we found that the combination of both techniques was less
effective than applying Quantisation alone. The reduction in size was
approximately the same, and the final mIoU value was slightly lower. Our
interpretation suggests that quantization, when applied after pruning, is less
effective due to its impact on a reduced number of weights compared to the
unpruned model.

##  5 Conclusion

The study’s findings contribute to the development of efficient waste-sorting
technology for improved recycling. The research emphasizes the importance of
optimizing the model architecture and reducing memory footprint without
compromising the segmentation accuracy required for effective waste sorting.
The chosen network architectures successfully achieve accurate semantic
segmentation for waste sorting, adhering to the stringent 10MB memory
constraint in most cases.

Our findings reveal that ICNet excels under standard settings, outperforming
the other models. Interestingly, when trained with different loss functions,
both ENet and BiSeNet yield results that are comparable to ICNet.

entation and Custom ENet, meanwhile, didn’t meet expectations.

A significant outcome of our research is the effect of Quantisation on BiSeNet
and ICNet. This technique has made it possible to have an outstanding decrease
in model size while maintaining the same performance.

## References

  * [1] Maria Koskinopoulou, Fredy Raptopoulos, George Papadopoulos, and Nikitas Mavrakis.  Robotic waste sorting technology: Toward a vision-based categorization system for the industrial robotic separation of recyclable waste, 2021.
  * [2] Hengshuang Zhao, Xiaojuan Qi, Xiaoyong Shen, Jianping Shi, and Jiaya Jia.  Icnet for real-time semantic segmentation on high-resolution images, 2018\.
  * [3] Changqian Yu, Jingbo Wang, Chao Peng, Changxin Gao, Gang Yu, and Nong Sang.  Bisenet: Bilateral segmentation network for real-time semantic segmentation, 2018.
  * [4] Changqian Yu, Jingbo Wang, Chao Peng, Changxin Gao, Gang Yu, and Nong Sang.  Bisenet v2: Bilateral network with guided aggregation for real-time semantic segmentation, 2020.
  * [5] Adam Paszke, Abhishek Chaurasia, Sangpil Kim, and Eugenio Culurciello.  Enet: Real-time semantic segmentation (semantic segmentation), 2016.
  * [6] Tsung-Yi Lin, Priya Goyal, Ross Girshick, Kaiming He, and Piotr Dollár.  Focal loss for dense object detection, 2018.
  * [7] Carole H. Sudre, Wenqi Li, Tom Vercauteren, Sébastien Ourselin, and M. Jorge Cardoso.  Generalised dice overlap as a deep learning loss function for highly unbalanced segmentations, 2017.
  * [8] Yin Cui, Menglin Jia, Tsung-Yi Lin, Yang Song, and Serge Belongie.  Class-balanced loss based on effective number of samples, 2019.
  * [9] Wang Xindi.  Human protein classification in microscope images using deep learning and focal-lovász loss, 2020.
  * [10] Michela Paganini.  Pruning tutorial, 2023.  Pruning tutorial in Python.
  * [11] Jonathan Frankle and Michael Carbin.  The lottery ticket hypothesis: Finding sparse, trainable neural networks, 2019.
  * [12] Suraj Subramanian, Mark Saroufim, and Jerry Zhang.  Practical quantization in pytorch, 2022.  Quantization tutorial in Python.
  * [13] Amir Gholami, Sehoon Kim, Zhen Dong, Zhewei Yao, Michael W. Mahoney, and Kurt Keutzer.  A survey of quantization methods for efficient neural network inference, 2021.
  * [14] Raghuraman Krishnamoorthi.  Quantizing deep convolutional networks for efficient inference: A whitepaper, 2018.
  * [15] Hao Wu, Patrick Judd, Xiaojie Zhang, Mikhail Isaev, and Paulius Micikevicius.  Integer quantization for deep learning inference: Principles and empirical evaluation, 2020.
  * [16] G. Thung and M. Yang.  Classification of trash for recyclability status, 2016.
  * [17] P. F. Proença and P. Simões.  Trash annotations in context for litter detection, 2020.
  * [18] Maxim Berman, Amal Rannen Triki, and Matthew B. Blaschko.  The lovász-softmax loss: A tractable surrogate for the optimization of the intersection-over-union measure in neural networks, 2018.


# Collective motions of heterogeneous swarms

Klementyna Szwaykowska  U.S. Naval Research Laboratory
Code 6792
Plasma Physics Division
Nonlinear Dynamical Systems Section
Washington, DC 20375
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
Luis Mier-y-Teran Romero  U.S. Naval Research Laboratory
Code 6792
Plasma Physics Division
Nonlinear Dynamical Systems Section
Washington, DC 20375
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
Ira B. Schwartz  U.S. Naval Research Laboratory
Code 6792
Plasma Physics Division
Nonlinear Dynamical Systems Section
Washington, DC 20375
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>

###### Abstract

The emerging collective motions of swarms of interacting agents are a subject
of great interest in application areas ranging from biology to physics and
robotics. In this paper, we conduct a careful analysis of the collective
dynamics of a swarm of self-propelled heterogeneous, delay-coupled agents. We
show the emergence of collective motion patterns and segregation of
populations of agents with different dynamic properties; both of these
behaviors (pattern formation and segregation) emerge naturally in our model,
which is based on self-propulsion and attractive pairwise interactions between
agents. We derive the bifurcation structure for emergence of different
swarming behaviors in the mean field as a function of physical parameters and
verify these results through simulation.

## Note to Practitioners

Our research deals with understanding the emerging behaviors of groups of
simple, interacting agents. The motivation for studying this subject is
twofold: first, understanding the mechanisms that govern collective motions of
biological organisms in processes like wound healing, cancer growth, flocking
and herding, etc. Second, the application of our insights to synthesis of
controllers for swarms of autonomous robotic agents to perform surveillance or
monitoring in uncertain environments. Swarming behavior is typically modeled
for groups of identical agents, under the assumption that sensing and
processing times are negligibly small. We incorporate the real-world
complications of (1) finite sensing/processing time, which appears as a delay
in our model of agent motion, and (2) differences in the dynamical
capabilities of swarming agents. We conduct a theoretical analysis of the
collective motions of the swarm. We show the emergence of large-scale patterns
in the swarm motion as a function of the physical parameters or the swarm, as
well as segregation of the agents into separate groups where all agents in a
given group have identical dynamics.

##  I Introduction

The dynamics of aggregates, or swarms, of interacting mobile agents form an
active area of study for biological, physical, and synthetic systems. Simple
rules of interaction between agents can lead to a wide range of complex
aggregate behaviors, even in the absence of leader agents and global motion
strategy [1]. The emergence of rich collective behaviors from simple
interactions is, in fact, a wide-spread phenomenon in many application
domains. In biology, the formation of aggregates is common on a wide range of
spatio-temporal scales, for organisms ranging from bacteria to fish to birds
and humans [2, 3, 4, 5, 6]. In robotics, aggregates of locally interacting
agents have been proposed as a means to create scalable sensor arrays for
surveillance and exploration [7, 8]; and for formation of reconfigurable modal
systems, in which a group of simple agents can be used to accomplish a task
that would be impossible for any agent individually, as in [9, 10, 11].

Understanding the dynamical characteristics of swarm behavior is essential for
algorithm design and implementation. There is a wide range of existing works
which model the dynamics of swarms on the level of individual agents [5, 6,
12, 4], as well as using continuum models [13, 14, 3]. It has been shown that,
under the right conditions, swarms converge to organized steady-state
behaviors; and furthermore, that environmental noise and/or processing delay
acting on agent dynamics can lead to formation of new steady-state motions, or
phase transitions between between co-existing steady states [15, 1, 16]. Noise
is used to model effects of environmental disturbance and unknown interaction
dynamics in robotic systems. Delays are important in biological modeling of
population dynamics, blood cell production, and genetic networks [17, 18, 19],
etc.; and in mathematical models of robot networks where communication and
processing delays must be taken into account [20].

Most existing works assume that the swarm is made up of agents with identical
dynamics. However, real-world swarms often include agents with varying
dynamical properties, which leads to new collective behaviors. In biological
systems, heterogeneity arises quite naturally when, for example, motion or
sensing capabilities in an age-structured swarm vary significantly with age. A
more striking example is that of of predator-prey interactions between a herd
of prey animals and an individual or small group of predators, where there are
distinct time-scale differences in the motion of predator and prey animals
[6]. Another systems where heterogeneity plays a significant role is the
segregation of intermingled cell types, as during growth and development of an
organism. It has been shown that segregation can be achieved simply by
introducing heterogeneity in intercell adhesion properties [21, 22], or by
increasing the intercell attraction between self-propelled cells of a single
type [23].

An approach based on the cell segregation model in [23] is used in [24] to
design a potential-based controller that achieves segregation in swarms of
self-propelled autonomous robots. Heterogeneity also appears in robotic
systems when individual robots with disparate capabilities are used together
to achieve a common goal, as in [11]. Certain robots in the swarm may lack
capabilities that are costly to implement. Stranieri et al [25], for example,
show that flocking behavior can be achieved when a fraction of the agents lack
the ability to align their velocities with those of their neighbors.
Additionally, heterogeneity may arise over time as some agents in the swarm
malfunction. For example, [26] introduces an observer to judge the overall
“health” of a swarm, as individual agents lose speed from energy dissipation.

In this paper we carry out a systematic analysis of the motion of a swarm
composed of heterogeneous agents, using the methodology outlined in [1]. We
extend the model in [1] and analyze the dynamical behaviors of a heterogeneous
swarm of delay-coupled agents, where the swarm is divided into two distinct
populations with different motion capabilities. The inspiration for our model
comes from the idea of using swarms of autonomous mobile agents as sensor
platforms to survey/monitor an area of interest. Such agents may have
different dynamical properties if, for example, some agents but not others are
equipped with a particular sensor package that interferes with their motion.
The package may be too expensive or otherwise impractical to mount on all
swarm agents. Overall, allowing for heterogeneity in dynamical behaviors of
swarm agents gives greater flexibility in system design, and is therefore
desirable not only from a theoretical but also from a practical point of view.

The research presented here gives a general approach of modeling and analysis
that can be used to understand the effects of individual agent dynamics on the
collective motion of swarms. We know that swarms of self-propelled delay-
coupled agents exhibit self-ordering and pattern formation, and that the
collective patterns formed depend on the model parameters [15, 1];
furthermore, we observe in simulation that heterogeneity in the swarm
composition leads to segregation of the individual swarm populations. We will
show how collective motion patterns (translation, ring formation, and rotation
about a common center of mass) and segregation of individual populations
emerge in a basic but general swarming model.

##  II Problem Statement

Consider a swarm of delay-coupled self-propelled agents, or robots, comprised
of two distinct populations (1 and 2), following a single motion strategy, but
with heterogeneous dynamics. The agents in Population 2 are less
“maneuverable” in the sense that they are not able to accelerate as rapidly as
those in Population 1. This setup models co-deployment of small, fast agents,
and larger, slower agents in a given area. Let $\kappa_{1}$ and $\kappa_{2}$
be the inverse mass of agents in Populations 1 and 2, respectively. We scale
units so that $\kappa_{1}=1$ and $\kappa_{2}=\kappa\in(0,1)$.

Let $r_{i}^{k}\in\mathbb{R}^{2}$ denote the position of the $i^{\rm th}$ agent
in Population $k$ ($k=1,2$); let $N_{1}$ and $N_{2}$ denote the number of
agents in Populations 1 and 2, respectively; and let $N=N_{1}+N_{2}$ be the
total number of agents in the swarm. The agents have self-propulsion and are
globally attracted to each other in a symmetric fashion, with coupling
coefficient $a$, however, there is a delay $\tau$ in sensing of agent
positions. For notational convenience, we introduce the following notation:
let $\kappa_{1}=1$ and $\kappa_{2}=\kappa$. The motion of the agents is
governed by the following set of delay differential equations (dots denote
differentiation with respect to time):

$\displaystyle\ddot{r}^{1}_{i}$
$\displaystyle=\kappa_{1}\left(1-\left\|\,\dot{r}^{1}_{i}\,\right\|\right)^{2}\dot{r}^{1}_{i}$
(1a) $\displaystyle\qquad-\frac{a\kappa_{1}}{N}\Bigg{(}\sum_{j\neq
i,j=1}^{N_{1}}(r^{1}_{i}(t)-r^{1}_{j}(t-\tau))$
$\displaystyle\qquad+\sum_{j=1}^{N_{2}}(r^{1}_{i}(t)-r^{2}_{j}(t-\tau))\Bigg{)}$
$\displaystyle\ddot{r}^{2}_{i}$
$\displaystyle=\kappa_{2}\left(1-\left\|\,\dot{r}^{2}_{i}\,\right\|\right)^{2}\dot{r}^{2}_{i}$
(1b)
$\displaystyle\qquad-\frac{a\kappa_{2}}{N}\Bigg{(}\sum_{j=1}^{N_{1}}(r^{2}_{i}(t)-r^{1}_{j}(t-\tau))$
$\displaystyle\qquad+\sum_{j\neq
i,j=1}^{N_{2}}(r^{2}_{i}(t)-r^{2}_{j}(t-\tau))\Bigg{)}.$

The first term in the above equations represents the self-propulsion of swarm
agents, while the second models pairwise attraction between all agents in the
swarm. This simplified model does not include short-range repulsion or other
collision-avoidance strategies; however, earlier studies with homogeneous
swarms indicate that the collective dynamics of the swarm are not
significantly altered by the introduction of short-range repulsion terms.

The goal is now to characterize the steady-state motions of this system.
Following the approach in [1], we begin by considering the dynamics in the
limit where the number of agents goes to infinity.

##  III Mean-Field approximation

Since basic collective swarm motions. as observed in simulation, consist of
translation and rotation, the steady-state motions of the centers of mass of
the individual populations are a means to characterize the motion of the
overall group. Let $R^{1}$ and $R^{2}\in\mathbb{R}^{2}$ denote the position of
the centers of mass of Populations 1 and 2, respectively:

$R^{k}(t)=\frac{1}{N_{k}}\sum_{i=1}^{N_{k}}r^{k}_{i}(t),\quad k=1,2.$ (2)

As in [1], we assume that the deviations of the robots from the centers of
mass of their respective populations are small. We analyze the steady-state
motions of the swarm in the limit as $N_{k}\rightarrow\infty$ for $k=1,2$.

The positions of the agents in each population can be written relative to the
respective center of mass as

$r^{k}_{i}(t)=R^{k}(t)+\delta r^{k}_{i}(t).$ (3)

Note that

$\sum_{i=1}^{N_{1}}\delta r^{1}_{i}(t)=\sum_{i=1}^{N_{2}}\delta
r^{2}_{i}(t)=0.$ (4)

For convenience, we introduce the notation

$\bar{k}=\begin{cases}2&\quad\text{for }k=1\\\ 1&\quad\text{for
}k=2.\end{cases}$ (5)

Substituting (3) into (1a) and simplifying the resulting expression using (4)
allows us to write the equations of motion in terms of $R^{k}$ and $\delta
r^{k}$:

$\begin{split}\ddot{R}^{k}+\delta\ddot{r}^{k}_{i}&=\kappa_{k}\left(1-\left\|\,\dot{R}^{k}+\delta\dot{r}^{k}_{i}\,\right\|^{2}\right)(\dot{R}^{k}+\delta\dot{r}^{k}_{i})\\\
&\quad-\frac{a\kappa_{k}}{N}\big{(}(N_{k}-1)(R^{k}(t)-R^{k}(t-\tau)\\\
&\quad+\delta r^{k}_{i}(t))+\delta r^{k}_{i}(t-\tau)\\\
&\quad+N_{\bar{k}}(R^{k}(t)-R^{\bar{k}}(t-\tau)+\delta
r^{k}_{i}(t))\big{)}.\end{split}$ (6)

Summing the equations for $\delta r^{k}_{i}$ over $i=1,\ldots,N_{k}$, and
dividing through by $N_{k}$, we get the equation of motion for the centers of
mass of Population $k$:

$\begin{split}\ddot{R}^{k}&=\kappa_{k}\left(1-\left\|\,\dot{R}^{k}(t)\,\right\|^{2}\right)\dot{R}^{k}(t)\\\
&\quad-\frac{\kappa_{k}}{N_{k}}\sum_{i=1}^{N_{k}}\Bigg{(}\left\|\,\delta\dot{r}^{k}_{i}\,\right\|^{2}\dot{R}^{k}(t)\\\
&\quad+\left[\left\|\,\delta\dot{r}^{k}_{i}(t)\,\right\|^{2}+2\langle\dot{R}^{k}(t),\,\delta
r^{k}_{i}(t)\rangle\right]\delta r^{k}_{i}(t)\Bigg{)}\\\
&\quad-\frac{a\kappa_{k}}{N}\Big{(}(N-1)R^{k}(t)\\\
&\quad-(N_{k}-1)R^{k}(t-\tau)-N_{\bar{k}}R^{\bar{k}}(t-\tau)\Big{)},\end{split}$
(7)

where $\langle\cdot,\cdot\rangle$ denotes the dot product in $\mathbb{R}^{2}$.

We now take the limit $N\rightarrow\infty$, while keeping the fraction of
agents in Population 1,

$c=N_{1}/N,$ (8)

constant. Under the assumption of small deviations of the agents from the
centers of mass of the respective populations, terms in $\delta r^{k}_{i}$ can
be neglected. We get the following equations for the motion of the center of
mass of Population $k$ ($k=1,2$):

$\begin{split}\ddot{R}^{k}&=\kappa_{k}\left(1-\left\|\,\dot{R}^{k}(t)\,\right\|^{2}\right)\dot{R}^{k}(t)\\\
&\quad-a\kappa_{k}\Big{(}R^{k}(t)-cR^{1}(t-\tau)-(1-c)R^{2}(t-\tau)\Big{)}.\end{split}$
(9)

Let $[X_{k},Y_{k}]=R^{k}$ and $[U_{k},V_{k}]=\dot{R}^{k}$ denote,
respectively, the position and velocity of the center of mass of population
$k=1,2$. Let superscript $\tau$ denote a delay $\tau$, so that
$X^{\tau}(t)=X(t-\tau)$. The equations of motion can be written in terms of
$X_{k}$, $Y_{k}$, $U_{k}$, and $V_{k}$ as

$\displaystyle\dot{X}_{k}$ $\displaystyle=U_{k}$ (10a)
$\displaystyle\dot{Y}_{k}$ $\displaystyle=V_{k}$ (10b)
$\displaystyle\dot{U}_{k}$
$\displaystyle=\kappa_{k}(1-U_{k}^{2}-V_{k}^{2})U_{k}$
$\displaystyle\qquad-a\kappa_{k}(X_{k}-cX_{1}^{\tau}-(1-c)X_{2}^{\tau})$ (10c)
$\displaystyle\dot{V}_{k}$
$\displaystyle=\kappa_{k}(1-U_{k}^{2}-V_{k}^{2})V_{k}$
$\displaystyle\qquad-a\kappa_{k}(Y_{k}-cY_{1}^{\tau}-(1-c)Y_{2}^{\tau}).$
(10d)

The system in (10) has an invariant stationary solution given by

$\begin{split}X_{1}=X_{2}=X_{0},&\qquad Y_{1}=Y_{2}=Y_{0}\\\
U_{1}=U_{2}=0,&\qquad V_{1}=V_{2}=0,\end{split}$ (11)

as well as a translating solution where the center of mass travels in a
straight line at constant velocity.

###  III-A Bifurcation of the stationary solution

About the stationary solution, the system exhibits a number of Hopf
bifurcations for different values of the parameters $a$, $c$, $\kappa$, and
$\tau$. To find the locations of these bifurcation points, consider the
linearization of the dynamics (10) about the stationary solution (without loss
of generality, we choose $X_{0}=Y_{0}=0$). The linearized dynamics are

$\displaystyle\dot{X}_{k}$ $\displaystyle=U_{k}$ (12a)
$\displaystyle\dot{Y}_{k}$ $\displaystyle=V_{k}$ (12b)
$\displaystyle\dot{U}_{k}$
$\displaystyle=\kappa_{k}U_{k}-a\kappa_{k}\Big{(}X_{k}-cX_{1}^{\tau}-(1-c)X_{2}^{\tau}\Big{)}$
(12c) $\displaystyle\dot{V}_{k}$
$\displaystyle=\kappa_{k}V_{k}-a\kappa_{k}\Big{(}Y_{k}-cY_{1}^{\tau}-(1-c)Y_{2}^{\tau}\Big{)}.$
(12d)

Let $\xi=[X_{1},\,Y_{1},\,U_{1},\,V_{1},\,X_{2},\,Y_{2},\,U_{2},\,V_{2}]^{T}$.
The above system takes the form $\dot{\xi}=\mathcal{L}\xi$, where
$\mathcal{L}$ is a linear operator. Let $\nu$ denote an eigenvector of
$\mathcal{L}$; then a solution starting at $\nu$ can be expressed as
$e^{\lambda t}\nu$. This equation can only be satisfied if the matrix
$M(\lambda;a,c,\kappa,\tau)$ is singular, where $M=\lambda I-\mathcal{L}$.
That is, $\lambda$ must satisfy $0=\det M=D^{2}$, where

$\displaystyle D(\lambda;a,c,\kappa,\tau)$
$\displaystyle=(\lambda^{2}-\lambda+a)(\lambda^{2}-\kappa\lambda+a\kappa)$
$\displaystyle\quad-((\kappa+c-\kappa
c)\lambda^{2}-\kappa\lambda+a\kappa)ae^{-\lambda\tau}.$ (13)

Hopf bifurcations of the mean-field equations occur when ${\rm
Re}(\lambda)=0$. Setting $\lambda=i\omega$ gives
$D(i\omega;a,c,\kappa,\tau)=0$ which allows us to solve for parameter values
of where Hopf bifurcations occur. Solutions in terms of $a$ and $\tau$, for
different values of $c$ and $\kappa$, are shown by the solid blue lines in
Fig. 1.

(a) $\kappa=0.2$ and $c=0.2$

(b) $\kappa=0.6$ and $c=0.2$

(c) $\kappa=0.9$ and $c=0.2$

(d) $\kappa=0.2$ and $c=0.5$

(e) $\kappa=0.6$ and $c=0.5$

(f) $\kappa=0.9$ and $c=0.5$

(g) $\kappa=0.2$ and $c=0.7$

(h) $\kappa=0.6$ and $c=0.7$

(i) $\kappa=0.9$ and $c=0.7$

Figure 1: The solid blue lines show $\tau$ vs $a$ Hopf bifurcation curves for
the center-of-mass heterogeneous swarm dynamics, for different values of the
parameters $c$ and $\kappa$. The location of the pitchfork bifurcation where
the translating state disappears is shown by the dashed red curve. The point
where the Hopf curve intersects the pitchfork bifurcation curve is the
Bogdanov-Takens point. The “$\Delta$” and “+” in (b) show the points in
parameter space corresponding to the simulations in Fig. 2 and Fig. 4,
respectively.

Below the first Hopf bifurcation curve, the mean-field predicts a stationary
state which corresponds to a ring state in the full swarm dynamics. This is
similar to the ring state described in [1], where swarm agents circle about a
stationary center of mass in either direction, with constant radius and speed.
The first Hopf bifurcation in the mean-field approximation gives rise to a
rotating state analogous to the one in [1], in which the centers of mass of
the swarm populations rotate about a common stationary point. Higher-order
Hopf bifurcations lead to formation of rotating states with higher angular
frequency, but these states appear to be unstable, based on our simulations
with homogeneous swarms. The introduction of heterogeneity leads to a
separation between the agents in the two populations in both of these steady
state motions.

###  III-B Ring State

The ring state in the heterogeneous swarm is similar to that described in [1]
for homogeneous agent swarms; that is, agents move in either direction about a
stationary center of mass, with constant speed and radius. The heterogeneity
introduces a split in the rings formed by the agents of the two populations,
however, so that they become separated (see Fig. 2).

(a) $t=10.5$

(b) $t=31.5$

(c) $t=315$

Figure 2: Simulated swarm of $N=300$ agents, with $60$ agents in Population 1
(blue) and $240$ in Population 2 (red), converging to the ring state. In this
simulation, $\kappa=0.6$, $c=0.2$, $a=1.0$, and $\tau=2.1$. This point in
parameter space is marked by a “$\Delta$” in Fig. 1(b).

It can be shown that the angular frequency $\omega_{i}$ and radius $\rho_{i}$
of the particles in population $i=1,2$ satisfy

$\displaystyle\rho_{1}$ $\displaystyle=1/\sqrt{a}\quad\omega_{1}=\sqrt{a}$
(14) $\displaystyle\rho_{2}$
$\displaystyle=1/\sqrt{a\kappa}\quad\omega_{2}=\sqrt{a\kappa}$ (15)

(see Appendix Acknowledgments for details). Note that the radius for each
population depends only on the strength of the coupling constant and the
acceleration factor; that is, the radii of the two populations are not coupled
and are independent of the time delay $\tau$.

The above calculations were verified using a full-swarm simulation with 300
agents, and different values of the parameters $a$, $\kappa$, $c$, and $\tau$.
The results of comparing the ring radii and angular velocities obtained from
simulation and theory are shown in Fig. 3.

Figure 3: Comparison of theoretical and simulated radius and angular velocity
in the ring state. Theoretical values are shown by the solid lines, while
values obtained from simulations are shown by the red crosses. The simulations
were run for a swarm of $N=300$ agents, with fraction in Population 1 $c=0.2$
and time delay $\tau=1.0$.

###  III-C Rotating State

The rotating state, like the ring state, is also present in the case of a
homogeneous swarm [1]. In the rotating state, the swarm populations collapse
to their respective centers of mass and rotate about a common center point
with constant phase offset (see Fig. 4).

Figure 4: Swarm in the rotating state at $t=323.8$. Agents in Population 1 are
shown in blue, while those in Population 2 are in red. The dotted circle shows
the trajectory of the two swarm populations about a common stationary point.
The simulation was run with $N=300$ agents, with $N_{1}=60$ and $N_{2}=240$.
The parameter values are: $\kappa=0.6$, $c=0.2$, $a=1.0$, and $\tau=5.0$. This
point in parameter space is marked by a “+” in Fig. 1(b).

Our numerical simulations of the full swarm dynamics suggest that the radii of
the rotating populations are equal. Let $\rho$ denote the radius of the
rotating state, $\omega$ the angular frequency, and let
$\Delta\theta=\theta_{2}-\theta_{1}$ denote the phase offset. It can be shown
(see Appendix Acknowledgments for details) that these quantities must satisfy
the following relations:

$\displaystyle\sin\Delta\theta$
$\displaystyle=(2c-1)P(c,\kappa,\omega)\sin\omega\tau$ (16)
$\displaystyle\omega^{2}$ $\displaystyle=a\kappa\Big{[}1-\cos\omega\tau$ (17)
$\displaystyle\qquad+c((2c-1)\sin^{2}\omega\tau+\cos^{2}\omega\tau)P(c,\kappa,\omega)\Big{]}$
(18) $\displaystyle\rho$
$\displaystyle=\frac{\sqrt{1-a\left(1-2c(1-c)P(c,\kappa,\omega)\cos\omega\tau\right)\frac{\sin\omega\tau}{\omega}}}{|\omega|}.$
(19)

where

$P(c,\kappa)=\frac{(1-\kappa)(1-\cos\omega\tau)}{(1+k)c-1+2(1-\kappa)c(1-c)\sin^{2}\omega\tau}.$
(20)

The above relations may be used to derive theoretical values for the radius,
angular velocity, and phase offset between Populations 1 and 2. A comparison
of the theoretical values and those observed in full-swarm simulations is
shown in Fig. 5, for different values of the parameters $\kappa$, $c$, $a$,
and $\tau$. Note that the above relations, derived from the mean-field
approximation, give a good approximation to values obtained from the full
swarm simulation; however, in some cases, the use of the mean-field
approximation leads to significant error in computed values.

(a) Real vs. theoretical phase difference between the two swarm populations.

(b) Real vs. theoretical angular frequency for the rotating state.

(c) Real vs. theoretical radius of the rotating state.

Figure 5: Comparison of theoretical and simulated phase difference, angular
velocity, and radius in the rotating state. Theoretical values are along the
x-axis, while values obtained from simulations are along the y-axis. The
simulations were run for a swarm of 300 agents, for $\kappa=0.3,0.6,0.9$,
$c=0.2$, $a=0.5,1.0,2.0,4.0$, and $\tau=4.0,5.0$.

###  III-D Translating state

The system in (10) has a steady-state translating solution, where
$\dot{U}_{1}=\dot{U}_{2}=\dot{V}_{1}=\dot{V}_{2}=0$, $U_{1}=U_{2}=U_{0}$,
$V_{1}=V_{2}=V_{0}$, and

$\displaystyle X_{1}(t)=X_{2}(t)$ $\displaystyle=X_{0}+U_{0}t$ (21a)
$\displaystyle Y_{1}(t)=Y_{2}(t)$ $\displaystyle=Y_{0}+V_{0}t.$ (21b)

$U_{0}$ and $V_{0}$ must satisfy:

$U_{0}^{2}+V_{0}^{2}=1-a\tau,$ (22)

which is possible only if $a\tau\leq 1$. In fact, the system (10) has a
pitchfork bifurcation along the parameter-space curve $\tau=1/a$ (see Fig. 1),
where the stationary solution gives rise to the translating state (the other
branch of the pitchfork corresponds to an unphysical solution with imaginary
speed). The same bifurcation curve exists in the homogeneous system
($\kappa=1$) [1].

The point where the pitchfork bifurcation coincides with the first Hopf curve
is a Bogdanov-Takens (BT) point (see Fig. 1). In the homogeneous swarm case,
this point is located at $a=1/2$, $\tau=2$; for the heterogeneous swarm the
location of the point depends on the acceleration factor $\kappa$ and on the
fraction $c$ of agents in Population 1. The BT point is at

$\displaystyle a_{BT}$ $\displaystyle=\frac{\kappa}{2(1-c(1-\kappa))}$ (23)
$\displaystyle\tau_{BT}$ $\displaystyle=\frac{1}{a_{BT}}.$ (24)

The value of coupling coefficient at the Bogdanov-Takens point $a_{BT}$ as a
function of $\kappa$ and $c$ is shown in Fig. 6.

Figure 6: Contour plot of the coupling coefficient at the Bogdanov-Takens
point $a_{BT}$ as a function of $\kappa$ and $c$. Different values of $a_{BT}$
are shown by the colors (see colorbar on the right).

##  IV Conclusion

In this paper we have analyzed the collective motions of a swarm of delay-
coupled heterogeneous agents. The swarm motions are characterized by the
emergence of large-scale patterns (translation, ring formation, and rotation),
and the automatic segregation of populations of agents with different
dynamical properties. Separation of the swarm into distinct populations is a
direct consequence of swarm heterogeneity, and is not observed under
homogeneous swarm dynamics.

The patterns observed in simulation were shown to arise in the motions of the
swarm center of mass, in the limit as the number of agents in each population
goes to infinity. We derive expressions for the speed of the swarm in the
translating state as a function of time delay and coupling coefficient; for
the radii and angular velocities of both agent populations in the ring and
rotating states; and for the fixed phase offset between populations in the
rotating state. We have verified these calculations with simulations of the
full-swarm dynamics. In spite of discrepancies, it is remarkable that our
model reduction, which starts with $N$ second-order delay-differential
equations and yields one equation of the same type, is able to quantitatively
capture so many aspects of the full swarm dynamics.

A real-world model of swarming physical agents must incorporate a collision-
avoidance strategy. This could be implemented, for example, by adding a short-
range repulsion to the agent dynamics. Such interactions may affect the
collective motion of the swarm to some degree, but our preliminary simulations
of homogeneous swarms indicates that the qualitative behavior of the swarm is
not affected by short-range repulsion forces. This will be addressed more
carefully in a future paper.

In our model, we have assumed that the motion of each agent in the swarm
depends on the positions of all other agents. In future work, we will relax
this assumption to model the effects of non-global coupling on the collective
swarm motion; we will also add noise to the swarm dynamics. We know that
adding noise causes switching between co-existing stable states (ring and
rotating state) in homogeneous swarms [1]. We will investigate how switching
behavior changes when the swarm is made up of heterogeneous agents.

Our work presents new insights into the collective motions of aggregates of
heterogenous, self-propelled agents, whether biological or artificial. Our
results are important from a practical design standpoint for artificial
systems, as when a swarm of robots is used to survey/monitor a given area of
interest. In addition to their relevance in the study of swarming and herding
motions in biological systems, our results on heterogeneity play a predictive
role where the dynamics of individual agents are to large degree beyond our
control.

## Acknowledgments

This research was performed while KS held a National Research Council Research
Associateship Award at the U.S. Naval Research Laboratory. This research is
funded by the Office of Naval Research contract no. N0001412WX2003 and the
Naval Research Laboratory 6.1 program contract no. N0001412WX30002.

[Ring State]

In the ring state, the agents in either population rotate about a common
stationary center of mass. To study the dynamics of the ring state, we must
therefore re-introduce the full swarm dynamics. For convenience, we express
these in polar coordinates, with the origin located at the position of the
stationary center of mass, so that $R^{1}(t)=R^{2}(t)\equiv 0$. Then let

$\rho_{i}^{1}k=\left\|\,\delta
r_{i}^{k}\,\right\|,\quad\theta_{i}^{k}=\angle\delta r_{i}^{k}$ (25)

for $k=1,2$. Setting $R^{k}=\dot{R}^{k}=\ddot{R}^{k}=0$ in (6) gives:

$\begin{split}\delta\ddot{r}_{i}^{k}=\frac{\kappa_{k}}{N_{k}}\sum_{j=1}^{N_{k}}\left\|\,\delta\dot{r}_{j}^{k}\,\right\|^{2}\delta\dot{r}_{j}^{k}+\kappa_{k}\left(1-\left\|\,\delta\dot{r}_{i}^{k}\,\right\|^{2}\right)\delta\dot{r}_{i}^{k}\\\
\qquad-\frac{a\kappa_{k}}{N}\left((N-1)\delta r_{i}^{k}+\delta
r_{i}^{k,\tau}\right).\end{split}$ (26)

In the ring state, $R^{k}=\dot{R}^{k}=\ddot{R}^{k}=0$ requires that
$\sum_{j=1}^{N_{k}}\left\|\,\delta\dot{r}_{j}^{k}\,\right\|^{2}\delta\dot{r}_{j}^{k}=0$
for $k=1,\,2$ [1]; so that, in the limit as $N\rightarrow\infty$,

$\delta\ddot{r}_{i}^{k}=\kappa_{k}\left(1-\left\|\,\delta\dot{r}_{i}^{k}\,\right\|^{2}\right)\delta\dot{r}_{i}^{k}-a\kappa_{k}\delta
r_{i}^{k}.$ (27)

Converting to polar coordinates leads to the following set of equations:

$\ddot{\rho}_{i}^{k}=\kappa_{k}\dot{\rho}_{i}^{k}\Big{(}1-(\rho_{i}^{k}\dot{\theta}_{i}^{k})^{2}-(\dot{\rho}_{i}^{k})^{2}\Big{)}+\Big{(}(\dot{\theta}_{i}^{k})^{2}-a\Big{)}\rho_{i}^{k}$
(28a)
$\rho_{i}^{k}\ddot{\theta}_{i}^{k}=\kappa_{k}\rho_{i}^{k}\theta_{i}^{k}\Big{(}1-(\rho_{i}^{k}\dot{\theta}_{i}^{k})^{2}-(\dot{\rho}_{i}^{k})^{2}\Big{)}-2\dot{\rho}_{i}^{k}\dot{\theta}_{i}^{k}.$
(28b)

Note that the equations governing the two populations are entirely uncoupled.
In the ring state, $\dot{\rho}_{i}^{k}=\ddot{\rho}_{i}^{k}=0$ and the agents
move with constant angular velocity so that $\ddot{\theta}_{i}^{k}=0$ for
$k=1,2$. Let $\omega_{i}^{k}$ denote the constant angular velocity
$\dot{\theta}_{i}^{k}$ of agent $i$ in population $k$. Then (28) can be
written as:

$\displaystyle 0$
$\displaystyle=\left((\omega_{i}^{k})^{2}-a\kappa_{k}\right)\rho_{i}^{k}$
(29a) $\displaystyle 0$
$\displaystyle=\rho_{i}^{k}\omega_{i}^{k}\left(1-(\rho_{i}^{k}\omega_{i}^{k})^{2}\right),$
(29b)

and it follows that

$\rho_{i}^{k}=1/|\omega_{i}^{k}|,\quad\omega_{i}^{k}=\pm\sqrt{a\kappa_{k}}$
(30)

for all agents in the swarm.

[Rotating State]

To find the parameters describing the rotating state of the swarm, we convert
the equations for the swarm dynamics to polar coordinates. Suppose that the
ring state is formed about the stationary point
$(X_{s},Y_{s})^{T}\in\mathbb{R}^{2}$, and choose the origin of the polar
coordinates to lie on $(X_{s},Y_{s})^{T}$. Let $(\rho_{k},\theta_{k})$ denote
the position, in polar coordinates, of the center of mass of Population $k$,
that is

$\displaystyle\rho_{k}$
$\displaystyle=\sqrt{(X_{k}-X_{s})^{2}+(Y_{k}-Y_{s})^{2}}$ (31a)
$\displaystyle\theta_{k}$
$\displaystyle=\tan^{-1}\frac{Y_{k}-Y_{s}}{X_{k}-X_{s}}.$ (31b)

The equations of motions for the motion of the centers of mass of the two
swarm populations in polar coordinates, are

$\displaystyle\begin{split}\ddot{\rho}_{k}&=\kappa_{k}\Big{(}1-\rho_{k}^{2}\dot{\theta}_{k}^{2}-\dot{\rho}_{k}^{2}\Big{)}\dot{\rho}_{k}+\rho_{k}\dot{\theta}_{k}^{2}\\\
&\qquad-a\kappa_{k}\Big{(}\rho_{k}-c\rho_{1}^{\tau}\cos(\theta_{k}-\theta_{1}^{\tau})\\\
&\qquad\qquad\qquad-(1-c)\rho_{2}^{\tau}\cos(\theta_{k}-\theta_{2}^{\tau})\Big{)}\end{split}$
(32a)
$\displaystyle\begin{split}\rho_{k}\ddot{\theta}_{k}&=\kappa_{k}\Big{(}1-\rho_{k}^{2}\dot{\theta}_{k}^{2}-\dot{\rho}_{k}^{2}\Big{)}\rho_{k}\dot{\theta}_{k}-2\dot{\rho}_{k}\dot{\theta}_{k}\\\
&\qquad-a\kappa_{k}\Big{(}c\rho_{1}^{\tau}\sin(\theta_{k}-\theta_{1}^{\tau})\\\
&\qquad\qquad\qquad+(1-c)\rho_{2}^{\tau}\sin(\theta_{k}-\theta_{2}^{\tau})\Big{)}.\end{split}$
(32b)

In the rotating state, the radii of the populations and the angular
frequencies are constant. Let $\omega_{k}=\dot{\theta}_{k}$. Then

$\displaystyle\rho_{k}(t)$ $\displaystyle=\rho_{k}^{0}$ (33a)
$\displaystyle\theta_{k}(t)$ $\displaystyle=\theta_{k}^{0}+\omega_{k}t,$ (33b)

and $\ddot{\rho}_{k}=\dot{\rho}_{k}=\ddot{\theta}_{k}=0$. Furthermore,
simulations of the full swarm dynamics suggest that the radii of the two
populations in the rotating state are equal; we therefore set
$\rho_{1}^{0}=\rho_{2}^{0}=\rho$. Let $\Delta\theta=\theta_{1}-\theta_{2}$
denote the phase difference between the two populations. Substituting these
equations into (32) and simplifying the resulting expressions gives:

$\begin{split}\omega_{k}^{2}&=a\kappa_{k}\big{(}1-c\cos(\omega_{1}\tau+(\omega_{k}-\omega_{1})t+\theta_{k}^{0}-\theta_{1}^{0})\\\
&\qquad-(1-c)\cos(\omega_{2}\tau+(\omega_{k}-\omega_{2})t+\theta_{k}^{0}-\theta_{2}^{0})\big{)}\end{split}$
(34a)
$\begin{split}(1-\rho^{2}\omega_{k}^{2})\omega_{k}&=a\kappa_{k}\big{(}c\sin(\omega_{1}\tau+(\omega_{k}-\omega_{1})t+\theta_{k}^{0}-\theta_{1}^{0})\\\
&+(1-c)\sin(\omega_{2}\tau+(\omega_{k}-\omega_{2})t+\theta_{k}^{0}-\theta_{2}^{0})\big{)}.\end{split}$
(34b)

Note that the time dependence on the right hand sides of all equations in (34)
can be eliminated if and only if $\omega_{1}=\omega_{2}$. Let $\omega$ denote
the common frequency of both populations about the center. Thus, we finally
have the four equations describing the behavior of the swarm in the ring
state:

$\begin{split}\omega^{2}&=a\kappa_{k}\big{(}1-c\cos(\omega\tau+\theta_{k}^{0}-\theta_{1}^{0})\\\
&\qquad-(1-c)\cos(\omega\tau+\theta_{k}^{0}-\theta_{2}^{0})\big{)}\end{split}$
(35a)
$\begin{split}(1-\rho^{2}\omega^{2})\omega&=a\kappa_{k}\big{(}c\sin(\omega\tau+\theta_{k}^{0}-\theta_{1}^{0})\\\
&\qquad+(1-c)\sin(\omega\tau+\theta_{k}^{0}-\theta_{2}^{0})\big{)}.\end{split}$
(35b)

Relations (16)-(19) can be derived from (35) through some rather involved
algebraic manipulations.

## References

  * [1] L. Mier-y-Teran Romero, E. Forgoston, and I. B. Schwartz, “Coherent Pattern Prediction in Swarms of Delay-Coupled Agents,” IEEE Transactions on Robotics, vol. 28, pp. 1034–1044, Oct. 2012.
  * [2] E. O. Budrene and H. C. Berg, “Dynamics of formation of symmetrical patterns by chemotactic bacteria,” Nature, vol. 376, pp. 49–53, 1995.
  * [3] A. A. Polezhaev, R. A. Pashkov, A. I. Lobanov, and I. B. Petrov, “Spatial patterns formed by chemotactic bacteria Escherichia coli,” The International journal of developmental biology, vol. 50, pp. 309–314, Jan. 2006\.
  * [4] K. r. Tunstrø m, Y. Katz, C. C. Ioannou, C. Huepe, M. J. Lutz, and I. D. Couzin, “Collective states, multistability and transitional behavior in schooling fish,” PLoS computational biology, vol. 9, p. e1002915, Jan. 2013.
  * [5] D. Helbing and P. Molnar, “Social force model for pedestrian dynamics,” Physical Review E, vol. 51, no. 5, pp. 4282–4286, 1995.
  * [6] S.-H. Lee, “Predator’s attack-induced phase-like transition in prey flock,” Physics Letters A, vol. 357, pp. 270–274, Sept. 2006.
  * [7] P. Bhatta, E. Fiorelli, F. Lekien, N. E. Leonard, D. A. Paley, F. Zhang, R. Bachmayer, D. M. Fratantoni, R. E. Davis, and R. J. Sepulchre, “Coordination of an underwater glider fleet for adaptive sampling,” in Proceedings of the International Workshop on Underwater Robotics, no. August, pp. 61–69, 2005.
  * [8] W. Wu and F. Zhang, “Cooperative exploration of level surfaces of three dimensional scalar fields,” Automatica, vol. 47, pp. 2044–2051, Sept. 2011.
  * [9] K. M. Lynch, I. B. Schwartz, P. Yang, and R. A. Freeman, “Decentralized Environmental Modeling by Mobile Sensor Networks,” IEEE Transactions on Robotics, vol. 24, pp. 710–724, June 2008.
  * [10] S. Kar and J. M. F. Moura, “Distributed linear parameter estimation in sensor networks: Convergence properties,” Oct. 2008.
  * [11] M. Dorigo, D. Floreano, L. M. Gambardella, F. Mondada, S. Nolfi, T. Baaboura, M. Birattari, M. Bonani, M. Brambilla, A. Brutschy, D. Burnier, A. Campo, A. L. Christensen, A. Decugniere, G. Di Caro, F. Ducatelle, E. Ferrante, A. Forster, J. M. Gonzales, J. Guzzi, V. Longchamp, S. Magnenat, N. Mathews, M. Montes de Oca, R. O’Grady, C. Pinciroli, G. Pini, P. Retornaz, J. Roberts, V. Sperati, T. Stirling, A. Stranieri, T. Stutzle, V. Trianni, E. Tuci, A. E. Turgut, and F. Vaussard, “Swarmanoid: A Novel Concept for the Study of Heterogeneous Robotic Swarms,” IEEE Robotics & Automation Magazine, vol. 20, pp. 60–71, Dec. 2013.
  * [12] T. Vicsek, A. Czirok, E. Ben-Jacob, I. Cohen, and O. Shochet, “Novel type of phase transition in a system of self-driven particles,” 2006.
  * [13] L. Edelstein-Keshet, D. Grunbaum, and J. Watmough, “Do travelling band solutions describe cohesive swarms? An investigation for migratory locusts,” Journal of Mathematical Biology, vol. 36, pp. 515–549, July 1998.
  * [14] C. M. Topaz and A. L. Bertozzi, “Swarming Patterns in a Two-Dimensional Kinematic Model for Biological Groups,” SIAM Journal on Applied Mathematics, vol. 65, pp. 152–174, Jan. 2004.
  * [15] L. Mier-y-Teran Romero, E. Forgoston, and I. B. Schwartz, “Noise, Bifurcations, and Modeling of Interacting Particle Systems,” in Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 3905–3910, Jan. 2011.
  * [16] B. S. Lindley, L. Mier-y-Teran Romero, and I. B. Schwartz, “Noise Induced Pattern Switching in Randomly Distributed Delayed Swarms,” in Proc. 2013 American Control Conference (ACC 2013), pp. 4587–4591, 2013.
  * [17] A. Martin and S. Ruan, “Predator-prey models with delay and prey harvesting,” Journal of Mathematical Biology, vol. 43, pp. 247–267, Sept. 2001.
  * [18] S. Bernard, J. Bélair, and M. C. Mackey, “Bifurcations in a white-blood-cell production model,” Comptes Rendus Biologies, vol. 327, pp. 201–210, Mar. 2004.
  * [19] N. A. M. Monk, “Oscillatory Expression of Hes1, p53, and NF-kB Driven by Transcriptional Time Delays,” Current Biology, vol. 13, pp. 1409–1413, 2003.
  * [20] E. Forgoston and I. B. Schwartz, “Delay-induced instabilities in self-propelling swarms,” Physical Review E, vol. 77, no. 302, p. 035203, 2008.
  * [21] M. S. Steinberg, “Reconstruction of Tissues by Dissociated Cells,” Science, vol. 141, pp. 401–408, Aug. 1963.
  * [22] F. Graner, “Simulation of the differential adhesion driven rearrangement of biological cells,” Physical Review E, vol. 47, no. 3, pp. 2128–2154, 1993\.
  * [23] J. Belmonte, G. Thomas, L. Brunnet, R. de Almeida, and H. Chaté, “Self-Propelled Particle Model for Cell-Sorting Phenomena,” Physical Review Letters, vol. 100, p. 248702, June 2008.
  * [24] M. Kumar, D. P. Garg, and V. Kumar, “Segregation of Heterogeneous Units in a Swarm of Robotic Agents,” IEEE Transactions on Automatic Control, vol. 55, no. 3, pp. 743–748, 2010.
  * [25] A. Stranieri, E. Ferrante, A. E. Turgut, V. Trianni, C. Pinciroli, M. Birattari, and M. Dorigo, “Self-Organized Flocking with a Heterogeneous Mobile Robot Swarm,” in Advances in Artificial Life, ECAL 2011: 11th European Conference on the Synthesis and Simulation of Living Systems, no. 2002, pp. 789–796, 2010.
  * [26] P. M. Kingston, M. Egerstedt, and E. I. Verriest, “Health monitoring of networked systems,” in Mathematical Theory of Networked Systems (MTNS), 2008.