# Intelligent Known and Novel Aircraft Recognition - A Shift from
Classification to Similarity Learning for Combat Identification

Ahmad Saeeda, Haasha Bin Atifa, Usman Habiba, Mohsin Bilala,b
aDepartment of Artificial Intelligence & Data Science
National University of Computer and Emerging Sciences, Islamabad, Pakistan
bCollege of Computer Engineering and Sciences
Prince Sattam Bin Abdulaziz University, Al-Kharj, Saudi Arabia
{I212281, haasha.atif, usman.habib<EMAIL_ADDRESS>
###### Abstract

Precise aircraft recognition in low-resolution remote sensing imagery is a
challenging yet crucial task in aviation, especially combat identification.
This research addresses this problem with a novel, scalable, and AI-driven
solution. The primary hurdle in combat identification in remote sensing
imagery is the accurate recognition of Novel/Unknown types of aircraft in
addition to Known types. Traditional methods, human expert-driven combat
identification and image classification, fall short in identifying Novel
classes. Our methodology employs similarity learning to discern features of a
broad spectrum of military and civilian aircraft. It discerns both Known and
Novel aircraft types, leveraging metric learning for the identification and
supervised few-shot learning for aircraft type classification.To counter the
challenge of limited low-resolution remote sensing data, we propose an end-to-
end framework that adapts to the diverse and versatile process of military
aircraft recognition by training a generalized embedder in fully supervised
manner.Comparative analysis with earlier aircraft image classification methods
shows that our approach is effective for aircraft image classification
(F1-score Aircraft Type of $0.861$) and pioneering for quantifying the
identification of Novel types (F1-score Bipartitioning of $0.936$). The
proposed methodology effectively addresses inherent challenges in remote
sensing data, thereby setting new standards in dataset quality. The research
opens new avenues for domain experts and demonstrates unique capabilities in
distinguishing various aircraft types, contributing to a more robust, domain-
adapted potential for real-time aircraft recognition.

###### Index Terms:

Aircraft, Bipartitioning, Combat Identification(CID), Embedder, Few shot
learning, Novel class, Remote Sensing (RS), Recognition, Youden Index

##  I Introduction

Figure 1: Flow Diagram from left to Right showing a)Traditional CID , b) Image
classification & c) Intelligent Known and Novel Aircraft Recognition (INNAR)
to find Known and Novel class

Aircraft recognition in remote sensing imagery presents a far-reaching
challenge due to its wide-ranging applications, encompassing border security
surveillance, emergency response, disaster management, air traffic control,
environmental monitoring, maritime surveillance, counter-terrorism efforts and
critical asset security. The principal challenge of combat identification
(CID) [2, 27] stems from the need to identify and label potential targets as
friend, foe, or neutral aircraft, a task of considerable practical importance.
The primary hurdle in CID is the accurate recognition of Novel/Unknown classes
of aircraft in addition to Known aircraft types (or classes). Recognition
hinges on distinguishing Known classes from Novel classes (unfamiliar/disjoint
types). The former represents established types encountered during training,
while the latter poses challenges due to the model’s lack of explicit
training. Traditional methods, such as human expert-driven CID (Figure 1-a,
and image classification-based aircraft recognition (Figure 1-b, fall short in
identifying Novel classes. This paper presents a pioneering methodology termed
’Intelligent kNown and Novel Aircraft Recognition (INNAR)’ illustrated in
Figure 1-c. This innovative approach signifies a paradigm shift from
traditional image classification to similarity learning, with the objective of
automating CID. It facilitates the recognition of both Known and Novel
aircraft, thereby setting a new benchmark in CID.

Incorporating deep learning into CID processes enhances pattern analysis and
image recognition [8], improving accuracy and speed in large, diverse
datasets. Recognizing various aircraft, especially Novel classes, extends
beyond standard image classification tasks. The primary challenge lies in the
continuous introduction of new, unknown aircraft into fleets. Limited training
data, diverse designs, dynamic appearance changes, and intra-class variability
increase remote sensing imagery complexity. These challenges necessitate
advance deep learning (DL) models to adapt to evolving aircraft technology,
sparse and noisy data, and the absence of comprehensive contextual
information.

Figure 2:  MTARSI-INNAR [23] Embedder Training Set Showcasing Remote Sensing
Military & Civil Aircraft highlighting Remote Sensing challenges as
illumination conditions,orientation, background, noise and capturing angles.

To this end, we are proposing INNAR, a transformative approach that redefines
the solution to the CID problem. This approach integrates a generalized
aircraft embedder and similarity learning within an end-to-end deep learning
framework, enabling efficient aircraft recognition with minimal training data.
Current state-of-the-art multi-classification algorithms [22, 19, 37],[14] can
predict classes based on learned patterns from training data, but fall short
as a comprehensive solution to the CID problem. Section II further discusses
the literature available on aircraft classification. As depicted in Figure 1,
traditional CID approaches are limited to predicting classes within the domain
of input training embedding, whether derived from live or offline streams. In
contrast, an automated CID solution necessitates a data-efficient,
generalizable, and robust approach that can recognize brand-new (few-shot
samples and Novel classes) aircraft types, even when they are absent in the
training data but present in the target fleet. This approach eliminates the
need for re-training or fine-tuning of the image embedder, thereby advancing
the state-of-the-art in CID.

$d(\mathbf{x},\mathbf{y})=\left(\sum_{i=1}^{n}|x_{i}-y_{i}|^{p}\right)^{\frac{1}{p}}$
(1)

Equation 1 assesses vector proximity ($\mathbf{x}$ and $\mathbf{y}$) in a
specified vector space. Parameter $p$ denotes the norm type, defining distance
metrics like Manhattan ($L1$) and Euclidean ($L2$). These feature vectors
undergo processing through fully connected layers, utilizing similarity
metrics crucial for security applications. The focus lies in discerning
aircraft features, especially in few-shot learning. Our proposed method excels
in identifying novel classes and integrates state-of-the-art techniques to
create an embedding space, effectively distinguishing between Known and Novel
classes. Section III explains INNAR and its empirical evaluation.

Moreover, remote sensing imagery poses unique challenges and characteristics
when compared to optical [13],[16] [20] and medical images [5, 4, 1]. These
distinctions arise from inherent complexities, including diverse environmental
settings, limitations imposed by satellite sensors, fluctuating weather
conditions, and noisy datasets as highlighted in these studies [38, 9]. In
this study, we worked with the Multi-Type Aircraft Remote Sensing Images
(MTARSI) dataset [21], Figure 2 & 3 show a few samples of all aircraft types
from training and testing sets showcasing diversity in capturing angles and
simulating scenarios. MTARSI is the only dataset for aircraft recognition, but
contains several errors and issues related to class labeling and cross-
contamination. We have performed a thorough evaluation and cleaning of the
MTARSI dataset [33] by involving input from field experts (pilots) and
satellite imagery analysis. This process aimed to conclusively address class
labeling and cross-contamination issues, as highlighted in Figure 2. Our
refined techniques not only reduce errors but also facilitate a precise,
unambiguous interpretation of the dataset, thereby establishing a new
benchmark for technical precision in data processing. Section IV describes the
dataset evaluation and cleaning procedure in detail.

Figure 3:  MTARSI-INNAR [23] Novel Testing Set highlighting unique classes
covering role and features as Fighter, ISR, Transport, Surveillance and Multi-
Mission Platforms.

Our INNAR approach is a novel method that effectively integrates a
thresholding technique in the recognition process that effectively determines
image alignment with the embedding space distribution, enabling informed
decision-making during testing. Simultaneously, it incorporates advanced deep
nets within the existing framework, eliminating the need for a completely new
architecture, showcasing its efficiency and adaptability in addressing key
challenges in aircraft recognition. Unlike image classification that makes
false promise of very high accuracy (up to 99%[12]) on original noisy MTARSI
dataset [32], the proposed INNAR methodology utilizes cutting-edge convnets
and leverages similarity learning to construct robust and generalizable
feature representation with image triplets.

This paper makes significant contributions to the aircraft recognition and
combat identification, which are listed below:

  1. 1.

We introduced a novel method to achieve CID in an automated manner.

  2. 2.

We introduced a new and better version of the dataset - MTARSI-INNAR that
advances automated CID development and evaluation after identifying errors in
MTARSI dataset and performing a rigorous data cleaning process that involves
domain experts. 111”To contribute in open science and reproducibility, we will
share the code repository for research purposes and the dataset is available
at Zenodo.org [21]”

  3. 3.

We proposed INNAR, an innovative methodology that distinguishes between Known
(Friend) and Novel (Foe) classes with high accuracy to enhance adaptability in
CID. It utilizes cutting-edge convnets and leverages similarity learning to
construct robust and generalizable feature representation with image triplets.

  4. 4.

We validated that image classification makes false promises of very high
accuracy on original noisy MTARSI dataset [32] and propose a shift to
similarity and few shot learning for aircraft recognition and combat
identification.

##  II Related Work

The evolution of aircraft recognition in remote sensing, with its multifaceted
components of classification, detection, and segmentation, has shown a
paradigm shift in recent years towards end-to-end network development. This
shift underscores the increasing significance of seamless integration across
diverse applications. Dire shift in from convolution[29],[15] to
Transformers[10] and now again convNext[25] Deep Learning networks has
advanced formidably, particularly in object classification in the form of
feature representation/ extraction capabilities. The contemporary approach
treats object detection as a classification challenge for regions of interest,
harnessing deep architectures to autonomously extract intricate image
features.

In order to address aircraft shadows and robust feature extraction combination
of methods are introduced like [31] direction estimation through a
reconstruction-based similarity measure and a jigsaw matching pursuit
algorithm. Evaluation with Quickbird imagery validates the method’s
effectiveness, while a Principal Component Analysis (PCA)-based CNN approach
[18] showcases enhanced segmentation with a novel low downsampling ratio,
though it encounters difficulties in addressing large aircraft in salient
regions and managing unbalanced datasets.An impressive work in this domain
Multiple Class Activation Mapping (MultiCAM) approach [11] demonstrates
improved class activation maps by precisely localizing object parts and
addressing background interference, yet faces challenges in covering large
aircraft, ensuring interpretability with unbalanced datasets, and managing CNN
mapping complexity. However, limitations include insufficient evaluation
details, concerns about generalization, and a lack of real-world examples and
datasets.In the same relam, TransEffiDet [30],innovates aircraft detection
with EfficientDet and Transformer, excelling in aerial imagery with BiFPN.
Achieving enhanced military accuracy, challenges include detecting specific
aircraft types due to less distinct shapes and lacking real-time detection,
critical for timely responses. An important factor in above-mentioned methods
and established remote sensing datasets like UCMerced LandUse[35], NWPU-
RESISC45[36], PatternNet[39], AID [34][7],[31] and FAIR1M[26] present
challenges by treating aircraft as a single class, creating a skewed
distribution that hinders accurate classification due to intricate
complexities. This limitation makes these datasets unsuitable for Known and
Novel class recognition techniques, revealing a critical research gap in
addressing the challenges of CID and Novel class recognition in aircraft
datasets. Aircraft recognition in eXplainable Artificial Intelligence (XAI)
framework by [28] makes a notable contribution by combining the Hybrid Global
Attribution Mapping (HGAM) algorithm, Path Aggregation Network (PANet) module
for feature learning, and Class-specific Confidence Scores Mappings (CCSM)
metrics to enhance deep neural network interpretability in synthetic aperture
radar-based aircraft detection. Despite introducing novel XAI techniques to a
domain with known challenges in comprehensibility, the method exhibits
limitations such as insufficient evaluation details, concerns about
generalization, and a lack of real-world examples and datasets.

Figure 4: Miss labelling & cross contamination issues in MTARSI datasets. a)
B-777, B-747 and Airbus being displayed as Boeing. b) B-777, B-747 and T-1A
being misclassified with C-40. c) C-130, DC-4E and P3C being displayed as
DC-4.

