# Persistence-based operators in machine learning

Mattia G. Bergomi
Independent Researcher
Milan, Italy
<EMAIL_ADDRESS>
Massimo Ferri
ARCES and Dept of Mathematics,
University of Bologna, Italy
<EMAIL_ADDRESS>
Alessandro Mella
Independent Researcher
Verona, Italy
<EMAIL_ADDRESS>
Pietro Vertechi
Independent Researcher
Trieste, Italy
<EMAIL_ADDRESS>
###### Abstract

Artificial neural networks can learn complex, salient data features to achieve
a given task. On the opposite end of the spectrum, mathematically grounded
methods such as topological data analysis allow users to design analysis
pipelines fully aware of data constraints and symmetries. We introduce a class
of persistence-based neural network layers. Persistence-based layers allow the
users to easily inject knowledge about symmetries (equivariance) respected by
the data, are equipped with learnable weights, and can be composed with state-
of-the-art neural architectures.

##  1 Introduction

Topological data analysis and topological persistence (TP) rely on user-
defined functions to generate concise fingerprints of topological objects,
e.g., triangulable manifolds and simplicial complexes. These fingerprints
carry information about the geometrical and topological features of an object
as seen through the lenses of the user-defined function. On the other hand,
artificial neural architecture layers learn weights to represent their input
optimally for a user-defined task.

TP requires users to endow the data with a topological structure and then
devise specialized continuous functions to highlight salient features of the
transformed dataset for the task at hand. Artificial neural networks learn
such functions through gradient optimization of a differentiable error
function and provide layer templates adapted to the structure of most data
types, e.g., convolutional layers [1] for images and recurrent architectures
[2] for time-varying signals. However, only few theoretical frameworks and
algorithms provide ways to inject knowledge into neural networks.

Interactions between TP and deep learning are of broad interest [3, 4, 5].
Ideally, combining the two methods would yield easily constrainable and
learnable layers, composable with state-of-the-art neural network layers. We
believe that the need to map data to topological objects and express their
features as critical points of continuous functions hinders the development of
TP-inspired neural layers.

#### Aim.

We provide a plain approach to the design of persistence-based layers for
artificial neural architectures. Particularly, we leverage rank-based
persistence—a generalization of topological persistence [6]—to avoid complex
auxiliary constructions mapping data to topological objects and work, when
needed, with more natural data representations. Then, thanks to the notion of
persistent features developed in [7], we define persistence-based operators
taking advantage of the properties of the data itself.

#### Contribution.

We provide a streamlined introduction to topological and rank-based
persistence, and to persistent features. Then, we define and give constructive
examples of operators based on persistent features and discuss their
properties, particularly equivariance (constrainability) and noise robustness.
After showcasing these properties on images, we define the persistent feature-
based neural network layer. We base our proposal of persistence-based layer on
two main principles. On the one hand, we aim to learn relevant (persistent)
features from data points. On the other hand, we provide simple strategies to
take advantage of locality and equivariance, two key notions for the analysis
of structured data. We provide an algorithm for a persistence-based pooling
operator, test it on several architectures and datasets, and compare it with
some classical pooling layers.

#### Structure.

Section 2 provides intuition on the central mathematical concepts involved in
the definition of persistence-based layer: topological persistence (e.g.,
persistent homology), rank-based persistence, and persistent feature. In
section 3, we devise an image filtering algorithm based on persistent
features, discuss its main properties, and provide examples. Thereafter, we
define a persistence-based neural network layer and specialize it to act as a
pooling layer in convolutional neural networks. Computational experiments in
section 4 evaluate and compare the performance of the proposed pooling layer
in an image-classification task on several datasets and on two different
architectures. In the same section, we provide a qualitative analysis of the
most salient features detected by the persistence-based pooling, the classical
max-pooling, and LEAP [8].

##  2 Background

Topological persistence and persistent homology have been extended in several
ways, e.g., [9, 10, 11, 12, 13]. However, we place our proposal in the rank-
based framework to work as independently as possible from auxiliary mappings
from the data points to topological spaces.

In the following paragraphs, we intuitively define and provide references for
the essential mathematical constructions that motivate and inspire the idea of
persistent-based layers: persistent homology, rank-based persistence, and
steady persistent features.

###  2.1 Rank-based persistence

Persistent homology requires three main ingredients:  1. A filtered
topological space,  2. the homology functor $S_{k}$ mapping topological spaces
to finite vector spaces, and  3. a notion of rank, e.g., dimension for vector
spaces or cardinality for sets [14].  See fig. 1 for an exemplification of
persistent homology, and [15] for details.

Figure 1: Persistent homology. Let us consider a topological space $X$ and a
continuous function $f:X\rightarrow{\mathbb{R}}$. The (homological) critical
values of $f$ induce a sub-level set filtration of $X$. (a) Critical values
$C=\\{c_{1},\dots,c_{6}\\}$ of the height function on a a topological sphere.
Sublevels of the filtering function $f$—namely
$f^{-}1\left((-\infty,c]\right)$, for every $c\in C$—yield a filtration of the
topological sphere. (b) Changes in number of generators of the $k$th homology
groups along the filtration can be represented as a persistence diagram.
$0$-dimensional holes (connected components) are represented as green points.
The void obtained at the last sublevel set gives rise to the blue line. (c)
Persistence diagrams can be compared by computing an optimal matching of
points. Unmatched points are associated with their projection on the diagonal.

We choose to frame our work in a more general context than homological
persistence, namely rank-based persistence [6]. There, assuming an axiomatic
standpoint based on the three building blocks of homological persistence
mentioned above, the authors generalize persistence to categories and functors
other than topological spaces and homology. Importantly, under few
assumptions, persistence built in the rank-based framework still guarantees
fundamental properties such as flexibility (dependence on the filtering
function), stability [16], and robustness [17]. In this setting, we can work
with data types such as images and time series, without intermediary
topological constructions. We refer to [6] for details and provide a list of
analogies between classical and rank-based persistence in table 1.

Classical framework | Categorical framework
---|---
Topological spaces | Arbitrary source category $\mathbf{C}$
Vector spaces | Regular target category $\mathbf{R}$
Dimension | Rank function on $\mathbf{R}$
Homology functor | Arbitrary functor from $\mathbf{C}$ to $\mathbf{R}$
Filtration of topological spaces |  ${(\mathbb{R},\leq)}$-indexed diagram in $\mathbf{C}$
Table 1: Analogy between the classical and rank-based persistence frameworks.
Figure 2: Persistent features. (a) A weighted graph $(G,f)$. The weight
values—integers in the set $\\{2,5,10\\}$—are encoded as the thickness of the
edges. (b) The sublevel set filtration induced by the weights. Teal vertices
are the vertices in each sublevel with local degree prevalence. (c) The
persistence diagram obtained by considering the steadiness of each true subset
along the filtration. One vertex realizes local degree prevalence at level $5$
and stops being prevalent entering level $10$. Another vertex is prevalent at
level $10$ and shall never stop being such because $f^{-1}((-\infty,10])=G$.

###  2.2 Persistent features

Figure 3: Persistent features. An image (a) and its interpretation as weighted
graph. (b) Given a focus pixel and its neighborhood (a $3\times 3$ patch in
the example), we map the image to a graph $G$ having as vertices the patch’s
pixels and edges connecting adjacent pixels. We weight edges of $G$ by
evaluating the function
$f:{\mathbb{R}}\times{\mathbb{R}}\rightarrow{\mathbb{R}}$ mapping the
intensity values of two vertices to the minimum intensity values of the
respective pixels in the image. Edges with weight $0$ are not showed. (c) The
sublevel-set filtration induced by the weights. Teal vertices are the ones
with prevalent local degree. (d) The persistence diagram obtained considering
the filtration/feature pair.

In the spirit of the aforementioned generalization, [7, Sec. 2.2] introduces
the concept of steady persistent features for weighted graphs.

A weighted graph is a pair $(G,f)$, where $G=(V,E)$ is a graph defined by a
set of vertices $V$ and edges $E$, and $f$ is a function assigning (tuples of)
real-valued weights to the edges of $G$, in symbols
$f:e_{i}=[v_{i,1},v_{i,2}]\mapsto w_{i}$. The weighting function naturally
induces a sublevel set filtration

$\emptyset\subseteq S_{1}=f^{-1}((-\infty,w_{1}])\subseteq\cdots\subseteq
S_{n}=f^{-1}((-\infty,w_{n}])=G.$

For an intuition, see fig. 2, panels (a) and (b).

Let $S=2^{V\cup E}$ be the set of all subsets of elements (vertices and edges)
of $G$. Let $F$ be a graph-theoretical property, e.g., local degree
prevalence, independence. The persistent feature
$\mathcal{F}:S\rightarrow\\{\textrm{true},\textrm{false}\\}$ associated with
$F$ is a boolean mapping returning true if the property $F$ holds for a
certain subset $s\in S$ and false otherwise. Symmetrically to the topological
persistence framework, we evaluate $\mathcal{F}$ for every subset of every
$\\{S_{i}\\}_{i}$. See fig. 2, panel (b). Then, we compute the steadiness
$\sigma$ of each subset $s$ along the filtration by counting subsequent
sublevels such that $\mathcal{F}(s)=\textrm{true}$. As in [7], we refer to
$\sigma((G,f,\mathcal{F}))$ as the steady persistence of the feature
$\mathcal{F}$ on $(G,f)$. This construction yields a persistence diagram. See
fig. 2, panel (c).

##  3 Persistence-based layers

Figure 4: Persistence-based filter. (a). The persistence-based filter acts in
an equivariant fashion (the same feature is recognized throughout the image)
and parametrization changes lead to detection of heterogeneous features. (b)
We perform edge detection on a noisy input ($40\%$ of the pixels are salt and
pepper noise). Performance are compared across the proposed persistence-based
filter, Canny, and Sobel edge-detection algorithms with and without
preprocessing (median filter). Results are showcased for different ratios of
noisy pixels.

Applying the definition of steady persistent function, we build a persistence-
based operator that can act as a filter on grayscale images (RGB images can be
treated as by considering channels independently). We discuss important
properties of such operators, such as locality and equivariance. Then, we
adapt the operator to work as a pooling layer in a convolutional neural
network.

###  3.1 Persistent features as equivariant filters

Locality and equivariance are crucial features for convolutional neural
networks, and in general for any group-equivariant model. Indeed,

  1. 1.

the intensity of a pixel in a grayscale image carries knowledge only when
compared to neighboring pixels;

  2. 2.

identical configurations located in different regions of the image
(translated) are recognized by translation-equivariant models.

#### Locality.

In this setting, considering the notion of persistent feature introduced in
section 2.2, we think about an image as a graph in which vertices are pixels
and edges connect adjacent pixels. Patches (or windows) of size $k$ around a
pixel (point) correspond to $k$-distance neighborhoods of the vertex
associated to such pixel.

#### Flexibility.

Persistent features require a filtered space to be computed. Thus, after
associating a graph to an image (or time series), we define the filtration
$f:S\rightarrow{\mathbb{R}}^{n}$, where $S$ is the set of all subsets of
$V\cup E$ and $n\in\mathbb{N}$. Importantly, $f$ can carry additional
information about the original data: when considering images, one can
associate with each vertex the intensity value of its underlying pixel, and
leverage this information to compute appropriate weights. See fig. 3, panels
(a) and (b).

#### Equivariance.

Once the pair $(G,f)$ has been associated to our data, the proposed
construction is naturally equivariant with respect to translation. Indeed,
sublevel set filtrations and persistent features are totally determined by the
weights and connectivity of the graphs at each filtration level. It is
important to notice that the flexibility of the proposed solution makes it
possible to further control the equivariance of the operator. For instance,
weighting functions that only depend on pairwise intensity values will
generate operators that not only are equivariant with respect to translations,
but also to isometries (translation, rotations, reflection, and scaling) of
the original data.

#### Parametrization.

We can create parametrized $f$ and $\mathcal{F}$ to create operators endowed
with more complex equivariance and learnable parameters. Let
$S_{t}=\iota^{-1}((-\infty,t])$ be a sublevel of $G$ naturally induced by the
intensity of pixels (edges are added when the vertices they connect are
added). We define $\mathcal{G}_{m,n}^{k}(v,t)$ as the feature mapping $v$ to
true if more than $m$ and less than $n$ pixels in the $k$-distance
neighborhood of $v$ have intensity less than $t$. Panel (a) of fig. 4 shows
how varying parameters $m$ and $n$ allows us to highlight radically different
aspects of a binary image.

