Search

• We consider online optimization for signal processing and machine learning. • We study online algorithms based on the prediction-correction paradigm. • We propose a novel prediction strategy suitable for the mentioned applications. • We provide convergence results, both for primal and dual problems. • We discuss numerical examples from signal processing, learning, robotics. In this paper, we focus on the solution of online optimization problems that arise often in signal processing and machine learning, in which we have access to streaming sources of data. We discuss algorithms for online optimization based on the prediction-correction paradigm, both in the primal and dual space. In particular, we leverage the typical regularized least-squares structure appearing in many signal processing problems to propose a novel and tailored prediction strategy, which we call extrapolation-based. By using tools from operator theory, we then analyze the convergence of the proposed methods as applied both to primal and dual problems, deriving an explicit bound for the tracking error, that is, the distance from the time-varying optimal solution. We further discuss the empirical performance of the algorithm when applied to signal processing, machine learning, and robotics problems. [ABSTRACT FROM AUTHOR]

There is a common belief that the ADMM, a popular algorithm employed for distributed convex optimization over graphs, is faster than another distributed algorithm typically referred as the Average Consensus. This belief is based on the observation that the ratio of the number of iterations necessary to achieve a desired error with respect to the optimal solution of the ADMM vs the Average Consensus goes to zero as the graph becomes larger or less connected. In this work, we provide a closed form expression for the rate of ADMM as a function of the essential spectral radius of the graph, which is a measure of connectivity of the graph, for scalar quadratic cost functions with identical curvature, and we show that its rate of convergence can be slower than the Average Consensus when the graph is highly connected. Moreover, via extensive simulations, we show that ADMM performance, differently from the average consensus, rapidly degrade as the cost functions become skewed, thus making the latter approach competitive also for sparse graphs. [ABSTRACT FROM AUTHOR]

A class of abstract aerial robotic systems is introduced, the laterally bounded force vehicles, in which most of the control authority is expressed along a principal thrust direction, while along the lateral directions a (smaller and possibly null) force may be exploited to achieve full-pose tracking. This class approximates platforms endowed with noncollinear rotors that can modify the orientation of the total thrust in a body frame. If made possible by the force constraints, the proposed SE(3)-based control strategy achieves the independent tracking of position-plus-orientation trajectories. The method, which is proven using a Lyapunov technique, deals seamlessly with both underactuated and fully actuated platforms, and guarantees at least the position tracking in the case of an unfeasible full-pose reference trajectory. Several experimental tests are presented that clearly show the approach practicability and the sharp improvement with respect to state of the art. [ABSTRACT FROM AUTHOR]

In this paper, we consider a voltage control problem in power distribution grids. The specific goal is that of keeping the voltages within preassigned operating limits by commanding the reactive power output of the microgenerators connected to the grid. We propose three strategies. The first two strategies are purely local, meaning that each microgenerator updates the amount of reactive power to be injected based only on local measurements of the voltages’ magnitude. Instead the third one is distributed, namely, the microgenerators, to perform the updating steps, require some additional information coming from the neighboring agents. The local strategies are simpler to be implemented, but they might fail in solving the voltage control problem. Instead, the distributed one requires the microgenerators to be endowed with communication capabilities, but it is effective in driving the voltages within the admissible intervals and, additionally, it exploits the cooperation among the agents to reach also a power losses minimization objective. Theoretical analysis and extensive numerical simulations are provided to confirm the arguments aforementioned. [ABSTRACT FROM PUBLISHER]

Abstract: We consider the optimal servicing of a queue with sigmoid server performance. There are various systems with sigmoid server performance, including systems involving human decision making, visual perception, human–machine communication and advertising response. Tasks arrive at the server according to a Poisson process. Each task has a deadline that is incorporated as a latency penalty. We investigate the trade-off between the reward obtained by processing the current task and the penalty incurred due to the tasks waiting in the queue. We study this optimization problem in a Markov decision process (MDP) framework. We characterize the properties of the optimal policy for the MDP and show that the optimal policy may drop some tasks; that is, may not process a task at all. We determine an approximate solution to the MDP using the certainty-equivalent receding horizon optimization framework and derive performance bounds on the proposed receding horizon policy. We also suggest guidelines for the design of such queues. [Copyright &y& Elsevier]