In 2020, [33] addressed the lack of standardized benchmarks in aircraft type
recognition by introducing the MTARSI dataset, consisting of 9,385 images of
20 aircraft types and over 12,000 samples in version -1 & II [32] [21] with
diverse backgrounds and resolutions. The dataset proved crucial for fair
comparisons, demonstrating a 26% improvement in average accuracy through
transfer learning using shallow networ like AlexNet and EfficiNet. However,
limitations include noise and imbalance in dataset, neglecting multi-
resolution impact on aerial images for generalization to diverse scenarios in
remotely sensed images. The MTARSI dataset open new horizon for the researcher
community on military aircraft recognition, where [3] introduces a novel
approach integrating handcrafted and DCNN features, achieving successful
identification. However, limitations include lack of impact of the multi-
resolution RS images specifically negating noise and imbalance in dataset,
thus more emphasis on accuracy rather than correct identification. In the
realm of advance network techniques, like Swin Transformer [12] in combination
of state-of-the-art super resolution method for image upsampling which
improves validation accuracy and emphasizes the importance of the training
procedure over model selection, suggesting a nuanced understanding of the
dataset and the learning process. It also critically examines the limitations
of the MTARSI dataset, such as mislabeling, class scopes, and cross-
contamination, and recommends training on multiple datasets to achieve
generalizable models. Another paper [22] applies advanced deep learning
methods, such as Vision Transformers, ResNet50v2, EfficientNetB0, and
InceptionNetV3, to the MTARSI dataset and achieves higher classification
accuracy than the benchmark. It focuses on the design and fine-tuning of the
architectures to capture the features and patterns of complex military
platforms. In current era , the introduction of few shot learning by [17]
introduces S2I-DAFSL, a novel domain adaptive few-shot learning method for
aircraft recognition, utilizing an attention transferred importance-weighting
network (ATIN) for enhanced transferability from satellites to inverse
synthetic aperture radar (ISAR). This approach strength lies in cross-domain
few-shot ISAR aircraft recognition tasks, however,it lacks in task-specific
model adaptability to new samples alongwith domain adaptive robustness,
assuming labeled data availability in the source domain.

Model training procedure and role of loss, is essential for effective image
recognition and classification in handling imbalanced, noisy, and
heterogeneous data [6]. The batch hard triplet approach, which offers
stability and faster convergence, outperforms conventional methods for image
recognition. However, it candidly admits the approach’s limited success in
achieving high accuracy on $Unknown$ classes, acknowledging the persistent
challenge posed by fine-grained classes with high intra-class variance.
FaceNet significantly contributes [24] by introducing a unified system for
facial recognition, optimizing training to generate discriminative embeddings
capable of recognizing and verifying faces under various conditions. Its
innovative use of a triplet-based loss function efficiently minimizes
distances between similar faces and maximizes distances between different
individuals, marking a substantial leap in facial analysis and verification
systems.

##  III Proposed INNAR Methodology

This research focuses on designing an end-to-end pipeline for aircraft
recognition, particularly in identifying Known classes vs Novel aircraft.
Firstly, we train a model to recognize aircraft via similarity learning,
elaborated in Section III-A. This forms the basis for the next steps and is
essential for the model to distinguish effectively between various aircraft
categories. Secondly, we use the model trained in the first step to construct
an embedding space through few-shot learning. Thirdly, we introduce a model
adaptive thresholding mechanism discussed in Section III-B to determine if an
image belongs to a Known or Novel distribution for the recognition pipeline.
If the image belongs to a Known category, it undergoes further classification
using a few-shot classifier, refining the model’s discernment for more
granular distinctions within established aircraft categories. To understand
the process better, the details of each step and the intricate workings
contributing to the model’s prowess in aircraft recognition in subsequent
sections and as illustrated in Figure 5.

Figure 5: Proposed INNAR Methodology of Automated CID to identify Novel Class;
where the input image gets transformed into feature vector which is then used
to identify as a Known or Novel followed by classification. a) Embedder
Architecture training b) Few shot learning for embedding space c)
Bipartitioning for out-of distribution images d) Few-Shot Classification

###  III-A Embedding Architecture Training

The siamese network learns embeddings designed to capture the similarity
between input triplets. During the training process, we construct triplets of
samples, comprising an anchor, a positive, and a negative sample. The anchor
signifies the input for which we seek to learn a meaningful embedding, with
the positive being a sample similar to the anchor and the negative being a
dissimilar sample. The objective actively involves minimizing the distance
between the anchor and the positive while simultaneously maximizing the
distance between the anchor and the negative, as highlighted in Equation 2.
This approach effectively creates a margin that encourages the model to map
similar instances close together and dissimilar instances far apart in the
embedding space, as illustrated in the Embedder Training section within Figure
5.

$L(a,p,n)=\max\\{d(a_{i},p_{i})-d(a_{i},n_{i})+margin,0\\}$ (2)

The loss function associated with the triplet loss typically takes the form of
the hinge loss, penalizing the model when the margin constraints are violated.
The network’s parameters are then updated through backpropagation, optimizing
the embedding space for the given task. This methodology proves especially
effective in scenarios where pairwise information about similarity or
dissimilarity between samples is available, making it valuable for tasks
ranging from image verification to recommendation systems.

For a comprehensive evaluation, we conducted extensive trials using a diverse
range of architectures, exploring variations in both structure and nature to
ensure a thorough examination of the model’s performance. This involved
testing with several deep learning architectures like ResNet, EfficientNet,
Swin Transformer, and ConvNext, each serving as embedders to generate distinct
embedding vectors for our evaluation purposes.

After completing the initial step, we acquired an embedder with the ability to
generate vector representations for any input aircraft image. To overcome data
scarcity and ensure scalability for newly incorporated aircraft without
retraining, we embraced few-shot learning. We considered a limited set of
images for each aircraft, fed them into the embedder, and obtained
corresponding embedding vectors. These vectors, along with their labels, were
stored to create an embedding space addressing both data scarcity and
scalability issues. This space allows us to calculate distances with test-time
embedding vectors using Euclidean Distance.

###  III-B Bipartitioning for out-of distribution images

In this crucial step, we introduce a thresholding technique to discern whether
an image aligns with the distribution of our generated embedding space. If the
image falls outside our generated embedding space, it indicates that the
provided image does not pertain to any of the aircraft classes encompassed by
our space. To achieve this, we transformed the aircraft labels into a binary
format, where 0 represents the classes used for our known aircraft
representation, and 1 signifies classes set aside that are not part of this
space. With the transformed labels, we selected an image from the development
set and computed its distance within our embedding space. These distances for
all development images were recorded and used to plot their distributions as
highlighted in Figure 7 and compute Receiver Operating Curve (ROC) enabling
the identification of the True Novel Rate (or True Positive Rate) and False
Novel Rate (or False Positive Rate) respectively. By scrutinizing this, we can
make an informed decision on selecting a threshold that aligns with our model
and other preferences—whether prioritizing a higher TPR, a higher FPR, or a
balanced point. This chosen threshold is then applied during testing to
distinguish images belonging to our distribution from those in out-of-
distribution classes. For this study, we opted for Youden Index for the
selection of optimal threshold which tries to capture maximum potential
effectiveness for a distribution. After determining whether an image falls
within our embedding space. The next step involves classification for those
images that do belong to the space. Employing the K-Nearest Neighbor method,
we leverage the Known embedding space and their corresponding labels for this
classification. Once an embedding vector is generated for a test image, its
distances are computed with all vectors in the embedding space. The labels of
the closest K vectors are extracted, and a consensus is reached among these
labels, assigning the most recurrent label to the image in question. To gauge
the overall performance of our pipeline, we evaluate it using weighted
F1-Score.

This algorithm goes into detail about how the final step is carried out. It
explains the specific actions and methods involved in this step, aiming to
make the process more understandable. The goal is to provide a clear and
accessible explanation of the final phase, ensuring that the steps taken are
straightforward and easy to grasp within the overall algorithm.

Algorithm 1 Automated CID Embedding-based Algorithm

0: Images

0: Aircraft recognition into Known classes or Novel Class

1: Initialization: $Embedder,Threshold,K$
$Set_{A}=\\{x_{A1},x_{A2},\ldots,x_{AN}\\}$ (Set of Known Classes)
$Set_{B}=\\{x_{B1},x_{B2},\ldots,x_{BN}\\}$ (Set of Novel Classes)
$Set_{C}=Set_{A}\cup Set_{B}$ (Set of All Classes)

