Figure 4.6c shows a calculated learning process with N1, N2, and N3 as attractor neurons evidencing the gradual storage of corresponding attractor state via potentiation of mutual excitatory synapses (top) due to the convergence of corresponding RRAM devices to high conductance values (bottom). After implementing attractor learning, the network was operated in another mode referred to as recall mode. During recall process, a high-frequency stimulation of a part of stored attractor state is applied, e.g., only one out of 3 attractor neurons, leading to activation of high currents across high conductance synapses shared with other attractor neurons which are transmitted at their inputs. As a result, attractor neurons with no external stimulation start spiking, thus retrieving the whole attractor state via a sustained spiking activity able to persist even after removing external stimulation [35]. Importantly, the ability of Hopfield networks to recall an attractor state by its incomplete stimulation was exploited to replicate in simulation a fundamental mammalian primitive referred to as associative memory taking inspiration from the Pavlov's dog experiments [37]. Indeed, as illustrated in Fig. 4.6d, after repeatedly stimulating a dog combining the ring of a bell with the presentation of food leading it to salivate, an external stimulation only with the ring of bell is able to reactivate the bell-food-salivation attractor in the dog [35]. Finally, Hopfield neural network with 1T1R synapses was also successfully used to explore in simulation pattern completion task, namely the reconstruction of an image stimulating its small features [38], which supports the strong potential of Hopfield neural networks with resistive synapses in computational tasks.

#### **4.6 Conclusions**

This chapter covers design, modeling and simulation of SNNs with CMOS/RRAM synapses capable of implementing brain-inspired neuromorphic computing. First, unsupervised learning at synaptic level has been addressed by development of 1T1R synapse and 4T1R synapse capable of replicating STDP and SRDP, respectively. Then, applications of these resistive synapses in SNNs have been investigated. A perceptron network with 4T1R synapses has been simulated demonstrating its ability to achieve on-line learning of sequential images via SRDP-based adaptation of synaptic weights. In addition, attractor learning and recall processes have been achieved in a Hopfield recurrent neural network with excitatory/inhibitory 1T1R synapses by simulations supporting its ability to implement associative memory. These results support RRAM as promising technology for future development of large-scale neuromorphic systems capable of emulating unrivaled energy and computational efficiency of biological brain.

#### **References**

**Open Access** This chapter is licensed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license and indicate if changes were made.

The images or other third party material in this chapter are included in the chapter's Creative Commons license, unless indicated otherwise in a credit line to the material. If material is not included in the chapter's Creative Commons license and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder.

## **Part III Computer Science and Engineering**

## **Chapter 5 Learning and Adaptation to Detect Changes and Anomalies in High-Dimensional Data**

#### **Diego Carrera**

**Abstract** The problem of monitoring a datastream and detecting whether the data generating process changes from normal to novel and possibly anomalous conditions has relevant applications in many real scenarios, such as health monitoring and quality inspection of industrial processes. A general approach often adopted in the literature is to learn a model to describe normal data and detect as anomalous those data that do not conform to the learned model. However, several challenges have to be addressed to make this approach effective in real world scenarios, where acquired data are often characterized by high dimension and feature complex structures (such as signals and images). We address this problem from two perspectives corresponding to different modeling assumptions on the data-generating process. At first, we model data as realization of random vectors, as it is customary in the statistical literature. In this settings we focus on the change detection problem, where the goal is to detect whether the datastream permanently departs from normal conditions. We theoretically prove the intrinsic difficulty of this problem when the data dimension increases and propose a novel non-parametric and multivariate change-detection algorithm. In the second part, we focus on data having complex structure and we adopt dictionaries yielding sparse representations to model normal data. We propose novel algorithms to detect anomalies in such datastreams and to adapt the learned model when the process generating normal data changes.

#### **5.1 Introduction**

The general problem we address here is the monitoring of datastreams to detect in the data-generating process. This problem has to be faced in several applications, since the change could indicate an issue that has to be promptly alarmed and solved. In particular, we consider two meaningful examples. Figure 5.1a shows a Scanning Electron Microscope (SEM) image acquired by an inspection system that monitors

D. Carrera (B)

Politecnico di Milano, Piazza Leonardo da Vinci 32, Milan, Italy e-mail<EMAIL_ADDRESS>
© The Author(s) 2020

B. Pernici (ed.), *Special Topics in Information Technology*, PoliMI SpringerBriefs, https://doi.org/10.1007/978-3-030-32094-2\_5

**Fig. 5.1 a** A detail of a SEM image acquired by the considered inspection system depicting nanofibrous material. The two small *beads*, i.e., fiber clots, on the right reduce the quality of the produced material. **b** Example of few seconds of ECG signal containing 4 normal heartbeats (one of which highlighted in green) and an anomalous one (highlighted in red) (Color figure online)

the quality of nanofibrous materials produced by a prototype machine. In normal conditions, the produced material is composed of tiny filaments whose diameter ranges up to 100 nanometers. However, several issues might affect the production process and introduce small defects among the fibers, such as the clots in Fig. 5.1a. These defects have to be promptly detected to improve the overall production quality.

The second scenario we consider is the online and long-term monitoring of ECG signals using wearable devices. This is a very relevant problem as it would ease the transitioning from hospital to home/mobile health monitoring. In this case the data we analyze are the heartbeats. As shown in Fig. 5.1b, normal heartbeats feature a specific morphology, while the shape of anomalous heartbeats, that might be due to potentially dangerous arrhythmias, is characterized by a large variability. Since the morphology of normal heartbeats depends on the user and the position of the device [16], the anomaly-detection algorithm has to be configured every time the user places the device.

Monitoring this kind of datastream raises three main challenges: at first data are characterized by complex structure and high dimension and there is no analytical model able to describe them. Therefore, it is necessary to learn models directly from data. However, only normal data can be used during learning, since acquiring anomalous data can be difficult if not impossible (e.g., in case of ECG monitoring acquiring arrhythmias might be dangerous for the user). Secondly, we have to careful design indicators and rules to assess whether incoming data fit or not the learned model. Finally, we have to face the domain adaptation problem, since normal condition might changes during time and the learned model might not be able to describe incoming normal data, thus it has to be adapted accordingly. For example, in ECG monitoring the model is learned over a training set of normal heartbeats acquired at low heart rate, but the morphology of normal heartbeats changes when the heart rate increases, see Fig. 5.2b.

**Fig. 5.2 a** Details of SEM images acquired at different scales. The content of these images is different, although they are perceptually similar. **b** Examples of heartbeats acquired at different heart rate. We report the name of the waveforms of the ECG [13]

We investigate these challenges following two directions, and in particular, we adopt two different modeling assumptions on data-generating process. At first, we assume that data can be described by a smooth probability density function, as customary in the statistics literature. In these settings we focus on the change-detection problem, namely the problem of detecting permanent changes in the monitored datastreams. We investigate the intrinsic difficulty of this problem, in particular when the data dimension increases. Then, we propose QuantTree, a novel change detection algorithms based on histograms that enables the non-parametric monitoring of multivariate datastreams.We theoretically prove that any statistic compute over histograms defined by QuantTree does not depend on the data-generating process.

In the second part we focus on data having a complex structure, and address the anomaly detection problem. We propose a very general anomaly-detection algorithm based on a dictionary yielding sparse representation learned from normal data. As such, it is not able to provide sparse representation to anomalous data, and we exploit this property to design low dimensional indicators to assess whether new data conform or not to the learned dictionary. Moreover, we propose two domain adaptation algorithms to make our anomaly detector effective in the considered application scenarios.

The chapter is structure as follows: Sect. 5.2 presents the most relevant related literature and Sect. 5.3 formally state the problem we address. Section 5.4 focuses on the contribution of the first part of the thesis, where we model data as random vectors, while Sect. 5.5 is dedicated to the second part of the thesis, where we consider data having complex structures. Finally, Sect. 5.6 presents the conclusions and the future works.

#### **5.2 Related Works**

The first algorithms [22, 24] addressing the change-detection problem were proposed in the statistical process control literature [15] and consider only univariate datastreams. These algorithms are well studied and several properties have been proved due to their simplicity. Their main drawback is that they require the knowledge of the data generating distributions. Non-parametric methods, namely those that can operate when this distribution is unknown, typically employ statistics that are based on natural order of the real numbers, such as Kolmogorov–Smirnov [25] and Mann-Whitney [14]. Extending these methods to operate on multivariate datastreams is far from being trivial, since no natural order is well defined on R*d* . The general approach to monitor multivariate datastreams in is to learn a model that approximates φ0 and monitor a univariate statistic based on the learned model. One of the most popular non-parametric approximation of φ0 is given by Kernel Density Estimation [17], that however becomes intractable when the data dimension increases.

All these methods assume that data can be described by a smooth probability density function (pdf). However, complex data such as signal and images live close to a low-dimensional manifold embedded in a higher dimensional space [3], and do not admit a smooth pdf. In these cases, it is necessary to learn meaningful representations to data to perform any task, from classification to anomaly detection. Here, we consider dictionary yielding sparse representations that have been originally proposed to address image processing problems such as denoising [1], but they were also employed in supervised tasks [19], in particular classification [20, 23]. The adaptation of dictionaries yielding sparse representations to different domain were investigated in particular to address the image classification problem [21, 27]. In this scenario training images are acquired under different conditions than the test ones, e.g. different lightning and view angles, and therefore live in a different domain.

#### **5.3 Problem Formulation**

Let as consider a datastream {**s***t*}*t*=1,..., where **s***t* ∈ R*d* is drawn from a process P*N* in normal condition. We are interest in detect whether **s***t* ∼ P*A*, i.e., **s***t* is drawn from an alternative process P*A* representing the anomalous conditions. Both P*N* and P*A* are unknown, but we assume that a training set of normal data is available to approximate P*N* . In what follows we describe in details the specific problems we consider in the thesis.

**Change Detection**. At first, we model **s***t* as a realization of a continuous random vector, namely we assume that P*N* and P*A* admit smooth probability density functions φ0 and φ1, respectively. This assumption is not too strict, as it usually met after a feature extraction process.

We address the problem of detecting abrupt change in the data-generating process. More precisely, our goal is to detect if there is a change point τ ∈ N in the datastreams such that **s***t* ∼ φ0 for *t* ≤ τ and **s***t* ∼ φ1 for *t* > τ . For simplicity, we analyze the datastream in batches *W* = {**s**1,...,**s**ν } of ν samples and detect changes by performing the following hypothesis test:

$$H\_0: \ W \sim \phi\_0, \qquad H\_1: \ W \sim \phi\_0 \tag{5.1}$$

The null hypothesis is rejected whether T(*W*)>γ , where T is a statistic typically defined upon the model that approximate the density φ0, and γ is defined to guarantee a desired probability of false positive rate α, i.e. *P*φ0 (*T* (*W*)> γ) ≤ α.

**Anomaly Detection**. The anomaly-detection problem is strictly related to change detection. The main difference is that in anomaly detection we analyze each **s***t* independently to whether is draw from P*N* or P*A*, without taking into account the temporal correlation (for this reason we will omit the subscript *t*). In this settings we consider data having complex structure, such as heartbeats or patches, i.e., small region extracted from an image. We adopt dictionaries yielding sparse representation to describe **s** ∼ P*N* , namely we assume that**s** ≈ *D***x**, where *D* ∈ R*d*×*n* is a matrix called *dictionary*, that has to be learned from normal data and the coefficient vector **x** ∈ R*n* is *sparse*, namely it has few of nonzero components. To detect anomalies, we have to define a decision rule, i.e., a function T : R*d* → R and a threshold γ such that

$$\mathbf{s} \text{ is anomalous} \iff \mathcal{T}(\mathbf{s}) \succ \mathcal{Y},\tag{5.2}$$

where T(**s**) is defined using the sparse representation **x** of **s**.

**Domain Adaptation**. The process generating normal data P*N* may change over time. Therefore, a dictionary *D* learned on training data (i.e., in the source domain), might not be able to describe normal data during test (i.e., in the target domain). To avoid degradation in the anomaly-detection performance, *D* has to be adapted has soon as P*N* changes. For example, in case of ECG monitoring the morphology of normal heartbeats changes when the heart rate increases, while in case of SEM images, the magnification level of the microscope may change, and this modify the qualitative content of the patches, as shown in Fig. 5.2.

#### **5.4 Data as Random Vectors**

In this section we consider data modeled as random vectors. At first we investigate the detectability loss phenomenon, showing that the change-detection performance are heavily affected by the data dimension. Then we propose a novel change-detection algorithm that employs histograms to describe normal data.

#### *5.4.1 Detectability Loss*