Abstract: This work presents a distributed method for control centers to monitor the operating condition of a power network, i.e., to estimate the network state, and to ultimately determine the occurrence of threatening situations. State estimation has been recognized to be a fundamental task for network control centers to operate safely and reliably a power grid. We consider (static) state estimation problems, in which the state vector consists of the voltage magnitude and angle at all network buses. We consider the state to be linearly related to network measurements, which include power flows, current injections, and voltage phasors at some buses. We admit the presence of several cooperating control centers, and we design two distributed methods for them to compute the minimum variance estimate of the state, given the network measurements. The two distributed methods rely on different modes of cooperation among control centers: in the first method an incremental mode of cooperation is used, whereas, in the second method, a diffusive interaction is implemented. Our procedures, which require each control center to know only the measurements and the structure of a subpart of the whole network, are computationally efficient and scalable with respect to the network dimension, provided that the number of control centers also increases with the network cardinality. Additionally, a finite-memory approximation of our diffusive algorithm is proposed, and its accuracy is characterized. Finally, our estimation methods are exploited to develop a distributed algorithm to detect corrupted network measurements. [Copyright &y& Elsevier]

We propose distributed algorithms to automatically deploy a team of mobile robots to partition and provide coverage of a nonconvex environment. To handle arbitrary nonconvex environments, we represent them as graphs. Our partitioning and coverage algorithm requires only short-range, unreliable pairwise “gossip” communication. The algorithm has two components: 1) a motion protocol to ensure that neighboring robots communicate at least sporadically and 2) a pairwise partitioning rule to update territory ownership when two robots communicate. By studying an appropriate dynamical system on the space of partitions of the graph vertices, we prove that territory ownership converges to a pairwise-optimal partition in finite time. This new equilibrium set represents improved performance over common Lloyd-type algorithms. Additionally, our algorithm is an ``anytime algorithm'' that also scales well for large teams and can be run by on-board computers with limited resources. Finally, we report on large-scale simulations in complex environments and hardware experiments using the Player/Stage robot control system. [ABSTRACT FROM PUBLISHER]

Abstract: Iterative distributed algorithms are studied for computing arithmetic averages over networks of agents connected through memoryless broadcast erasure channels. These algorithms do not require the agents to have any knowledge about the global network structure or size. Almost sure convergence to state agreement is proved, and the communication and computational complexities of the algorithms are analyzed. Both the number of transmissions and the number of computations performed by each agent of the network are shown to grow not faster than poly-logarithmically in the desired precision. The impact of the graph topology on the algorithms’ performance is analyzed as well. Moreover, it is shown how, in the presence of noiseless communication feedback, one can modify the algorithms, significantly improving their performance versus complexity trade-off. [ABSTRACT FROM AUTHOR]

Abstract: This paper considers the average consensus problem on a network of digital links, and proposes a set of algorithms based on pairwise “gossip” communications and updates. We study the convergence properties of such algorithms with the goal of answering two design questions, arising from the literature: whether the agents should encode their communication by a deterministic or a randomized quantizer, and whether they should use, and how, exact information regarding their own states in the update. [Copyright &y& Elsevier]

Abstract: Let a set of communicating agents compute the average of their initial positions, where every agent is restricted to communicate to a given small number of other agents (average consensus problem). We prove that the optimal topology of communication is given by a de Bruijn graph. Consensus is then reached in finitely many steps. This solution is valid when the number of agents is an exact power of the out-degree of the communication graph. We introduce an algebraic tool, the shifted Kronecker product, and a more general family of strategies, also based on a de Bruijn communication graph. Those strategies are compared to Cayley strategies in terms of the speed of convergence. We also show that quantized communication between the agents still allows finite convergence, to a consensus, which is not in general the average of the initial positions. [Copyright &y& Elsevier]

In this paper we study motion coordination problems for groups of robots that exchange information through a rate-constrained communication network. For one-dimensional rendezvous and deployment problems with communication path graphs, we propose an integrated control and communication scheme combining a logarithmic coder/decoder with linear coordination algorithms. We show that the closed-loop performance is comparable to that achievable in the quantization-free model: the time complexity is, asymptotically on the size of the network, unchanged, and the exponential convergence factor degrades smoothly as the quantization accuracy becomes coarser. [ABSTRACT FROM AUTHOR]

Abstract: The interrelationship between control and communication theory is becoming of fundamental importance in many distributed control systems, such as the coordination of a team of autonomous agents. In such a problem, communication constraints impose limits on the achievable control performance. We consider as instance of coordination the consensus problem. The aim of the paper is to characterize the relationship between the amount of information exchanged by the agents and the rate of convergence to the consensus. We show that time-invariant communication networks with circulant symmetries yield slow convergence if the amount of information exchanged by the agents does not scale well with their number. On the other hand, we show that randomly time-varying communication networks allow very fast convergence rates. We also show that by adding logarithmic quantized data links to time-invariant networks with symmetries, control performance significantly improves with little growth of the required communication effort. [Copyright &y& Elsevier]