2: Few Shot Phase:

3: for each class $c$ in the $Set_{A}$ do

4: Sample $N$ images $\\{x_{1}^{c},x_{2}^{c},\ldots,x_{N}^{c}\\}$ from class
$c$

5: Generate embedding vectors $\\{v_{1}^{c},v_{2}^{c},\ldots,v_{N}^{c}\\}$
using Embedder

6: Store vectors $(v_{i}^{c},c)$ for $i=1$ to $N$ in the database

7: Store labels $(l_{i}^{c},c)$ for $i=1$ to $N$ in the database

8: end for

9: Testing Phase:

10: for each class $c$ in the $C$ do

11: for each sample $s$ in the $c$ do

12: $v_{\text{test}}\leftarrow Embedder(s)$

13: $distances\leftarrow$Compute $p$-norm distance between $v_{\text{test}}$
and $v_{i}$ for $i=1$ to $N$

14: $topKsamples\leftarrow$ Select the top $K$ samples with minimum distance

15: $meanDistance\leftarrow$ Calculate the mean of the $topKsamples$

16: if $meanDistance\geq Threshold$ then

17: Output: Classify as Novel

18: else

19: Pass $v_{\text{test}}$ through our Few-Shot classifier

20: Output: Final Classification Result

21: end if

22: end for

23: end for

##  IV Dataset Quality Management

In 2020, the introduction of the MTARSI dataset [32],[21], which constitutes
three versions (V1,V2 & V3) offers a valuable resource for advancing research
in remote sensing and deep learning by establishing benchmarks to compare
different models. However, the datasets constitutes severe challenges like
contamination, miss-classification, duplicity, labeling inaccuracies and
integration inconsistencies. Certainly, Cross-contamination in image
classification labels involves unintentional mixing or mislabeling of images
from different classes during machine learning model training or testing,
leading to reduced accuracy and performance as the model may struggle to
distinguish between classes due to contaminated label information.

Figure 6: MTARSI-INNAR [23] samples with the number of Classes rectified for
duplicity & cross contamination in comparison to MTARSI datasets with
corresponding labels

To review and clean the MTARSI[32],[21] dataset, we adopt a comprehensive step
by step approach, whose broader contours are highlighted as follows:-

  1. 1.

A careful study of the dataset highlights identification of four data issues
in the shape of interference by objects in the vicinity, image dimensions not
compatible with the size (bigger aircraft with squeezed shapes), aircraft
background noises, image merging with the same surface (e.g black) and
problems such as exposure & weather issues, underscores the challenges within
the dataset, emphasizing the need for careful consideration in subsequent
analyses. The image samples in Figure 2 and Figure 3 highlight these issues.
Moreover, the dataset [32, 21] constitutes both military and civil image
samples, which provides a versatile research opportunity to analyse both
domains at the same time. In Figure 2 (training image samples) and Figure 3
(testing image samples), codes F, B, C, and T represent fighters, bomber,
transport and trainer categories, respectively.

  2. 2.

Several aircraft (up to 10 different) types erroneously labelled as airliner
class, which require careful re-categorization to overcome the contamination.
The confusion matrix in Figure 6 reports the number of samples mislabelled
because of this contamination and Figure 4 (a) show a few of those samples.

  3. 3.

B-29 Superfortress and P-3_Orion types contain highly identical image samples
which we have merged together as a single class as listed in Figure 6.

  4. 4.

As illustrated in Figure 4 (b), the confusion between the C-40 and aircraft
types B-777, B-747, and T-1A arises from their shared characteristics as
passenger planes.

  5. 5.

Figure 4 (c) emphasizes the confusion between DC-4 with C-130, DC-4E, and P3C
aircraft, highlighting the inherent visual similarities that affect
representation learning and classification.

  6. 6.

In the training set, mislabeling occurs due to similarities between F-4, F-18,
and F-22 with F-15, leading to potential convergence issues.

We have taken following steps to clean MTARSI dataset from above-mentioned
issues and duplicate samples:-

  1. 1.

A dedicated team of 12 specialists, as acknowledged in Section
Acknowledgments, cleaned the dataset. This team comprises professionals with
diverse expertise, including pilots and experts in satellite imagery
considering the role and feature types of various aircraft image samples.

  2. 2.

Duplicate samples, where the same sample is present in multiple aircraft
types, are identified automatically through a Python code snippet for
duplicates.

  3. 3.

We perform an iterative approach to refine the dataset, actively reviewing and
updating it based on feedback from specialists and any newly acquired
knowledge about the aircraft types.

  4. 4.

Finally, the above-mentioned steps ensured unified scaling to enhance quality
and accuracy. Following this, the samples are normalized to 224 pixels × 224
pixels to ensure compatibility with specific models or algorithms, ensuring
efficient processing and analysis.

##  V Experimental Results And Discussion

Figure 7: Histogram showing Known vs Novel class distributions for State of
Art deep learning architectures where X -axis represent Distance & Y-axis
represent the Frequency on MTARSI-INNAR [23] Development and Independent Test
Sets.

###  V-A Experimental Setup

We used Weights & Biases, extending beyond experiment management to encompass
logging, plotting, and version control. We executed the experiments on a
single Nvidia Tesla P100 GPU with 16GB memory. For dataset partitioning, 80%
was allocated for training and 20% for testing on a class-wise basis as
highlighted in where classes in bold correspond to Novel Class. To maintain
consistency, input dimensions were standardized, resizing images to 224x224
with a batch size of 32, and employing the ADAM optimizer with a learning rate
of 1e-4. We utilized various architectures, including Resnet, EfficientNet,
Swin, and ConvNext, as embedders. The embedder incorporated the Triplet Margin
Loss, configured with a margin of 1 and a threshold derived from the median
value of the ROC Curve in Figure 9. For classification, we rely on K-nearest
neighbors (KNN) with a constant K value of 5 across all experiments.

###  V-B Results & Discussion

In our exploration of the [32] and [21] datasets, our initial classification
efforts yielded impressive results, achieving a flawless 1.0 F1-Score for [32]
and an 0.84 F1-Score for [21] as highlighted in Figure 8 above. However, this
success brought to light a notable challenge: the models’ outstanding
performance on [32] revealed a significant limitation, specifically in terms
of cross-contamination. This issue arose when identical images were present in
both the training and testing sets of same class as well as in different
class. Consequently, this prompted a critical reassessment of improved dataset
to address and mitigate this unexpected phenomenon.

Figure 8: Comparative Analysis of MTARSI[32] & [21]. F1 Score highlights clear
decline in performance of various deep learning architectures on Noisy (left)
& less Noisy (Right) datasets

In the [32] dataset, the challenge of overfitting is primarily driven by a
complex interplay of multiple factors. These include labeling errors,
inconsistent class definitions and the absence of a canonical data split.
Labeling inaccuracies have proven to be a significant hurdle, causing our
experimental deep learning models to memorize specific, often erroneous
features within the training data. As a result, the models fixate on these
unique details, failing to grasp the general characteristics crucial for
accurate classification. Furthermore, the absence of a well-defined data split
complicates the evaluation of a model’s ability to generalize. This
complicates matters by potentially leading to overfitting on the validation
set, where models might perform remarkably well due to getting overly familiar
to specific validation set features. The issues extend to classes like B-2,
achieving perfect scores despite being indistinguishable from others. The
inconsistent class definitions, as seen in the ’Boeing’ class, further worsen
overfitting concerns. Additionally, the F-16 class contained images unrelated
to the actual F-16 aircraft, underlining the necessity of accurate data
labeling and maintaining consistent class definitions for effective model
training. Balancing the trade-off between correctly classifying Known entities
and accurately identifying unknown entities is a critical consideration. The
specific application’s requirements and priorities play a significant role in
determining the threshold values.

Figure 9: ROC Curve on Test Set between Known and Novel where Novel
corresponds to Positive class Figure 10:  Evaluation on test set of various
architectures. a) Biparitioning performance visualization using confusion
matrix and class-wise f1-score between Actual and Predicted labels of Known vs
Novel on Test Set. b) Radar plot showing the performance on MTARSI-INNAR [23]
Test set for 13 Known classes & Novel class. State of art deep learning
models’ F-1 Score on best performing ATR-72, B-57, DC-4E aircraft but show
performance decline on ARJ-21 and Light AC.

Addressing the challenging task of identifying Known classes which is a
crucial part of real-world problem of aircraft recognition and combat
identification, our approach involved a distinctive strategy: training an
embedder. This embedder, initialized with ImageNet weights, underwent further
refinement through the application of the Triplet Loss Function over several
epochs. In Figure 7, we illuminate key insights into the distributions on both
the development and test sets, emphasizing that each architecture embeds
vectors within a uniquely ranged space. It is evident that EfficientNet and
SwinV2 which are smaller architectures create the most confined embedding
space (Their distributions are much compact). On the other hand, ResNet and
ConvNext seems to have a wider distribution and they also have very less
overlapping region between the Known and Novel classes which is highlighted by
Blue and Orange color respectively.

Figure 11: Performance comparison of F1-Score Classification against F1-Score
Bipartitioning. The size of each point highlights the parameters of
architecture

We introduced a deliberate 22-5 split to the development set as highlighted in
Development Set(27 Classes), designating 22 classes as Known and 5 as Novel.
The implementation of few-shot learning entailed selecting K=5 representative
images for each of the 22 Known classes, generating their embedding vectors,
and subsequently validating them against other images from the same classes.
Notably, utilizing the few shot technique on training set, we identified an
optimal threshold using Youden Index to discern the separation between Known
and Novel classes, crucial for evaluating the performance of the embedder on
the testing set. For testing set, We took this a step further by introducing
16 completely new classes, all unseen during the embedder’s training. Out of
these, we utilized 13 as Known and 3 as Novel as mentioned in Testing Set(16
Classes).