As described in the Sect. 5.3, we assume that both P*N* and P*A* admit a smooth pdf φ0, φ1 : R*d* → R. For simplicity, we also assume that φ1 that can be expressed as φ1(**s**) = φ0(*Q***s** + **v**), where **v** ∈ R*d* and *Q* ∈ R*d*×*d* is an orthogonal matrix. This is quite a general model as it includes changes in the mean as well as in the correlations of components of **s***t* . To detect changes, we consider the popular approach that monitor the loglikelihood w.r.t. the distribution generating normal data φ0:

$$\mathcal{L}(\mathbf{s}\_l) = \log(\phi\_0(\mathbf{s}\_l)).\tag{5.3}$$

In practice, we reduce the multivariate datastream {**s***t*} to a univariate one {L(**s***t*)}. Since φ0 is unknown, we should preliminary estimate φ 0 from data, and use it in (5.3) in place of φ0. However, in what follows we will consider φ0 since it make easier to investigate how the data dimension affect the change-detection performance.

We now introduce two measures that we will use in our analysis. The *change magnitude* assesses how much φ1 differs from φ0 and is defined as sKL(φ0, φ1), namely the symmetric Kullback–Leibler divergence between φ0 and φ1 [12]. In practice, large values of sKL(φ0, φ1) makes the change very apparent, as proved in the Stein's Lemma [12]. The *change detectability* assesses how the change is perceivable by monitoring the datastream {L(**s***t*)} and is defined as the signal-tonoise ratio of the change φ0 → φ1:

$$\text{SNR}(\phi\_0, \phi\_1) := \frac{\left(\underset{\mathbf{s} \sim \phi\_0}{\operatorname{\mathbf{s}}} \{\mathcal{L}(\mathbf{s})\} - \underset{\mathbf{s} \sim \phi\_1}{\operatorname{\mathbf{s}}} \{\mathcal{L}(\mathbf{s})\}\right)^2}{\operatorname{var}\left[\mathcal{L}(\mathbf{s})\right] + \underset{\mathbf{s} \sim \phi\_0}{\operatorname{var}} \{\mathcal{L}(\mathbf{s})\}},\tag{5.4}$$

where *E* and var denote the expected value and the variance, respectively.

The following theorem proves *detectability loss* on Gaussian datastreams (the proof is reported in [2]).

**Theorem 1** *Let* φ0 = N(μ0, 0) *be a d-dimensional Gaussian pdf and* φ1 = φ0(*Q***s** + **v**)*, where Q* ∈ R*d*×*d is orthogonal and* **v** ∈ R*d . Then, it holds*

$$SNR(\phi\_0, \phi\_1) \le \frac{C}{d} \tag{5.5}$$

*where the constant C depends only on sKL*(φ0, φ1)*.*

The main consequences of Theorem 1 is that the change detectability decreases when the data dimension increases, as long as the change magnitude is kept fixed. Remarkably, this results is independent on how the changes affected the datastream (i.e., it is independent on *Q* and **v**), but only on the change magnitude. Moreover, it does not depend on estimation error, since in (5.4) we have considered the true and unknown distribution φ0. However, the detectability loss becomes more severe when the loglikelihood is computed w.r.t. the estimated φ -0, as we showed in [2].

Finally, we remark that the detectability loss holds also for more general distributions φ0, such as Gaussian Mixture, and on real data. In that case the problem cannot treated analytically, but we empirically show similar results using Controlling Change Magnitude (CCM) [6], a framework to inject changes of a given magnitude in real world datastreams.

#### *5.4.2 QuantTree*

In this section we present QuantTree, a novel change detection algorithm that computes a histogram to approximate φ0. A histogram *h* is defined as *h* = {(*Bk* ,π*k* )}*k*=1,...,*K* , where the bins {*Bk* } identify a partition of the data space, while the {π*k* } are the probabilities associated to the bins. In practice, we estimate *h* to approximate φ0 and π*k* is an estimate of the probability of **s** ∼ φ0 to fall inside *Bk* . As described in Sect. 5.3, we monitor the datastream in a batch-wise manner and we consider statistics T*h*(*W*) defined over the histogram *h*, namely statistics that depend only on the number *yk* of samples of *W* that fall in the bin *Bk* , for *k* = 1,..., *K*. Examples of such statistics are the Total Variation distance and the Pearson's statistic.

The proposed QuantTree algorithm takes as input target probability values {π*k* } and generates a partitioning {*Bk* } such that the corresponding probability {π*k* } are close to {π*k* }. QuantTree is an iterative splitting scheme that generate a new bin at each iteration *k*. The bin is defined by splitting along a component chosen at random among the *d* available. The splitting point is selected to contain exactly round(π*kN*) samples of the training set, where *S* is the number of training samples. An example of partitioning computed by QuantTree is show in Fig. 5.3.

The main property of QuantTree is that its peculiar splitting scheme makes the distribution of any statistics T*h* independent on the data-generating distribution φ0. This properly is formally stated in the following theorem, that we proved in [4].

**Theorem 2** *Let* T*h*(·) *be defined over an histogram h computed by QuantTree. When W* ∼ φ0*, the distribution of* T*h*(*W*) *depends only on* ν*, N and* {π*k* }*k .*