######  Remark 1.

$\mathcal{G}$ does not rely on the $2$-dimensional structure of the selected
patch, thus, its steady persistence diagram is not only invariant with respect
to translations, but also to permutations. This kind of equivariance meshes
the standard convolutional equivariance with the fully-connected input/output
representation typical of dense layers of an artificial neural network.

#### Robustness.

In the context of both topological and rank-based persistence, robustness
means small changes in the image do not give rise to significant perturbations
of the corresponding persistence diagram. This concept is defined in [7] for
persistent features and dubbed balancedness. In [18], it is formally shown
that $\mathcal{G}$ is a balanced feature in the sense of [7]. Robustness to
noise is tested in fig. 4, panel (b).

###  3.2 A steady, persistent-feature layer

Figure 5: Persistence-based Pooling.

The filter $\mathcal{G}$ and its steady persistence introduced in section 3.1
are endowed with features inherited from their mathematical foundation which
make them suitable for tackling typical machine learning tasks:  1.
$\mathcal{G}$enhances signal in correspondence of abrupt signal changes (a
max-pooling filter could be blind to such features);  2. the steady
persistence $\sigma(\mathcal{G})$ yields equivariant representations of the
input with respect to the group of isometry;  3. salt-and-pepper noise does
not impair the quality of detected features.

These properties motivate implementing and testing $\sigma(\mathcal{G})$ as a
complement to pooling and convolutional operators in standard artificial
neural networks. In the following paragraph, we discuss the computability of
$\sigma(\mathcal{G})$, and then introduce some learnable, i.e., continuous,
parameters allowing to fully integrate our operator in machine learning
pipelines based on automatic differentiation.

In the remainder, we discuss how to implement and add learnable parameters to
the pooling case. The same operator can be easily adapted to work as a
convolution-like layer.

#### Persistence-based pooling.

We consider an image $I$ and split it in a collection of patches
$\\{P(h,w)_{i}\\}$ of size $(h,w)\in\mathbb{N}^{2}$. For every pixel $p\in
P_{i}$, we compute $\sigma(\mathcal{G}_{m,n}^{k})(p)$ for some fixed values of
$m,n$ and $k$ (padding is added if needed). This procedure, which
computationally boils down to sorting and slicing operations, yields a
persistence diagram having a point per each pixel in $P_{i}$. Indeed, we
compute the operator $\mathcal{G}$ for every of $P_{i}$, padding the patch
whenever necessary. Symmetrically to the classical max-pooling operator, the
maximum persistence—i.e., the distance from the diagonal—shall determine the
value to be associated to the entire patch and its downsampling. As an
example, see fig. 5, panels (a), (b), and top row of (c).

#### Parametrization.

Alternatively and following the idea of learnable pooling operators, e.g. [8],
we propose to learn weights $\Lambda$ to modulate the contribution of each
non-zero component of the persistence diagram, as depicted in fig. 5 panel
(c). Because the persistence value associated with each pixel is continuous
and $\mathcal{G}$ is balanced, we learn such weights through standard
backpropagation.

##  4 Computational experiments

We assess the performance of the suggested pooling layer embedding it into two
neural architectures. First, we compare the performance of the persistence-
based pooling with some classical pooling implementations, then we test
differences in detected saliency across the considered pooling layers.

###  4.1 Datasets

We perform computational experiments on the MNIST [19], Fashion-MNIST [20],
and CIFAR-10 [21] datasets. The MNIST and Fashion-MNIST datasets are composed
of grayscale images labelled according to ten classes of hand-written digits
and fashion articles, respectively. Both dataset are composed of 60000, 28
pixel by 28 pixel, black and white images for training, and 10000 for testing.
The CIFAR-10 dataset is composed of 50000, 32 pixel by 32 pixel, RGB images
for training, belonging to ten classes: airplane, automobile, bird, cat, deer,
dog, frog, horse, ship, and truck. 10000 labelled test images are also
available.

Figure 6: Benchmark architectures. The two architectures used in computational
experiments. (a) A toy neural network where a pooling operator is applied
directly to input images. The downsampled output of the pooling layer is
passed to a dense classifier. In other words, first, the pooled output is
flattened, then its dimensionality reduced to match the number of classes to
be predicted by the network. (b) As common practice for CNNs, this
architecture alternates convolutional and pooling layers before the dense
classifier.

###  4.2 Architectures

We test the proposed layer with two neural network architectures, see fig. 6.
We designed the first architecture to provide the simplest configuration in
which different pooling operators could be compared during a supervised task
where parameters are learned via gradient propagation. The second architecture
is more akin to the standard convolutional neural network topology in a simple
image-classification task: we alternate convolutional an pooling layers,
before a dense classifier.

#### Training.

We use sparse categorical cross-entropy as loss function [22], and the ADAM
optimizer [23] with learning rate $3e-4$. Images are fed to the networks in
batches of size $32$. We accept a maximum of $100$ training epochs, setting
early stopping [24] with parameters $\textrm{min\\_delta}=0$ and
$\textrm{patience}=3$.

###  4.3 Results

Architecture \- Dataset | Max | LEAP |  PL (ours) |  PML (ours)
---|---|---|---|---
(a) - MNIST | 0.8905 | 0.9238 | $\boldsymbol{0.9472}$ | 0.9087
(b) - MNIST | 0.9886 | 0.9848 | $\boldsymbol{0.9908}$ | 0.9880
(a) - FMNIST | 0.7978 | 0.8385 | 0.8424 | $\boldsymbol{0.8435}$
(b) - FMNIST | 0.8845 | 0.8776 | 0.8930 | $\boldsymbol{0.8985}$
(a) - CIFAR-10 | 0.3226 | 0.3291 | $\boldsymbol{0.4185}$ | 0.3869
(b) - CIFAR-10 | 0.6145 | 0.5217 | 0.6355 | $\boldsymbol{0.6499}$
Table 2: The accuracy realized by the selected architectures when endowed with
ours and state-of-the-art pooling layers.

#### Performance.

We tested the architectures presented in section 4.2 on classification of the
MNIST, Fashion-MNIST, and CIFAR-10 datasets. For the latter dataset, we
adapted the persistence-based and convolutional layer to work with RGB images.
Specifically, the persistence-based pooling layer treats channels
independently, thus in parallel and without allowing for any interactions
among them.

We compared the performance of several pooling layers, namely:

  * •

max-pooling,

  * •

persistence-based-pooling (ours),

  * •

a combination of persistence-based- and max-pooling,

  * •

LEAP [8].

The combination between persitence-based- and max-pooling layers is realized
by adding the value obtained by max-pooling on a specific patch to the
weighted sum defined in section 3.2.

We report the results in terms of accuracy in table 2. The proposed layers
outperform max-pooling and LEAP on both datasets. The combination of max- and
persistence-based-pooling realizes maximum performance in three out of six
experiments. This hints to the complementarity of the two approaches.

######  Remark 2.

We combine the persistence-based- and max-pooling simply by adding the maximum
intensity value of the patch to the weighted sum defined in section 3 and
described in fig. 5, panel (c).

#### Explainability

We believe that persistence (topological or generalized) can be of great help
in making artificial intelligence explainable, an issue that is luckily
gaining more and more attention [25, 26, 27] Pooling operators aim to select
salient features of their input. We evaluate the similarity across the
features detected by the examined pooling layers via Grad-CAM heatmaps [28].
Some examples are showcased in fig. 7.

Figure 7: Grad-CAM heatmaps show pixel-wise saliency of features of an image
with respect to the neural network’s gradients. Each row provides an example
from a different dataset: MNIST, Fashion-MNIST, and CIFAR-10, respectively.

##  5 Conclusions

We work at the crossroad between artificial neural networks, and topological
persistence and its generalizations. On the one hand, artificial neural
networks can approximate arbitrarily complex functions optimizing an error
functions with respect to their input data. On the other hand, the persistence
framework provides swift strategies to build easily constrainable analysis
pipelines.

We introduce persistence-based layers to pave the road to the design and
implementation of hybrid strategies: data-driven and easily constrainable. We
base our proposal on the rank-based persistence framework and the concept of
steady persistent feature. This foundation endows our layer of important
properties such as equivariance and robustness to noise, without requiring
auxiliary topological construction that could, a priori alter the information
originally carried by data of non-topological nature.

Computational experiments on image classification showcase the performance of
the proposed persistence-based pooling—a special case of persistence-based
layer—against standard pooling operators. Moreover, a pixel-wise saliency
analysis through Grad-CAM heatmaps on input images reveals how the proposed
pooling layer relies on different features than max-pooling and LEAP.

This approach meshes well with the framework developed in [29], where inputs,
outputs, and weights of a neural network layer are expressed as functions on
smooth or discrete spaces. There, we showed how several classes of linear
neural network layers can be expressed as a combination of function pullback
(from a smaller to a larger space), pointwise multiplication of functions, and
integration along fibers. We believe that, by combining the two approaches, it
will be possible to define general parametric nonlinear layers, where the
architecture is defined by means of the parametric spans introduced in [29],
whereas the geometry-aware nonlinear computation descends from the methods
developed here.

## Acknowledgement

Work performed under the auspices of INdAM-GNSAGA.

## References

  * [1] Y. LeCun, P. Haffner, L. Bottou, Y. Bengio, Object recognition with gradient-based learning, in: Shape, contour and grouping in computer vision, Springer, 1999, pp. 319–345.
  * [2] Y. Yu, X. Si, C. Hu, J. Zhang, A review of recurrent neural networks: Lstm cells and network architectures, Neural computation 31 (7) (2019) 1235–1270.
  * [3] Z. Cang, G.-W. Wei, Integration of element specific persistent homology and machine learning for protein-ligand binding affinity prediction, International journal for numerical methods in biomedical engineering 34 (2) (2018) e2914.
  * [4] M. G. Bergomi, P. Frosini, D. Giorgi, N. Quercioli, Towards a topological–geometrical theory of group equivariant non-expansive operators for data analysis and machine learning, Nature Machine Intelligence 1 (9) (2019) 423–433.
  * [5] C. S. Pun, S. X. Lee, K. Xia, Persistent-homology-based machine learning: a survey and a comparative study, Artificial Intelligence Review (2022) 1–45.
  * [6] M. G. Bergomi, P. Vertechi, Rank-based persistence, Theory and applications of categories 35 (2020) 34.
  * [7] M. G. Bergomi, M. Ferri, A. Tavaglione, Steady and ranging sets in graph persistence, Journal of Applied and Computational Topology (2022) 1–24.
  * [8] M. Sun, Z. Song, X. Jiang, J. Pan, Y. Pang, Learning pooling for convolutional neural network, Neurocomputing 224 (2017) 96–104.
  * [9] P. Bubenik, J. A. Scott, Categorification of Persistent Homology, Discrete & Computational Geometry 51 (3) (2014) 600–627.  doi:10.1007/s00454-014-9573-x.
URL https://doi.org/10.1007/s00454-014-9573-x

  * [10] M. Lesnick, The theory of the interleaving distance on multidimensional persistence modules, Foundations of Computational Mathematics (2015) 1–38doi:10.1007/s10208-015-9255-y.
URL http://dx.doi.org/10.1007/s10208-015-9255-y

  * [11] S. Y. Oudot, Persistence theory: from quiver representations to data analysis, Vol. 209, American Mathematical Society Providence, RI, 2015.
  * [12] A. McCleary, A. Patel, Bottleneck stability for generalized persistence diagrams, Proceedings of the American Mathematical Society 148 (733) (2020).
  * [13] D. Govc, R. Levi, J. P. Smith, Complexes of tournaments, directionality filtrations and persistent homology, Journal of applied and computational topology 5 (2) (2021) 313–337.
  * [14] M. G. Bergomi, M. Ferri, P. Vertechi, L. Zuffi, Beyond topological persistence: Starting from networks, Mathematics 9 (23) (2021) 3079.
  * [15] H. Edelsbrunner, D. Letscher, A. Zomorodian, Topological persistence and simplification, in: Proceedings 41st Annual Symposium on Foundations of Computer Science, 2000, pp. 454–463.  doi:10.1109/SFCS.2000.892133.
  * [16] D. Cohen-Steiner, H. Edelsbrunner, J. Harer, Stability of Persistence Diagrams, Discrete & Computational Geometry 37 (1) (2007) 103–120.  doi:10.1007/s00454-006-1276-5.
