Roberto Tempo

Matthias Lorenzen, Fabrizio Dabbene, Roberto Tempo et al.

Constraint tightening to non-conservatively guarantee recursive feasibility and stability in Stochastic Model Predictive Control is addressed. Stability and feasibility requirements are considered separately, highlighting the difference between existence of a solution and feasibility of a suitable, a priori known candidate solution. Subsequently, a Stochastic Model Predictive Control algorithm which unifies previous results is derived, leaving the designer the option to balance an increased feasible region against guaranteed bounds on the asymptotic average performance and convergence time. Besides typical performance bounds, under mild assumptions, we prove asymptotic stability in probability of the minimal robust positively invariant set obtained by the unconstrained LQ-optimal controller. A numerical example, demonstrating the efficacy of the proposed approach in comparison with classical, recursively feasible Stochastic MPC and Robust MPC, is provided.

Anton V. Proskurnikov, Roberto Tempo

In recent years, we have observed a significant trend towards filling the gap between social network analysis and control. This trend was enabled by the introduction of new mathematical models describing dynamics of social groups, the advancement in complex networks theory and multi-agent systems, and the development of modern computational tools for big data analysis. The aim of this tutorial is to highlight a novel chapter of control theory, dealing with applications to social systems, to the attention of the broad research community. This paper is the first part of the tutorial, and it is focused on the most classical models of social dynamics and on their relations to the recent achievements in multi-agent systems.

Anton Proskurnikov, Roberto Tempo

Recent years have witnessed a significant trend towards filling the gap between Social Network Analysis (SNA) and control theory. This trend was enabled by the introduction of new mathematical models describing dynamics of social groups, the development of algorithms and software for data analysis and the tremendous progress in understanding complex networks and multi-agent systems (MAS) dynamics. The aim of this tutorial is to highlight a novel chapter of control theory, dealing with dynamic models of social networks and processes over them, to the attention of the broad research community. In its first part [1], we have considered the most classical models of social dynamics, which have anticipated and to a great extent inspired the recent extensive studies on MAS and complex networks. This paper is the second part of the tutorial, and it is focused on more recent models of social processes that have been developed concurrently with MAS theory. Future perspectives of control in social and techno-social systems are also discussed.

Matthias Lorenzen, Fabrizio Dabbene, Roberto Tempo et al.

For discrete-time linear systems subject to parametric uncertainty described by random variables, we develop a sampling-based Stochastic Model Predictive Control algorithm. Unlike earlier results employing a scenario approximation, we propose an offline sampling approach in the design phase instead of online scenario generation. The paper highlights the structural difference between online and offline sampling and provides rigorous bounds on the number of samples needed to guarantee chance constraint satisfaction. The approach does not only significantly speed up the online computation, but furthermore allows to suitably tighten the constraints to guarantee robust recursive feasibility when bounds on the uncertain variables are provided. Under mild assumptions, asymptotic stability of the origin can be established.

Seyed Mehran Dibaji, Hideaki Ishii, Roberto Tempo

We consider the problem of multi-agent consensus where some agents are subject to faults/attacks and might make updates arbitrarily. The network consists of agents taking integer-valued (i.e., quantized) states under directed communication links. The goal of the healthy normal agents is to form consensus in their state values, which may be disturbed by the non-normal, malicious agents. We develop update schemes to be equipped by the normal agents whose interactions are asynchronous and subject to non-uniform and time-varying time delays. In particular, we employ a variant of the so-called mean subsequence reduced (MSR) algorithms, which have been long studied in computer science, where each normal agent ignores extreme values from its neighbors. We solve the resilient quantized consensus problems in the presence of totally/locally bounded adversarial agents and provide necessary and sufficient conditions in terms of the connectivity notion of graph robustness. Furthermore, it will be shown that randomization is essential both in quantization and in the updating times when normal agents interact in an asynchronous manner. The results are examined through a numerical example.

Hideaki Ishii, Roberto Tempo

In the search engine of Google, the PageRank algorithm plays a crucial role in ranking the search results. The algorithm quantifies the importance of each web page based on the link structure of the web. We first provide an overview of the original problem setup. Then, we propose several distributed randomized schemes for the computation of the PageRank, where the pages can locally update their values by communicating to those connected by links. The main objective of the paper is to show that these schemes asymptotically converge in the mean-square sense to the true PageRank values. A detailed discussion on the close relations to the multi-agent consensus problems is also given.

Matthias Lorenzen, Frank Allgöwer, Fabrizio Dabbene et al.

The problem of achieving a good trade-off in Stochastic Model Predictive Control between the competing goals of improving the average performance and reducing conservativeness, while still guaranteeing recursive feasibility and low computational complexity, is addressed. We propose a novel, less restrictive scheme which is based on considering stability and recursive feasibility separately. Through an explicit first step constraint we guarantee recursive feasibility. In particular we guarantee the existence of a feasible input trajectory at each time instant, but we only require that the input sequence computed at time $k$ remains feasible at time $k+1$ for most disturbances but not necessarily for all, which suffices for stability. To overcome the computational complexity of probabilistic constraints, we propose an offline constraint-tightening procedure, which can be efficiently solved via a sampling approach to the desired accuracy. The online computational complexity of the resulting Model Predictive Control (MPC) algorithm is similar to that of a nominal MPC with terminal region. A numerical example, which provides a comparison with classical, recursively feasible Stochastic MPC and Robust MPC, shows the efficacy of the proposed approach.