Given that threshold selection is based on the development set, certain
architectures exhibit excellent performance on development data but struggle
on the test set. A closer examination of SwinV2’s distributions reveals a
considerable separation between Known and Novel classes in the development
set, with minimal overlap. However, this architecture undergoes a significant
transformation in range and representation on the test set. The F1-Score of
biparitioning on the Independent Test Set stands at 0.83.

EfficientNet, on the other hand, manifests a broader development distribution
but contracts significantly on the test set however the data separation remain
roughly intact. It achieves an F1-Score Bipartitioning of 0.827 on the
Independent Test Set. Even though this score seems great however it is still
the worst performer amongst other architectures. The largest model in our
study, ConvNext, achieves the highest F1-Score Bipartitioning on the test set
standing at 0.936.

ResNet showed the second best performance on bipartitioning. The distributions
generated by it are much wider compared to any other architecture and it
retains it’s performance on both development and test set. It achieves an
F1-Score bipartitioning of 0.892 on the independent test set being roughly 3%
less than ConvNext.

Each architecture exhibits unique properties on the development and test set.
The confusion matrix highlights their intricacies on the Independent Test set
in Figure 10 $a)$.

Apart from bipartitioning performance, it is also important to evaluate each
architecture’s performance on the classification of aircraft within the Known
Class. For this, we’ve computed weighted F1-Score Aircraft Types. SwinV2
performs the worst here on both the development and test set. It achieves an
F1-Score of 0.847 on the development set putting which then drops down to
0.7053 on the test set. In contrast, EfficientNet is able to achieve an
F1-Score of 0.7224 which is 2% better than that of SwinV2 however the
difference is not very significant. Both of these architectures fail to
produce sparse embedding representations in our case. The distributions of
both of these architectures are the most compact as visible in Figure 7.

ResNet even though being a relatively outdated model than SwinV2 and
EfficientNet is able to achieve an F1-Score of 0.8358 on the development set
and 0.7668 on the test set. ResNet also exhibits the decline in performance
which could be due to the difference of classes in embedder training set and
test set. In contrast, our top-performing architecture ConvNext exhibits
superior performance compared to other architectures, striking a balance
between sparseness (evidenced by a higher F1-score) and generalizability
across datasets. With consistent distributions and minimal overlap between
Known and Novel classes in both training and test sets, ConvNext achieves
F1-Scores of 0.8879 on the development set and 0.8612 on the testing sets
revealing a modest 2% decline. This decline is the smallest among other models
in classification, indicating the model’s robustness. ConvNext’s balanced and
consistent performance underscores its efficacy in handling both Known and
Novel classes as well as classification.

The radar plot in Figure 10 $b)$ shows F1-scores obtained by each method on
the test set. ResNet exhibits diverging performance pattern. It demonstrates
an intense focus on specific classes, attaining remarkably high F1-Scores for
them but exhibits sub-optimal performance for other classes, particularly
struggling with T-1A and Light AC, where it records F1-Scores of 0.39 and 0.3,
respectively. Of significance is ResNet’s noteworthy competence in recognizing
Novel classes, positioning itself as the second-best performer in this regard.
It is worth noting that across all architectures, there is a unanimous
struggle in accurately classifying the ARJ-21 class, owing to its significant
similarity to the ATR-72 — a distinction discussed in previous sections.

The challenges persist across various aircraft classes, such as Light AC,
RC-135, and T-1A, where all architectures exhibit subpar performance.
Nevertheless, a compelling revelation emerges in the performance of ConvNext,
which maintains an F1-Score of approximately 0.72 on Novel classes. This
achievement stands out prominently within the context of our anticipated
results, showcasing ConvNext’s robust adaptability and effectiveness in
handling previously unseen classes.

The INNAR being potentially extendable presents a well-structured and
comprehensive approach to tackling image classification challenges and
distinguishing between Novel and Known classes in the context of aircraft
recognition. While the INNAR effectively addresses and adept challenges in
aircraft recognition, its current pipeline has a limitation of considering
image-based embedding space only and not accommodating diverse sensor (multi-
modal) inputs for decision-making, like radar and infrared data that will
further enhance the accuracy and impact of automated combat identification.
For an effective identification of new aircraft types, INNAR needs an
intermediate dataset (Development Set) with unseen aircraft types as a Novel
class; without it, determining the appropriate threshold becomes impossible.
Similarly, INNAR distinguishes all unseen aircraft types as Novel but it do
not further classify each sub-type within the Novel Category.

##  VI Conclusion and Future Work

This paper presents an innovative methodology for the recognition of military
aircraft from remote sensing imagery, utilizing embedding and similarity
metrics for precise few-shot learning across both Known and Novel aircraft
classes. Our experimental evaluation, encompassing a variety of architectures
of different scales and complexities, reveals a significant trend: larger
models demonstrate enhanced performance in our scenario, highlighting their
ability to generate sparse vector representations and capture nuanced insights
effectively.

In addition to evaluating the performance of different architectures, we have
addressed challenges in dataset quality, effectively mitigating issues of
cross-contamination and erroneous annotations. With a focus on robustness, our
approach offers a promising solution for the aviation industry and researchers
striving for efficient recognition within the complex domain of military
aircraft from satellite imagery. As we look to the future, we emphasize the
need for diverse datasets that cover a wide range of aircraft types. These
datasets not only enable more comprehensive research but also promote the
development of advanced algorithms essential for accurate and nuanced aircraft
type recognition. The practical implications of fine-grained classification
span various domains, including aviation, defense, and other sectors where
precise aircraft identification is of utmost importance.

## Acknowledgments

We are grateful to the pilots and remote sensing specialists (Murad Ali,
Saleem Raza, Shahbaz Ahmad, and Usman Qamar) and their assistants for their
expertise and dedication in refining the MTARSI[32] dataset. Their careful
analysis of remote sensing imagery improved the dataset’s quality [23] and
reliability, contributing to the progress of remote sensing.