Volterra series approximate a broad range of nonlinear systems. Their identification is challenging due to the curse of dimensionality: the number of model parameters grows exponentially with the complexity of the input–output response. This fact limits the applicability of such models and has stimulated recently much research on regularized solutions. Along this line, we propose two new strategies that use kernel-based methods. First, we introduce the multiplicative polynomial kernel (MPK). Compared to the standard polynomial kernel, the MPK is equipped with a richer set of hyperparameters, increasing flexibility in selecting the monomials that really influence the system output. Second, we introduce the smooth exponentially decaying multiplicative polynomial kernel (SED-MPK), that is a regularized version of MPK which requires less hyperparameters, allowing to handle also high-order Volterra series. Numerical results show the effectiveness of the two approaches. [ABSTRACT FROM AUTHOR]

State Estimation (SE) is one of the essential tasks to monitor and control the smart power grid. This paper presents a method to estimate the state variables combining the measurement of power demand at each bus with the data collected from a limited number of Phasor Measurement Units (PMUs). Although PMU data are usually assumed to be perfectly synchronized with the Coordinated Universal Time (UTC), this work explicitly considers the presence of time-synchronization errors due, for instance, to the actual performance of GPS receivers and the limited stability of the internal oscillator. The proposed algorithm is a recursive Kalman filter which not only estimates the state variables of the power system, but also the frequency deviations causing clock offsets which eventually affect the timestamps of the measures returned by different PMUs. The proposed solution was tested and compared with alternative approaches using both synthetic data applied to the IEEE 123 bus distribution feeder and real-field data collected from a small-size medium-voltage (MV) distribution system located inside the EPFL campus in Lausanne. Results show the validity of the proposed method in terms of state estimation accuracy. In particular, when some synchronization errors are present, the proposed algorithm can estimate and compensate for them. [ABSTRACT FROM AUTHOR]

In this work we study the problem of multi-robot coverage of a planar region when the sensory field used to approximate the density of event appearance is not known in advance. We address the problem by considering two different communication architectures: client–server and peer-to-peer . In the first architecture the robots are allowed to communicate with a central server/base station. In the second the robots communicate among neighboring peers by means of a gossip protocol in a distributed fashion. For both the architectures, we resort to nonparametric Gaussian regression approach to estimate the unknown sensory field of interest from a collection of noisy samples. We propose a probabilistic control strategy based on the posterior of the estimation error variance, which lets the robots to estimate the true sensory field with any arbitrary accuracy while simultaneously computing and exploiting the corresponding centroidal Voronoi partitions. We also present a numerically efficient approximation based on a spatial discretization to trade-off the accuracy of the estimated map against the required computational complexity. This trade-off can be tuned based on explicit estimation error bounds which depend on the spatial resolution and the Gaussian kernel parameters. Finally, we test the proposed solutions via extensive numerical simulations. [ABSTRACT FROM AUTHOR]

This paper deals with distributed consensus optimization problems in which a connected network of agents aims at minimizing the sum of local cost functions over a common variable. In particular, we focus on the ADMM-based algorithm proposed by Shi et al. in Shi et al. (2014) that, under the assumption that local cost functions are strongly convex with Lipschitz continuous gradients, was shown to converge linearly to the optimal solution. In Shi et al. (2014), an upper bound to the convergence rate, depending on the network topology and on few properties of the local cost functions, has been derived and used to propose an optimal design of the penalty parameter of the algorithm. In this paper, assuming also twice differentiability of the costs function around the optimal solution, we refine the result of Shi et al. (2014) deriving a novel upper bound which is based on the additional knowledge of the curvatures of the cost functions around the optimal solution. We conjecture this bound to be tight in most cases and, to corroborate its effectiveness we perform a numerical analysis over important families of graphs showing that: (i) the bound we introduce improves significantly the bound derived in Shi et al. (2014) and, as a consequence, (ii) the design of the penalty parameter proposed in Shi et al. (2014) might lead to poor performance. [ABSTRACT FROM AUTHOR]