Hideaki Ishii, Roberto Tempo, Er-Wei Bai

The PageRank algorithm employed at Google assigns a measure of importance to each web page for rankings in search results. In our recent papers, we have proposed a distributed randomized approach for this algorithm, where web pages are treated as agents computing their own PageRank by communicating with linked pages. This paper builds upon this approach to reduce the computation and communication loads for the algorithms. In particular, we develop a method to systematically aggregate the web pages into groups by exploiting the sparsity inherent in the web. For each group, an aggregated PageRank value is computed, which can then be distributed among the group members. We provide a distributed update scheme for the aggregated PageRank along with an analysis on its convergence properties. The method is especially motivated by results on singular perturbation techniques for large-scale Markov chains and multi-agent consensus.

Keyou You, Roberto Tempo, Li Qiu

This paper is concerned with distributed computation of several commonly used centrality measures in complex networks. In particular, we propose deterministic algorithms, which converge in finite time, for the distributed computation of the degree, closeness and betweenness centrality measures in directed graphs. Regarding eigenvector centrality, we consider the PageRank problem as its typical variant, and design distributed randomized algorithms to compute PageRank for both fixed and time-varying graphs. A key feature of the proposed algorithms is that they do not require to know the network size, which can be simultaneously estimated at every node, and that they are clock-free. To address the PageRank problem of time-varying graphs, we introduce the novel concept of persistent graph, which eliminates the effect of spamming nodes. Moreover, we prove that these algorithms converge almost surely and in the sense of $L^p$. Finally, the effectiveness of the proposed algorithms is illustrated via extensive simulations using a classical benchmark.

Anton V. Proskurnikov, Roberto Tempo, Ming Cao et al.

Investigation of social influence dynamics requires mathematical models that are "simple" enough to admit rigorous analysis, and yet sufficiently "rich" to capture salient features of social groups. Thus, the mechanism of iterative opinion pooling from (DeGroot, 1974), which can explain the generation of consensus, was elaborated in (Friedkin and Johnsen, 1999) to take into account individuals' ongoing attachments to their initial opinions, or prejudices. The "anchorage" of individuals to their prejudices may disable reaching consensus and cause disagreement in a social influence network. Further elaboration of this model may be achieved by relaxing its restrictive assumption of a time-invariant influence network. During opinion dynamics on an issue, arcs of interpersonal influence may be added or subtracted from the network, and the influence weights assigned by an individual to his/her neighbors may alter. In this paper, we establish new important properties of the (Friedkin and Johnsen, 1999) opinion formation model, and also examine its extension to time-varying social influence networks.

Alberto Tarable, Alessandro Nordio, Fabrizio Dabbene et al.

This paper deals with the problem of stabilizing an unstable system through networked control over the wireless medium. In such a situation a remote sensor communicates the measurements to the system controller through a noisy channel. In particular, in the AWGN scenario, we show that protograph-based LDPC convolutional codes achieve anytime reliability and we also derive a lower bound to the signal-to-noise ratio required to stabilize the system. Moreover, on the Rayleigh-fading channel, we show by simulations that resorting to multiple sensors allows to achieve a diversity gain.

Chiara Ravazzi, Paolo Frasca, Roberto Tempo et al.

This paper regards the relative localization problem in sensor networks. We study a randomized algorithm, which is based on input-driven consensus dynamics and involves pairwise "gossip" communications and updates. Due to the randomness of the updates, the state of this algorithm ergodically oscillates around a limit value. Exploiting the ergodicity of the dynamics, we show that the time-average of the state almost surely converges to the least-squares solution of the localization problem. Remarkably, the computation of the time-average does not require the sensors to share any common clock. Hence, the proposed algorithm is fully distributed and asynchronous.

Simone Formentin, Fabrizio Dabbene, Roberto Tempo et al.

In this paper, we address robust static anti-windup compensator design and performance analysis for saturated linear closed loops in the presence of nonlinear probabilistic parameter uncertainties via randomized techniques. The proposed static anti-windup analysis and robust performance synthesis correspond to several optimization goals, ranging from minimization of the nonlinear input/output gain to maximization of the stability region or maximization of the domain of attraction. We also introduce a novel paradigm accounting for uncertainties in the energy of the disturbance inputs. Due to the special structure of linear static anti-windup design, wherein the design variables are decoupled from the Lyapunov certificates, we introduce a significant extension, called scenario with certificates (SwC), of the so-called scenario approach for uncertain optimization problems. This extension is of independent interest for similar robust synthesis problems involving parameter-dependent Lyapunov functions. We demonstrate that the scenario with certificates robust design formulation is appealing because it provides a way to implicitly design the parameter-dependent Lyapunov functions and to remove restrictive assumptions about convexity with respect to the uncertain parameters. Subsequently, to reduce the computational cost, we present a sequential randomized algorithm for iteratively solving this problem. The obtained results are illustrated by numerical examples.