## References

  * [1] Salman Ahmed, Haasha bin Atif, Muhammad Bilal Shabbir, and Hammad Naveed.  Prnet: Progressive resolution based network for radiograph based disease classification.  In 2021 Ethics and Explainability for Responsible Data Science (EE-RDS), pages 1–5. IEEE, 2021.
  * [2] D.H. Andrews, L.C.R.P. Herz, M.B. Wolf, P.D. Harris, E. Salas, and P.N.A. Stanton.  Human Factors Issues in Combat Identification.  Human Factors in Defence. Ashgate Publishing Limited, 2012.
  * [3] Faisal Azam, Akash Rizvi, Wazir Zada Khan, Mohammed Y Aalsalem, Heejung Yu, and Yousaf Bin Zikria.  Aircraft classification based on pca and feature fusion techniques in convolutional neural network.  IEEE Access, 9:161683–161694, 2021.
  * [4] Mohsin Bilal, Robert Jewsbury, Ruoyu Wang, Hammam M AlGhamdi, Amina Asif, Mark Eastwood, and Nasir Rajpoot.  An aggregation of aggregation methods in computational pathology.  Medical Image Analysis, page 102885, 2023.
  * [5] Mohsin Bilal, Mohammed Nimir, David Snead, Graham S Taylor, and Nasir Rajpoot.  Role of ai and digital pathology for colorectal immuno-oncology.  British Journal of Cancer, 128(1):3–11, 2023.
  * [6] Mohsin Bilal, Yee Wah Tsang, Mahmoud Ali, Simon Graham, Emily Hero, Noorul Wahab, Katherine Dodd, Harvir Sahota, Shaobin Wu, Wenqi Lu, et al.  Development and validation of artificial intelligence-based prescreening of large-bowel biopsies taken in the uk and portugal: a retrospective cohort study.  The Lancet Digital Health, 5(11):e786–e797, 2023.
  * [7] Gong Cheng, Junwei Han, and Xiaoqiang Lu.  Remote sensing image scene classification: Benchmark and state of the art.  Proceedings of the IEEE, 105(10):1865–1883, 2017.
  * [8] Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei.  Imagenet: A large-scale hierarchical image database.  In 2009 IEEE conference on computer vision and pattern recognition, pages 248–255. Ieee, 2009.
  * [9] Jian Ding, Nan Xue, Gui-Song Xia, Xiang Bai, Wen Yang, Michael Ying Yang, Serge Belongie, Jiebo Luo, Mihai Datcu, Marcello Pelillo, and Liangpei Zhang.  Object detection in aerial images: A large-scale benchmark and challenges.  IEEE Transactions on Pattern Analysis and Machine Intelligence, 44(11):7778–7796, 2022.
  * [10] Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, et al.  An image is worth 16x16 words: Transformers for image recognition at scale.  arXiv preprint arXiv:2010.11929, 2020.
  * [11] Kun Fu, Wei Dai, Yue Zhang, Zhirui Wang, Menglong Yan, and Xian Sun.  Multicam: Multiple class activation mapping for aircraft recognition in remote sensing images.  Remote sensing, 11(5):544, 2019.
  * [12] Kyle Gao, Hongjie He, Dening Lu, Linlin Xu, Lingfei Ma, and Jonathan Li.  Optimizing and evaluating swin transformer for aircraft classification: Analysis and generalizability of the mtarsi dataset.  IEEE Access, 10:134427–134439, 2022.
  * [13] Zhang. J. Gu. Y., Zhang. Y.  Integration of spatial–spectral information for resolution enhancement in hyperspectral images.  IEEE Trans. Geosci. Remote Sensing, 2008.
  * [14] Yonghui Guo, Yuntao Li, and Yu Zhang.  Research on mimo-isar high resolution imaging technology.  In 2021 IEEE 4th Advanced Information Management, Communicates, Electronic and Automation Control Conference (IMCEC), volume 4, pages 169–174. IEEE, 2021.
  * [15] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Deep residual learning for image recognition.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770–778, 2016.
  * [16] G. Krizhevsky, A.; Hinton.  Learning multiple layers of features from tiny images.  University of Toronto: Toronto, ON, Canada, 2009.
  * [17] Binquan Li, Yuan Yao, and Qiao Wang.  Domain adaptive few-shot learning for isar aircraft recognition with transferred attention and weighting importance.  Electronics, 12(13):2909, 2023.
  * [18] Ge Liu, Xian Sun, Kun Fu, and Hongqi Wang.  Aircraft recognition in high-resolution satellite images using coarse-to-fine shape prior.  IEEE Geoscience and Remote Sensing Letters, 10(3):573–577, 2012\.
  * [19] Ze Liu, Yutong Lin, Yue Cao, Han Hu, Yixuan Wei, Zheng Zhang, Stephen Lin, and Baining Guo.  Swin transformer: Hierarchical vision transformer using shifted windows.  In Proceedings of the IEEE/CVF international conference on computer vision, pages 10012–10022, 2021.
  * [20] Subhransu Maji, Esa Rahtu, Juho Kannala, Matthew Blaschko, and Andrea Vedaldi.  Fine-grained visual classification of aircraft.  arXiv preprint arXiv:1306.5151, 2013.
  * [21] R Rudd-Orthner and L Mihaylova.  Multi-type aircraft of remote sensing images: Mtarsi 2.  Zenodo, 2021.
  * [22] Ahmad Saeed, Haasha Bin Atif, Usman Habib, and Mohsin Bilal.  Remote sensing aircraft classification harnessing deep learning advancements.  In 2023 18th International Conference on Emerging Technologies (ICET), pages 50–55, 2023.
  * [23] Ahmad Saeed, Haasha Bin Atif, Mohsin Bilal, and Usman Habib.  Mtarsi-innar.  Zenodo.org, January 2024.
  * [24] Florian Schroff, Dmitry Kalenichenko, and James Philbin.  Facenet: A unified embedding for face recognition and clustering.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 815–823, 2015.
  * [25] Tao.Lei Song.F, Peng.Z.  Raih-det: An end-to-end rotated aircraft and aircraft head detector based on convnext and cyclical focal loss in optical remote sensing images.  IEEE Trans. Geosci. Remote Sensing, 2023.
  * [26] Xian Sun, Peijin Wang, Zhiyuan Yan, Feng Xu, Ruiping Wang, Wenhui Diao, Jin Chen, Jihao Li, Yingchao Feng, Tao Xu, et al.  Fair1m: A benchmark dataset for fine-grained object recognition in high-resolution remote sensing imagery.  ISPRS Journal of Photogrammetry and Remote Sensing, 184:116–130, 2022.
  * [27] Bin Tan, Qiuni Li, Tingliang Zhang, and Hui Zhao.  The research of air combat intention identification method based on bilstm+ attention.  Electronics, 12(12):2633, 2023.
  * [28] Wei Tang, Chenwei Deng, Yuqi Han, Yun Huang, and Baojun Zhao.  Srarnet: A unified framework for joint superresolution and aircraft recognition.  IEEE Journal of Selected Topics in Applied Earth Observations and Remote Sensing, 14:327–336, 2020.
  * [29] Ferhat Ucar, Besir Dandil, and Fikret Ata.  Aircraft detection system based on regions with convolutional neural networks.  International Journal of Intelligent Systems and Applications in Engineering, 8(3):147–153, 2020.
  * [30] Yanfeng Wang, Tao Wang, Xin Zhou, Weiwei Cai, Runmin Liu, Meigen Huang, Tian Jing, Mu Lin, Hua He, Weiping Wang, et al.  Transeffidet: aircraft detection and classification in aerial images based on efficientdet and transformer.  Computational Intelligence and Neuroscience, 2022, 2022.
  * [31] Qichang Wu, Hao Sun, Xian Sun, Daobing Zhang, Kun Fu, and Hongqi Wang.  Aircraft recognition in high-resolution optical satellite remote sensing images.  IEEE Geoscience and Remote Sensing Letters, 12(1):112–116, 2014\.
  * [32] Z Wu.  Multi-type aircraft of remote sensing images: Mtarsi.  Zenodo. org, 10, 2019.
  * [33] Zhi-Ze Wu, Shou-Hong Wan, Xiao-Feng Wang, Ming Tan, Le Zou, Xin-Lu Li, and Yan Chen.  A benchmark data set for aircraft type recognition from remote sensing images.  Applied Soft Computing, 89:106132, 2020.
  * [34] Gui-Song Xia, Jingwen Hu, Fan Hu, Baoguang Shi, Xiang Bai, Yanfei Zhong, Liangpei Zhang, and Xiaoqiang Lu.  Aid: A benchmark data set for performance evaluation of aerial scene classification.  IEEE Transactions on Geoscience and Remote Sensing, 55(7):3965–3981, 2017.
  * [35] Yi Yang and Shawn Newsam.  Bag-of-visual-words and spatial extensions for land-use classification.  In Proceedings of the 18th SIGSPATIAL international conference on advances in geographic information systems, pages 270–279, 2010.
  * [36] Yuhang Zhang, Hao Sun, Jiawei Zuo, Hongqi Wang, Guangluan Xu, and Xian Sun.  Aircraft type recognition in remote sensing images based on feature learning with conditional generative adversarial networks.  Remote Sensing, 10(7):1123, 2018.
  * [37] Baojun Zhao, Wei Tang, Yu Pan, Yuqi Han, and Wenzheng Wang.  Aircraft type recognition in remote sensing images: Bilinear discriminative extreme learning machine framework.  Electronics, 10(17):2046, 2021.
  * [38] Qi Zhao, Shuchang Lyu, Yuewen Li, Yujing Ma, and Lijiang Chen.  Mgml: Multigranularity multilevel feature ensemble network for remote sensing scene classification.  IEEE Transactions on Neural Networks and Learning Systems, 2021\.
  * [39] Weixun Zhou, Shawn Newsam, Congmin Li, and Zhenfeng Shao.  Patternnet: A benchmark dataset for performance evaluation of remote sensing image retrieval.  ISPRS journal of photogrammetry and remote sensing, 145:197–209, 2018.


# Adapting Surprise Minimizing Reinforcement Learning Techniques for
Transactive Control

William Arnold  Electrical Engineering and Computer Sciences, University of
California, Berkeley ,  Tarang Srivastava  Electrical Engineering and Computer
Sciences, University of California, Berkeley ,  Lucas Spangher  Electrical
Engineering and Computer Sciences, University of California, Berkeley ,
Utkarsha Agwan  Electrical Engineering and Computer Sciences, University of
California, Berkeley and  Costas Spanos  Electrical Engineering and Computer
Sciences, University of California, Berkeley

(2021)

###### Abstract.

Optimizing prices for energy demand response requires a flexible controller
with ability to navigate complex environments. We propose a reinforcement
learning controller with surprise minimizing modifications in its
architecture. We suggest that surprise minimization can be used to improve
learning speed, taking advantage of predictability in peoples’ energy usage.
Our architecture performs well in a simulation of energy demand response. We
propose this modification to improve functionality and savin a large-scale
experiment.

Reinforcement Learning, Surprise Minimizing Reinforcement Learning, Office
building energy demand response, Demand Response, Transactive Control, Novelty
minimizing techniques

††copyright: rightsretained††journalyear: 2021††conference: The Twelfth ACM
International Conference on Future Energy Systems; June 28-July 2, 2021;
Virtual Event, Italy††booktitle: The Twelfth ACM International Conference on
Future Energy Systems (e-Energy ’21), June 28-July 2, 2021, Virtual Event,
Italy††doi: 10.1145/3447555.3466590††isbn: 978-1-4503-8333-2/21/06††ccs:
Computing methodologies Reinforcement learning††ccs: Hardware Smart grid

##  1\. Introduction

The electricity grid may be seen as a beautifully decentralized organism: one
in which individual energy demands are met by individual generators largely
without direct coordination or knowledge of recipient. Market signals simply
translate into generators commanding their resources to increase or decrease.
However, as volatile resources like wind and solar replace on-demand resources
like fossil fuels, a potentially worrying question arises: what happens to
demand when the generation becomes decoupled from commands; i.e., when energy
is demanded but the sun isn’t shining? Grids that do not adequately prepare
for this question will face daunting consequences, ranging from curtailment of
resources (Spangher et al., 2020b) to voltage instability and physical damage.

A common solution is demand response: a strategy in which customers are
incentivized to shift loads to periods of the day where energy is plentiful.
Given the lack of material infrastructure required, it has several positives
above physical energy storage systems. One primary application of demand
response is in buildings, and central-level appliance coordination has been
thoroughly studied in residential and industrial settings (Asadinejad et al.,
2018; Ma et al., 2015; Li et al., 2018; Yoon et al., 2014; Johnson et al.,
2015). However, while physical infrastructure of office buildings has been
studied for demand response ((Kim, 2018)), there has been no large scale
experiment aimed to elicit a behavioral demand response.

The lack of experiment is understandable given most offices do not have
mechanisms to pass energy prices to office workers (Das et al., 2019). If they
did, however, not only could a large fleet of decentralized batteries –
laptops, cell phone chargers, etc. – be coordinated to function as a large
deferable resource, but building managers could save money(Das et al., 2020).

The SinBerBEST collaboration has developed a Social Game that facilitates
workers to engage in competition around energy (Konstantakopoulos et al.,
2019a), (Konstantakopoulos et al., 2019b). Through this framework, a first-of-
its-kind experiment has been proposed to implement behavioral demand response
within an office building (Spangher et al., 2020b). Prior work has proposed to
describe an hourly price-setting controller that learns how to optimize its
prices (Spangher et al., 2020a).

However, given the costliness of iterations in this experiment, further work
in simulation is needed to refine a controller that can adapt faster to the
behavior of office workers.

We endeavor to report one such refinement. In Section 2 we will contextualize
the architecture of our reinforcement learning (RL) controller within the
general domain of RL and improve it with a surprise minimizing algorithm. In
Section 3 we will describe the simulation setup and the specific modification
we propose. In Section 4 we will give results and in Section 5 we will discuss
implications of the controller and the future work this entails.

##  2\. Background

###  2.1. Reinforcement Learning

Reinforcement learning (RL) is a type of agent-based machine learning where
control of a complex system requires actions that maximize the agent’s outcome
(Sutton and Barto, 2018), i.e. they seek to optimize the expected sum of
rewards for actions ($a_{t}$) and states ($s_{t}$) with a policy $p_{\pi}$ and
reward given by $r$ in a policy parametirized by $\theta$; i.e.,
$J(\theta)=\operatorname{\mathbb{E}}\sum_{s_{t},a_{t}\sim
p_{\pi}}[r(s_{t},a_{t})]$.