**Fig. 5.3** A partitioning with *K* = 5 bins computed by QuantTree over a training set of *N* = 30 samples. We set π*k* = 1/*K* to yield a uniform density histograms, thus all the bins contain 6 samples each

In practice, the distribution of any statistic T*h* depends only on the cardinalities of the training set and the window *W* and on the target probabilities {π*k* }. The main consequence of Theorem 2 is that the threshold γ that guarantees a given false positive rate α does not depend on φ0. Therefore, we can precompute γ through by estimating the distribution of T*h* over synthetically generated samples though Montecarlo simulations. To the best of our knowledge, QuantTree is one of the first algorithms that performs non-parametric monitoring of multivariate datastreams.

We compare the histograms computed by QuantTree with other partitioning in the literature in [4] through experiments on Gaussian datastreams and real world datasets. Histograms computed by QuantTree yield a larger power and are the only ones that allows to properly control the false positive rate. We remark that also QuantTree suffers of the detectability loss, confirming the generality of our results on detectability loss.

#### **5.5 Data Featuring Complex Structures**

In this section we employ dictionaries yielding sparse representations to model data having complex structures. At first we present our general anomaly detection algorithm, then we introduce our two domain-adaptation solutions, specifically designed for the application scenarios described in Sect. 5.1.

#### *5.5.1 Sparsity-Based Anomaly Detection*

Our modeling assumption is that normal data **s** ∼ P*N* can be well approximated as **s** ≈ *D***x**, where **x** ∈ R*n* is sparse, namely it has only few nonzero components and the dictionary *D* ∈ R*d*×*n* approximates the process P*N* . The sparse representation **x** is computed by solving the sparse coding problem:

$$\mathbf{x} = \underset{\mathbf{X} \in \mathbb{R}^n}{\arg\min} \frac{1}{2} \|\mathbf{s} - D\mathbf{x}\|\_2^2 + \lambda \|\mathbf{x}\|\_1,\tag{5.6}$$

where the 1 norm **x** 1 is used to enforce sparsity in **x**, and the parameter λ ∈ R controls the tradeoff between the 1 norm and the reconstruction error **s** − *D***x** 2 2. The dictionary *D* is typically unknown, and we have to learn it from a training set of normal data by solving the dictionary learning problem:

$$\|D, X = \underset{\widetilde{D} \in \mathbb{R}^{d \times n}, \widetilde{X} \in \mathbb{R}^{n \times n,}}{\text{arg min}} \frac{1}{2} \|S\_0 - \widetilde{D}\widetilde{X}\|\_2^2 + \lambda \|X\|\_1,\tag{5.7}$$

where *S*0 ∈ R*d*×*m* is the training set that collects normal data column-wise.

To assess whether **s** is generated or not from P*N* , we define a bivariate indicator vector **f** ∈ R2 collecting the reconstruction error and the sparsity of the representation:

$$\mathbf{f}(\mathbf{s}) = \begin{bmatrix} \|\mathbf{s} - D\mathbf{x}\|\_2 \\ \|\mathbf{x}\|\_1 \end{bmatrix}. \tag{5.8}$$

In fact, we expect that when **s** is anomalous it deviates from normal data either in the sparsity of the representation or in the reconstruction error. This means that **f**(**s**) would be an outlier w.r.t. the distribution φ0 of **f** computed over normal data. Therefore, we detect anomalies as in (5.2) by setting T = − log(φ0), where φ0 is estimate from a training set of normal data (different from the set *S*0 used in dictionary learning) using Kernel Density Estimation [5].

We evaluate our anomaly-detection algorithm on a dataset containing 45 SEM images. In this case **s** ∈ R15×15 is a small squared patch extracted from the image. We analyze each patch independently to determine if it is normal or anomalous. Since each pixel of the image is contained in more than one patch, we obtain several decisions of each pixel. To detect defects at pixel level, we aggregate all the decisions through majority voting. An example of the obtained detections is shown in Fig. 5.4: our algorithm is able to localize all the defects by keeping the false positive rate small. More details on our solution and experiments are reported in [8].

In case of ECG monitoring, the data to be analyzed are the heartbeats, that are extracted from the ECG signal using traditional algorithms. Since our goal is to perform ECG monitoring directly on the wearable device, that has limited computational capabilities, we adopt a different sparse coding procedure, that is based on the 0 "norm" and it is performed by means of greedy algorithms [11]. In particular, we proposed a novel variant of the OMP algorithm [9], that is specifically designed for dictionary *D* ∈ R*d*×*n* where *n* < *d*, that is settings we adopt in ECG monitoring. Dictionary learning, that is required every time the device is positioned as the shape of normal heartbeats depends both of the users and device position, is performed on a host device, since the computational resources of wearable devices are not sufficient.

#### *5.5.2 Multiscale Anomaly-Detection*

In the quality inspection through SEM images, we have to face the domain adaptation problem since the magnification level of the microscope may change during monitoring. Therefore, we improve our anomaly-detection algorithm to make it scaleinvariant. The three key ingredients we use are: *(i)* a multiscale dictionary that is able to describe patch extracted from image at different resolution, *(ii)* a multiscale sparse representation that captures the structure in the patch at different scales and *(iii)* a triviate indicator vector, that is more powerful that the one in (5.8).

We build the multiscale dictionary as *D* = [*D*1| ... |*DL* ]. Each subdictionary *Dj* is learned by solving problem (5.7) over patched extracted from synthetically rescaled

**Fig. 5.4** Detail of defect detection at pixel level. Green, blue and red pixel identify the true positive, false negative and false positive, respectively. The threshold γ in (5.2) was set to yield a false positive rate equal to 0.05 (Color figure online)

version of training images. Therefore, we can learn a multiscale dictionary even if the training images are acquired at a fixed scale. To compute the multiscale representation **x** we solve the following sparse coding problem:

$$\hat{\mathbf{x}} = \operatorname\*{arg\,min}\_{\mathbf{x}} \frac{1}{2} \|\mathbf{s} - D\mathbf{x}\|\_2^2 + \lambda \|\mathbf{x}\|\_1 + \xi \sum\_{j=1}^{L} \|\mathbf{x}\_j\|\_2,\tag{5.9}$$

where each **x***j* refers to the subdictionary *Di* and **x** collects all the **x***j* . The group sparsity term *L j*=1 **x***j* 2 ensures that each patch is reconstructed using coefficients of **x** that refers only to few scales. Finally, we define a trivariate indicator vector **f** that includes the reconstruction error and the sparsity as in (5.8) and also the group sparsity term *j* **x***j* 2. We detect anomalies using the same approach described in Sect. 5.5.1. Our experiments [7] show that employing a multiscale approach in all phases of the algorithm (dictionary learning, sparse coding and anomaly indicators) achieves good anomaly detection performance even when training and test images are acquired at different scales.

#### *5.5.3 Dictionary Adaptation for ECG Monitoring*

To make our anomaly-detection algorithm effective in long-term ECG monitoring, we have to adapt the user-specific dictionary. In fact, to keep the training procedure safe for the user, this dictionary is learned from heartbeats acquired in resting conditions, and it would be not able to describe normal heartbeats acquired during daily activities, when the heart rate increases and normal heartbeats get transformed, see Fig. 5.2b. These transformations are similar for every user: the T and P waves approach the QRS complex and the support of the heartbeats narrows down. Therefore, we adopt user-independent transformations *Fr*,*r*0R*dr*×*dr*0 to adapt the user-specific dictionary *Du*,*r*0 ∈ R*dr*0×*n*:

$$D\_{u,r} = F\_{r,r\_0} D\_{u,r\_0},\tag{5.10}$$

where *r*0 and *r* denotes the heart rates in resting condition and during daily activities, respectively, and *u* indicates the user. The transformation *Fr*,*r*0 depends only on the heart rates and is learned from collections *Su*,*r* of training sets of normal heartbeats of several users acquired at different heart rates extracted from publicly available datasets of ECG signals. The learning has to performed only ones by solving the following optimization problem:

$$F\_{r,r\_0} = \underset{F, \{X\_u\}\_u}{\text{arg min}} \frac{1}{2} \sum\_{u=1}^L \left\| S\_{u,r} - FD\_{u,r\_0} X\_u \right\|\_2^2 + \mu \sum\_{u=1}^L \left\| X\_u \right\|\_1 + \frac{\lambda}{2} \left\| W \odot F \right\|\_2^2 + \xi \left\| W \odot F \right\|\_1,$$

where the first term ensures that the transformed dictionaries *F Du*,*r*0 provide good approximation to the heartbeats of the user *u*. Moreover, we adopt three regularization terms: the first one is based on 1 norm and enforces sparsity in the representations of heartbeats at heart rate *r* for each user *u*. The other two terms represent a weighted elastic net penalization over *F* to improves the stability of the optimization problem, and the weighting matrix *W* introduces regularities in *Fr*,*r*0 .

The learned *Fr*,*r*0 (for several values of *r* and *r*0) are then hard-coded in the wearable device to perform online monitoring [18]. We evaluate our solution on ECG signals acquired using the Bio2Bit Dongle [18]. Our experiments [10] show that the reconstruction error is kept small when the heart rate increases, implying that our transformations effectively adapt the dictionaries to operate at higher heart rate. Moreover, our solution is able to correctly identify anomalous heartbeats even at very large heart rate, when the morphology of normal heartbeats undergoes severe transformations.

#### **5.6 Conclusions**

We have addressed the general problem of monitoring a datastream to detect whether the data generating process departs from normal conditions. Several challenges have to be addressed in practical applications where data are high dimensional and feature complex structures. We address these challenges from two different perspectives by making different modeling assumption on the data generating process.

At first we assume that data can be described by a smooth probability density function and address the change detection problem. We prove the detectability loss phenomenon, that relates the change-detection performance and the data dimension, and we propose QuantTree, that is one of the first algorithms that enables nonparametric monitoring of multivariate datastream. In the second part, we employ dictionary yielding sparse representation to model data having featuring complex structures and propose a novel anomaly-detection algorithm. To make this algorithm effective in practical applications, we propose two domain-adaptation solutions that turn to be very effective in long-term ECG monitoring and in a quality inspection of an industrial process.

Future works include the extension of QuantTree to design a truly multivariate change-detection algorithm, and in particular to control the average run length instead of the false positive rate. Another relevant directions is the design of models that provide good representation for detection tasks. In fact, our dictionaries are learned to provide good reconstruction to the data, and not to perform anomaly detection. Very recent works such as [26] show very promising results using deep learning, but a general methodology is still not available.

#### **References**

**Open Access** This chapter is licensed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license and indicate if changes were made.

The images or other third party material in this chapter are included in the chapter's Creative Commons license, unless indicated otherwise in a credit line to the material. If material is not included in the chapter's Creative Commons license and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder.

## **Chapter 6 Enhancing Video Recommendation Using Multimedia Content**

**Yashar Deldjoo**

**Abstract** Video recordings are complex media types. When we watch a movie, we can effortlessly register a lot of details conveyed to us (by the author) through different multimedia channels, in particular, the audio and visual modalities. To date, majority of movie recommender systems use collaborative filtering (CF) models or content-based filtering (CBF) relying on metadata (e.g., editorial such as genre or wisdom of the crowd such as user-generated tags) at their core since they are human-generated and are assumed to cover the 'content semantics' of movies by a great degree. The information obtained from multimedia content and learning from muli-modal sources (e.g., audio, visual and metadata) on the other hand, offers the possibility of uncovering relationships between modalities and obtaining an in-depth understanding of natural phenomena occurring in a video. These discerning characteristics of heterogeneous feature sets meet users' differing information needs. In the context of this Ph.D. thesis [9], which is briefly summarized in the current extended abstract, approaches to automated extraction of multimedia information from videos and their integration with video recommender systems have been elaborated, implemented, and analyzed. Variety of tasks related to movie recommendation using multimedia content have been studied. The results of this thesis can motivate the fact that recommender system research can benefit from knowledge in multimedia signal processing and machine learning established over the last decades for solving various recommendation tasks.

#### **6.1 Introduction and Context**

Users base their decision making about which movie to watch typically on its content, whether expressed in terms of metadata (e.g., genre, cast, or plot) or the feeling experienced after watching the corresponding movie trailer in which the visual content (e.g., color, lighting, motion) and the audio content (e.g., music or spoken dialogues)

Y. Deldjoo (B)

SisInf Lab, Department of Electrical Engineering and Information Technology, Polytechnic University of Bari, Via Orabona, 4, 70125 Bari, Italy e-mail<EMAIL_ADDRESS><EMAIL_ADDRESS>
© The Author(s) 2020

B. Pernici (ed.), *Special Topics in Information Technology*, PoliMI SpringerBriefs, https://doi.org/10.1007/978-3-030-32094-2\_6

play a key role in users' perceived affinity to the movie. The above examples underline that human interpretation of media items is intrinsically content-oriented.

Recommender systems support users in their decision making by focusing them on a small selection of items out of a large catalogue. To date, most video recommendation models use collaborative filtering (CF), content-based filtering on metadata (CBF-metadata), or a combination thereof at their core [33, 35, 42]. While CF models exploit the correlations encoded in users' preference indicators—either implicit (clicks, purchases) or explicit (ratings, votes)—to predict the best-matching useritem pairs, CBF models use the preference indications of a single target user and content information available about the items in order to build a user model (aka user profile) and compute recommendations. CBF approaches typically leverage *metadata* as a bridge between items and users, effectively disregarding a wealth of information encoded in the actual audio visual signals [13]. If we assume the primary role of a recommender system is to help people make choices that they will ultimately be satisfied with [7], such systems should thus take into account multiple source of information driving users' perception of media content and make a rational decision about their relative importance. This would in turn offer users the chance to learn more about their multimedia taste (e.g., their visual or musical taste) and their semantic interests [10, 13, 44].

The above are underlying ideas about why multimedia content can be useful for recommendation of *warm items* (videos with sufficient interactions). Nevertheless, in most video streaming services, new videos are continuously added. CF models are unable to make predictions in such scenario, since the newly added videos lack interactions, technically known as *cold-start* problem [5] and the associated items are referred by *cold items*(videos with few interactions) or *new items*(videos with no interactions). Furthermore, metadata can be rare/absent for cold/new videos, making it difficult to provide good quality recommendations [43]. Despite much research conducted in the field of RS for solving different tasks, the cold start (CS) problem is far from solved and most existing approaches suffer from it. Multimedia information *automatically extracted* from the audio-visual signals can serve as a proxy to solve the CS problem; in addition, it can act as a complementary information to identify videos that "look similar" or "sound similar" in warm start (WS) settings. These discerning characteristics of multimedia meet users' different information needs. As a branch of recommender systems, my Ph.D. thesis [9] investigates a particular area in the design space of recommender system algorithm in which the generic recommender algorithm needs to be optimized in order to use a wealth of information encoded in the actual image and audio signals.

#### **6.2 Problem Formulation**

In this section, we provide a formal definition of *content-based filtering video recommendation systems* (CBF-VRS) exploiting *multimedia content information*. In particular, we propose a general recommendation model of videos as composite media objects, where the recommendation relies on the computation of distinct utilities, associated with image, audio, and textual modalities and a final utility, which is computed by aggregating individual utility values [22].1

A CBF-VRS based on multimedia content information is characterized by the following components:

**1. Video Items**: A video item *s* is represented by the triple: *s* = *(sV ,sA,sT )* in which *sV* , *sA*, *sT* refer to the *visual*, *aural*, and *textual* modalities, respectively. *sV* encodes the *visual information* represented in the video frames;*sA* encodes the *audio information* represented in sounds, music, spoken dialogues of a video; finally *sT* is the metadata (e.g., genre labels, title) or natural language (e.g., sub-captions or speech spoken by humans and transcribed as text).

A video is a *multi-modal (composite)* media type (using *sA*, *sV* and *sT* ). This is while an audio item that represents performance of a classical music piece can be seen as an *uni-modal (atomic)* media type (using only *sA*). A pop song with lyrics can be regarded as composite (using *sA* and *sT* ), while an image of a scene or a silent movie atomic as well (using *sV* ). Multi-modal data supplies the system with rich and diverse information on the phenomenon relevant to the given task [27].

**Definition 6.1** A CBF-VRS exploiting multimedia content is characterized as a system that is able to store and manage video items *s* ∈ S, in which S is a repository of video items.

**2. Multimedia Content-Based Representation**: Developing a CBF-VRS based on multimedia content relies on content-based (CB) descriptions according to distinct modalities (*sV* , *sA*, *sT* ). From each modality, useful features can be extracted to describe the information of that modality. Different features can be classified based on several dimensions, e.g., the semantic expressiveness of features, level of granularity among others [4]. As for the former for instance, it is common to distinguish three levels of expressiveness, with increasing extent of semantic meaning: *low-level*, *midlevel*, and *high-level* features with respect to which features are categorized as shown in Table 6.1.

Over the last years, a large number of CB descriptors have been proposed to quantify various type of information in a video as summarized in Table 6.1. These descriptors are usually extracted by applying some form of signal processing or machine learning specific to a modality, and are described based on specific feature vectors. For example, in the visual domain, a rich suite of of low-level visual features are proposed by research in communities of multimedia, machine learning and computer vision for the purpose of image understanding, which we deem important for a CBF-VRS. The most basic and frequently used low-level features are *color*, *texture*, *edge* and *shape*, which are used to describe the "visual contents" of an image [26]. Besides, in the last two decades the need for devising descriptors that reduce or eliminate sensitivity to variations such as illumination, scale, rotation, and view point was

1Note that in this section, although definition of utilities are based on CBF model, in practice they can include a combination of CBF and CF models at their core.

**Table 6.1** Categorization of different multimedia features based on their semantic expressiveness. Low-level features are close to the raw signal (e.g., energy of an audio signal, contrast in an image, motion in a video, or number of words in a text), while high-level features are close to the human perception and interpretation of the signal (e.g., motif in a classical music piece, emotions evoked by a photograph, meaning of a particular video scene, story told by a book author). In between, mid-level features are more advanced than low-level ones, but farther away from being semantically meaningful as high-level ones. They are often expressed as a combination or transformations of low-level features, or they are inferred from low-level features via machine learning

recognized in the community of computer vision. This gave rise to the development of a number of popular computer vision algorithms for image understanding [46]. They include for instance scale invariant feature transform (*SIFT*) [36], speeded up robust features (*SURF*) [6], local binary patterns (*LBP*) [41], discrete Wavelet transform (*DWT*), such as Gabor filters [37], discrete Fourier transform (*DFT*), and histogram of oriented gradients (*HOG*) [8]. The peak of these developments was reached in the early 2010s, when deep convolutional neural networks (*CNNs*) achieved groundbreaking accuracy for image classification [34]. One of the most frequently stated advantages of the Deep Neural Networks (*DNNs*) is that, they leverage the representational power of high-level semantics encoded in DNNs to narrow the semantic gap between the visual contents of the image and high-level concepts in the user's mind when consuming media items.

**Definition 6.2** A CBF-VRS exploiting multimedia content is a system that is able to process video items and represent each modality in terms of a feature vector **fm** = [ *f*1*, f*2*, ... f*|**fm**|] ∈ R|**fm**| where *m* ∈ {*V, A, T* } represents the visual, audio or textual modality.2

**3. Recommendation Model**: A recommendation model provides suggestions for items that are most likely of interest to a particular user [42].

Let U and S denote a set of users and items, respectively. Given a target user *u* ∈ U, to whom the recommendation will be provided, and a repository of items *s* ∈ S, the general task of a personalized recommendation model is to identify the video item *s*∗ that satisfies

$$\forall \boldsymbol{\mu} \in \mathcal{U}, \; s\_{\boldsymbol{\mu}}^{\*} = \arg\max\_{\boldsymbol{s} \in \mathcal{S}} \; R(\boldsymbol{u}, \boldsymbol{s}) \tag{6.1}$$

2Note that here we step our attention outside the end-to-end learning approaches often performed by deep neural networks where the intermediate step of feature extraction is not done explicitly, and instead feature extraction and the final machine learning task are jointly performed.

where *R(u,s)* is the *estimated utility* of item *s* for the user *u* on the basis of which the items are ranked [3]. The utility is infact a measure of *usefulness* of an item to a user and is measured by the RS to judge how much an item is *worth* being recommended. For example, some examples of such a utility function include a utility represented by a *rating* or a *profit* function [1].

**Definition 6.3** A **multi-modal CBF-VRS** is a system that aims to improve learning performance using the knowledge/information aquired from different data sources of different video modalities. The utility of recommendations in a multi-modal CBF-VRS can be specified with respect to several specific utilities computed across each modality, thus

$$\forall \boldsymbol{\mu} \in \mathcal{U}, \; s\_{\boldsymbol{\mu}}^{\*} = \arg\max\_{\boldsymbol{s} \in \mathcal{S}} \; R(\boldsymbol{\mu}, \mathbf{s}) = F(R\_{\boldsymbol{m}}(\boldsymbol{\mu}, \mathbf{s})) \tag{6.2}$$

where *Rm(u,s)* denotes the utility of item *s for user u* with regards to modality *m* ∈ {*V, A, T* }, and *F* is an aggregation function of the estimated utilities for each modality.

Based on the semantics of the aggregation, different functions can be employed, each implying a particular interpretation of the affected process. A standard and simplest form of aggregation functions are *conjunctive* (such as min operator), *disjunctive* (such as max operator), and *averaging* [39, 45]. As an example of the latter, and the one used in the field of multimedia information retrieval (MMIR), the weighted average linear combination is commonly used thus

$$R(\mu, s) = \sum\_{m} w\_{m} R\_{m}(\mu, s) \tag{6.3}$$

where *wm* is a weight factor indicating the importance of modality *m*, known as modality weights. The weights can be chosen as fixed weights or learned via machine learning. For example, recently studies based on *dictionary learning*, *co-clustering* and *multi-modal topic modeling* have become increasingly popular paradigms for the task of multi-modal inference [30]. For instance, multi-modal topic modelling (commonly methods based on latent semantic analysis or latent Dirichlet allocation) [30] models visual, audio and textual words with an underlying latent topic space.

#### **6.3 Brief Overview of Ph.D. Research**

The main processing stages involved in a CBF-VRS exploiting multimedia content are shown in Fig. 6.1. The input information are videos (movies) and the preference indications of a single user on them, and the output is a rank list of recommended videos (movies) tailored to target user's preference on the content

• **Temporal segmentation**: The goal of temporal segmentation is to partition the video item—infact the audio and image signals—into smaller structural units that

**Fig. 6.1** The general framework illustrating the main processing steps involved in a CBF-VRS exploiting multimedia content. The framework focuses on the multimedia processing stages required to build a CBF system, however it can be extended to incorporate CF knowledge (e.g., in a hybrid CBF+CF system) and contextual factor (e.g., in context-aware CBF system)

have similar semantic content [29]. For the audio domain, segmentation approaches commonly operate at the *frame-level* or the *block-level*, the latter sometimes referred to as *segment-level* [25, 31]. For the visual domain, temporal segmentation segments the video into shots based on visual similarity between consecutive frames [15]. Some works consider scene-based segmentation, where a scene is semantically/hierarchically a higher-level video unit compared to a shot [15, 32]. Yet a simpler approach relies on capturing video at a fixed frame rate e.g., 1 fps and use all the resulting frames for processing [40].

• **Feature Extraction**: Feature extraction algorithms aim at encoding the content of the multimedia items in a concise and descriptive way, so to represent them for further use in retrieval, recommendation or similar systems [38]. An accurate feature representation can reflect item characteristics from various perspectives and can be highly indicative of user preferences.

In the context of this Ph.D., a wide set of audio and visual features has been used to solve different movie recommendation tasks. As for the visual domain, they include *mise-en-scène visual features* (average short length, color variation, motion and lighting key) [12, 15], visual features based on the *MPEG-7 standard* and *pre-trained CNNs* [17] and the most stable and recent datasets, named Multifaceted Movie Trailer Feature dataset (MMTF-14K) and Multifaceted Video Clip Dataset (MVCD-7K) [11, 21], which we made publicly available online. In particular, MMTF-14K3 provides state-of-the-art audio and visual descriptors for approximately 14K Hollywood-type *movie trailers* accompanied with metadata and user preference indicators on movies that are linked to the ML-20M dataset. The visual descriptors consist of two categories of descriptors: *aesthetic features*

3https://mmprj.github.io/mtrm\_dataset/index.

and *pre-trained CNN* (AlexNet) features, each of them including different aggregation schemes for the two types of visual features. The audio descriptors consist of two classes of descriptors: *block-level features* (BLF) and *i-vector features* capturing spectral and timbral features of audio signal. To the best of our knowledge, MMTF-14K is the only large scale **multi-modal** dataset to date providing a rich source for devising and evaluating movie recommender systems.

A criticism of the MMTF-14K dataset however is that its underlying assumption relies on the fact that *movie trailers are representative of full movies*. Movie trailers are human-edited and artificially produced with lots of thrills and chills as their main goal is to motivate users to come back (to the cinema) and watch the movie. For this reason, the scenes in trailers are usually taken from the most exciting, funny, or otherwise noteworthy parts of the film,4 which is a strong argument against the representativeness of trailers for the full movie. To address these shortcomings, in 2019 we introduced a new dataset of video clips, named Multifaceted Video Clip Dataset (MFVCD-7K).5 Each movie in MFVCD-7K can have several associated video clips, each focused on a particular scene, displaying it at its natural pace. Thus, video clips in MFVCD-7K can serve as a more *realistic* summary of the movie story than trailers.

4https://filmshortage.com/the-art-of-the-trailer/.

5https://mmprj.github.io/MFVCD-7K.

**Fig. 6.2** The proposed collaborative-filtering-enriched content-based filtering (CFeCBF) movie recommender system framework proposed in [13] to solve the new/cold-item problem

sets into a unified ranking of videos and showed promising improvements of the final ranking. Note that a different level of hybridization—from a recommendation point of view—can involve fusing CBF system with a CF model, which we considered e.g., in [14, 17].

• **Content-based learning of user profile and Recommendation**: The goal of this step is to learn a user-specific model which is used to predict the target user's interest in (multimedia) items based on her past history of interaction with the items [2]. The learned user profile model is compared to representative item features (or item profiles) in order to make recommendations tailored to target user's preference on the content.

For instance, in [10] a *multi-modal content-based movie recommender system* is presented that exploits rich content descriptors based on state-of-the-art multimedia descriptors: *block-level and i-vector features for audio* and *aesthetic and deep visual features*. For multi-modal learning, a novel late fusion strategy based on an extended version of the Borda rank aggregation strategy was proposed which resulted in an improved ranking of videos. Evaluation was carried out on a subset of MovieLens-20M and multimedia features extracted from 4,000 movie trailers, by (i) a *system-centric study* to measure the offline quality of recommendations in terms of accuracy-related (MRR, MAP, recall) and beyond-accuracy (novelty, diversity, coverage) performance, and (ii) a *user-centric online experiment*, measuring different subjective metrics (relevance, satisfaction, diversity). Results of empirical evalua-

tion indicates that multimedia features can provide a good alternative to metadata (as baseline), with regards to both accuracy measures and beyond accuracy measures.

In [13] a novel *movie multi-modal recommender system* is proposed that specifically addresses the *new item cold-start problem* by: (i) integrating state-of-the-art audio and visual descriptors, which can be automatically extracted from video content and constitute what we call the *movie genome*; (ii) exploiting an effective data fusion method named *canonical correlation analysis*(CCA) to better exploit complementary information between different modalities; (iii) proposing a two-step hybrid approach which trains a CF model on warm items (items with interactions) and leverages the learned model on the movie genome to recommend cold items (items without interactions). The recommendation method is thus named collaborative-filtering enriched CBF (CFeCBF), which has a different functioning concept compared with a standard CBF system (compare Figs. 6.1 and 6.2). Experimental validation is carried out using a system-centric study on a large-scale, real-world movie recommendation dataset both in an absolute cold start and in a cold to warm transition; and a usercentric online experiment measuring different subjective aspects, such as satisfaction and diversity. Results from both the offline study as well as a preliminary user-study confirm the usefulness of their model for new item cold start situations over current editorial metadata (e.g., genre and cast).

Finally, in Table 6.2, we provide a brief comparison of a selected number of research works completed in the course of this Ph.D. thesis by highlighting their main aspects. Readers are referred to the comprehensive literature review on recommender system leveraging multimedia content in which I describe many domains where multimedia content plays a key role in human decision making and are considered in the recommendation process [23].

#### **6.4 Conclusion**

This extended abstract briefly discusses the main outcomes of my Ph.D. thesis [9]. This Ph.D. thesis studies video recommender systems using multimedia content in detail—a particular area in the design space of recommender system algorithms where the generic recommender algorithm can be configured in order to integrate a rich source of information extracted from the actual audio-visual signals of video. I believe different systems, techniques and tasks for movie recommendation, which were studied in this Ph.D. thesis can pave the path for a new paradigm of video (and in general multimedia) recommender system by designing recommendation models built on top of rich item descriptors extracted from content.

#### **References**

**Open Access** This chapter is licensed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license and indicate if changes were made.

The images or other third party material in this chapter are included in the chapter's Creative Commons license, unless indicated otherwise in a credit line to the material. If material is not included in the chapter's Creative Commons license and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder.

## **Chapter 7 Dynamic Application Autotuning for Self-aware Approximate Computing**

**Davide Gadioli**

**Abstract** The energy consumption limits the application performance in a wide range of scenarios, ranging from embedded to High-Performance Computing. To improve computation efficiency, this Chapter focuses on a software-level methodology to enhance a target application with an adaptive layer that provides selfoptimization capabilities. We evaluated the benefits of dynamic autotuning in three case studies: a probabilistic time-dependent routing application from a navigation system, a molecular docking application to perform virtual-screening, and a stereomatching application to compute the depth of a three-dimensional scene. Experimental results show how it is possible to improve computation efficiency by adapting reactively and proactively.

#### **7.1 Introduction**

The increasing demand for computation power shifted the optimization focus towards efficiency in a wide range of energy-constrained systems, from embedded platforms to High-Performance Computing (HPC) [1]. A promising way to improve energy efficiency is approximate computing [2], which aims at finding a *good enough* solution, avoiding the unnecessary computation effort. It is possible to approximate the computation at different levels: from approximate hardware [3] to software techniques such as loop perforation [4]. Moreover, a large class of applications exposes software parameters that define an accuracy-throughput trade-off, especially in the multimedia field [5]. In this chapter, we focus at the software-level, where an application exposes*software-knobs*[6] that can alter its extra-functional behaviour. In this context, the definition of application performance includes several extra-functional properties (EFPs) in conflict to each other.

The value of an EFP might depend on the underlying architecture configuration, the system workload, and the features of the current input. Since this information usually changes at runtime, it is not trivial to find a one-fits-all configuration of

D. Gadioli (B)

Politecnico di Milano, Piazza Leonardo da Vinci, 32, Milan, Italy e-mail<EMAIL_ADDRESS>
© The Author(s) 2020

B. Pernici (ed.), *Special Topics in Information Technology*, PoliMI SpringerBriefs, https://doi.org/10.1007/978-3-030-32094-2\_7

the application software-knobs at design-time. This is a well-known problem in the autonomic computing field [7], where researchers investigate approaches to provide self-optimization capabilities to a target application, for identifying and seizing optimization opportunities at runtime.

In this context, we propose a methodology to enhance an application with an adaptation layer that exposes reactive and proactive mechanisms to provide continuously the most suitable software-knobs configuration according to application requirements. The decision process is based on the application knowledge, which describes the relationship between software-knob configurations and EFPs. It is possible to learn the application knowledge either at design-time, by using well-known Design Space Exploration techniques [8], or at runtime by using an external component that coordinates a distributed DSE [9]. The benefits of the latter approach are the following: (1) the application can observe its behaviour with the same execution environment of the production run, (2) it can leverage features of the production input, and in the context of a distributed computation, (3) it can leverage the number of application instances to lower the learning time.

We evaluate the benefits of the methodology implementation, named *mARGOt*, in three real-world case studies. In particular, we use a stereo-matching application [5] to assess the benefits of reactive adaptation mechanisms, with respect to changes of both application requirements and performance. We use a probabilistic time-dependent routing stage in a navigation car system [10] to evaluate the benefits of the proactive adaptation mechanisms. Finally, we use a molecular docking application for virtual screening, to assess the benefits of learning the application knowledge at runtime.

The remainder of the Chapter is organized as follows. First, Sect. 7.2 provides an overview of autonomic computing, focusing on application autotuning and highlighting the main contributions of the proposed methodology. Then, in Sect. 7.3, we formalize the problem and describe the *mARGOt* framework. Section 7.4 discusses the benefits of the proposed methodology. Finally, Sect. 7.5 concludes the chapter.

#### **7.2 Autonomic Computing and Application Autotuning**

In the context of autonomic computing [7], we perceive a computing system as an ensemble of autonomous elements capable of self-management. The main idea is to enable the system to perform autonomously a task which is traditionally assigned to a human, to cope with the increasing complexity of computation platforms and applications. For example, if the system is able to incorporate new components whenever they become available, the system has the self-configuration ability. To qualify for the self-management ability, a system must satisfy all the related self-\* properties. How to provide these properties is still an open question and previous surveys [11, 12] summarize the research effort in this area.

In this chapter, we focus on the self-optimization property at the software-level, which is the ability to identify and seize optimization opportunities at runtime. The methodologies to provide self-optimization properties are also known in the literature as *autotuners*. It is possible to categorize autotuners in two main categories: static and dynamic.

Static autotuners aim at exploring a large space of software-knobs configuration space to find the most suitable software-knob configuration, assuming a predictable execution environment and targeting software-knobs that are loosely inputdependent. Among static autotuners, we might consider the following works. Auto-Tune [13] targets multi-node applications and it leverages the Periscope framework [14] to measure the execution time. It targets application-agnostic parameters exposed by the computation pipeline such as communication buffers and OpenHMPP/MPI parameters. QuickStep [15] and Paraprox [16] perform code transformations to automatically apply approximation techniques for enabling and leveraging an accuracy-throughput trade-off. OpenTuner [17] and the ATF framework [18] explicitly address the exponential growth in the complexity of exploring the parameters space, by using an ensemble of DSE techniques and by taking into account dependencies between software-knobs. Although very interesting, these approaches work at design-time and they usually target a different set of software-knobs with respect to dynamic autotuners.

The methodology proposed in this chapter belongs to the category of dynamic autotuners, which aim at changing the software-knobs configuration during the application runtime according to the system evolution. Therefore, they focus on providing adaptation mechanisms, typically based on application knowledge. Among dynamic autotuners, we might consider the following works. The Green framework [19] and PowerDial [6] enhance an application with a reactive adaptation layer, to change the software-knob configurations according to a change on the observed behaviour. The IRA framework [20] and Capri [21] focus instead on providing proactive adaptation mechanisms to select the software-knob configuration according to the features of the current input. On the other hand, Petabricks [22] and Anytime Automaton [23] are capable to adapt the application reactively and proactively. However, they require a significant integration effort from the application developers. Moreover, they are capable to leverage only accuracy-throughput trade-off. All these previous works are interesting and they have significantly contributed to the field, according to their approach on how to provide the self-optimization capabilities. The main contributions of *mARGOt* is to provide a single methodology to provide an adaptation layer with the following characteristics:

configuration file and the methodology is capable to generate an easy-to-use interface to wrap the target region of code.

Furthermore, being possible to define the application knowledge at runtime, *mARGOt* can use an external component to orchestrate a distributed DSE at runtime, during the production phase.

#### **7.3 The mARGOt Autotuning Framework**

This section describes how the proposed methodology can enhance the target application with an adaptation layer. At first, we formalize the problem, the application requirements and how the *mARGOt* interacts with the application. Then, we describe the main components of the framework and how they can adapt the application reactively and proactively.

#### *7.3.1 Problem Definition*

Figure 7.1 shows the overview of the *mARGOt* and how it interacts with an application. To simplify, we assume that the application is composed of a single computation kernel *g* that reads a stream of input *i* to produce the required stream of output *o*. However, *mARGOt* is capable to manage several regions of code independently. Moreover, the target kernel exposes a set software-knobs *x* that alter the extra-functional behaviour. Since a change of the configuration of these knobs might lead to a different quality of the results, we might define the application as *o* = *g*(*i*, *x*).

Given this definition, the application requirements are expressed as a constrained multi-objective optimization problem described in Eq. 7.1:

$$\begin{array}{rcl} \max(\min) & r(\overline{x}; \overline{m} \mid \overline{f}) \\ \text{s.t. } C\_1 : \omega\_1(\overline{x}; \overline{m} \mid \overline{f}) & \propto & k\_1 \text{ with } \alpha\_1 \text{ confidence} \\ & C\_2 : \omega\_2(\overline{x}; \overline{m} \mid \overline{f}) & \propto & k\_2 \\ & & \cdots & \\ & C\_n : \omega\_n(\overline{x}; \overline{m} \mid \overline{f}) & \propto & k\_n \end{array} \tag{7.1}$$

where *r* denotes the objective function to maximize (minimize), *m* is the vector of metrics of interest (i.e. the EFPs), and *f* is the vector of input features. Let *C* be the set of constraints, where each constraint *Ci* is expressed as the function ω*i* over *m* or *x*, that must satisfy the relationship ∝∈ {<, ≤, >, ≥}, with a confidence α*i* , if ω*i* targets a statistical variable. If the application is input-dependent, ω*i* and *r* depend on its features.

In this context, the goal of the autotuner is to solve the optimization problem by inspection, using the application knowledge. The application always needs a

**Fig. 7.1** The overview of the proposed autotuning framework. Green elements represent framework components, while blue elements represent application components (Color figure online)

software-knob configuration, therefore if the problem is unfeasible, *mARGOt* can relax the constraints, according to their priority, until it finds a valid solution.

We implemented *mARGOt* as a standard C++ library that should be linked to the target application. Being the time spent by the framework to select the most suitable software-knob configuration stolen from the application, the *mARGOt* implementation has been designed to be lightweight and to minimize the introduced overhead. We publicly released the framework source code [24].

#### *7.3.2 Application-Knowledge*

To solve the optimization problem we need a model of the application behaviour. However, the relationship between software-knobs, EFPs, and input features is complex and unknown. Therefore, *mARGOt* defines the application-knowledge as a list of *Operating Points* (OPs). Each OP θ corresponds to a software-knob configuration, together with the reached EFPs. If the application is input-dependent, the OP includes also the information on the related input features: θ = {*x*, *m*, *f* }.

This representation has been chosen for the following reasons: it provides a high degree of flexibility to describe the application behaviour, *mARGOt* can solve efficiently the optimization problem described in Eq. 7.1 and it prevents the possibility to select an invalid software-knob configuration.

The application-knowledge is considered an input of *mARGOt*, and there are several tools that can explore the Design Space efficiently. In particular,*mARGOt* uses the XML format of Multicube Explorer [25] to represent the application-knowledge. Moreover, it is possible to learn it at runtime, as described in Sect. 7.3.4.

#### *7.3.3 Interaction with the Application*

The core component of *mARGOt* is the application manager, which is in charge of solving the optimization problem and of providing to the application the most suitable software-knob configuration. The application is able to change the application requirements at runtime according to the system evolution. Moreover, if the EFPs are input-dependent, the application can provide features of the actual input to adapt proactively [9].

To enable the reactive adaptation, *mARGOt* must observe the actual behaviour of the application and compare it with the expected one. In particular, we compute a coefficient error for each observed EFP as *emi* = *expectedi observedi* , where *emi* is the error coefficient for the *i*-th EFP. Under the assumption of linear error propagation among the OPs, *mARGOt* is able to adapt reactively.

The methodology implementation provides to application developers a suite of monitors to observe the most common metrics of interest, such as throughput or performance events using PAPI [26]. The customization of a monitor to observe an application-specific EFP, such as the accuracy, is straightforward.

#### *7.3.4 Runtime Application-Knowledge Learner*

The *mARGOt* flexibility enables the possibility to change the application knowledge at runtime. Therefore, it is possible to learn the application knowledge directly at runtime, during the production phase. Although this approach is platform independent, it focuses on the High-Performance Computing Scenario. The idea is to perform a distributed Design Space Exploration, leveraging the parallelism level of the platform to lower the exploration time. In particular, when we spawn an application, it notifies its existence to a central coordinator, along with information about the exploration, such as the software-knobs domains, and the list of EFPs. According to a Design of Experiments, the central coordinator dispatches software-knobs configuration to evaluate at each application instance, which provides as feed-back telemetry information. Once the central coordinator collects the required observations, it uses learning techniques to derive the application-knowledge to broadcast to the application instances.

Figure 7.2 shows an overview of the central coordinator. In particular, it uses a thread pool of *application remote-handlers*to interact with *application local-handler* of the application instances. The communication uses the lightweight MQTT or

MQTTs protocols, while we use the Cassandra database to store the required information. The learning module leverages a well-known approach [27] to interpolate application performance, implemented by the state-of-the-art R package [28].

#### **7.4 Experimental Results**

This section assesses the benefits of the proposed adaptation layer, by deploying the *mARGOt* framework in three different case studies. Each case study highlights a different characteristic of *mARGOt*.

#### *7.4.1 Evaluation of the Reactive Adaptation*

This experiment aims at assessing the benefits of the reactive adaptation mechanisms. We focus on a Stereo-matching application deployed in a quad-core architecture [29]. The application takes as input a pair of stereo images of the same scene and it computes the disparity map as output. The algorithm exposes application-specific software-knobs that define an accuracy-throughput trade-off. Moreover, it is possible to change the number of software threads that the application can use to carry out the computation.

We create the application-knowledge at design-time, evaluating each configuration in isolation. In this experiment, we execute four instances of stereo-matching, overlapping their execution: each application has an execution time of 200 s, and we spawn them with a delay of 50 s between each other. The application designer would like to maximize the accuracy of the elaboration, provided that the application must sustain a throughput of 2 fps.

In this experimental setup, we compare two adaptation strategies. On one hand, we consider as *baseline* the reaction policy that monitors the throughput of the

**Fig. 7.3** Distribution of deadline misses with respect to the constraint on the throughput, according to the distance from the target value (2 fps)

application and that reacts accordingly, since it is commonly used in literature. In particular, if the monitors observe that the actual throughput of the application is lower than the expected one, *mARGOt* will choose a configuration with an higher expected throughput to compensate. On the other hand, we exploit the *mARGOt* flexibility to consider also the CPU usage in the requirements. In particular, we define a constraint on the available resource usage on top of the one on the throughput, to limit the number of software threads according to the available resources. The value of the constraint is continuously updated at runtime as follows:

$$CPU\_{available} = \Gamma - \gamma + \pi\_{measured}$$

where is the maximum CPU quota available in the platform, γ is the monitored CPU quota used by the system, and π*measured* is the monitored CPU quota assigned to the application by the Operating System. The *mARGOt* capability to consider an arbitrary number of EFPs enables this adaptation strategy.

From the experimental results, we can observe how the two strategies are capable to satisfy the application requirements on average. However, Fig. 7.3 shows the distribution of the deadline misses for the two strategies. The baseline strategy relies on the scheduler for a fair assignment of the CPU quota, therefore the contention on the resources reduces the predictability of the throughput. Conversely, the *mARGOt* approach avoids this contention by observing the CPU usage. However, we are not able to guarantee a fair allocation of the CPU quota by using this approach.

#### *7.4.2 Evaluation of the Proactive Adaptation*

This experiment aims at assessing the benefits of the proactive adaptation mechanisms. We focus on a phase of a car navigation system: the probabilistic timedependent routing (PTDR) application [10]. It takes as input the starting time of the travel and the speed profiles of all the segments that compose the target path. The

**Table 7.1** Number of independent route traversal simulations by varying the requested maximum error and the statistical properties of interest

speed profiles of a segment vary during the week, with a fifteen minutes granularity. To estimate the arrival time distribution, the PTDR application uses a Monte Carlo approach that simulates multiple times an independent route traversal. The output of the application is a statistical property of the arrival time distribution such as the 50th or 75th percentile. This application has been already optimized to leverage the target HPC node [30], therefore it exposes as software-knob the number of route traversal simulations.

The application designer would like to minimize the number of route traversal simulations, given that the difference between the value computed with the selected configuration and with 1M samples are below a given threshold. The threshold value might vary according to the type of user that generates the request. In this experiment, we consider 3% for premium users and 6% for free users.

To evaluate the benefits of the proactive adaptation, we compare two adaptation strategies. On one hand, we fix the number of samples according to the worst path in a representative input set [30]. We use this strategy as a baseline. On the other hand, we use an adaptive strategy that extracts a feature from the actual input to select the number of simulations according to the target path [10].

Table 7.1 shows the experimental results of a large experimental campaign with randomly selected pairs of Czech Republic routes and starting times. The adaptive approach can significantly reduce the number of required simulations according to the target statistical property and the maximum error level. Moreover, we modelled the car navigation system with the simulation environment Java Modeling Tools to measure the benefits of the adaptive strategy at the system level. With a load of 100 k requests every 2 min, an error threshold of 6%, and assuming that we are interested in the 95th percentile, the adaptive strategy can reduce the number of nodes by 26%. These parameters estimate the requested generated by a Smart City with the size of the Milan urban area.

#### *7.4.3 Evaluation of the Runtime Learner*

This experiment aims at evaluating the benefits of learning the application knowledge at runtime. In the context of the early stages of the drug discovery process, we focus

on a molecular docking application for virtual screening [31]. It takes as input two information. On one hand, the docking site of the target molecule, named *pocket*. On the other hand, a huge library of possible solutions, named *ligands*. The output of the application is a small set of ligands which may have a strong interaction with the target pocket, to forward to the later stages of the process. The application exposes application-specific software-knobs that expose an accuracy-throughput trade-off.

Due to the complexity of estimating a ligand-pocket interaction, and due to the embarrassingly parallel nature of the problem, this application is a perfect match for HPC computation. In this scenario, the application designer would like to maximize the quality of the elaboration, given an upper bound on the time-to-solution. The relationship between the throughput and the software-knobs configuration depends on the characteristic of the actual input, especially of the pocket. Therefore, in this experiment we use *mARGOt* to learn at runtime such relationship, to be exploited in the remainder of the production run.

Figure 7.4 shows the distributions of the prediction error on the time-to-solution with six pocket from the RCSB Protein Databank (PDB) [32]. We use a chemical library with heterogeneous ligands [9]. For example, the number of their atoms range from 28 to 153. Since the prediction error is limited (<10%), *mARGOt* is able to improve the computation efficiency.

#### **7.5 Conclusion**

This chapter focuses on a methodology to enhance the target application with an adaptation layer, based on the application-knowledge, that provides the most suitable software-knobs configuration according to the application requirements.

We assessed the benefits of *mARGOt* in three case studies that belong to different application domains. Experimental results show how it is possible to improve drastically the computation efficiency by adapting reactively and proactively. Moreover, it is possible to learn the relationship between EFPs, software-knobs, and input features using the input of the production run, identifying and seizing optimization opportunities.

7 Dynamic Application Autotuning for Self-aware … 101

#### **References**

**Open Access** This chapter is licensed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license and indicate if changes were made.

The images or other third party material in this chapter are included in the chapter's Creative Commons license, unless indicated otherwise in a credit line to the material. If material is not included in the chapter's Creative Commons license and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder.

## **Chapter 8 CAOS: CAD as an Adaptive Open-Platform Service for High Performance Reconfigurable Systems**

**Marco Rabozzi**

**Abstract** The increasing demand for computing power in fields such as genomics, image processing and machine learning is pushing towards hardware specialization and heterogeneous systems in order to keep up with the required performance level at sustainable power consumption. Among the available solutions, Field Programmable Gate Arrays (FPGAs), thanks to their advancements, currently represent a very promising candidate, offering a compelling trade-off between efficiency and flexibility. Despite the potential benefits of reconfigurable hardware, one of the main limiting factor to the widespread adoption of FPGAs is complexity in programmability, as well as the effort required to port software solutions to efficient hardware-software implementations. In this chapter, we present CAD as an Adaptive Open-platform Service (CAOS), a platform to guide the application developer in the implementation of efficient hardware-software solutions for high performance reconfigurable systems. The platform assists the designer from the high-level analysis of the code, towards the optimization and implementation of the functionalities to be accelerated on the reconfigurable nodes. Finally, CAOS is designed to facilitate the integration of external contributions and to foster research on Computer Aided Design (CAD) tools for accelerating software applications on FPGA-based systems.

#### **8.1 Introduction**

Over the last 40 years, software performance has benefited from the exponential improvement of General Purpose Processors (GPPs) that resulted from a combination of architectural and technological enhancements. Despite such achievements, the performance measured on standard benchmarks in the last 3 years only improved

© The Author(s) 2020

M. Rabozzi (B)

Dipartimento di elettronica, informazione e bioingegneria, Politecnico di Milano, Piazza Leonardo da Vinci 32, 20133 Milano, Italy e-mail<EMAIL_ADDRESS>
B. Pernici (ed.), *Special Topics in Information Technology*, PoliMI SpringerBriefs, https://doi.org/10.1007/978-3-030-32094-2\_8

at a rate of about 3% per year [11]. Indeed, after the failure of Dennard scaling [21], the current diminishing performance improvements of GPP reside in the difficulty to efficiently extract more fine-grained and coarse-grained parallelism from software. Considering the shortcomings of GPP, in current years we are assisting at a new era of computer architectures in which the need for energy-efficiency is pushing towards hardware specialization and the adoption of heterogeneous systems. This trend is also reflected in the High Performance Computing (HPC) domain that, in order to sustain the ever-increasing demand for performance and energy efficiency, started to embrace heterogeneity and to consider hardware accelerators such as Graphics Processing Units (GPUs), FPGAs and dedicated Application-Specific Integrated Circuits (ASICs) along with standard CPU. Albeit ASICs show the best performance and energy efficiency figure, they are not cost-effective solutions due to the diverse and ever-evolving HPC workloads and the high complexity of their development and deployment, especially for HPC. Among the available solutions, FPGAs, thanks to their advancements, currently represent the most promising candidate, offering a compelling trade-off between efficiency and flexibility. Indeed, FPGAs are becoming a valid HPC alternative to GPUs, as they provide very high computational performance with superior energy efficiency by employing customized datapaths and thanks to hardware specialization. FPGA devices have also attained renewed interests in recent years as hardware accelerators within the cloud domain. The possibility to access FPGAs as on-demand resources is a key step towards the democratization of the technology and to expose them to a wide range of potential domains [2, 6, 24].

Despite the benefits of embracing reconfigurable hardware in both the HPC and cloud contexts, we notice that one of the main limiting factor to the widespread adoption of FPGAs is complexity in programmability as well as the effort required to port a pure software solution to an efficient hardware-software implementation targeting reconfigurable heterogeneous systems [1]. During the past decade, we have seen significant progress in High-Level Synthesis (HLS) tools which partially mitigate this issue by allowing to translate functions written in a high-level language such as C/C++ to a hardware description language suitable for hardware synthesis. Nevertheless, current tools still require experienced users in order to achieve efficient implementations. In most cases indeed, the proposed workflows require the user to learn the usage of specific optimization directives [22], code rewriting techniques and, in other cases, to master domain specific languages [10, 13]. In addition to this, most of the available solutions [9, 10, 13] focus on the acceleration of specific kernel functions and leave to the user the responsibility to explore hardware/software partitioning as well as to identify the most time-consuming functions which might benefit the most from hardware acceleration. To tackle these challenges, we propose the CAOS platform bringing the following contributions:

Section 8.2 describes the overall CAOS platform, its design flow and infrastructure, while Sect. 8.3 presents an overview of the supported architectural. Section 8.4 discuss the experimental results on case studies targeting different architectural templates. Finally, Sect. 8.5 draws the conclusions.

#### **8.2 The CAOS Platform**

The CAOS platform has been developed in the context of the Exploiting eXascale Technology with Reconfigurable Architectures (EXTRA) project and shares with it the same vision [19]. CAOS targets both application developers and researches while its design has been conceived focusing on three key principles: usability, interactivity and modularity. From a usability perspective, the platform supports application designers with low expertise on reconfigurable heterogeneous systems in quickly optimizing their code, analyzing the potential performance gain and deploying the resulting application on the target reconfigurable architecture. Nevertheless, the platform does not aim to perform the analysis and optimizations fully automatically, but instead interactively guides the users towards the design flow, providing suggestion and error reports at each stage of the process. Finally, CAOS is composed of a set of independent modules accessed by the CAOS flow manager that orchestrates the execution of the modules according to the current stage of the design flow. Each module is required to implement a set of well-defined APIs so that external researchers can easily integrate their implementations and compare them against the ones already offered by CAOS.

#### *8.2.1 CAOS Design Flow*

The platform expects the application designer to provide the application code written in a high-level language such as C/C++, one or multiple datasets to be used for code profiling and a description of the target reconfigurable system. In order to narrow down and simplify the set of possible optimizations and analysis that can be performed on a specific algorithm, CAOS allows the user to accelerate its application using one of the available architectural templates. An *architectural template* is a characterization of the accelerator both in terms of its computational model and the communication with the off-chip memory. As a consequence, an architectural template constrains the architecture to be implemented on the reconfigurable hardware and poses restrictions on the application code that can be accelerated, so that the

**Fig. 8.1** High-level overview of the CAOS platform. The overall design flow can be divided in three main parts: the *frontend*, the *functions optimization* and the *backend* flow. The application code, datasets to profile the application and an HW description constitute the input data provided by the designer. The final outputs generated by the platform are the bitstreams, that the user can use to configure the FPGAs, and the application runtime, needed to run the optimized version of the application

number and types of optimizations available can be tailored for a specific type of implementation. Furthermore, CAOS is meant to be orthogonal and build on top of tools that perform High-Level Synthesis (HLS), place and route and bitstream generation. Code transformations and optimizations are performed at the source code level while each architectural template has its own requirements in terms of High-Level Synthesis (HLS) and hardware synthesis tools to use.

As shown in Fig. 8.1, the overall CAOS design flow is subdivided into three main flows: the frontend flow, the function optimization flow and the backend flow. The main goal of the frontend is to analyze the application provided by the user, match the application against one or more architectural templates available within the platform, profile the user application against the user specified datasets and, finally, guide

**Fig. 8.2** CAOS infrastructure in terms of its main components and their interaction

the user through the hardware/software partitioning of the application to define the functions of the application that should be implemented on the reconfigurable hardware. The function optimization flow performs static analysis and hardware resource estimation of the functionalities to be accelerated on the FPGA. Such analyses are dependent upon the considered architectural template and the derived information are used to estimate the performance of the hardware functions and to derive the optimizations to apply (such as loop pipelining, loop tiling and loop unrolling). After one or more iterations of the function optimization flow, the resulting functions are given to the backend flow in which the desired architectural template for implementing the system is selected and the required High-Level Synthesis (HLS) and hardware synthesis tools are leveraged to generate the final FPGA bitstreams. Within the backend, CAOS takes care of generating the host code for running the FPGA accelerators and optionally guides the place and route tools by floorplanning the system components.

#### *8.2.2 CAOS Infrastructure*

In order to simplify the adoption of the platform while being open to contributions, the CAOS infrastructure is organized as a microservices architecture which can be accessed by application designers through a web user interface. The infrastructure, shown in Fig. 8.2, leverages on Docker [8] application containers to isolate the modules and to provide scalability. Each module is deployed in a single container, and several implementations of the same module can coexist to provide different functionalities to different users. Moreover, each module's implementation can be replicated to scale horizontally depending on system load. The modules are connected together and driven by the *CAOS Flow manager* which serves the User Interface (UI) and provides the glue logic that routes each request to the proper module.

The interaction between the flow manager and the CAOS modules is performed by means of data transfer objects defined with a JSON Domain Specific Language (DSL). The user can specify at each phase the desired module implementation and the platform will take care of routing the request to the proper module automatically. Moreover, the platform supports modules deployed remotely by simply specifying their IP address. Another advantage of the proposed infrastructure is that, thanks to Docker containers, it can also be easily deployed on cloud instances, possibly featuring FPGA boards, such as the Amazon EC2 F1 instances. This allows a complete design process in the cloud in which the user can optimize the application through a web UI, while the final result of the CAOS design flow can be directly tested and run on the same cloud instance. CAOS supports the integration of new implementations of the modules described in Sect. 8.2.1. Researchers are free to adopt the preferred tools and programming languages that fit their needs, as long as the module provides the implementation of the REST APIs prescribed by the CAOS flow manager.

#### **8.3 Architectural Templates**

The core idea for devising efficient FPGA-based implementations in CAOS revolves around matching software functions to an architectural template suitable for its acceleration. CAOS currently supports three architectural templates: Master/Slave, Dataflow and Streaming architectural templates. In the next sections, we provide an overview of the templates, describing the supported software functions and hardware platforms, the proposed optimizations and the tools on which the templates rely.

#### *8.3.1 Master/Slave Architectural Template*

The Master/Slave architectural template [7] targets systems with a shared Double Data Rate (DDR) memory that can be accessed both by the host running the software portion of the application and by the FPGA devices on which we implement the accelerated functionalities (also referred as kernel). The template also requires that the communication between the accelerator and the DDR memory is performed via memory mapped interfaces. Such requirements allow to standardize the data transfer as well as to support random memory accesses to pointer arguments of the target C/C++ function. Currently, the template supports two target systems: Amazon F1 instances in the cloud and Xilinx Zynq System-on-Chips (SoCs).

The generality of the communication model of the Master/Slave architectural template allows supporting a wide range of C/C++ functions. In particular, the function has to abide to quite general constraints for High-Level Synthesis (HLS) such as no dynamic creation of objects/arrays, no syscalls and no recursive function calls. The Master/Slave architectural template currently leverages on Vivado HLS [23] for the High-Level Synthesis (HLS) of C/C++ code to Hardware Description Language (HDL). Hence, in the CAOS frontend, we verify the applicability of the template to a given function by running Vivado HLS on it and verify that no errors are generated. In addition to the Vivado HLS constraints, we also require the size of the function arguments to be known. This is needed by CAOS to properly estimate the kernel performance throughout the function optimizations flow. During the CAOS functions optimization flow, the template performs static code analysis by leveraging on custom Low-Level Virtual Machine (LLVM) [12] passes. In particular, it identifies loop nests with their trip counts, local arrays and information on the input and output function arguments. Furthermore, the template collects hardware and performance estimations of the current version of the target function directly from Vivado HLS. Such information is then used to identify the next candidate optimizations among loop pipelining, loop unrolling, on-chip caching and memory partitioning. The user can then either select the suggested optimization or conclude the optimization flow if he/she is satisfied with the estimated performance. After having optimized the kernel, the design proceeds to the CAOS backend flow. Here the optimized C/C++ function is translated to HDL and, according to the target system, the template leverages either on the Xilinx SDAccel toolchain [22] or Xilinx Vivado [23] for the implementation and bitstream generation. In both cases, CAOS takes care of modifying the original application and inserts the necessary code and APIs calls to offload the computation of the original software function to the generated FPGA accelerator.

#### *8.3.2 Dataflow Architectural Template*

The dataflow architectural template trades off the generality of codes supported by the Master/Slave architectural template in order to achieve higher performance. In a dataflow computing model, the data is streamed from the memory directly to the chip containing an array of Processing Elements (PEs) each of which is responsible for a single operation of the algorithm. The data flow from a PE to the next one in a statically defined directed graph, without the need for any kind of control mechanism. In such a model, each PE performs its operation as soon as the input data is available and forwards the result to the next element in the network as soon as it is computed.

The target system for the dataflow architectural template consists in a host CPU and the dataflow accelerator deployed on a FPGA connected via PCIe to the host. Both the host CPU and the FPGA logic have access to the host DDR memory containing the input/output data. The FPGA accelerator is organized internally as a Globally Asynchronous Locally Synchronous (GALS) architecture divided into the actual accelerated kernel function and a manager. The manager handles the asynchronous communication between the host and the accelerator, whereas the kernel is internally organized as a set of synchronous PEs that perform the computation in parallel.

The architectural template leverages on the OXiGen toolchain [18] and its extension [17] to translate C/C++ functions into optimized dataflow kernels defined with the MaxJ language. In order to efficiently perform the translation from sequential C/C++ code to a dataflow representation, the target function has to satisfy certain requirements detailed in [18]. An exemplary code supported by the template is shown in Listing 8.1. The code requirements are validated in the CAOS frontend flow in order to identify functions that can be optimized with the dataflow architectural template. Within the CAOS function optimization flow, OXiGen performs the dataflow graph construction directly from the LLVM Intermediate Representation (IR) of the target function. Nevertheless, the initial dataflow design might either exceed or underutilize the available FPGA resources. Hence, in order to identify an optimal implementation that fits within the FPGA resources and available data transfer bandwidth, OXiGen supports loop rerolling, to reduce resource consumption, and vectorization, to replicate the processing elements in order to fully utilize the available bandwidth and compute resources. In order to derive the best implementation, OXiGen relies on resource and performance models and runs a design space exploration using an approach based on Mixed-Integer Linear Programming (MILP). Once having generated an optimized kernel, the CAOS backend runs MaxCompiler [13] to synthesize the MaxJ code generated by OXiGen to a Maxeler DFE (Dataflow Engine) that can be accessed by the host system.

**Listing 8.1** An exemplary code supported by the dataflow template. The function takes as input a combination of array types and scalar types. The outer loops iterate over the outer dimension of the array types which are translated as streams. Accesses to the streams are linear with constant offsets.  The basic structure of ISLs is depicted in Algorithm 8.1; the outer loop iterates for a given number of times, so-called *time-steps*, while, at each time-step, the inner

**Fig. 8.3** Architecture of an SST-based accelerator for ISL

loop updates each value of the *n*-dimensional input vector by means of the *stencil* function, computing a weighted sum of the neighbor values in the vector.

The Streaming architectural template specifically targets stencil codes written in C and leverages the SST architecture proposed by [3] for its implementation. The architectural template of the SST-based accelerator [14] is depicted in Fig. 8.3. The basic SST module performs the computation of a single time-step and is conceptually separated in a *memory system*, responsible for storage and data movement, and a *computing system*, that performs the actual computation. The SST module is designed in order to operate in a streaming mode on the various elements of the input vector; this internal structure is derived by means of the *polyhedral analysis* that allows refactoring the algorithm to optimize on-chip memory resource consumption and implement a dataflow model of computation. Then, the complete SST-based architecture is obtained by replicating *N* times the basic module to implement a pipeline, where each module computes in streaming a single time-step of the outer loop of the algorithm. Such a pipeline is finally connected with a fixed communication subsystem interfacing with the host machine. Within this context, CAOS offers a design exploration algorithm [20] that jointly maximizes the number of SST processors that can be instantiated on the target FPGA and identifies a floorplan of the design that minimizes the inter-component wire-length in order to allow implementing the system at high frequency. In the frontend, CAOS identifies those functions having the ISL structure shown in Algorithm 8.1, while the CAOS function optimization flow runs the design space exploration algorithm detailed in [20] on the function to accelerate. The approach starts by generating an initial version of the system consisting of a single SST [14] to obtain an initial resource estimate. Subsequently, it solves a maximum independent set problem formulated as an Integer Linear Programming (ILP) to identify the maximum number of SST as well as their floorplan and solves a Traveling Salesman Problem (TSP) to identify the best routing among SSTs. Finally, the CAOS backend generates the accelerator bitstream through Xilinx Vivado while enforcing the identified floorplanning constraints.

#### **8.4 Experimental Results**

Within this section we discuss the results achieved by CAOS on different case studies targeting the discussed architectural templates. The first case study we consider is the N-Body simulation, which is a well known problem in physics having applications in a wide range of fields. In particular, we focused on the *all-pair* method: the algorithm alternates a computationally intensive force computation step, in which the pairwise forces between each pair of bodies are computed and a position update step, that updates the velocities and positions of the bodies according to the current resulting forces. CAOS, after profiling and analyzing the application in the frontend, properly identified the force computation as the target function to accelerate and matched it to the Master/Slave architectural template. As we can see from Table 8.1, the CAOS implementation targeting an Amazon F1 instance greatly outperforms, both in terms of performance and energy efficiency, the software implementation from [5] running in parallel on 40 threads on an Intel Xeon E5-2680 v2 and the implementation from [4] on a Xilinx VC707 board. Nevertheless, the bespoke implementation from [5] targeting the same hardware provides 11% higher performance than the CAOS one. However, the CAOS design was achieved semi-automatically in approximately a day of work, while the design from [5] required several weeks of manual effort.

As a second test case, we consider the Curran approximation algorithm [16] for calculating the pricing of Asian options. More specifically, we tested two flavors of the algorithm using 30 and 780 averaging points. Within CAOS, we started from a C implementation and we targeted a host machine featuring an Intel(R) Core(TM) i7-6700 CPU @ 3.40 GHz connected via PCIe gen1 x8 to a MAX4 Galava board equipped with an Altera Stratix V FPGA. Since the algorithms operate on subsequent independent data items, the overall computations are easily expressed in C using the structure in Listing 8.1. Hence CAOS identified and optimized the computations leveraging on the dataflow architectural template. As the initial designs did not fit within the device, CAOS applied the rerolling optimization for both cases. As shown in Table 8.2, both CAOS implementations achieve speedups over 100x against the single thread execution on the host system only. Moreover, we compared

**Table 8.1** Performance and energy efficiency of the all-pairs N-Body algorithm accelerated via CAOS and the results achieved by bespoke designs proposed in [4, 5]

**Table 8.2** Results achieved by CAOS on the Curran approximation algorithm with 30 and 780 averaging points compared against CPU and the bespoke FPGA-based implementations from [15]

**Table 8.3** Results achieved by the CAOS streaming architectural template compared to [14]

the results against the DFE execution times reported from the designs in [15]. For the version with 30 averaging points, we achieved a speedup of 1.23x. For the version with 780 averaging points, our implementation shows a speed down of about 0.5x. Nevertheless, it was obtained in less than a day of work.

As a final test case, we evaluated the streaming architectural template on three representative ISL computations (Jacobi2D, Heat3D and Seidel2D) targeting a Xilinx Virtex XC7VX485T device [20]. Table 8.3 reports the performance improvement and the design time reduction compared to the methodology in [14]. Thanks to FPGA floorplanning we are able to increase the target frequency for the Jacobi2D and Heat3D algorithms of approximately 11%. Additionally, for the Jacobi2D case, the floorplanner is also able to allocate two additional SSTs improving the performance up to 13%. Nevertheless, the Seidel2D algorithm does not provide the same improvement figure. Indeed, since the total number of SSTs that can be placed into the design is small, the floorplanning reduces its impact on the overall design by leaving more room to the place and route algorithm. Regarding the design time, our approach allows to greatly reduce the number of trial synthesis required, thus leading to an execution time saving of 15.84x for Jacobi2D.

#### **8.5 Conclusions**

In this chapter we presented CAOS, a platform whose main objective is to improve productivity and simplify the design of FPGA-based accelerated systems, starting from pure high-level software implementations. Currently, the slowing rate at which general purpose processors improve performance is strongly pushing towards specialized hardware. We expect FPGAs to have a more prominent role in the upcoming years as a technology to achieve efficient and high performance solutions both in the HPC and cloud domains. Hence, by embracing this idea, we designed CAOS in a modular fashion, providing well-defined APIs that allow external researchers to integrate extensions or different implementations of the modules within the platform. Indeed, the second, yet not less important, objective of CAOS, is to foster research on tools and methods for accelerating software on FPGA-based architectures.

#### **References**

**Open Access** This chapter is licensed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license and indicate if changes were made.

The images or other third party material in this chapter are included in the chapter's Creative Commons license, unless indicated otherwise in a credit line to the material. If material is not included in the chapter's Creative Commons license and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder.

## **Part IV Systems and Control**

## **Chapter 9 A General Framework for Shared Control in Robot Teleoperation with Force and Visual Feedback**

#### **Davide Nicolis**

**Abstract** In the last decade, the topic of human robot interaction has received increasing interest from research and industry, as robots must now interface with human users to accomplish complex tasks. In this scenario, robotics engineers are required to take the human component into account in the robot design and control. This is especially true in telerobotics, where interaction with the user plays an important role in the controlled system stability. By means of a thorough analysis and practical experiments, this contribution aims at giving a concrete idea of the aspects that need to be considered in the design of a complete control framework for teleoperated systems, that are able to seamlessly integrate with a human operator through shared control.

#### **9.1 Introduction**

Although many branches of robotics are currently striving for complete autonomy, such as self-driving cars and drones, a parallel research line is instead trying to tie together robots and humans in a integrated way. Indeed, on the one hand, robots are often called to work together with humans as they are inherently designed to interact with their environment, on the other hand, the purpose of robots is that of being useful to its users. Therefore "closing the loop" around this human component is paramount for an optimal system design.

In certain applications demanding high-level reasoning, human presence is not only advised, but it is also mandatory. Nonetheless, the harshness and inaccessibility of the environments where they are called to operate makes the use of remotely controlled robotic systems, essential to complete the required tasks. With its first modern applications in the '50s in the field of nuclear material handling, robot teleoperation is nowadays commonly associated by the general public with surgical robots [19].

D. Nicolis (B)

© The Author(s) 2020

Politecnico di Milano, Piazza Leonardo da Vinci, 32, 20133 Milano, Italy e-mail<EMAIL_ADDRESS>
B. Pernici (ed.), *Special Topics in Information Technology*, PoliMI SpringerBriefs, https://doi.org/10.1007/978-3-030-32094-2\_9

Even so, its use has spread to multiple domains, and it has sought the interest not only of the research community, but also industries. In the frame of the H2020 *RoMaNS* project, innovative teleoperation interfaces and visual servoing are proposed for the sorting of radioactive material [2], while the *WALK-MAN* project has aimed at building a humanoid teleoperated platform for inspection in dangerous unstructured environments damaged by natural events [11].

Massive attention is being given to telerobotics by industries producing pharmaceuticals, to handle toxic substances and customize drug production [18]. Clean room applications of teleoperated robots are now being investigated by ESA and NASA, in the scope of the Mars Sample Return exploration campaign, which aims at bringing back Mars samples for the analysis of life traces. Whereas classical glovebox systems are inadequate for planetary protection protocols, a remotely controlled robot can solve this problem by ensuring a high degree of isolation between the robotized cell and the external environment [21]. Nevertheless, space telerobotics is already a reality for in-orbit servicing, and at an advanced research stage in terms of exploration, with both directly teleoperated systems, such as the ones used in the *Kontur* project, and embedding the concept of supervised autonomy in the scope of *METERON* [17], with experiments already conducted from aboard the International Space Station.

#### *9.1.1 Research Challenges*

Historically, research on bilateral teleoperation has considered the closed loop system stability in presence of communication delays and with uncertain dynamics of the environment and the user [8]. The foundations of modern teleoperation were outlined by Anderson and Spong [4] with the scattering approach, highlighting the trade-off between stability and transparency, i.e. the system displayable impedance range. More recent approaches have shifted towards less conservative techniques such as time-domain passivity. However, to ensure practical stability, some feeling of presence at the remote location has to be sacrificed, degrading the user perception of the remote environment [10].

In the unstructured environments where teleoperation is required, the robust control of master and slave robots interaction dynamics are paramount, in order to ensure the accurate execution of the desired task and its stability. The problem of impedance control in teleoperation has been investigated in [15], which proposed tuning guidelines for the intercontinental control of a humanoid robot subject to communication delays.

The development of interfaces and control algorithms for kinesthetic, tactile, and visual feedback in teleoperation has found fertile grounds in research, for applications where it is critical that the user has a strong sense of presence, while exploiting these cues to improve the system usability. In [7] classical visual servoing aids a physician in the execution of a tele-ecography, by exploiting image features to automatically turn the robot tool while optimizing the ultrasound image quality. Overall, these topics outline a research interest that is increasingly focusing on the interaction between user and control system in the form of shared autonomy architectures. Splitting the burden of operation between user and robot becomes the main design objective, in order to reduce operator fatigue and offer an intuitive experience when using the platform for tasks that are physically and cognitively demanding [3]. Shared human-robot controllers can be the answer for an efficient and seamless human-robot cooperation, with estimation and prediction of user behavior being able to further improve the user experience.

The present paper aims at briefly illustrating a comprehensive control framework for teleoperated robot systems, from the low level motion control aspects, interaction control, and system stability analysis with human-in-the-loop, to the higher level visual-aided control algorithms reducing the operator cognitive load. In Sect. 9.2, a robust controller exploiting sliding mode control techniques is proposed for redundant robot manipulators to arbitrarily and reliably assign the robot impedance in the task space and track the user input in a teleoperation scenario. The enclosing optimization-based high level model predictive controller ensures robustness of the sliding mode to actuation delays and unmodeled system dynamics. System stability is proved using absolute stability criteria, with guidelines to tune the controller parameters. In Sect. 9.3, this architecture is exploited to allow the straightforward definition of virtual fixtures and their rendering to the operator via force feedback. Finally, in Sect. 9.4, the framework is extended to include visual feedback from a camera mounted on a dual-arm slave robot, and visual servoing is employed to improve user interaction with the system, by introducing some autonomy into the slave robot in terms of camera control. Section 9.5 concludes this brief.

#### **9.2 Robust Impedance Shaping of Redundant Teleoperators**

At a local control level, robust control theory is used to guarantee a desired dynamic behavior of the robot during interaction. Sliding mode control [20] robustly shapes master and slave manipulators impedances, irrespectively of uncertainties. This formulation is addressed by directly specifying the task sliding manifold, while the manipulator redundancy is considered by successive null-space projections of sliding manifolds defined by lower priority tasks.

A hierarchical optimization outer layer takes into account individual control and motion constraints, such as torque or joint limits, while its model predictive nature also guarantees robust compensation of actuation delays and unmodeled input filter dynamics. The overall stability analysis in presence of variable communication delays during contact is performed thanks to Llewellyn's absolute stability criterion.

#### *9.2.1 Model Predictive Sliding Mode Control*

The generic manipulator dynamics can be represented by the following model

$$B(q)\ddot{\vec{q}} + n(q, \dot{\vec{q}}) = \pi - J(q)^T F\_e \tag{9.1}$$

where *q*, *q***˙**, *q***¨** ∈ R*n* are the robot joint positions, velocities and accelerations respectively, *B*(*q*) ∈ R*n*×*n* is the symmetric positive definite inertia matrix, *n*(*q*, *q***˙**) ∈ R*n* is a vector comprising Coriolis, gravitational, and friction terms, *τ* ∈ R*n* is the actuation torque, *Fe* ∈ R*m* is the external generalized force due to interaction with the environment, and finally *J*(*q*) ∈ R*m*×*n* is the robot end effector Jacobian, with *m* ≤ *n*. The objective of impedance control is to change the displayed end effector dynamics according to the following equation

$$M\ddot{\tilde{\mathbf{x}}} + D\dot{\tilde{\mathbf{x}}} + K\tilde{\mathbf{x}} = \hat{F}\_e \tag{9.2}$$

where *M*, *D*, *K* > 0 ∈ R*m*×*m* are the desired inertia, damping and stiffness matrices respectively, while *x***˜** = *xr* − *x* ∈ R*m* is the end effector tracking error with *xr* being the reference trajectory, and ˆ(·) indicating estimated quantities.

Unfortunately, the simple application of a nominal control law [9] results in a system that is heavily affected by uncertainties and disturbances (the second term on the right-hand side of (9.3)), and that is not able to satisfy the dynamics requirement.

$$M\ddot{\tilde{\mathbf{x}}} + D\dot{\tilde{\mathbf{x}}} + K\tilde{\mathbf{x}} = \hat{F}\_c - M\,\mathbf{J}\,\hat{B}^{-1}(\tilde{B}\ddot{\tilde{q}} + \eta) \tag{9.3}$$

Therefore, the following Second Order sliding mode control law [6] is proposed in order to compensate the uncertainties, while maintaining a negligible control chattering

$$\nu = \nu\_0 + \nu\_{smc} = \nu\_0 + k\_1 \frac{\mathbf{E}\_q}{\sqrt{\|\mathbf{E}\_q\|}} + k\_2 \int\_{t\_0}^t \frac{\mathbf{E}\_q}{\|\mathbf{E}\_q\|} d\tau \tag{9.4}$$

where *v* is the auxiliary control to be selected after applying a feedback linearizing controller to (9.1), *v*0 the nominal control used to obtain the desired impedance, and *q* the so-called sliding variable. By appropriately choosing *q* , we can prove the following

**Theorem 9.1** *Consider the partially feedback linearized version of the robot dynamics* (9.1) *and the control* (9.4) *with sufficiently high gains. Let*

$$
\Sigma\_q(t) = \dot{\bar{q}}(t) - \dot{\bar{q}}\_0(t) \tag{9.5}
$$

*with q***˙** 0(*t*) = ∫*t t*0 *v*0*d*τ + *q***˙**(*t*0)*. On the sliding manifold q* = **0***, the system evolves with dynamics free of disturbances and uncertainties. Moreover, this holds beginning from the initial time instant t*0 *(integral sliding mode).*

Therefore, thanks to (9.4), we can completely disregard the uncertainties, and select the nominal control *v*0 to ensure the desired end effector impedance as in the nominal case. For redundant manipulators (*m* < *n*), however, other tasks can be accomplished simultaneously. Hence, we enclose the sliding mode controller with a hierarchical formulation of model predictive control:

The proposed controller results in a cascade of optimizations starting from the higher priority one, enforcing the impedance (9.6a), to the tasks with lower priority (9.6b)

$$\begin{aligned} \boldsymbol{\nu}\_{0,0} &= \underset{\boldsymbol{\nu}\_0}{\text{arg min}} \; \|\dot{\boldsymbol{\sigma}}\|\_{\mathcal{Q}}^2\\ \text{s.t.} \; \underline{\mathbf{r}} &\le \underline{\mathbf{r}}(\boldsymbol{\nu}\_0, \boldsymbol{\nu}\_{smc}) \le \overline{\mathbf{r}}\\ \underline{\mathbf{q}} &\le \underline{\mathbf{q}} \le \overline{\mathbf{q}}\\ \boldsymbol{A}\boldsymbol{\nu}\_0 &\le \underline{\mathbf{b}} \end{aligned} \tag{9.6a}$$

$$\begin{aligned} \boldsymbol{\nu}\_{0,i} &= \operatorname\*{arg\,min}\_{\boldsymbol{\nu}\_0} \left\| \dot{\boldsymbol{\sigma}}\_i \right\|\_{\mathcal{Q}\_i}^2 \\ \text{s.t.} &\quad \text{constraints up to task } i - 1 \\ &\quad \boldsymbol{J}\_{i-1} \boldsymbol{\nu}\_0 = \boldsymbol{J}\_{i-1} \boldsymbol{\nu}\_{0,i-1} \end{aligned} \tag{9.6b}$$

where *σ***˙** *i* represents the derivative of the desired task sliding manifold, and *Qi* cost weighting factors.

By taking the predictions of the state and the sliding manifolds, robustness up to *d* steps of actuation delay is guaranteed by applying the following control law at time *k*, where (·)∗ indicates predicted quantities.

$$\boldsymbol{\sigma}\_{k} = \hat{\boldsymbol{B}}(\boldsymbol{q}\_{k+d}^{\*})\boldsymbol{v}\_{k} + \hat{\boldsymbol{n}}(\boldsymbol{q}\_{k+d}^{\*}, \dot{\boldsymbol{q}}\_{k+d}^{\*}) + \boldsymbol{J}\_{k+d}^{\*T}\hat{\boldsymbol{F}}\_{c,k+d}^{\*} \tag{9.7}$$

$$\boldsymbol{\nu}\_{k} = \boldsymbol{\nu}\_{0}(\dot{\boldsymbol{\sigma}}\_{k+d}^{\*}) + \boldsymbol{\nu}\_{smc}(\boldsymbol{\Sigma}\_{q,k+d}^{\*}) \tag{9.8}$$

#### *9.2.2 Robust Impedance Shaping*

The application of this Model Predictive Sliding Mode Control scheme (Fig. 9.1) to a teleoperation system is straightforward, if we modify the desired impedance in order to reflect the slave environment force *Fe* on the master (9.9), and ensure master reference tracking *x***˜** = *xs* − *k p xd m* for the slave (9.10), where *k f* and *k p* are force and position scaling factors, and (·)*d* indicates a delayed quantity due to the communication delay between the two systems.

**Fig. 9.1** The proposed model predictive sliding mode control scheme

$$\mathbf{M}\_m \ddot{\mathbf{x}}\_m + \mathbf{D}\_m \dot{\mathbf{x}}\_m + \mathbf{K}\_m \mathbf{x}\_m = \mathbf{F}\_h - k\_f \mathbf{F}\_c^d \tag{9.9}$$

$$\mathbf{M}\_s \ddot{\tilde{\mathbf{x}}} + \mathbf{D}\_s \dot{\tilde{\mathbf{x}}} + \mathbf{K}\_s \tilde{\mathbf{x}} = -\mathbf{F}\_e \tag{9.10}$$

Tuning guidelines for the master and slave parameters can be obtained by analyzing the hybrid matrix *H* describing the interconnected system, while guaranteeing teleoperation stability in presence of delays.

$$
\begin{bmatrix} F\_h \\ -\dot{\lambda}\_s \end{bmatrix} = H \begin{bmatrix} \dot{\lambda}\_m \\ F\_c \end{bmatrix} = \begin{bmatrix} \frac{M\_m s^2 + D\_m s + K\_m}{s} & \frac{k\_f}{(1+s\tau)^2} e^{-s d\_2} \\\ -k\_p e^{-s d\_1} & \frac{s}{M\_s s^2 + D\_s s + K\_s} \end{bmatrix} \begin{bmatrix} \dot{\lambda}\_m \\ F\_c \end{bmatrix} \tag{9.11}
$$