Background: Brain-computer interfaces (BCIs) are systems capable of translating human brain patterns, measured through electroencephalography (EEG), into commands for an external device. Despite the great advances in machine learning solutions to enhance the performance of BCI decoders, the translational impact of this technology remains elusive. The reliability of BCIs is often unsatisfactory for end-users, limiting their application outside a laboratory environment.Methods: We present the analysis on the data acquired from an end-user during the preparation for two Cybathlon competitions, where our pilot won the gold medal twice in a row. These data are of particular interest given the mutual learning approach adopted during the longitudinal training phase (8 months), the long training break in between the two events (1 year) and the demanding evaluation scenario. A multifaceted perspective on long-term user learning is proposed: we enriched the information gathered through conventional metrics (e.g., accuracy, application performances) by investigating novel neural correlates of learning in different neural domains.Results: First, we showed that by focusing the training on user learning, the pilot was capable of significantly improving his performance over time even with infrequent decoder re-calibrations. Second, we revealed that the analysis of the within-class modifications of the pilot's neural patterns in the Riemannian domain is more effective in tracking the acquisition and the stabilization of BCI skills, especially after the 1-year break. These results further confirmed the key role of mutual learning in the acquisition of BCI skills, and particularly highlighted the importance of user learning as a key to enhance BCI reliability.Conclusion: We firmly believe that our work may open new perspectives and fuel discussions in the BCI field to shift the focus of future research: not only to the machine learning of the decoder, but also in investigating novel training procedures to boost the user learning and the stability of the BCI skills in the long-term. To this end, the analyses and the metrics proposed could be used to monitor the user learning during training and provide a marker guiding the decoder re-calibration to maximize the mutual adaptation of the user to the BCI system. [ABSTRACT FROM AUTHOR]

Energy Harvesting Wireless Sensor Devices are increasingly being considered for deployment in sensor networks, due to their demonstrated advantages of prolonged lifetime and autonomous operation. However, irreversible degradation mechanisms jeopardize battery lifetime, calling for intelligent management policies, which minimize the impact of these phenomena while guaranteeing a minimum Quality of Service (QoS). This paper explores a mathematical characterization of these devices, focusing on the interplay between the battery discharge policy and the irreversible degradation of the storage capacity. We propose a stochastic Markov chain framework, suitable for policy optimization, which captures the degradation status of the battery. We present a general result of Markov chains, which exploits the timescale separation between the communication time-slot of the device and the battery degradation process, and enables an efficient optimization. We show that this model fits well the behavior of real batteries for what concerns their storage capacity degradation over time. We demonstrate that a degradation-aware policy significantly improves the lifetime of the sensor compared to "greedy" policies, while guaranteeing the minimum required QoS. Finally, a simple heuristic policy, which never discharges the battery below a given threshold, is shown to achieve near-optimal performance in terms of battery lifetime. [ABSTRACT FROM PUBLISHER]

We study the non-parametric reconstruction of spatio-temporal dynamical processes via Gaussian Processes (GPs) regression from sparse and noisy data. GPs have been mainly applied to spatial regression where they represent one of the most powerful estimation approaches also thanks to their universal representing properties. Their extension to dynamical processes has been instead elusive so far since classical implementations lead to unscalable algorithms or require some sort of approximation. We propose a novel procedure to address this problem by coupling GPs regression and Kalman filtering. In particular, assuming space/time separability of the covariance (kernel) of the process and rational time spectrum, we build a finite-dimensional discrete-time state-space process representation amenable to Kalman filtering. With sampling over a finite set of fixed spatial locations, our major finding is that the current Kalman filter state represents a sufficient statistic to compute the minimum variance estimate of the process at any future time over the entire spatial domain. In machine learning, a representer theorem states that an important class of infinite-dimensional variational problems admits a computable and finite-dimensional exact solution. In view of this, our result can be interpreted as a novel Dynamic Representer Theorem for GPs. We then extend the study to situations where the spatial input locations set varies over time. The proposed algorithms are tested on both synthetic and real field data, providing comparisons with standard GP and truncated GP regression techniques. [ABSTRACT FROM AUTHOR]

This paper proposes a technique to control distributed energy resources in low-voltage microgrids aiming at (i) allowing power flow control at the point of connection with the upstream grid, (ii) keeping voltage profiles within the operational limits. The first feature is crucial in smart low-voltage power systems. In fact, it enables both demand-responses, which is extremely valuable from the point of view of distribution system operators and for energy trading, and the autonomous operation of the microgrid. The latter can be achieved by regulating to zero the power exchanged with the main grid. The second feature allows to limit voltage increases due to active power injection by distributed energy resources and, thus, to limit stresses on the electrical infrastructure and the served loads, which is a concrete issue as renewables become widely deployed in the low-voltage scenario. The proposed approach is firstly described in detail, then a systematic analysis of its local and global properties is reported. All the obtained results are verified considering the IEEE 37 test feeder in realistic operating conditions. [ABSTRACT FROM AUTHOR]