Policy gradient methods are a class of RL algorithms used to train policy
networks that suggest actions. We propose the use of a variant of these
methods, Proximal Policy Optimization (PPO) (Schulman et al., 2017), which
works by computing an estimator of the policy gradient and plugging it into a
stochastic gradient ascent algorithm.

RL has been used for a number of demand response situations, but most of the
work consists of agents that directly schedule resources (Liu et al., 2015; Li
and Jayaweera, 2014; Zhang and van der Schaar, 2014; Wei et al., 2015; Raju et
al., 2015; Fuselli et al., 2013). RL architectures can vary significantly, for
example Mbuwir et. al. manages a battery directly using batch Q-learning
(Mbuwir et al., 2017). In another example, Kofinas et. al. deploys a fuzzy
Q-learning multi-agent that learns to coordinate appliances to increase
reliability (Kofinas et al., 2018).

###  2.2. Surprise Minimizing Reinforcement Learning

Some stability of control is desirable, for both human subjects and the agent.
Incentivizing the agent to minimize the surprise it experiences is equivalent
to incentivizing it to minimize peoples’ change in energy usage across days.
This corresponds to adjusting people’s habits in a stable system rather than
forcing them to confront and attempt to understand an unstable one.
Additionally, people behave predictably on aggregate, and thus choosing to
minimize surprise may in fact make it easier for the agent to learn. In
general, we define surprise minimization to be the reduction of novel events
experienced by the RL agent. In this context, this equates to the RL
controller experiencing stable energy demands by the office workers.

Surprise Minimizing Reinforcement Learning (SMiRL) is an algorithm that aims
to reduce the entropy of visited states. SMiRL is useful when the environment
provides sufficient unexpected and novel events for learning where the
challenge for the agent is to maintain a steady equilibrium state. (Berseth et
al., 2019)

SMiRL maintains a distribution $p_{\theta}(s)$ about which states are likely
under its current policy. The agent then modifies its policy $\pi$ so that it
encounters states $s$ with high $p_{\theta}(s)$, as well as to seek out states
that will change the model $p_{\theta}(s)$ so that future states are more
likely.

We make use of SMiRL as an auxiliary reward in addition to our usual reward to
calculate a combined reward $r_{\text{combined}}=r_{\text{energy}}+\alpha
r_{\text{SMiRL}}$. With a SMiRL weight $\alpha$ as a measure of how much the
SMiRL reward influences the total reward. We will describe the explicit
formulation of the SMiRL reward in Section 3.

##  3\. Methods

We adapt SMiRL to the problem of optimizing a price-serving agent for energy
demand response. We will briefly explain the baseline Proximal Policy
Optimization (PPO). We will then describe the simulation environment we test
this in.

###  3.1. Environment

We summarize an OpenAI gym environment modeled after an environment to
simulate demand response in office buildings, visualized in Figure 1 (Brockman
et al., 2016; Spangher et al., [n.d.]). Each step in the environment is a day,
where the RL controller (or agent) is given prices by the utility. The
controller then proposes prices to office workers, who modify their behavior
in order to achieve the lowest cost of energy possible, which is then rewarded
by the controller. The controller then aims to assign prices to office workers
which minimize the total cost of energy paid to the utility.

Figure 1. Reinforcement Learning Control Flow

Can an RL agent learn to provide optimal price signals by implicitly
predicting causal factors? The space of reasonable energy prices to assign is
simple enough to efficiently cover with an entropy maximizing agent, so we
employ a Proximal Policy Optimization (PPO) architecture. We use Ray’s RLLib
PPO algorithm. The reward for the price-setting agent is
$r_{\text{energy}}=\log(d^{t}g)$ where $d$ is the demand of the person it
studies, and $g$ is the grid pricing. We use parameters of learning rate
$\alpha=0.003$, batch size of $256$, training stochastic gradient descent
minibatch of $32$, clip parameter $0.3$ and all other parameters were RLLib
PPO defaults. For other implementation choices, please see our Github111Our
Github may be found at the following link: https://github.com/Aphoh/temp_tc.

###  3.2. SMiRL Reward Formulation

A SMiRL agent recieves an auxiliary reward for experiencing familiar states
based on an updating distribution of states it has experienced. This is
exactly equivalent to learning a policy with the lowest entropy. Assuming we
have a fully-observed controlled Markov process (CMP) with state $s_{t}$ and
action $a_{t}$ at time $t$, and $p(s_{0})$ as the initial state distribution,
and transition probabilities $T(s_{t+1}|s_{t},a_{t})$, the agent learns a
policy $\pi_{\phi}(a|a)$ parameterized by $\phi$. As described earlier, we
keep track of an estimated state marginal $p_{\theta_{t-1}}(s_{t})$ for the
actual state marginal $d^{\pi_{\phi}}(s_{t})$. As usual we denote entropy of a
state $s_{t}$ by $\mathcal{H}\left(s_{t}\right)$. The entropy can then be
calculated by the marginal as

(1) $\displaystyle\sum_{t=0}^{T}\mathcal{H}\left(\mathbf{s}_{t}\right)$
$\displaystyle=-\sum_{t=0}^{T}\mathbb{E}_{\mathbf{s}_{t}\sim
d^{\pi}\phi\left(\mathbf{s}_{t}\right)}\left[\log
d^{\pi_{\phi}}\left(\mathbf{s}_{t}\right)\right]$ (2)
$\displaystyle\leq-\sum_{t=0}^{T}\mathbb{E}_{\mathbf{s}_{t}\sim
d^{\pi}\phi\left(\mathbf{s}_{t}\right)}\left[\log
p_{\theta_{t-1}}\left(\mathbf{s}_{t}\right)\right]$

We bound (1) by the entropy of an estimated marginal $p_{\theta_{t-1}}$ in
(2). Minimizing the right side bound is then equivalent to maximizing an RL
objective with reward $r_{\text{SMiRL}}(s_{t})=\log p_{\theta_{t-1}}(s_{t})$
We note that the optimal policy must also consider future changes to
$p_{\theta_{t-1}}(s_{t})$ since the distribution of visited states changes at
each step. To account for this we use an augmented MDP that captures this
notion. (Berseth et al., 2019) We note that in our implementation of SMiRL,
$p_{\theta_{t}}(s)$ is normally distributed. To construct the augmented MDP we
include sufficient statistics for $p_{\theta_{t}}(s)$ in the state space such
as the paramaeters of our normal distribution and the number of states seen so
far.

###  3.3. SMiRL Implementation

SMiRL is simply implemented in our existing OpenAI socialgame environment. We
introduce SMiRL into our existing socialgame environment by initializing a
buffer that tracks the agent’s observed states and computes an estimated state
marginal $p_{\theta_{t}}$. As noted earlier, in the augmented MDP the state
space also contains the number of observed states and this information is
stored in the buffer as well. At each step in our simulation we add newly
observed states to our buffer, and update $p_{\theta_{t}}$. The agent then
adjusts the its policy based on the combined reward.

We notice that since $p_{\theta}(s)$ is modeled as an independent Gaussian for
each dimension (hour) in the observation (consumption for a day), then the
SMiRL reward is expressed as

(3) $\displaystyle
r_{\text{SMiRL}}(s_{t})=-\sum\limits_{i}\left(\log\sigma_{i}+\frac{(s_{i}-\mu_{i})^{2}}{2\sigma_{i}^{2}}\right)$

where $\mu_{i}$ and $\sigma_{i}$ are the sample mean and standard deviation
from our state marginal and $s_{i}$ is the $i^{th}$ feature ($i^{th}$ hour of
day) of $s$ (Berseth et al., 2019). With this formulation we can efficiently
calculate the SMiRL reward from our buffer.

###  3.4. SMiRL as an Auxilary Reward

We use SMiRL as an auxilary reward to provide faster learning and more stable
outputs. We achieve this by calculating the SMiRL reward $r_{\text{SMiRL}}$ as
described in the previous section, and applying a SMiRL weight $\alpha$ to it
and then using the sum with our usual energy reward
$r_{\text{energy}}=\log(d^{t}g)$. This gives us a combined reward of

(4) $r_{\text{combined}}=r_{\text{energy}}+\alpha r_{\text{SMiRL}}$

and it is this reward that we use to train the RL agent. In our simulations,
we found the optimal SMiRL weight $\alpha$ to be around $\alpha=0.12$ after
hyperparameter tuning. We will discuss the exact results of various SMiRL
weights in Section 4.

##  4\. Results

We now discuss our two aims: more effective learning and a more stable
environment.

###  4.1. Sample Entropy

####  4.1.1. Observing Lower Sample Entropy

As the primary objective of a surprise minimization technique is to, in fact,
minimize surprise, it is natural to determine whether SMiRL does so.

We first quantify the degree to which the environment is more or less entropic
when under the influence of an agent employing SMiRL. Since we assume each
variable in our sample space is normally distributed in a given timeframe, we
can compute its entropy as $H=\frac{1}{2}\ln(2\pi e\sigma^{2})$. For each
step, we compute the sample variance of the last 100 steps and use this to
compute a sample entropy, shown in Figure 2.

While both agents do reduce the sample entropy over time, the SMiRL + PPO
agent does so earlier than the baseline PPO agent. The SMiRL + PPO
implementation exhibits lower sample entropy for all iterations compared to
baseline PPO, and hence energy usage over the course of the simulation is more
consistent when using SMiRL.

Additionally, the SMiRL + PPO agent converges towards a policy which generates
a more stable final environment than the baseline PPO agent. The SMiRL + PPO
agent’s behaviour confirms our hypothesis that the stability of our
environment is superior to our baseline PPO agent by incentivizing the RL
agent to revisit familiar states. We also note that the both agents continue
to explore changes to their policies after convergence, however the SMiRL +
PPO maintains a lower sample entropy in late timesteps. Hence, the SMiRL + PPO
agent explores in ways that maintain a more stable environment, while the PPO
agent’s exploration results in more unstable energy usage.