URL https://doi.org/10.1007/s00454-006-1276-5

  * [17] B. Di Fabio, C. Landi, A mayer–vietoris formula for persistent homology with an application to shape recognition in the presence of occlusions, Foundations of Computational Mathematics 11 (5) (2011) 499.
  * [18] A. Mella, Non-topological persistence for data analysis and machine learning, Ph.D. thesis, Alma Mater Studiorum Università di Bologna (2021).
  * [19] Y. LeCun, C. Cortes, MNIST handwritten digit database (2010) [cited 2016-01-14 14:24:11].
URL http://yann.lecun.com/exdb/mnist/

  * [20] H. Xiao, K. Rasul, R. Vollgraf, Fashion-mnist: a novel image dataset for benchmarking machine learning algorithms (2017).  arXiv:cs.LG/1708.07747.
  * [21] A. Krizhevsky, et al., Learning multiple layers of features from tiny images (2009).
  * [22] F. Chollet, et al., Keras, https://keras.io (2015).
  * [23] D. P. Kingma, J. Ba, Adam: A method for stochastic optimization, arXiv preprint arXiv:1412.6980 (2014).
  * [24] L. Prechelt, Early stopping-but when?, in: Neural Networks: Tricks of the trade, Springer, 1998, pp. 55–69.
  * [25] A. Holzinger, A. Saranti, C. Molnar, P. Biecek, W. Samek, Explainable ai methods-a brief overview, in: International Workshop on Extending Explainable AI Beyond Deep Models and Classifiers, Springer, 2022, pp. 13–38.
  * [26] A. Angerschmid, J. Zhou, K. Theuermann, F. Chen, A. Holzinger, Fairness and explanation in ai-informed decision making, Machine Learning and Knowledge Extraction 4 (2) (2022) 556–579.
  * [27] F. Cabitza, A. Campagner, G. Malgieri, C. Natali, D. Schneeberger, K. Stoeger, A. Holzinger, Quod erat demonstrandum?-towards a typology of the concept of explanation for the design of explainable ai, Expert Systems with Applications 213 (2023) 118888.
  * [28] R. R. Selvaraju, M. Cogswell, A. Das, R. Vedantam, D. Parikh, D. Batra, Grad-cam: Visual explanations from deep networks via gradient-based localization, in: Proceedings of the IEEE international conference on computer vision, 2017, pp. 618–626.
  * [29] M. G. Bergomi, P. Vertechi, Neural network layers as parametric spans, arXiv preprint arXiv:2208.00809 (2022).


# On-board Deep Q-Network for UAV-assisted Online Power Transfer and Data
Collection

Kai Li<EMAIL_ADDRESS>Wei Ni  Eduardo Tovar  Real-Time and Embedded
Computing Systems Research Centre, Portugal  Commonwealth Scientific and
Industrial Research Organization, Australia

###### Abstract

Unmanned Aerial Vehicles (UAVs) with Microwave Power Transfer (MPT) capability
provide a practical means to deploy a large number of wireless powered sensing
devices into areas with no access to persistent power supplies. The UAV can
charge the sensing devices remotely and harvest their data. A key challenge is
online MPT and data collection in the presence of on-board control of a UAV
(e.g., patrolling velocity) for preventing battery drainage and data queue
overflow of the sensing devices, while up-to-date knowledge on battery level
and data queue of the devices is not available at the UAV. In this paper, an
on-board deep Q-network is developed to minimize the overall data packet loss
of the sensing devices, by optimally deciding the device to be charged and
interrogated for data collection, and the instantaneous patrolling velocity of
the UAV. Specifically, we formulate a Markov Decision Process (MDP) with the
states of battery level and data queue length of sensing devices, channel
conditions, and waypoints given the trajectory of the UAV; and solve it
optimally with Q-learning. Furthermore, we propose the on-board deep Q-network
that can enlarge the state space of the MDP, and a deep reinforcement learning
based scheduling algorithm that asymptotically derives the optimal solution
online, even when the UAV has only outdated knowledge on the MDP states.
Numerical results demonstrate that the proposed deep reinforcement learning
algorithm reduces the packet loss by at least 69.2%, as compared to existing
non-learning greedy algorithms.

###### keywords:

Unmanned aerial vehicle, microwave power transfer, online resource allocation,
deep reinforcement learning, Markov decision process

.epspdf.pdfpstopdf #1 -o

##  1 Introduction

Wireless sensing devices operating on limited batteries have been airlifted
and deployed in remote, human-unfriendly environments. Conventional
terrestrial communication networks and persistent power supplies are
unavailable or unreliable in such harsh environments. Unmanned Aerial Vehicles
(UAVs) have been proposed to harvest data from the sensing devices, and
offload command or software pitch, thanks to UAVs’ excellent mobility and
maneuverability, flexible deployment, and low operational costs [1, 2, 3].
Figure 1 depicts a typical real-time application using the UAV in rescue
operations, where the wireless sensing device on the ground, typically running
with limited battery, records critical information, such as locations,
temperature, health conditions of rescuers, and oxygen supply. Each ground
device generates data packets at an application-specific sampling rate, and
put them into a data queue for future transmission.

A UAV can be employed to hover over the area of interest, collecting and
ferrying the sensory data of the ground device. Since the ground device is
constrained by a typically limited battery power which limits scalability and
sustainability of the sensor network, Microwave Power Transfer (MPT) has been
studied to enable energy harvesting in UAV-assisted data collection [4, 5].
Particularly, we consider a power-splitting MPT technique, e.g., Simultaneous
Wireless Information and Power Transfer (SWIPT), where the UAV sends response
messages to the ground device meanwhile charging its batteries [6, 7, 8].
Moreover, the ground device, equipped with a data communication antenna and a
wireless power receiver, collects electrical energy conveyed by radio
frequency signals while recovering the data from the signals. With SWIPT,
every ground device only needs a single RF chain with a reduced hardware cost,
since MPT and data transmission can work in the same radio frequency band.

Figure 1: UAV-assisted MPT and data collection with the wireless powered
ground devices.

In practical scenarios, energy harvesting and data transmission could be
severely affected by movements of the UAV and time-varying channels. Moreover,
the up-to-date knowledge about battery level and data queue length of the
ground devices is not available at the UAV. Therefore, scheduling MPT and data
collection online in the presence of on-board control of the UAV (e.g.,
patrolling velocity) for preventing battery drainage and data queue overflow
is critical in UAV-assisted wireless powered sensor networks.

In this paper, the problem is formulated as a Markov Decision Process (MDP)
with the states of battery level and data queue length of the ground devices,
channel conditions, and waypoints given the trajectory of the UAV, which can
be optimally solved by a reinforcement learning approach, e.g., Q-learning.
However, Q-learning suffers from the well-known curse of dimensionality, which
is impractical for the resource allocation in the UAV-assisted online MPT and
data collection due to a large number of states and actions. Furthermore, we
propose an on-board deep Q-network that can enlarge the state and action space
of the MDP to minimize the data packet loss of the entire system. A new Deep
Reinforcement Learning based Scheduling Algorithm (DRL-SA) is developed, which
derives the optimal solution online by taking current network state and action
as the input and delivering a corresponding action-value function. DRL-SA
learns an optimal resource allocation strategy asymptotically through online
training at the on-board deep Q-network, where the selection of the ground
device, modulation scheme, and instantaneous patrolling velocity of the UAV
are jointly optimized based on the action-value function. DRL-SA utilizes an
$\epsilon$-greedy policy to balance the network cost minimization with respect
to the knowledge already known with trying new actions to obtain knowledge
unknown. Moreover, DRL-SA carries out experience replay [9] to significantly
reduce expansion of the state space in which the algorithm’s scheduling
experiences at each time step are stored in a data set. DRL-SA is implemented
using Keras deep learning library with Google TensorFlow as the backend
engine. Numerical results demonstrate that the proposed DRL-SA is able to
reduce the packet loss by 69.2%, as compared to existing non-learning greedy
algorithms.

In our earlier work [10, 11], scheduling strategies were studied with a focus
on reducing packet loss in small-scale static wireless powered sensor networks
in response to battery level and data queue statues of the ground devices. Due
to the low-dimensional channel and device state spaces, the resource
allocation problem can be solved by reinforcement learning or dynamic
programming. However, in the UAV-assisted MPT and data collection, the
mobility of the UAV with the varying patrolling velocity causes rapidly
changing wireless channels. As a result, both the state space and the action
space are exceedingly large and grow dramatically fast with the size of the
network. This prevents conventional resource allocation approaches, such as
[10] and [11], from scaling to the high-dimensional input spaces.

The rest of this paper is organized as follows. Section 2 presents related
work on UAV-assisted data communication with power transfer. Section 3 studies
system structure of UAV-assisted MPT and data collection, as well as the
communication protocol design. In Section 4, a deep reinforcement learning
algorithm is proposed to address the resource allocation problem for UAV-
assisted online MPT and data collection. Numerical results and evaluation are
presented in Section 5. Section 6 concludes the paper.

##  2 Related Work

In this section, we review the literature on data communication, trajectory
planning, and power transfer in UAV networks.

###  2.1 UAV-assisted wireless communications

An energy-efficient UAV relaying scheme is studied in [12] to schedule the
data transmission between the UAV and the sensor nodes while guaranteeing
packet success rate. A practical and computationally efficient algorithm is
designed to extend network lifetime, by decoupling energy balancing and
modulation adaptation of the UAVs, and optimizing in an alternating manner.
The authors in [13] implement passive scanning at the sensor nodes and
periodic beaconing at the UAV to reduce network energy consumption. A non-
cooperative game is constructed and equilibrium beaconing period durations are
characterized for the UAVs. A learning algorithm is described to allow a UAV
to discover the equilibrium beaconing strategy without observing the other
UAVs’ relaying schedules. Network outage probability is analyzed in which a
number of UAVs are used to relay the source signals to a data sink in a
decode-and-forward manner [14]. The use of multiple antennas at the data sink
is considered and their respective performance is also examined. The network
outage problem can be decoupled into power allocation and trajectory planning
subproblems [15]. An approximate solution that iteratively addresses the two
subproblems is developed for approaching the minimum outage probability. In
each iteration, the trajectory is planned according to the power control
results obtained by the last iteration, and then the power control subproblem
is solved given the UAV trajectory. A resource allocation algorithm is
presented for improving network throughput while guaranteeing a seamless
relaying transmission to the data sink outside network coverage via UAV [16].
By analyzing the outage probability, it is shown that non-orthogonal
transmissions improve the performance of the UAV relaying network over
orthogonal transmissions.

###  2.2 UAV trajectory planning

UAV trajectory planning is studied in [17, 18, 19, 20], where the UAV acts as
a communication relay for connecting the sensor nodes. Network throughput and
communication delay can be improved by the motion control of the UAV, e.g.,
heading, velocity, or radius of the flight trajectory. In [21, 22], the
transmit power of the UAV and the trajectory planning are studied to increase
network throughput over a finite time horizon. The power allocation exploits
the predictable channel changes induced by the UAV’s movement while the
trajectory planning balances the throughput between the source-UAV and UAV-
sink links. The UAV can also be used as a buffer-aided relay in free-space
optical systems, which stores data emanating from some stationary sensor nodes
for possible future delivery to other nodes [23]. Since an optical link
between the two transceivers can be easily smeared by ambient atmospheric
conditions, e.g., an intervening cloud, the UAV adjusts its altitude in such a
way that would eliminate the cloud attenuation effect.

The existing resource allocation approaches in the UAV relaying network
improve the performance based on power control and trajectory planning of the
UAV. However, scheduling energy harvesting and data collection was yet to be
considered.

###  2.3 UAV-assisted power transfer