Keyou You, Roberto Tempo, Pei Xie

This paper proposes distributed algorithms to solve robust convex optimization (RCO) when the constraints are affected by nonlinear uncertainty. We adopt a scenario approach by randomly sampling the uncertainty set. To facilitate the computational task, instead of using a single centralized processor to obtain a "global solution" of the scenario problem (SP), we resort to {\it multiple interconnected processors} that are distributed among different nodes of a network to simultaneously solve the SP. Then, we propose a primal-dual sub-gradient algorithm and a random projection algorithm to distributedly solve the SP over undirected and directed graphs, respectively. Both algorithms are given in an explicit recursive form with simple iterations, which are especially suited for processors with limited computational capability. We show that, if the underlying graph is strongly connected, each node asymptotically computes a common optimal solution to the SP with a convergence rate $O(1/(\sum_{t=1}^kζ^t))$ where $\{ζ^t\}$ is a sequence of appropriately decreasing stepsizes. That is, the RCO is effectively solved in a distributed way. The relations with the existing literature on robust convex programs are thoroughly discussed and an example of robust system identification is included to validate the effectiveness of our distributed algorithms.

Fabrizio Dabbene, Mario Sznaier, Roberto Tempo

The classical approach to system identification is based on stochastic assumptions about the measurement error, and provides estimates that have random nature. Worst-case identification, on the other hand, only assumes the knowledge of deterministic error bounds, and establishes guaranteed estimates, thus being in principle better suited for the use in control design. However, a main limitation of such deterministic bounds lies on their potential conservatism, thus leading to estimates of restricted use. In this paper, we propose a rapprochement between the stochastic and worst-case paradigms. In particular, based on a probabilistic framework for linear estimation problems, we derive new computational results. These results combine elements from information-based complexity with recent developments in the theory of randomized algorithms. The main idea in this line of research is to "discard" sets of measure at most ε, where εis a probabilistic accuracy, from the set of deterministic estimates. Therefore, we are decreasing the so-called worst-case radius of information at the expense of a given probabilistic ``risk." In this setting, we compute a trade-off curve, called violation function, which shows how the radius of information decreases as a function of the accuracy. To this end, we construct randomized and deterministic algorithms which provide approximations of this function. We report extensive simulations showing numerical comparisons between the stochastic, worst-case and probabilistic approaches, thus demonstrating the efficacy of the methods proposed in this paper.

Sergey E. Parsegov, Anton V. Proskurnikov, Roberto Tempo et al.

Unlike many complex networks studied in the literature, social networks rarely exhibit unanimous behavior, or consensus. This requires a development of mathematical models that are sufficiently simple to be examined and capture, at the same time, the complex behavior of real social groups, where opinions and actions related to them may form clusters of different size. One such model, proposed by Friedkin and Johnsen, extends the idea of conventional consensus algorithm (also referred to as the iterative opinion pooling) to take into account the actors' prejudices, caused by some exogenous factors and leading to disagreement in the final opinions. In this paper, we offer a novel multidimensional extension, describing the evolution of the agents' opinions on several topics. Unlike the existing models, these topics are interdependent, and hence the opinions being formed on these topics are also mutually dependent. We rigorous examine stability properties of the proposed model, in particular, convergence of the agents' opinions. Although our model assumes synchronous communication among the agents, we show that the same final opinions may be reached "on average" via asynchronous gossip-based protocols.

Mohammadreza Chamanbaz, Fabrizio Dabbene, Roberto Tempo et al.

In this paper, we propose new sequential randomized algorithms for convex optimization problems in the presence of uncertainty. A rigorous analysis of the theoretical properties of the solutions obtained by these algorithms, for full constraint satisfaction and partial constraint satisfaction, respectively, is given. The proposed methods allow to enlarge the applicability of the existing randomized methods to real-world applications involving a large number of design variables. Since the proposed approach does not provide a priori bounds on the sample complexity, extensive numerical simulations, dealing with an application to hard-disk drive servo design, are provided. These simulations testify the goodness of the proposed solution.

Paolo Frasca, Chiara Ravazzi, Roberto Tempo et al.

In this paper we study a novel model of opinion dynamics in social networks, which has two main features. First, agents asynchronously interact in pairs, and these pairs are chosen according to a random process. We refer to this communication model as "gossiping". Second, agents are not completely open-minded, but instead take into account their initial opinions, which may be thought of as their "prejudices". In the literature, such agents are often called "stubborn". We show that the opinions of the agents fail to converge, but persistently undergo ergodic oscillations, which asymptotically concentrate around a mean distribution of opinions. This mean value is exactly the limit of the synchronous dynamics of the expected opinions.