In this sense, the addition of the SMiRL reward can allow an agent to strike a
balance between exploration and stability.

Figure 2. A comparison between the PPO + SMiRL agent and the baseline PPO
agents’ (a) rewards and (b) sample entropies over training steps. Shaded
regions are one standard deviation of observations binned to every 100 steps.

###  4.2. Improved Learning with SMiRL (Compared to Baseline PPO)

While environment stability is important, it is essenital that the agent still
encorages efficient energy usage. We also wish to understand whether the SMiRL
reward models our assumption of predictability in our system by improved
learning speed.

####  4.2.1. Faster Learning and Consistent Outcomes

We observe that our SMiRL + PPO implementation induces significantly faster
learning and convergence to an equally optimal policy, with the same reward.
As shown by Figure 2(a), both agents maintain similar rewards up until step
~30k, after which the SMiRL + PPO agent begins to achieve, on average, a
higher reward. The SMiRL + PPO implementation converges in roughly half the
time as the baseline PPO agent (step ~50k v.s. step ~110k). The reward in the
environment around step ~60k whereas the PPO baseline does not converge to the
maximum reward in the environment until step ~110k. Our results support our
hypothesis that an auxilary SMiRL reward improves learning speed.

Note that we compare the energy rewards ($r_{\text{energy}}$) here directly
and not the combined reward which includes the SMiRL reward and weight. This
demonstrates the influence of the SMiRL reward on the energy reward, which
describes the overall effectiveness of our agent. Hence the inclusion of the
SMiRL reward results in improved learning speed of our agent in the task it is
given.

Figure 3. Energy consumption with the PPO and SMiRL + PPO agent at steps 10k,
40k, 80k, and 130k compared to the grid price. Please see section 5 for a
brief note on the seemingly adverse behavior in the SMiRL+PPO.

Faster convergence is demonstrated by Figure 3, where energy consumption is
shown at different steps in the environment. The grid price signal the agent
recieves is shown. We observe that, for both the PPO and SMiRL + PPO agent,
the price signal effectively shifts people’s energy consumption away from
times when the grid price is higher. By step 40k, however, the SMiRL + PPO
agent has already begun to greatly reduce consumption during peak, and people
have shifted it towards just before that peak. By step 80k, the SMiRL + PPO
agent has completely diminished any energy usage during the peak pricing,
while the PPO agent only does so by step ~120k (when its reward converges).

####  4.2.2. Optimal SMiRL Weights

We note that while an appropriate SMiRL weight provides significant
improvement in learning speed and sample entropy, an inadequate SMiRL weight
can lead to poor learning that converges to a suboptimal result, and may not
outperform a baseline PPO.

Specifically, we found SMiRL weights of $\alpha=0.25$ and higher performed
worse than baseline PPO. In fact, we find that they converge to a suboptimal
reward in the environment, hinting that too much surprise minimization might
hinder exploration.

For much lower SMiRL weights such as $\alpha=0.01$, we do not see any
significant benefits when compared to baseline PPO; there isn’t enough weight
on the SMiRL reward to have a meaningful impact.

####  4.2.3. Sample Entropy and Environment Reward Curves

When comparing the sample entropy and reward curves in Figure 2 we see that
beginning at steps ~50k, the SMiRL + PPO agent’s observed sample entropy drops
significantly below that of the baseline PPO agent. This correlates closely at
~50k steps where the PPO + SMiRL implementation begins to experience
significantly greater rewards than baseline PPO. Lastly, we observe that at
~110k steps, both agents have observed a drop in sample entropy, and their
environment rewards converge. This correlation between entropy and reward may
support our hypothesis that aiming for a stable environment via surprise
minimization can help the agent learn faster.

##  5\. Discussion

A careful observer may note in Figure 3 that although the energy consumptions
are certainly minimizing the price that a building manager might pay (i.e. the
controller’s reward), large peaks would be unfavorable for the grid if
incentivized large scale. We argue that this is not a defect perse of the
SMiRL modification; only the exploitation of an externality our simulation
does not account for. First, the SMiRL agent is achieving a goal: environment
stability, evidenced in the tightening of confidence bounds around energy
consumption outcomes. Outcome behavior confidence is accomplished by
incentivizing people’s consumption tightly up against the shoulder of TOU
pricing because the mechanics of the simulated office worker cause it to shift
energy usage when offered high prices. Therefore the controller learns to rely
on shifting. While the SMiRL + PPO and PPO agents are equal in the energy
reward the controller receives, the inclusion of the SMiRL reward creates more
consistent energy usage from day to day. The behavior is optimal given the
externalities we have encoded (or not encoded) into the reward, so should not
be seen as a deficit of the controller. It would be straightforward, and the
subject of future work, to modify the reward in order to direct the controller
to spread energy evenly amonst non-peak hours.

After consider this, SMiRL has shown promising results in increasing
environment stability, and observed improvements in learning speeds support
our hypothesis that SMiRL can take advantage of inherent predictability in
people’s energy consumption.

From the energy consumptions in Figure 3 we note that SMiRL induces faster
convergence to cheaper energy consumptions, which would translate into direct
energy cost.

The results of our simulation and related work show that in appropriate
environments, the auxiliary SMiRL reward can improve learning while also
letting the RL agent explore. We argue that a human-in-the-loop environment is
necessarily complex enough that encouraging surprise minimization encourages
the agent to more quickly grasp the latent similarities that govern the
environment. We look towards our experiment to continue to demonstrate this.

###  5.1. Future Research

SMiRL can handle variations in a $k$-discrete state-space by creating $k$
separate buffers, one for each variation of the state-space, that shrink the
action sampling towards each $k$ category. We propose to adapt this to a
continuous state-space by clustering main categories of observation. One of
the main inputs to the state space is price signals, so we propose to cluster
based on a semantic feature search proposed in (Afzalan and Jazizadeh, 2019)
for building load profiles.

###  5.2. Acknowledgements

We gratefully acknowledge the input of Manan Khattar, Austin Jang, and Dustin
Luong as working group collaborators, and Glen Berseth for his initial work on
SMiRL.