Several studies have integrated MPT technologies into the UAV network. The UAV
carrying an MPT transmitter is used to collect sensory data and extend the
lifetime of sensor networks in harsh terrains [24, 25]. With consideration of
transferred power attenuation, residual energy and buffered data at the sensor
node, the UAV is scheduled to selectively charge the nodes and collect their
data. In [26], the UAV trajectory planning with the velocity control is
exploited for charging all the sensor nodes in a fair fashion. The problem
formulation and solution imply that the hovering location and duration can be
designed to enhance the MPT efficiency. Moreover, machine learning techniques
can be utilized to predict the UAV’s trajectory and improve the energy
harvesting efficiency [27]. In [8], SWIPT is introduced into the UAV relaying
network, where the sensor node’s energy limit can be alleviated by scavenging
wireless energy from radio signals transmitted by the UAV. The network
throughput is improved by adjusting the UAV’s transmit power and the flight
trajectory. Several MPT platforms are developed for the UAV to charge
batteries of the sensor nodes remotely from the electric grid [28, 29, 30, 31,
32]. The lightweight design of hardware, control algorithms, and experiments
are presented to verify the feasibility, reliability and efficiency of the
UAV-assisted power transfer. However, the existing literature only focuses on
improving the energy efficiency of MPT. The data loss caused by buffer
overflows and poor channels is not considered.

##  3 System Model and Communication Protocol

In this section, we introduce the system model and the communication protocol
of UAV-assisted online MPT and data collection. Notations used in the paper
are summarized in Table 1.

###  3.1 System model

Table 1: The list of fundamental variables defined in system model Notation |  Definition
---|---
$I$ |  number of wireless powered ground devices
$v_{\rm max}$, $v_{\rm min}$ |  the maximum and minimum velocity of the UAV
$Z$ |  number of laps the UAV patrols
$P^{z}_{i}(t)$ |  transmit power of device $i$
$\tilde{P}^{z}_{i}(t)$ |  power transferred to device $i$
$P_{\rm UAV}^{tx}$ |  transmit power of the UAV
$\zeta_{z}(t)$ |  location of the UAV on its trajectory
$\mathbf{h}_{i}^{z}(t)$ |  channel gain between device $i$ and the UAV
$q_{i,z}(t)$ |  queue length of device $i$
$D$ |  maximum queue length of the ground device
$\phi_{i}^{z}(t)$ |  modulation scheme of device $i$
$\Phi$ |  the highest modulation order
$\gamma_{i}$ |  SNR between device $i$ and the UAV
$\omega(d_{i}^{z}(t),\theta_{i}^{z}(t))$ |  MPT efficiency factor
$e_{i,z}(t)$ |  battery level of device $i$
$E$ |  battery capacity of the ground device
$K$ |  the highest battery level of the ground device
$B$ |  number of bits of the data packet
$\varepsilon$ |  required BER of the channel between the ground device and the UAV
$\widehat{T}^{z}_{i}(t)$ |  contact time between device $i$ and the UAV
$\mathcal{A}$ |  action set of MDP
$\delta$ |  discount factor for future states
$l$ |  learning iteration in the deep Q-network
$\varphi_{l}$ |  learning weight in the deep Q-network

The network that we consider consists of $I$ wireless powered ground devices
in a remote area. The UAV that acts as a data collection node flies a
predetermined circular trajectory for $Z$ laps, where the number of laps is
limited by the lifetime of the UAV’s battery. Let $v_{\rm max}$ and $v_{\rm
min}$ denote the maximum and minimum patrolling velocity of the UAV,
respectively. The patrolling velocity at time slot $t$, i.e., $v^{z}(t)$, can
be adjusted during the flight, where $v^{z}(t)\in[v_{\rm min},v_{\rm max}]$
and $z\in[1,Z]$. The location of the UAV on its trajectory at $t$ in lap $z$
is denoted by $\zeta_{z}(t)$. The UAV is also responsible for remotely
charging the ground devices using MPT. Specifically, receive beamforming is
enabled at the UAV to enhance the received signal strength (RSS) and reduce
bit error rate (BER). Device $i$ ($\in[1,I]$) harvests energy from the UAV to
power its operations, e.g., sensing, computing and communication. In addition,
multi-user beamforming techniques, e.g., zero-forcing beamforming, conjugate
beamforming, and singular value decomposition, can be applied to UAV-assisted
MPT and data collection. However, they are not considered in this work, due to
their requirement of real-time feedback on channel state information.

The complex coefficient of the reciprocal wireless channel between the UAV and
device $i$ at $t$ in lap $z$ is $\mathbf{h}_{i}^{z}(t)$, which can be known by
channel reciprocity. The modulation scheme of device $i$ at $t$ in lap $z$ is
denoted by $\phi_{i}^{z}(t)$. In particular, $\phi_{i}^{z}(t)$ = 1, 2, and 3
indicates binary phase-shift keying (BPSK), quadrature-phase shift keying
(QPSK), and 8 phase-shift keying (8PSK), respectively, and
$\phi_{i}^{z}(t)\geq 4$ provides $2^{\phi_{i}^{z}(t)}$ quadrature amplitude
modulation (QAM).

Suppose that the BER requirement is $\varepsilon$. Consider the generic
Nakagami-$m$ fading channel model, $\varepsilon$ is given by [33]

$\displaystyle\varepsilon\approx\frac{0.2}{\Gamma(m)}(\frac{m}{\bar{\gamma}_{i}})^{m}\Big{[}\frac{\Gamma(m,b_{\phi_{i}^{z}(t)}\gamma_{i}(\phi_{i}^{z}(t)))}{(b_{\phi_{i}^{z}(t)})^{m}}-$
$\displaystyle~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}\frac{\Gamma(m,b_{\phi_{i}^{z}(t)}\gamma_{i}(\phi_{i}^{z}(t)+1))}{(b_{\phi_{i}^{z}(t)})^{m}}\Big{]},$
(1) $\displaystyle
b_{\phi_{i}^{z}(t)}=\frac{m}{\bar{\gamma}_{i}}+\frac{3}{2(2^{\phi_{i}^{z}(t)}-1)},$
(2)

where $\Gamma(\cdot)$ is the Gamma function [34], and $\bar{\gamma}_{i}$ is
the average SNR. $\gamma_{i}(\phi_{i}^{z}(t))$ is the SNR between device $i$
and the UAV using $\phi_{i}^{z}(t)$, as given by

$\displaystyle\gamma_{i}(\phi_{i}^{z}(t))=\frac{\|\mathbf{h}_{i}^{z}(t)\|^{2}P^{z}_{i}(t)}{\sigma_{0}^{2}},$
(3)

where $P^{z}_{i}(t)$ is the transmit power of device $i$, and $\sigma_{0}^{2}$
is noise power at the UAV. In particular, for illustration convenience, we
consider a special case of the Nakagami-$m$ model in this paper where $m=1$
[35, 36, 37]. Note that the proposed deep reinforcement learning approach is
generic, and can work with other Nakagami fading channel model with any $m$
values. The required transmit power of the ground device depends on
$\phi_{i}^{z}(t)$ and $\mathbf{h}_{i}^{z}(t)$, and can be given by [12]

$\displaystyle
P_{i}^{z}(t)\approx\frac{\kappa_{2}^{-1}\ln\frac{\kappa_{1}}{\varepsilon}}{\|\mathbf{h}_{i}^{z}(t)\|^{2}}(2^{\phi_{i}^{z}(t)}-1),$
(4)

where $\kappa_{1}$ and $\kappa_{2}$ are channel related constants.

According to [38], the MPT efficiency is jointly decided by the distance
between the MPT transmitter and the receiver, and their antenna alignment.
Therefore, the power transferred to device $i$ at $t$ in lap $z$ via MPT is
given by

$\displaystyle\tilde{P}^{z}_{i}(t)=\omega(d_{i}^{z}(t),\theta_{i}^{z}(t))P_{\rm
UAV}^{tx}\|\mathbf{h}_{i}^{z}(t)\|^{2},$ (5)

where $\|\cdot\|$ stands for norm. $\omega(d_{i}^{z}(t),\theta_{i}^{z}(t))$ is
the MPT efficiency factor given the distance $d_{i}^{z}(t)$ and the MPT
transceiver alignment $\theta_{i}^{z}(t)$ between the ground device and the
UAV. The transmit power of the UAV is fixed and set to be $P_{\rm UAV}^{tx}$,
so that the operations at the UAV can keep simple.

Each of the wirelessly powered ground devices harvests energy from the UAV.
The rechargeable battery is finite with the capacity of $E$ Joules, and the
battery overflows if overcharged. Moreover, the battery readings are
continuous variables with variance difficult to be traced in real-time.
Therefore, to improve the mathematical tractability of the problem and for
illustration convenience, the continuous battery is discretized into $K$
levels, as $0<\mathcal{E}<2\mathcal{E}<\cdots<K\mathcal{E}=E$.
$e_{i,z}(t)\in\\{0,\mathcal{E},2\mathcal{E},\cdots,K\mathcal{E}\\}$ [39]. In
other words, the battery level of the ground device is lower rounded to the
closest discrete level.

We also assume that all the ground devices have the same battery size, data
queue size, packet length, and the BER requirement. However, our proposed
resource allocation approach can be extended to a heterogeneous network
setting, where the complexity of the resource allocation problem may grow as
the result of an increased number of MDP states.

###  3.2 Communication protocol

Figure 2 illustrates the communication protocol for UAV-assisted online MPT
and data collection. Specifically, each communication frame that contains a
number of time slots is allocated to the ground device for MPT and data
transmission. The ground device selection is determined by the UAV, using DRL-
SA which will be illustrated in Section 4. Then, the UAV broadcasts a short
beacon message to the selected ground device for data transmission. On the
reception of the ground device’s data, the UAV is aware of the information for
MPT, i.e., $d_{i}^{z}(t)$, $\theta_{i}^{z}(t)$, and $\mathbf{h}_{i}^{z}(t)$.
Moreover, a control segment of the device’s data packet contains $q_{i,z}(t)$
and $e_{i,z}(t)$. The overhead of this control segment is small. For example,
consider $e_{i,z}(t)$ of 100 and $q_{i,z}(t)$ of 100 packets, the overhead is
only 12 bits, much smaller than the size of the data packet. Therefore, we
assume that the transmission time and the energy consumption of the control
segment are negligible.

Figure 2: The communication protocol for UAV-assisted online MPT and data
collection.

The UAV processes the received data packets online, and responds to the ground
device’s requests, e.g., providing network access services, or online
information query. SWIPT is utilized to transmit the response to the ground
device and charge its battery via MPT simultaneously. Meanwhile, DRL-SA is
conducted by the UAV to schedule the other ground device for MPT and data
transmission in the next communication frame.

##  4 Deep Reinforcement Learning for UAV-assisted online MPT and Data
Collection

In this section, we first present the problem formulation based on MDP, and
provide a reinforcement learning solution to the problem. Due to the curse-of-
dimensionality of reinforcement learning, we propose a new deep reinforcement
learning based scheduling algorithm to minimize overall data packet loss of
the ground devices, by optimally deciding the device to be charged and
interrogated for data collection, and the instantaneous patrolling velocity of
the UAV. The modulation scheme of the ground device is also optimized to
maximize the harvested energy. Finally, the optimality of the deep
reinforcement learning approach is analyzed.

###  4.1 MDP formulation

The UAV takes the actions of the ground device selection, the modulation
scheme, and the instantaneous patrolling velocity of the UAV. Each action
depends on the current network state, i.e, the battery level $e_{i,z}(t)$ and
queue length $q_{i,z}(t)$ of every device $i$, the channel quality
$\mathbf{h}_{i}^{z}(t)$, and the location of the UAV $\zeta_{z}(t)$ along the
flight trajectory. The actions also account for the potential influence on the
future evolution of the network. Particularly, the current action that the UAV
takes can affect the future battery level and queue length of every device
and, in turn, influence the future actions to be taken. Such actions are a
discrete-time stochastic control process which is partly random (due to the
random and independent arrival/queueing process of sensory data at every
device) and partly under the control of the decision-making UAV.