In this paper, we propose an inverse-kinematics controller for a class of multi-robot systems in the scenario of sampled communication. The goal is to make a group of robots perform trajectory tracking in a coordinated way when the sampling time of communications is much larger than the sampling time of low-level controllers, disrupting theoretical convergence guarantees of standard control design in continuous time. Given a desired trajectory in configuration space which is pre-computed offline, the proposed controller receives configuration measurements, possibly via wireless, to re-compute velocity references for the robots, which are tracked by a low-level controller. We propose joint design of a sampled proportional feedback plus a novel continuous-time feedforward that linearizes the dynamics around the reference trajectory: this method is amenable to distributed communication implementation where only one broadcast transmission is needed per sample. Also, we provide closed-form expressions for instability and stability regions and convergence rate in terms of proportional gain k and sampling period T. We test the proposed control strategy via numerical simulations in the scenario of cooperative aerial manipulation of a cable-suspended load using a realistic simulator (Fly-Crane). Finally, we compare our proposed controller with centralized approaches that adapt the feedback gain online through smart heuristics, and show that it achieves comparable performance. [ABSTRACT FROM AUTHOR]

Efficient management of energy resources is crucial in smart buildings. In this work, model predictive control (MPC) is used to minimize the economic costs of prosumers equipped with production units, energy storage systems, and electric vehicles. To this purpose, the predictive control manages the available energy resources by exploiting future information about energy prices, absorption and production power profiles, and electric vehicle (EV) usage, such as times of departure and arrival and predicted energy consumption. The predictive control is compared with a rule-based technique, herein referred to as a heuristic approach, that acts in an instant-by-instant fashion without considering any future information. The reported results show that the studied predictive approach allows one to achieve charging profiles that adapt to variable operating conditions, aiming at optimal performances in terms of economic cost minimization in time-varying price scenarios, reduction of rms current stresses, and recharging capability of EV batteries. Specifically, unlike the heuristic method, the MPC approach is proven to be capable of efficiently managing the available energy resources to ensure a full recharge of the EV battery during nighttime while always respecting all system constraints. In addition, the proposed control is shown to be capable of keeping the peak power absorption from the grid constrained within set limits, which is a valuable feature in scenarios with widespread adoption of EVs in order to limit the stress on the electrical system. [ABSTRACT FROM AUTHOR]

The diffusion of distributed energy resources in distribution networks requires new approaches to exploit the users' capabilities of providing ancillary services. Of particular interest will be the coordination of microgrids operating as an aggregate of demand and supply units. This work reports a model predictive control (MPC) application in microgrids for the efficient energy management of energy storage systems and photovoltaic units. The MPC minimizes the economic cost of aggregate prosumers into a prediction horizon by forecasting generation and absorption profiles. The MPC is compared in realistic conditions with a heuristic strategy that acts in a instant manner, without taking into account signals prediction. The work aims at investigating the effect that different types of energy tariffs have in enhancing the end-users' flexibility, based on three examples of currently applied tariffs, comparing the two storage control modes. The MPC always achieves a better solution than the heuristic approach in all considered scenarios from the cost minimization point of view, with an improvement that is amplified by increasing the energy price variations between peak and off-peak periods. Furthermore, the MPC approach provides a cost saving when compared to the case considering a microgrid endowed with only photovoltaic units, in which no storage is installed. Findings in this work confirm that storage units better perform when some knowledge of future demand and supply trends is provided, ensuring an economic cost saving and an important service for the overall community. [ABSTRACT FROM AUTHOR]

We address the problem of multi-agent partition-based convex optimization which arises, for example, in robot localization problems and in regional state estimation in smart grids. More specifically, the global cost function is the sum of locally coupled cost functions that depend only on each agent variables and their neighbors' variables. Inspired by a generalized gradient descent strategy, namely the Block Jacobi iteration, we propose an algorithm amenable to a scalable distributed implementation, i.e., each agent eventually computes only the optimal values for its own variables via local communication with its neighbors. In particular, we provide sufficient conditions for global and semi-global exponential stability for the proposed algorithms even in the presence of lossy communications and asynchronous updates. The theoretical analysis relies on novel tools on Lyapunov theory based on separation of time scales and averaging theory for discrete-time systems. Finally, the proposed algorithm is numerically tested on the IEEE 123 nodes distribution feeder in the context of multi-area robust state estimation of smart grids in the presence of measurement outliers. [ABSTRACT FROM AUTHOR]