## References

  * (1)
  * Afzalan and Jazizadeh (2019) Milad Afzalan and Farrokh Jazizadeh. 2019.  Semantic search in household energy consumption segmentation through descriptive characterization. In _Proceedings of the 6th ACM International Conference on Systems for Energy-Efficient Buildings, Cities, and Transportation_. 263–266.
  * Asadinejad et al. (2018) Ailin Asadinejad, Alireza Rahimpour, Kevin Tomsovic, Hairong Qi, and Chien-fei Chen. 2018.  Evaluation of residential customer elasticity for incentive based demand response programs.  _Electric Power Systems Research_ 158 (2018), 26–36.
  * Berseth et al. (2019) Glen Berseth, Daniel Geng, Coline Devin, Chelsea Finn, Dinesh Jayaraman, and Sergey Levine. 2019\.  SMiRL: Surprise Minimizing RL in Dynamic Environments.  _CoRR_ abs/1912.05510 (2019).  arXiv:1912.05510 http://arxiv.org/abs/1912.05510
  * Brockman et al. (2016) Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojciech Zaremba. 2016.  OpenAI Gym.  arXiv:arXiv:1606.01540
  * Das et al. (2020) Hari Prasanna Das, Ioannis Konstantakopoulos, Aummul Baneen Manasawala, Tanya Veeravalli, Huihan Liu, and Costas J Spanos. 2020.  Do Occupants in a Building exhibit patterns in Energy Consumption? Analyzing Clusters in Energy Social Games.  (2020).
  * Das et al. (2019) Hari Prasanna Das, Ioannis C Konstantakopoulos, Aummul Baneen Manasawala, Tanya Veeravalli, Huihan Liu, and Costas J Spanos. 2019\.  A novel graphical lasso based approach towards segmentation analysis in energy game-theoretic frameworks. In _2019 18th IEEE International Conference On Machine Learning And Applications (ICMLA)_. IEEE, 1702–1709.
  * Fuselli et al. (2013) Danilo Fuselli, Francesco De Angelis, Matteo Boaro, Stefano Squartini, Qinglai Wei, Derong Liu, and Francesco Piazza. 2013.  Action dependent heuristic dynamic programming for home energy resource scheduling.  _International Journal of Electrical Power & Energy Systems_ 48 (2013), 148–160.  https://doi.org/10.1016/j.ijepes.2012.11.023
  * Johnson et al. (2015) Brandon J Johnson, Michael R Starke, Omar A Abdelaziz, Roderick K Jackson, and Leon M Tolbert. 2015.  A dynamic simulation tool for estimating demand response potential from residential loads. In _2015 IEEE Power & Energy Society Innovative Smart Grid Technologies Conference (ISGT)_. IEEE, 1–5.
  * Kim (2018) Y. Kim. 2018.  Optimal Price Based Demand Response of HVAC Systems in Multizone Office Buildings Considering Thermal Preferences of Individual Occupants Buildings.  _IEEE Transactions on Industrial Informatics_ 14, 11 (2018), 5060–5073.  https://doi.org/10.1109/TII.2018.2790429
  * Kofinas et al. (2018) P. Kofinas, A.I. Dounis, and G.A. Vouros. 2018.  Fuzzy Q-Learning for multi-agent decentralized energy management in microgrids.  _Applied Energy_ 219 (2018), 53–67.  https://doi.org/10.1016/j.apenergy.2018.03.017
  * Konstantakopoulos et al. (2019a) Ioannis C Konstantakopoulos, Andrew R Barkan, Shiying He, Tanya Veeravalli, Huihan Liu, and Costas Spanos. 2019a.  A deep learning and gamification approach to improving human-building interaction and energy efficiency in smart infrastructure.  _Applied energy_ 237 (2019), 810–821.
  * Konstantakopoulos et al. (2019b) Ioannis C Konstantakopoulos, Hari Prasanna Das, Andrew R Barkan, Shiying He, Tanya Veeravalli, Huihan Liu, Aummul Baneen Manasawala, Yu-Wen Lin, and Costas J Spanos. 2019b.  Design, benchmarking and explainability analysis of a game-theoretic framework towards energy efficiency in smart infrastructure.  _arXiv preprint arXiv:1910.07899_ (2019).
  * Li et al. (2018) Chaojie Li, Chen Liu, Xinghuo Yu, Ke Deng, Tingwen Huang, and Liangchen Liu. 2018\.  Integrating Demand Response and Renewable Energy In Wholesale Market.. In _IJCAI_. 382–388.
  * Li and Jayaweera (2014) D. Li and S. K. Jayaweera. 2014.  Reinforcement learning aided smart-home decision-making in an interactive smart grid. In _2014 IEEE Green Energy and Systems Conference (IGESC)_. 1–6.  https://doi.org/10.1109/IGESC.2014.7018632
  * Liu et al. (2015) Y. Liu, C. Yuen, N. Ul Hassan, S. Huang, R. Yu, and S. Xie. 2015\.  Electricity Cost Minimization for a Microgrid With Distributed Energy Resource Under Different Information Availability.  _IEEE Transactions on Industrial Electronics_ 62, 4 (2015), 2571–2583.  https://doi.org/10.1109/TIE.2014.2371780
  * Ma et al. (2015) Kai Ma, Guoqiang Hu, and Costas J Spanos. 2015.  A cooperative demand response scheme using punishment mechanism and application to industrial refrigerated warehouses.  _IEEE Transactions on Industrial Informatics_ 11, 6 (2015), 1520–1531.
  * Mbuwir et al. (2017) Brida V. Mbuwir, Frederik Ruelens, Fred Spiessens, and Geert Deconinck. 2017.  Battery Energy Management in a Microgrid Using Batch Reinforcement Learning.  _Energies_ 10, 11 (2017).  https://www.mdpi.com/1996-1073/10/11/1846
  * Raju et al. (2015) Leo Raju, Sibi Sankar, and R.S. Milton. 2015.  Distributed Optimization of Solar Micro-grid Using Multi Agent Reinforcement Learning.  _Procedia Computer Science_ 46 (2015), 231–239.  https://doi.org/10.1016/j.procs.2015.02.016 Proceedings of the International Conference on Information and Communication Technologies, ICICT 2014, 3-5 December 2014 at Bolgatty Palace & Island Resort, Kochi, India.
  * Schulman et al. (2017) John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. 2017.  Proximal Policy Optimization Algorithms.  _CoRR_ abs/1707.06347 (2017).  arXiv:1707.06347 http://arxiv.org/abs/1707.06347
  * Spangher et al. (2020a) Lucas Spangher, Akash Gokul, Manan Khattar, Joseph Palakapilly, Utkarsha Agwan, Akaash Tawade, and Costas Spanos. 2020a.  Augmenting Reinforcement Learning with a Planning Model for Optimizing Energy Demand Response. In _Proceedings of the 1st International Workshop on Reinforcement Learning for Energy Management in Buildings & Cities_. 39–42.
  * Spangher et al. (2020b) Lucas Spangher, Akash Gokul, Manan Khattar, Joseph Palakapilly, Akaash Tawade, Adam Bouyamourn, Alex Devonport, and Costas Spanos. 2020b.  Prospective experiment for reinforcement learning on demand response in a social game framework. In _Proceedings of the Eleventh ACM International Conference on Future Energy Systems_. 438–444.
  * Spangher et al. ([n.d.]) Lucas Spangher, Akash Gokul, Joseph Palakapilly, Utkarsha Agwan, Manan Khattar, Wann-Jiun Ma, and Costas Spanos. [n.d.].  OfficeLearn: An OpenAI Gym Environment for Reinforcement Learning on Occupant-Level Building’s Energy Demand Response. In _Tackling Climate Change with Artificial Intelligence Workshop at NeurIPS, 2020_.
  * Sutton and Barto (2018) Richard S Sutton and Andrew G Barto. 2018.  _Reinforcement learning: An introduction_.  MIT press.
  * Wei et al. (2015) Q. Wei, D. Liu, and G. Shi. 2015.  A novel dual iterative Q-learning method for optimal battery management in smart residential environments.  _IEEE Transactions on Industrial Electronics_ 62, 4 (2015), 2509–2518.  https://doi.org/10.1109/TIE.2014.2361485
  * Yoon et al. (2014) Ji Hoon Yoon, Ross Baldick, and Atila Novoselac. 2014\.  Dynamic demand response controller based on real-time retail price for residential buildings.  _IEEE Transactions on Smart Grid_ 5, 1 (2014), 121–129.
  * Zhang and van der Schaar (2014) Y. Zhang and M. van der Schaar. 2014.  Structure-aware stochastic load management in smart grids. In _IEEE INFOCOM 2014 - IEEE Conference on Computer Communications_. 2643–2651.  https://doi.org/10.1109/INFOCOM.2014.6848212


Y ~=~ [\olft y_{n-1}+1,\ort y_n] ~\cup \bigcup_{1\le i<n} Y_i.
\]
%Intuitively, $Y$ represents the undefined set $Y_n$,
%where the non-existing level $\olft y_n$ has been replaced
%by the largest $\ort y_j$, that is $\ort y_n$ .
We prove a claim similar to the previous one,
but now aiming to cover $Y$ with a {\sl cycle}.
%As a matter of fact, the cycle that we will construct
%must coincide with $C$, since it is contained in $C$,
%$C$ is a strongly connected component, and every node
%of $C$ has in-/out-degree $1$.
%In particular, this will imply that $C$ contains $Y$.
Towards the end of the proof we will argue that the set
$Y$ coincides with the full interval $Z$,
thus showing that there is a component $C$
whose set of notes is precisely $Z$.

\begin{clm}
There is a cycle that covers $Y$.
\end{clm}

\begin{proof}
It is convenient to construct our cycle starting from the last
$\LR$-edge, that is, $\ort y_n \rightarrow \olft y_{n-1} + 1$,
since this will cover the upper node $\ort y_n=\max(Z)$.
%\felix{We need to state and explain that property somewhere}
%\gabriele{It is now explained above}
From there we continue to add edges and incremental paths,
following an approach similar to the proof of the previous
claim, until we reach the node $\ort y_n$ again.
More precisely, we consider the edges that depart from nodes strictly
between $\olft y_{n-1}$ and $\ort y_n$. As there are only $n-1$ $\RL$-edges,
we know that every node in the interval $[\olft y_{n-1}+1,\ort y_n-1]$
must be source of an $\LL$-edge, an $\RR$-edge, or an $\LR$-edge.
As usual, incremental edges do not pose particular problems for
the construction of the cycle, so we focus on the $\LR$-edges.
Let $\ort y_i \rightarrow \olft y_{i-1}+1$ be such an $\LR$-edge,
with $\ort y_i \in [\olft y_{n-1}+1,\ort y_n-1]$. Since $i < n$, we know
from the previous claim that there is a path from $\ort y_i$ to $\ort y_i+1$
that covers $Y_i$.
We can thus build a cycle $\pi$ by connecting the above
paths using the incremental edges and the $\LR$-edge
$\ort y_n \rightarrow \olft y_{n-1} + 1$.

By construction, the cycle $\pi$ covers
the interval $[\olft y_{n-1}+1,\ort y_n]$, and for every
$i<n$, if $\pi$ visits $\ort y_i$, then $\pi$ covers $Y_i$.
So to complete the proof --- namely, to show that $\pi$ covers the entire set $Y$ ---
it suffices to prove that $\pi$ visits each node $\ort y_i$, with $i<n$.

Suppose, by way of contradiction, that $\ort y_i$ is the node
with the highest index $i<n$ that is not visited by $\pi$.
Recall that $\ort y_i > \olft y_i$. This shows that
\[
\ort y_i ~\in~ [\olft y_i+1,\ort y_n] ~= \bigcup_{i\le j<n-1}[\olft y_j+1,\olft y_{j+1}] ~\cup~ [\olft y_{n-1}+1,\ort y_n].
\]
As we already proved that $\pi$ covers the interval $[\olft y_{n-1}+1,\ort y_n]$,
we know that $\ort y_i \in [\olft y_j+1,\olft y_{j+1}]$ for some $j$ with $i\le j<n-1$.
Now recall that $\ort y_i$ is the highest node that is not visited by $\pi$. This means
that $\ort y_{j+1}$ is visited by $\pi$. Moreover, since $j+1<n$, we know
that $\pi$ uses the incremental path from $\ort y_{j+1}$ to $\ort y_{j+1}+1$, which
covers $Y_{j+1} = [\olft y_j+1,\olft y_{j+1}]$. But this contradicts the fact that $\ort y_i$
is not visited by $\pi$, since $\ort y_i \in [\olft y_j+1,\olft y_{j+1}]$.
\end{proof}

We know that the set $Y$ is covered by a cycle of the subgraph of $Z$, and that
$Z$ is an interval whose endpoints are consecutive levels $z<z'$, with $d_z=d_{z'}=0$.
For the homestretch, we prove that $Y=Z$. This will imply that the nodes of
the cycle are precisely the nodes of the interval $Z$.
Moreover, because the cycle must coincide with a component $C$ of the flow
(recall that all the nodes have in-/out-degree $1$), this will show that
the nodes of $C$ are precisely those of $Z$.

To prove $Y=Z$ it suffices to recall its definition as the union of
the interval $[\olft y_{n-1}+1,\ort y_n]$ with the sets $Y_i$, for all $i=1,\dots,n-1$.
Clearly, we have that $Y\subseteq Z$.
For the converse inclusion, we also recall that
$\olft y_0+1 = 0 = \min(Z)$ and $\ort y_n=\max(Z)$.
Consider an arbitrary level $z\in Z$. Clearly, we have either
$z\le \olft y_i$, for some $1\le i<n$, or $z > \olft y_n$.
In the former case, by choosing the smallest index $i$ such that $z \le \olft y_i$,
we get $z\in [\olft y_{i-1}+1,\olft y_i]$, whence $z\in Y_i \subseteq Y$.
In the latter case, we immediately have $z\in Y$, by construction.
\end{proof}

%%% Local Variables:
%%% mode: latex
%%% TeX-master: "main.tex"
%%% End:

\end{document}