The action can be optimized in a sense that the optimality in regards of a
specific metric, e.g., packet loss from queue overflows and unsuccessful data
transmissions, is achieved in the long term over the entire stochastic control
process (rather than myopically at an individual time slot). Motivated by
this, we consider an MDP formulation for which the actions are chosen in each
state to minimize a long-term objective. An MDP is defined by the quadruplet
$\langle$$\mathcal{S}$, $\mathcal{A}$,
$C\Big{\\{}\mathcal{S}_{\beta}\Big{|}\mathcal{S}_{\alpha},k\Big{\\}}$,
$\Pr\Big{\\{}\mathcal{S}_{\beta}\Big{|}\mathcal{S}_{\alpha},k\Big{\\}}$$\rangle$,
where $\mathcal{S}$ is the set of possible states; $\mathcal{A}$ is the set of
actions; $C\Big{\\{}\mathcal{S}_{\beta}\Big{|}\mathcal{S}_{\alpha},k\Big{\\}}$
is the immediate cost yielded when action $k$ is taken at state
$\mathcal{S}_{\alpha}$ and the following state changes to
$\mathcal{S}_{\beta}$; and
$\Pr\Big{\\{}\mathcal{S}_{\beta}\Big{|}\mathcal{S}_{\alpha},k\Big{\\}}$
denotes the transition probability from state $\mathcal{S}_{\alpha}$ to state
$\mathcal{S}_{\beta}$ when action $k$ is taken.

The resource allocation problem of interest in UAV-assisted online MPT and
data collection can be formulated as a discrete-time MDP, where each state
$\mathcal{S}_{\alpha}$ collects the battery levels and queue lengths of the
ground devices, the channel quality between the UAV and device $i$, and the
location of the UAV, i.e.,
$\\{(q_{i,z}(t),e_{i,z}(t),\mathbf{h}_{i}^{z}(t),\zeta_{z}(t)),i=1,2,...,I;z=1,2,...,Z\\}$.
The size of the state space, i.e., the number of such states, is
$\Big{(}(K+1)(D+1)\Big{)}{IZ}+HZ+VZ$, where $H$ is the number of channel
states, and $V$ is the number of waypoints on the UAV’s trajectory. The action
$\mathcal{A}$ to be taken is to schedule one device to transmit data to the
UAV at time slot $t$, while specifying the modulation of the device and the
instantaneous patrolling velocity of the UAV, i.e.,
$\mathcal{A}\in\Big{\\{}(i,\phi_{i}^{z}(t),v^{z}(t)):i=1,2,...,I;z=1,2,...,Z;\phi_{i}^{z}(t)\in\\{1,2,...,\Phi\\};v_{\rm
min}\leq v^{z}(t)\leq v_{\rm max}\Big{\\}}$. The size of the action set is
$IZ|v^{z}(t)|$, where $|v^{z}(t)|$ stands for the cardinality of the set
$[v_{\rm min},v_{\rm max}]$.

To illustrate the proposed MDP model, Figure 3 presents an example of
transition diagram with 24 MDP states in one lap of the UAV’s flight, where
$I=1$, $Z=1$, $K=1$, $D=1$, $H=2$ (e.g., $-10$dB, $30$dB), and $V=4$. The
vertices stand for all possible states in MDP, i.e.,
$\\{(q_{i,z}(t),e_{i,z}(t),\mathbf{h}_{i}^{z}(t),\zeta_{z}(t))\\}$. The edges
show the transition from each state to other states according to
$\Pr\Big{\\{}\mathcal{S}_{\beta}\Big{|}\mathcal{S}_{\alpha},k\Big{\\}}$. The
state transition depends on the change of
$\\{(q_{i,z}(t),e_{i,z}(t),\mathbf{h}_{i}^{z}(t)\\}$ of the ground device and
$\zeta_{z}(t)$ along the trajectory of the UAV. In other words, the next state
of
$\\{(q_{i,z}(t_{1}),e_{i,z}(t_{1}),\mathbf{h}_{i}^{z}(t_{1}),\zeta_{z}(t_{1}))\\}$
can be one of the states at $\zeta_{z}(t_{2})$, $\zeta_{z}(t_{3})$, or
$\zeta_{z}(t_{4})$. For example, for $t_{1}$, the next state of
$\\{(q_{i,z}(t_{1})=1,e_{i,z}(t_{1})=1,\mathbf{h}_{i}^{z}(t_{1})=-10{\rm
dB},\zeta_{z}(t_{1}))\\}$ can be
$\\{(q_{i,z}(t_{2})=2,e_{i,z}(t_{2})=2,\mathbf{h}_{i}^{z}(t_{2})=-10{\rm
dB},\zeta_{z}(t_{2}))\\}$, if device $i$ is selected, but the data collection
is not successful; or
$\\{(q_{i,z}(t_{2})=1,e_{i,z}(t_{2})=2,\mathbf{h}_{i}^{z}(t_{2})=-10{\rm
dB},\zeta_{z}(t_{2}))\\}$, if the data collection is successful. Note that
Figure 3 gives a small-scale example of the transition of one of the states,
i.e., $\\{(q_{i,z}(t)=1,e_{i,z}(t)=1,\mathbf{h}_{i}^{z}(t)=-10{\rm
dB},\zeta_{z}(t))\\}$. The UAV’s trajectory can have hundreds of waypoints and
the model can contain over $8\times 10^{5}$ MDP states, as configured in
Section 5, which leads to an extremely complex state transition diagram.

Figure 3: An example of a transition diagram of 24 MDP states, which has 4
waypoints on the UAV’s trajectory.

The optimal policy in MDP can be determined by classical approaches, e.g.,
value iteration (computes and improves the action-value function estimate
iteratively) or policy iteration (redefines the policy at each step and
computes the value according to this new policy). However, these two methods
require that the transition probability and the cost of all states have been
accurately known. In contrast, this paper is interested in a practical
scenario where the UAV has no a-prior knowledge on
$C\Big{\\{}\mathcal{S}_{\beta}\Big{|}\mathcal{S}_{\alpha},k\Big{\\}}$ and
$\Pr\Big{\\{}\mathcal{S}_{\beta}\Big{|}\mathcal{S}_{\alpha},k\Big{\\}}$.

###  4.2 Q-learning

Q-learning, one of the reinforcement learning techniques, can obtain the
optimal resource allocation when the transition and/or cost functions are
unknown while minimizing the long-term expected accumulated discounted costs
(i.e., the expected packet loss of the ground devices) [10]. We define the
objective function of the resource allocation problem as $v(S_{\alpha})$,
which gives

$v(S_{\alpha})=\min_{\pi\in\Pi}~{}\mathbb{E}^{\pi}_{\mathcal{S}_{\alpha}}\left\\{\sum^{\infty}_{t=1}\delta^{t-1}C\Big{\\{}\mathcal{S}_{\beta}\Big{|}\mathcal{S}_{\alpha},k\Big{\\}}\right\\},$
(6)

where $\delta\in[0,1]$ is a discount factor for future states.
$C\Big{\\{}\mathcal{S}_{\beta}\Big{|}\mathcal{S}_{\alpha},k\Big{\\}}$ is the
cost from state $\mathcal{S}_{\alpha}$ to $\mathcal{S}_{\beta}$ when action
$k$ is carried out. $\mathbb{E}^{\pi}_{\mathcal{S}_{\alpha}}\\{\cdot\\}$
denotes the expectation with respect to policy $\pi$ and state
$\mathcal{S}_{\alpha}$. Furthermore, the action-value function
$Q\Big{\\{}\mathcal{S}_{\beta}\Big{|}\mathcal{S}_{\alpha},k\Big{\\}}$ defines
the expected cost after observing state $\mathcal{S}_{\alpha}$ and taking
action $k$ [40]. By performing the optimal action $k^{*}$, the optimal action-
value function can be expressed as a combination of the expected cost and the
minimum value of
$Q\Big{\\{}\mathcal{S}_{\beta^{\prime}}\Big{|}\mathcal{S}_{\beta},k^{\prime}\Big{\\}}$,
where $\mathcal{S}_{\beta^{\prime}}$ is the next state of
$\mathcal{S}_{\beta}$, and $k^{\prime}$ is the next action of $k$. Thus, we
have

$\begin{array}[]{c
l}&Q^{*}\Big{\\{}\mathcal{S}_{\beta}\Big{|}\mathcal{S}_{\alpha},k^{*}\Big{\\}}=(1-\varrho)Q^{*}\Big{\\{}\mathcal{S}_{\beta}\Big{|}\mathcal{S}_{\alpha},k^{*}\Big{\\}}+\\\
&~{}~{}\varrho\Big{[}C\Big{\\{}\mathcal{S}_{\beta}\Big{|}\mathcal{S}_{\alpha},k^{*}\Big{\\}}+\delta\min_{k^{\prime}\in\mathcal{A}}Q\Big{\\{}\mathcal{S}_{\beta^{\prime}}\Big{|}\mathcal{S}_{\beta},k^{\prime}\Big{\\}}\Big{]}.\end{array}$
(7)

where $\varrho\in(0,1]$ (a small positive fraction) indicates learning rate.
As observed in (7), the convergence rate of
$Q\Big{\\{}\mathcal{S}_{\beta}\Big{|}\mathcal{S}_{\alpha},k\Big{\\}}$ to
$Q^{*}\Big{\\{}\mathcal{S}_{\beta}\Big{|}\mathcal{S}_{\alpha},k^{*}\Big{\\}}$
depends on the discount factor $\delta$. Namely, the convergence rate of the
action-value function increases with the discount factor $\delta$.

However, Q-learning suffers from the well-known curse of dimensionality. Thus,
Q-learning is impractical for the resource allocation problem in the UAV-
assisted online MPT and data collection due to a large state and action space
in which the time needed for Q-learning to converge grows immeasurably. In
addition, Q-learning is unstable when combined with non-linear approximation
functions such as neural networks [41].

###  4.3 Deep reinforcement learning based approach

To circumvent the curse-of-dimensionality of reinforcement learning, we
propose an on-board deep Q-network for the UAV to optimize the resource
allocation online by approximating the optimal action-value function.

Figure 4: Schematic illustration of the proposed on-board deep Q-network.

As shown in Figure 4, the action-value function in (7) is represented by the
proposed on-board deep Q-network, which takes the current network state and
action as the input and derives the corresponding action-value function. Given
the total number of iterations $\Omega$,
$Q\Big{\\{}\mathcal{S}_{\beta}\Big{|}\mathcal{S}_{\alpha},k;\varphi_{l}\Big{\\}}$
is approximated by adapting a set of weights $\varphi_{l}$, where
$l\leq\Omega$. By optimizing $\varphi_{l}$, the outputs of the deep Q-network,
i.e., the approximated
$Q\Big{\\{}\mathcal{S}_{\beta}\Big{|}\mathcal{S}_{\alpha},k;\varphi_{l}\Big{\\}}$,
can be minimized.

Algorithm 1 Deep Reinforcement Learning based Scheduling Algorithm

1: 1\. Initialize:

2: $\mathcal{S}_{\alpha}\in{\cal S}$, $k\in\mathcal{A}$, $\varrho$, and $w$
$\to Q\Big{\\{}\mathcal{S}_{\beta}\Big{|}\mathcal{S}_{\alpha},k\Big{\\}}$.

3: Random weights $\varphi_{l}\to
Q\Big{\\{}\mathcal{S}_{\beta}\Big{|}\mathcal{S}_{\alpha},k;\varphi_{l}\Big{\\}}$.

4: Weights $\varphi_{l-1}=\varphi_{l}$ $\to$ target deep Q-network
$\hat{Q}\Big{\\{}\mathcal{S}_{\beta}\Big{|}\mathcal{S}_{\alpha},k;\varphi_{l-1}\Big{\\}}$.

5: Learning time $\to t_{\rm learning}$.

6: 2\. Learning:

7: for $episode=1\to M$ do

8: Start state $\mathcal{S}_{\alpha}\to\mathcal{S}_{1}$ and accordingly update
$\varphi_{l}\to\varphi_{1}$.

9: for $t=1\to t_{\rm learning}$ do

10: if Probability $\epsilon$ then

11: Select a random action $k_{t}$.

12: else

13:
$k_{t}\to\text{argmin}_{k}Q\Big{\\{}\mathcal{S}_{\beta}\Big{|}\mathcal{S}_{\alpha},k;\varphi_{l}\Big{\\}}$

14: end if

15: Execute action $k_{t}$ in the environment.

16: Obtain the cost
$C\Big{\\{}\mathcal{S}_{\beta}\Big{|}\mathcal{S}_{\alpha},k_{t}\Big{\\}}$ and
the next state $\mathcal{S}_{\beta}$ at $t+1$.

17: Store transition
$\Big{(}\mathcal{S}_{\alpha},\mathcal{S}_{\beta},k_{t},C\Big{\\{}\mathcal{S}_{\beta}\Big{|}\mathcal{S}_{\alpha},k_{t}\Big{\\}}\Big{)}_{t}\to\mathbb{D}[\cdot]$.

18: Sample random minibatch
$\Big{(}\mathcal{S}_{\alpha},\mathcal{S}_{\beta},k,C\Big{\\{}\mathcal{S}_{\beta}\Big{|}\mathcal{S}_{\alpha},k\Big{\\}}\Big{)}_{l}$
from $\mathbb{D}[\cdot]$.

19: if $\mathcal{S}_{\beta}$ terminates at step $l+1$ then

20: Set $y_{l}\to
C\Big{\\{}\mathcal{S}_{\beta}\Big{|}\mathcal{S}_{\alpha},k_{t}\Big{\\}}_{l}$.

21: else

22: Set $y_{l}\to
C\Big{\\{}\mathcal{S}_{\beta}\Big{|}\mathcal{S}_{\alpha},k_{t}\Big{\\}}_{l}+\delta\min_{k^{\prime}\in\mathcal{A}}\hat{Q}\Big{\\{}\mathcal{S}_{\beta^{\prime}}\Big{|}\mathcal{S}_{\beta},k^{\prime};\varphi_{l-1}\Big{\\}}$.

23: end if

24: Derive the loss function
$\Gamma_{l}(\varphi_{l})\to(y_{l}-Q\Big{\\{}\mathcal{S}_{\beta}\Big{|}\mathcal{S}_{\alpha},k_{t};\varphi_{l}\Big{\\}}_{t})^{2}$.

25: Perform (9) $\to$ gradients with respect to $\varphi_{l}$.

26: if There are $U$ number of learning updates. then

27: Synchronize $\varphi_{l-1}\to\varphi_{l}$.

28: Reset
$\hat{Q}\Big{\\{}\mathcal{S}_{\beta}\Big{|}\mathcal{S}_{\alpha},k;\varphi_{l-1}\Big{\\}}\to
Q\Big{\\{}\mathcal{S}_{\beta}\Big{|}\mathcal{S}_{\alpha},k_{t};\varphi_{l}\Big{\\}}_{t}$.

29: end if

30: end for

31: end for

32: 3\. Modulation:

33: Determining $\phi^{z}_{k}(t)^{\star}$ for the scheduled ground device $k$
(see Appendix).

In our on-board deep Q-network, experience replay is conducted to randomize
over the states and the actions of MDP at each time-step $t$, i.e.,
$\Big{(}\mathcal{S}_{\alpha},\mathcal{S}_{\beta},k,C\Big{\\{}\mathcal{S}_{\beta}\Big{|}\mathcal{S}_{\alpha},k\Big{\\}}\Big{)}_{t}$,
thereby removing correlations in the observation sequence and smoothing over
changes in the data distribution. Specifically,
$\Big{(}\mathcal{S}_{\alpha},\mathcal{S}_{\beta},k,C\Big{\\{}\mathcal{S}_{\beta}\Big{|}\mathcal{S}_{\alpha},k\Big{\\}}\Big{)}_{t}$
is stored in a data set $\mathbb{D}[\cdot]$, pooled over many episodes (where
an episode ends when a terminal state is reached) into an experience replay
memory. Moreover, samples (or minibatches) of the experience in the deep
Q-network are accordingly updated during learning. The deep Q-network is
trained by adjusting the weight $\varphi_{l}$ at iteration $l$ so as to
minimize a sequence of loss functions $\Gamma_{l}(\varphi_{l})$; see (8),

$\displaystyle\Gamma_{l}(\varphi_{l})=\mathbb{E}_{\Big{(}\mathcal{S}_{\alpha},\mathcal{S}_{\beta},k,C\Big{\\{}\mathcal{S}_{\beta}\Big{|}\mathcal{S}_{\alpha},k\Big{\\}}\Big{)}\sim\mathbb{D}\Big{[}\Big{(}C\Big{\\{}\mathcal{S}_{\beta}\Big{|}\mathcal{S}_{\alpha},k\Big{\\}}+\delta\min_{k^{\prime}\in\mathcal{A}}Q\Big{\\{}\mathcal{S}_{\beta^{\prime}}\Big{|}\mathcal{S}_{\beta},k^{\prime};\varphi_{l-1}\Big{\\}}-Q\Big{\\{}\mathcal{S}_{\beta}\Big{|}\mathcal{S}_{\alpha},k;\varphi_{l}\Big{\\}}\Big{)}^{2}\Big{]}},$
(8)

where $\varphi_{l}$ and $\varphi_{l-1}$ are the weights at iterations $l$ and
$(l-1)$, respectively. At each iteration of minimizing
$\Gamma_{l}(\varphi_{l})$, the weight $\varphi_{l-1}$ from iteration $(l-1)$
is fixed. Thus, the subproblem of learning $\Gamma_{l}(\varphi_{l})$ at
iteration $l$ $(l\leq\Omega)$ defines
$C\Big{\\{}\mathcal{S}_{\beta}\Big{|}\mathcal{S}_{\alpha},k\Big{\\}}+\delta\min_{k^{\prime}\in\mathcal{A}}Q\Big{\\{}\mathcal{S}_{\beta^{\prime}}\Big{|}\mathcal{S}_{\beta},k^{\prime};\varphi_{l-1}\Big{\\}}$.
For each sample (or minibatch), the current weight $\varphi_{l}$, gradient
descent is learned to derive weights $\varphi_{l}$, which iteratively computes
the gradient $\triangledown\Gamma_{l}(\varphi_{l})$, and updates the neural
network’s weights to reach the global minimum. We differentiate
$\Gamma_{l}(\varphi_{l})$ with regards to $\varphi_{l}$, and obtain (9).

$\displaystyle\triangledown\Gamma_{l}(\varphi_{l})=\mathbb{E}_{\Big{(}\mathcal{S}_{\alpha},\mathcal{S}_{\beta},k,C\Big{\\{}\mathcal{S}_{\beta}\Big{|}\mathcal{S}_{\alpha},k\Big{\\}}\Big{)}}\Big{[}\Big{(}$
$\displaystyle
C\Big{\\{}\mathcal{S}_{\beta}\Big{|}\mathcal{S}_{\alpha},k\Big{\\}}+\delta\min_{k^{\prime}\in\mathcal{A}}Q\Big{\\{}\mathcal{S}_{\beta^{\prime}}\Big{|}\mathcal{S}_{\beta},k^{\prime};\varphi_{l-1}\Big{\\}}-$
$\displaystyle
Q\Big{\\{}\mathcal{S}_{\beta}\Big{|}\mathcal{S}_{\alpha},k;\varphi_{l}\Big{\\}}\Big{)}\triangledown_{\varphi_{l}}Q\Big{\\{}\mathcal{S}_{\beta}\Big{|}\mathcal{S}_{\alpha},k;\varphi_{l}\Big{\\}}\Big{]}.$
(9)

Algorithm 1 presents the proposed DRL-SA scheme, which optimizes the actions
based on the deep Q-network to solve the online resource allocation problem.
Specifically, $U$ is a global parameter for counting the total number of
updates to the UAV, rather than counting the updates from the local learner.
The $\epsilon$-greedy policy is utilized to balance the action-value function
minimization based on the knowledge already known, as well as trying new
actions to obtain knowledge unknown. In particular, the optimal action of
determining $\phi_{i}^{z}(t)$ for maximizing the harvested energy (see the
Appendix) is carried out once the optimal ground device is selected from the
deep Q-network.

Note that the optimal solutions to a small-scale MDP problem of interest can
be solved by Q-learning in which the series of the optimal actions are
obtained in a state machine, given the optimal decisions at each of the
states. However, Q-learning is impractical for the complex resource allocation
problem that contains a large state and action space, due to the well-known
curse of dimensionality. As observed in Algorithm 1, our on-board deep
Q-network maintains two separate Q-networks
$Q\Big{\\{}\mathcal{S}_{\beta}\Big{|}\mathcal{S}_{\alpha},k;\varphi_{l}\Big{\\}}$
and
$Q\Big{\\{}\mathcal{S}_{\beta}\Big{|}\mathcal{S}_{\alpha},k;\varphi_{l-1}\Big{\\}}$
with current weights $\varphi_{l}$ and the old weights $\varphi_{l-1}$,
respectively [42]. $\varphi_{l}$ can be updated many times per time-step, and
copied into $\varphi_{l-1}$ after every $U$ iterations. At every update
iteration, the deep Q-network is trained to minimize the mean-squared Bellman
error, by minimizing the loss function $\Gamma_{l}(\varphi_{l})$. Therefore,
the proposed DRL-SA can achieve the optimality asymptotically, with the
growing size of the deep Q-network.

##  5 Numerical Results and Discussions

In this section, we first present network configurations and performance
metrics. Then, we evaluate the network cost of the proposed DRL-SA scheme with
regards to the network size, data queue length, and learning discount factors.
Here, the network cost defines the amount of packet loss due to the data queue
overflow and the failed transmission from the ground device to the UAV. We
also show the UAV’s velocity in terms of the network size, as well as the data
queue length.

###  5.1 Implementation of DRL-SA

The simulation platform is an INSYS Server running 64-bit Ubuntu 16.04 LTS,
with 4-core Intel i7-6700K 4GHz CPUs and 16G memory. DRL-SA is implemented in
Python 3.5 by using Google TensorFlow [43] (the symbolic math library for
numerical computation) with Keras [44] (the Python deep learning library). We
develop the on-board deep Q-network in DRL-SA according to the following
steps:

  * 1.

Initialize the configurations. Each device generates 100 data packets, where
the packet length is 128 bytes. The transmit power of the UAV is 100
milliwatts. $\varepsilon$ is set to 0.05%, however, the value of $\varepsilon$
can be configured depending on the traffic type and quality-of-service (QoS)
requirement of the user’s data, as well as the transmission capability of the
UAV. Other simulation parameters are listed in Table 2.

Table 2: TensorFlow configurations Parameters |  Values
---|---
Number of ground devices |  50 $\backsim$ 200
Queue length |  20 $\backsim$ 60
Energy levels |  50
Number of UAV’s waypoints |  100
Discount factor |  0.99
Learning rate |  0.0001
Replay memory size |  5000
Batch size |  32
Number of steps |  1000
Number of episodes |  500
  * 2.

Set up the architecture of the deep Q-network. Three fully connected hidden
layers are created by using tensorflow.layers.dense(inputs, dimensionality of
the output space, activation function). Then,
tensorflow.train.AdamOptimizer().minimize(loss function) is called to minimize
the loss function. In particular, the optimizer is imported from the Keras
library.

  * 3.

Build the memory for the experience replay. For online training the deep
Q-network, the memory stores the learning outcomes, a.k.a experience at every
step, using the quadruplet $<$state, action, cost, next_state$>$. The deep
Q-network updates the memory by calling the function memory.add_sample((state,
action, cost, next_state)), and retrieves the experiences by using
memory.sample(batch size).

  * 4.

Create a deep Q-network agent, and kick off the learning. The agent is
configured and compiled to take actions, and observe the cost and the new
state. A TensorFlow session is created by implementing tensorflow.Session() to
execute the learning and evaluate the learning progress.

For performance comparison, the proposed DRL-SA scheme is compared with two
other on-board online scheduling policies as

  * 1.

Random scheduling policy (RSA). The UAV randomly schedules one ground device
to collect data and transfer power at each time slot. The resource allocation
is independent of battery and data queue of the ground device, channel
variation, or UAV’s trajectory.

  * 2.

Longest queue scheduling policy (LQSA). This is a greedy algorithm, where the
scheduling is based on the data queue length of the ground device. The device
with the longest queue is given the highest priority to transmit data and
harvest power. For LQSA, it is assumed that the up-to-date information of the
data queue length at each device is known by the UAV.

Both RSA and LQSA are implemented in Matlab. Their scheduling policies are not
obtained by the deep Q-network. Note that the existing learning-based
approaches, e.g., QSA [10] or SARSA [45], can only solve the small-scale
scheduling problem, and do not apply to the resource allocation in UAV-
assisted online MPT and data collection. In addition, the resource allocation
optimization schemes, e.g., EHMDP [11] or EACH [46], require the a-prior
knowledge about the network and have to be conducted in offline.

###  5.2 Performance evaluation

####  5.2.1 Network size

We assess the performance of DRL-SA when the number of ground devices enlarges
from 50 to 200. Figure 5 shows the network cost at each episode, given
$I=120,150$ and $180$. The network cost of DRL-SA is high at the beginning of
the learning process. With an increasing number of episodes, the network cost
drops significantly until it reaches a relatively stable value. It confirms
the fact that deep Q learning gradually converges after a number of episodes.
Moreover, the average network cost is smaller when the number of ground
devices is 120, as compared to the cases where the number of ground devices is
150 and 180, since the increasing number of ground devices leads the data
queues to increasingly overflow.

Figure 5: Network cost at the episode in terms of the different number of ground devices, i.e., $I$.  |  |
---|---|---
|  |
(a) Network cost with regards to $I$ | (b) Packet loss rate with regards to $I$ |
(c) Patrolling velocity with regards to $I$ |  |
|  |
|  |
(d) Network cost with regards to $D$ | (e) Packet loss rate with regards to $D$ |
(f) Patrolling velocity with regards to $D$ |  |
Figure 6: A comparison of network cost and packet loss rate by DRL-SA and the
typical scheduling strategies, where the error bars show the standard
deviation over 20 runs. The patrolling velocity of the UAV given the different
number of ground devices and data queue length is also presented.

Figure 6(a) studies the network cost with an increasing number of ground
devices, where the data queue length of DRL-SA is set to 50 or 10. In general,
the proposed DRL-SA is able to reduce the network cost to a greater extent
than RSA and LQSA. Particularly, when $I$ = 200 and $D$ = 10, the maximum
network cost of DRL-SA is lower than RSA and LQSA by around 82.8% and 69.2%,
respectively. The performance gains keep growing with $I$. The reason is that
DRL-SA learns the ground devices’ energy consumption and data queue states, so
that the scheduling of MPT and data communications can minimize the data
packet loss of the entire network.

Figure 6(b) illustrates the packet loss rate, which is the ratio of the
network cost and the total number of data packets of all the ground devices.
Specifically, DRL-SA has a similar packet loss rate to LQSA, when there are 50
devices in the network. However, from $I$ = 80 to 200, DRL-SA outperforms the
two non-learning-based algorithms. In particular, when $I$ = 200, DRL-SA with
$D=10$ achieves 53%, and 25% lower packet loss rates than RSA and LQSA,
respectively. In Figure 6(b), we also see that the packet loss rate of DRL-SA
only slightly grows about 2% from $I$ = 50 to 200. In other words, adding more
devices to the network does not result in a critical data packet loss. This is
because DRL-SA takes the actions to adapt the instantaneous velocity of the
UAV to ensure the connection time and channel quality between the device and
the UAV, hence minimizing the data packet loss. As shown in Figure 6(c), the
patrolling velocity raises with an increase of $I$. This is reasonable because
the UAV needs to transfer power and collect data from more devices in order to
reduce their data queue overflow. Furthermore, it is also observed that
increasing the data queue length of the devices downgrades the patrolling
velocity of the UAV. The reason is that a larger data queue can hold more
packets. This allows an extended data transmission time between the ground
device and the UAV and in turn, reduces the patrolling velocity.

####  5.2.2 Data queue length of ground devices

We consider different data queue lengths of the ground devices, i.e., $D$,
where the number of ground devices is set to 140 or 300. Figures 6(d) and (e)
depict the network cost and packet loss rate with respect to the maximum data
queue length of the ground devices, respectively. We observe that DRL-SA
achieves lower network costs and packet loss rates than RSA and LQSA, while
DRL-SA outperforms RSA with substantial gains of 82.7% and 69% when $D$ = 20
and $I$ = 140. Moreover, given $I=300$, from $D$ = 20 to $D$ = 60, the network
cost and packet loss rate of DRL-SA drop by 62.2% and 13.2%. This confirms
that DRL-SA significantly reduces data queue overflow for all the ground
devices when enlarging their data queue length. In terms of the patrolling
velocity of the UAV, it is observed in Figure 6(f) that DRL-SA reduces the
velocity from 18.5 m/s to 14.1 m/s, and from 8.1 m/s to 6.2 m/s, given 300 and
140 ground devices in the network, respectively.

Figure 6 implies a tradeoff between the data packet loss and the battery
lifetime of the UAV. Specifically, an increase of the network size, or a
decrease of data queue length, results in a growth of the packet loss due to
the data queue overflow. In this case, the patrolling velocity of the UAV can
be increased so that more ground devices harvest energy and transmit data,
which reduces the packet loss of all the devices. However, accelerating the
patrolling velocity speeds up draining the energy of the UAV’s battery, and
reduces the lifetime of the network. Therefore, the network size and the data
queue length need to be balanced, so as to maintain a sustainable UAV-assisted
network while reducing the data packet loss.

####  5.2.3 The actions of the UAV

To further reveal the impact of network size and data queue length on the
actions of the UAV, Figure 7 demonstrates the patrolling velocity allocated by
the proposed DRL-SA, with respect to the episodes, given $(I=50,D=60)$ and
$(I=200,D=20)$. We can see that DRL-SA with $(I=200,D=20)$ allocates 8.7 m/s
higher patrolling velocity to the UAV than the one with $(I=50,D=60)$ on
average. This confirms that the patrolling velocity drops with a decrease of
network size or growth of data queue length, due to the data queue overflow,
as explained in Figure 6. Moreover, the result in Figure 7 also presents that
DRL-SA allocates the patrolling velocity adapting to the time-varying network
state. As observed, the patrolling velocity allocation converges with an
increase in the learning time (i.e., episodes).

Figure 7: The patrolling velocity of the UAV with respect to the episodes,
given $(I=50,D=60)$ and $(I=200,D=20)$.

####  5.2.4 Discount factor of learning

Since DRL-SA utilizes deep Q learning to approximate the Q function with
asymptotic convergence, the convergence time can be affected by the discount
factor in the learning process. Figure 8 plots the network cost of DRL-SA with
regards to the episodes given the discount factor $\delta=0.1,0.5$ and $0.99$.
$I$ and $D$ are set to 300 ground devices and 20, respectively. The other
settings are provided in Section 5.1.

As observed, DRL-SA has a high network cost at the beginning of the learning.
The performance improves with the increase of the episodes due to deep
reinforcement learning. In particular, the network cost of DRL-SA with
$\delta$ = 0.99 quickly falls to 0 from episode 1 to episode 359, and the
performance remains relatively stable afterward. However, the convergence of
DRL-SA with $\delta$ = 0.5 or 0.1 requires more than 475 or 500 episodes.
Therefore, the result in Figure 8 indicates that the convergence rate of DRL-
SA grows with $\delta$. In other words, a high discount factor of learning
accelerates the learning process of the deep Q-network, as confirmed by (7).

Figure 8: Network cost of DRL-SA with regards to the episodes given the
discount factor $\delta=0.1,0.5$ and $0.99$.

##  6 Conclusion

In this paper, we focus on online MPT and data collection in the presence of
on-board control of the patrolling velocity of the UAV, for preventing battery
drainage and data queue overflow of the sensing devices. The problem is
formulated as the MDP, with the states of battery level and data queue length
of the ground devices, channel conditions, and waypoints given the trajectory
of the UAV. We propose an on-board deep Q-network that can enlarge the state
and action space of the MDP to minimize the data packet loss of the entire
system. Based on deep reinforcement learning, DRL-SA is developed to learn the
optimal resource allocation strategy asymptotically through online training at
the on-board deep Q-network, where the selection of the ground device,
modulation scheme, and instantaneous patrolling velocity of the UAV are
jointly optimized. Moreover, DRL-SA carries out experience replay to reduce
expansion of the state space in which the algorithm’s scheduling experiences
at each time step are stored in a data set.

The proposed DRL-SA scheme is implemented by using Keras deep learning library
with Google TensorFlow as the backend engine. Numerical results demonstrate
that DRL-SA reduces packet loss by at least 69.2%, as compared to the existing
non-learning greedy algorithms.

## Acknowledgements

This work was partially supported by National Funds through FCT/MCTES
(Portuguese Foundation for Science and Technology), within the CISTER Research
Unit (CEC/04234); also by the Operational Competitiveness Programme and
Internationalization (COMPETE 2020) through the European Regional Development
Fund (ERDF) and by national funds through the FCT, within project
POCI-01-0145-FEDER-029074 (ARNET).

##  Appendix A [Optimizing $\phi_{i}^{z}(t)$]

To minimize the packet loss stemming from insufficient energy,
$\phi_{i}^{z}(t)$ of device $i$ is to be chosen to maximize the energy
harvested during a contact time with the UAV, with a length of
$\widehat{T}^{z}_{i}(t)$. The optimal modulation of the ground device,
$\phi^{z}_{i}(t)^{\star}$, is independent of the battery level and the queue
length. This is because $\phi^{z}_{i}(t)^{\star}$ is selected to maximize the
increase of the battery level at device $i$, under the bit error rate
requirement $\epsilon_{i}$ for the packet transmitted. As a result,
$\phi_{i}^{z}(t)$ can be decoupled from $\mathcal{A}$, and optimized in prior
by

$\displaystyle\phi_{i}^{z}(t)=$
$\displaystyle\arg\max_{\phi=1,\cdots,\Phi}\bigg{\\{}(\widehat{T}^{z}_{i}(t)-\frac{B}{\phi
W})P_{i}^{z}(t)-\frac{B}{\phi W}P_{i}^{z}(\phi)\bigg{\\}},$ (10)

the right-hand side (RHS) of which, by substituting (5) and (4), can be
rewritten as

$\displaystyle\max_{\phi=1,\cdots,\Phi}\bigg{\\{}(\widehat{T}^{z}_{i}(t)-\frac{B}{\phi
W})$ $\displaystyle\omega(d_{i}^{z}(t),\theta_{i}^{z}(t))P_{\rm
UAV}^{tx}\|\mathbf{h}_{i}^{z}(t)\|^{2}-$
$\displaystyle\frac{B\kappa_{2}^{-1}\ln(\frac{\kappa_{1}}{\epsilon})}{\|\mathbf{h}_{i}^{z}(t)\|^{2}\phi
W}\big{(}2^{\phi}-1\big{)}\bigg{\\}},$ (11)

where $W$ is the bandwidth of the uplink data transmission, $\frac{1}{W}$ is
the duration of an uplink symbol, and $\frac{B}{\phi W}$ is the duration of
uplink data transmission. $(\widehat{T}^{z}_{i}(t)-\frac{B}{\phi W})$ is the
rest of the time slots used for downlink WPT, and $\widehat{T}^{z}_{i}(t)$ is
the contact time between the ground device and the UAV in the time slot, which
is affected by the patrolling velocity of the UAV. Thus, we have

$\displaystyle\widehat{T}^{z}_{i}(t)=\frac{2\sqrt{(d_{i}^{z}(t))^{2}-(b^{z})^{2}}}{v^{z}(t)},$
(12)

where $b^{z}$ is the altitude of the UAV at lap $z$. We assume that the UAV
maintains the same altitude and the same heading in each lap.

By using the first-order necessary condition of the optimal solution, we have

$\displaystyle\frac{d}{d\phi}((\widehat{T}^{z}_{i}(t)-\frac{B}{\phi W})$
$\displaystyle\omega(d_{i}^{z}(t),\theta_{i}^{z}(t))P_{\rm
UAV}^{tx}\|\mathbf{h}_{i}^{z}(t)\|^{2}-$
$\displaystyle\frac{B\kappa_{2}^{-1}\ln(\frac{\kappa_{1}}{\epsilon})}{\|\mathbf{h}_{i}^{z}(t)\|^{2}\phi
W}\big{(}2^{\phi}-1\big{)})=0,$ (13)

$\displaystyle\phi^{-2}\frac{B}{W}\omega(d_{i}^{z}(t),\theta_{i}^{z}(t))P_{\rm
UAV}^{tx}\|\mathbf{h}_{i}^{z}(t)\|^{2}-\frac{B\kappa_{2}^{-1}\ln(\frac{\kappa_{1}}{\epsilon})}{\|\mathbf{h}_{i}^{z}(t)\|^{2}W}\cdot$
$\displaystyle~{}~{}~{}~{}(\phi^{-1}2^{\phi}\text{In}2-\phi^{-2}2^{\phi})-\frac{B\kappa_{2}^{-1}\ln(\frac{\kappa_{1}}{\epsilon})}{\|\mathbf{h}_{i}^{z}(t)\|^{2}W}\phi^{-2}=0.$
(14)

The $\phi$ values are then given as follows:

$\displaystyle\phi 2^{\phi}\text{In}2-2^{\phi}=$
$\displaystyle\frac{B}{W}\omega(d_{i}^{z}(t),\theta_{i}^{z}(t))P_{\rm
UAV}^{tx}\|\mathbf{h}_{i}^{z}(t)\|^{2}\frac{\|\mathbf{h}_{i}^{z}(t)\|^{2}W}{B\kappa_{2}^{-1}\ln(\frac{\kappa_{1}}{\epsilon})}-1.$
(15)

Since the left-hand side (LHS) of (15) monotonically increases with $\phi$,
the optimal value $\phi^{\star}$ can be obtained by applying a bisection
search method, and evaluating the two closest integers about the fixed point
of the bisection method [47]. Specifically, $\phi_{-}=1$ and $\phi_{+}=\Phi$
are initialized. Each iteration of the bisection method contains 4 steps
applied over the range of $\phi=[1,\Phi]$, as follows.

  * 1.

The midpoint of the modulation interval $[\phi_{-};\phi_{+}]$ is calculated,
which gives $\phi_{\rm mid}=\frac{\phi_{-}+\phi_{+}}{2}$.

  * 2.

Substitute $\phi_{\rm mid}$ into (15) to obtain the function value
$f(\phi_{\rm mid})$.

  * 3.

If the convergence is attained (that is, the modulation interval or
$|f(\phi_{\rm mid})|$ cannot be further reduced), return $\phi_{\rm mid}$ and
stop the iteration.

  * 4.

Replace either $(\phi_{-},f(\phi_{-}))$ or $(\phi_{+},f(\phi_{+}))$ with
$(\phi_{\rm mid},f(\phi_{\rm mid}))$.

## References

  * [1] T. Tomic, K. Schmid, P. Lutz, A. Domel, M. Kassecker, E. Mair, I. L. Grixa, F. Ruess, M. Suppa, D. Burschka, Toward a fully autonomous UAV: Research platform for indoor and outdoor urban search and rescue, IEEE robotics & automation magazine 19 (3) (2012) 46–56.
  * [2] C. Luo, P. Ward, S. Cameron, G. Parr, S. McClean, Communication provision for a team of remotely searching UAVs: A mobile relay approach, in: Globecom Workshops (GC Wkshps), IEEE, 2012, pp. 1544–1549.
  * [3] S. Waharte, N. Trigoni, Supporting search and rescue operations with UAVs, in: International Conference on Emerging Security Technologies (EST), IEEE, 2010, pp. 142–147.
  * [4] H. Wang, G. Ding, F. Gao, J. Chen, J. Wang, L. Wang, Power control in UAV-supported ultra dense networks: Communications, caching, and energy transfer, IEEE Communications Magazine 56 (6) (2018) 28–34.
  * [5] Y. Zeng, R. Zhang, T. J. Lim, Wireless communications with unmanned aerial vehicles: opportunities and challenges, IEEE Communications Magazine 54 (5) (2016) 36–42.
  * [6] T. D. P. Perera, D. N. K. Jayakody, S. K. Sharma, S. Chatzinotas, J. Li, Simultaneous wireless information and power transfer (SWIPT): Recent advances and future challenges, IEEE Communications Surveys & Tutorials 20 (1) (2017) 264–302.
  * [7] S. Yin, J. Tan, L. Li, UAV-assisted cooperative communications with wireless information and power transfer, arXiv preprint arXiv:1710.00174.
  * [8] S. Yin, Y. Zhao, L. Li, UAV-assisted cooperative communications with time-sharing SWIPT, in: 2018 IEEE International Conference on Communications (ICC), IEEE, 2018, pp. 1–6.
  * [9] L.-J. Lin, Reinforcement learning for robots using neural networks, Tech. rep., Carnegie-Mellon Univ Pittsburgh PA School of Computer Science (1993).
  * [10] K. Li, W. Ni, M. Abolhasan, E. Tovar, Reinforcement learning for scheduling wireless powered sensor communications, IEEE Transactions on Green Communications and Networking.
  * [11] K. Li, W. Ni, L. Duan, M. Abolhasan, J. Niu, Wireless power transfer and data collection in wireless sensor networks, IEEE Transactions on Vehicular Technology 67 (3) (2018) 2686–2697.
  * [12] K. Li, W. Ni, X. Wang, R. P. Liu, S. S. Kanhere, S. Jha, Energy-efficient cooperative relaying for unmanned aerial vehicles, IEEE Transactions on Mobile Computing (6) (2016) 1377–1386.
  * [13] S. Koulali, E. Sabir, T. Taleb, M. Azizi, A green strategic activity scheduling for UAV networks: A sub-modular game perspective, IEEE Communications Magazine 54 (5) (2016) 58–64.
  * [14] X. Li, Y. D. Zhang, Multi-source cooperative communications using multiple small relay UAVs, in: IEEE GLOBECOM Workshops, 2010, pp. 1805–1810.
  * [15] S. Zhang, H. Zhang, Q. He, K. Bian, L. Song, Joint trajectory and power optimization for UAV relay networks, IEEE Communications Letters 22 (1) (2018) 161–164.
  * [16] J. Baek, S. I. Han, Y. Han, Optimal resource allocation for non-orthogonal transmission in UAV relay systems, IEEE Wireless Communications Letters 7 (3) (2018) 356–359.
  * [17] Z. M. Fadlullah, D. Takaishi, H. Nishiyama, N. Kato, R. Miura, A dynamic trajectory control algorithm for improving the communication throughput and delay in UAV-aided networks, IEEE Network 30 (1) (2016) 100–105.
  * [18] D. H. Choi, S. H. Kim, D. K. Sung, Energy-efficient maneuvering and communication of a single UAV-based relay, IEEE Transactions on Aerospace and Electronic Systems 50 (3) (2014) 2320–2327.
  * [19] F. Jiang, A. L. Swindlehurst, Optimization of UAV heading for the ground-to-air uplink, IEEE Journal on Selected Areas in Communications 30 (5) (2012) 993–1005.
  * [20] P. Zhan, K. Yu, A. L. Swindlehurst, Wireless relay communications with unmanned aerial vehicles: Performance and optimization, IEEE Transactions on Aerospace and Electronic Systems 47 (3) (2011) 2068–2085.
  * [21] Q. Wu, Y. Zeng, R. Zhang, Joint trajectory and communication design for multi-UAV enabled wireless networks, IEEE Transactions on Wireless Communications 17 (3) (2018) 2109–2121.
  * [22] Y. Zeng, R. Zhang, T. J. Lim, Throughput maximization for UAV-enabled mobile relaying systems, IEEE Transactions on Communications 64 (12) (2016) 4983–4996.
  * [23] W. Fawaz, C. Abou-Rjeily, C. Assi, UAV-aided cooperation for FSO communication systems, IEEE Communications Magazine 56 (1) (2018) 70–75.
  * [24] Y. Pang, Y. Zhang, Y. Gu, M. Pan, Z. Han, P. Li, Efficient data collection for wireless rechargeable sensor clusters in harsh terrains using UAVs, in: Global Communications Conference (GLOBECOM), IEEE, 2014, pp. 234–239.
  * [25] J. Johnson, E. Basha, C. Detweiler, Charge selection algorithms for maximizing sensor network life with UAV-based limited wireless recharging, in: International Conference on Intelligent Sensors, Sensor Networks and Information Processing (ISSNIP), IEEE, 2013, pp. 159–164.
  * [26] J. Xu, Y. Zeng, R. Zhang, UAV-enabled wireless power transfer: Trajectory design and energy optimization, IEEE Transactions on Wireless Communications.
  * [27] S. Jeong, J. Bito, M. M. Tentzeris, Design of a novel wireless power system using machine learning techniques for drone applications, in: Wireless Power Transfer Conference (WPTC), IEEE, 2017, pp. 1–4.
  * [28] X. He, J. Bito, M. M. Tentzeris, A drone-based wireless power transfer and communications platform, in: Wireless Power Transfer Conference (WPTC), IEEE, 2017, pp. 1–4.
  * [29] C. Wang, Z. Ma, Design of wireless power transfer device for UAV, in: International Conference on Mechatronics and Automation (ICMA), IEEE, 2016, pp. 2449–2454.
  * [30] S. Chen, Y. Shu, B. Yu, C. Liang, Z. Shi, J. Chen, Mobile wireless charging and sensing by drones, in: International Conference on Mobile Systems, Applications, and Services Companion (MobiSys), ACM, 2016, pp. 99–99.
  * [31] A. Mittleider, B. Griffin, C. Detweiler, Experimental analysis of a UAV-based wireless power transfer localization system, in: Experimental Robotics, Springer, 2016, pp. 357–371.
  * [32] B. Griffin, C. Detweiler, Resonant wireless power transfer to ground sensors from a UAV, in: International Conference on Robotics and Automation (ICRA), IEEE, 2012, pp. 2660–2665.
  * [33] M.-S. Alouini, A. J. Goldsmith, Adaptive modulation over nakagami fading channels, Wireless Personal Communications 13 (1-2) (2000) 119–143.
  * [34] I. S. Gradshteyn, I. M. Ryzhik, Table of integrals, series, and products, Academic press, 2014.
  * [35] K. Li, W. Ni, X. Wang, R. P. Liu, S. S. Kanhere, S. Jha, EPLA: Energy-balancing packets scheduling for airborne relaying networks, in: International Conference on Communications (ICC), IEEE, 2015, pp. 6246–6251.
  * [36] X. Wang, K. Li, S. S. Kanhere, D. Li, X. Zhang, E. Tovar, PELE: Power efficient legitimate eavesdropping via jamming in UAV communications, in: International Wireless Communications and Mobile Computing Conference (IWCMC), IEEE, 2017, pp. 402–408.
  * [37] K. Li, N. Ahmed, S. S. Kanhere, S. Jha, Reliable transmissions in AWSNs by using O-BESPAR hybrid antenna, Pervasive and Mobile Computing 30 (2016) 151–165.
  * [38] K. Li, C. Yuen, S. Jha, Fair scheduling for energy harvesting WSN in smart city, in: SenSys, ACM, 2015, pp. 419–420.
  * [39] K.-H. Liu, Selection cooperation using RF energy harvesting relays with finite energy buffer, in: Wireless Communications and Networking Conference (WCNC), IEEE, 2014, pp. 2156–2161.
  * [40] V. Mnih, K. Kavukcuoglu, D. Silver, A. A. Rusu, J. Veness, M. G. Bellemare, A. Graves, M. Riedmiller, A. K. Fidjeland, G. Ostrovski, et al., Human-level control through deep reinforcement learning, Nature 518 (7540) (2015) 529.
  * [41] J. N. Tsitsiklis, B. Van Roy, An analysis of temporal-difference learning with function approximation, IEEE Transactions on Automatic Control 42 (5) (1997) 674–690.
  * [42] M. van Otterlo, M. Wiering, Reinforcement learning and markov decision processes, in: Reinforcement Learning, Springer, 2012, pp. 3–42.
  * [43] M. Abadi, P. Barham, J. Chen, Z. Chen, A. Davis, J. Dean, M. Devin, S. Ghemawat, G. Irving, M. Isard, et al., Tensorflow: a system for large-scale machine learning, in: OSDI, Vol. 16, 2016, pp. 265–283.
  * [44] F. Chollet.  Keras: Deep learning library for theano and tensorflow [online] (2019) [cited 2019].
  * [45] D. T. Hoang, D. Niyato, P. Wang, D. I. Kim, L. B. Le, Optimal data scheduling and admission control for backscatter sensor networks, IEEE Transactions on Communications 65 (5) (2017) 2062–2077.
  * [46] Y. Zhang, S. He, J. Chen, Y. Sun, X. S. Shen, Distributed sampling rate control for rechargeable sensor nodes with limited battery capacity, IEEE Transactions on Wireless Communications 12 (6) (2013) 3096–3106.
  * [47] D. Estep, The bisection algorithm, Practical Analysis in One Variable (2002) 165–177.