Visible to the public Biblio

Filters: Author is Geir Dullerud, University of Illinois at Urbana-Champaign  [Clear All Filters]
2015-11-17
Zhenqi Huang, University of Illinois at Urbana-Champaign, Yu Wang, University of Illinois at Urbana-Champaign, Sayan Mitra, University of Illinois at Urbana-Champaign, Geir Dullerud, University of Illinois at Urbana-Champaign.  2015.  Controller Synthesis for Linear Time-varying Systems with Adversaries.

We present a controller synthesis algorithm for a discrete time reach-avoid problem in the presence of adversaries. Our model of the adversary captures typical malicious attacks en- visioned on cyber-physical systems such as sensor spoofing, controller corruption, and actuator intrusion. After formu- lating the problem in a general setting, we present a sound and complete algorithm for the case with linear dynamics and an adversary with a budget on the total L2-norm of its actions. The algorithm relies on a result from linear control theory that enables us to decompose and precisely compute the reachable states of the system in terms of a symbolic simulation of the adversary-free dynamics and the total uncertainty induced by the adversary. With this de- composition, the synthesis problem eliminates the universal quantifier on the adversary’s choices and the symbolic con- troller actions can be effectively solved using an SMT solver. The constraints induced by the adversary are computed by solving second-order cone programmings. The algorithm is later extended to synthesize state-dependent controller and to generate attacks for the adversary. We present prelimi- nary experimental results that show the effectiveness of this approach on several example problems.

Zhenqi Huang, University of Illinois at Urbana-Champaign, Sayan Mitra, University of Illinois at Urbana-Champaign, Geir Dullerud, University of Illinois at Urbana-Champaign.  2012.  Differentially Private Iterative Synchronous Consensus. Workshop on Privacy in the Electronic Society (WPES 2012).

The iterative consensus problem requires a set of processes or agents with different initial values, to interact and update their states to eventually converge to a common value. Pro- tocols solving iterative consensus serve as building blocks in a variety of systems where distributed coordination is re- quired for load balancing, data aggregation, sensor fusion, filtering, and synchronization. In this paper, we introduce the private iterative consensus problem where agents are re- quired to converge while protecting the privacy of their ini- tial values from honest but curious adversaries. Protecting the initial states, in many applications, suffice to protect all subsequent states of the individual participants.

We adapt the notion of differential privacy in this setting of iterative computation. Next, we present (i) a server-based and (ii) a completely distributed randomized mechanism for solving differentially private iterative consensus with adver- saries who can observe the messages as well as the internal states of the server and a subset of the clients. Our analysis establishes the tradeoff between privacy and the accuracy.

Zhenqi Huang, University of Illinois at Urbana-Champaign, Yu Wang, University of Illinois at Urbana-Champaign, Sayan Mitra, University of Illinois at Urbana-Champaign, Geir Dullerud, University of Illinois at Urbana-Champaign.  2014.  On the Cost of Privacy in Distributed Control Systems. 3rd ACM International Conference on High Confidence Networked Systems (HiCoNS).

Individuals sharing information can improve the cost or performance of a distributed control system. But, sharing may also violate privacy. We develop a general framework for studying the cost of differential privacy in systems where a collection of agents, with coupled dynamics, communicate for sensing their shared environment while pursuing individ- ual preferences. First, we propose a communication strategy that relies on adding carefully chosen random noise to agent states and show that it preserves differential privacy. Of course, the higher the standard deviation of the noise, the higher the cost of privacy. For linear distributed control systems with quadratic cost functions, the standard deviation becomes independent of the number agents and it decays with the maximum eigenvalue of the dynamics matrix. Furthermore, for stable dynamics, the noise to be added is independent of the number of agents as well as the time horizon up to which privacy is desired.

Ray Essick, University of Illinois at Urbana-Champaign, Ji-Woong Lee, Pennsylvania State University, Geir Dullerud, University of Illinois at Urbana-Champaign.  2014.  Control of Linear Switched Systems with Receding Horizon Modal Information. IEEE Transactions on Automatic Control. 59(9)

We provide an exact solution to two performance problems—one of disturbance attenuation and one of windowed variance minimization—subject to exponential stability. Considered are switched systems, whose parameters come from a finite set and switch according to a language such as that specified by an automaton. The controllers are path-dependent, having finite memory of past plant parameters and finite foreknowledge of future parameters. Exact, convex synthesis conditions for each performance problem are expressed in terms of nested linear matrix inequalities. The resulting semidefinite programming problem may be solved offline to arrive at a suitable controller. A notion of path-by-path performance is introduced for each performance problem, leading to improved system performance. Non-regular switching languages are considered and the results are extended to these languages. Two simple, physically motivated examples are given to demonstrate the application of these results.

Qing Xu, Beihang University, Chun Zhang, Extreme Networks, Inc., Geir Dullerud, University of Illinois at Urbana-Champaign.  2014.  Stabilization of Markovian Jump Linear Systems with Log-Quantized Feedback. American Society Mechanical Engineers Journal of Dynamic Systems, Measurement and Control. 136(3)

This paper is concerned with mean-square stabilization of single-input Markovian jump linear systems (MJLSs) with logarithmically quantized state feedback. We introduce the concepts and provide explicit constructions of stabilizing mode-dependent logarithmic quantizers together with associated controllers, and a semi-convex way to determine the optimal (coarsest) stabilizing quantization density. An example application is presented as a special case of the developed framework, that of feedback stabilizing a linear time-invariant (LTI) system over a log-quantized erasure channel. A hardware implementation of this application on an inverted pendulum testbed is provided using a finite word-length approximation.

Ray Essick, University of Illinois at Urbana-Champaign, Ji-Woong Lee, Pennsylvania State University, Geir Dullerud, University of Illinois at Urbana-Champaign.  2014.  Path-By-Path Output Regulation of Switched Systems With a Receding Horizon of Modal Knowledge. American Control Conference (ACC).

We address a discrete-time LQG control problem over a fixed performance window and apply a receding-horizon type control strategy, resulting in an exact solution to the problem in terms of semidefinite programming. The systems considered take parameters from a finite set, and switch between them according to an automaton. The controller has a finite preview of future parameters, beyond which only the set of parameters is known. We provide necessary and sufficient convex con- ditions for the existence of a controller which guarantees both exponential stability and finite-horizon performance levels for the system; the performance levels may differ according to the particular parameter sequence within the performance window. A simple, physics-based example is provided to illustrate the main results.

Yu Wang, University of Illinois at Urbana-Champaign, Zhenqi Huang, University of Illinois at Urbana-Champaign, Sayan Mitra, University of Illinois at Urbana-Champaign, Geir Dullerud, University of Illinois at Urbana-Champaign.  2014.  Entropy-minimizing Mechanism for Differential Privacy of Discrete-time Linear Feedback Systems. 53rd IEEE Conference on Decision and Control (CDC 2014).

The concept of differential  privacy stems from the study of private query of datasets.  In  this work, we apply this concept  to metric spaces  to study a  mechanism  that randomizes a deterministic query by adding  mean-zero  noise to keep differential  privacy.

2016-10-24
Mohammad Naghnaeian, University of Illinois at Urbana-Champaign, Petros G. Voulgaris, University of Illinois at Urbana-Champaign, Geir Dullerud, University of Illinois at Urbana-Champaign.  2016.  A Unified Framework for lp Analysis and Synthesis of Linear Switched Sytems. American Control Confernce.

In this paper we develop a new framework to analyze stability and stabilizability of Linear Switched Systems (LSS) as well as their gain computations. Our approach is based on a combination of state space operator descritions and the Youda parametrization and provides a unified way to analysis an synthesis of LSS and in fact of Linear Time Varying (LTV) systems, in any lp induced norm sense. By specializing to the l case, we show how Linear Programming (LP) can be used to test stability, stabiliazbility and to synthesize stabilizing controllers that guarantee a near optimal closed-loop gain.

2016-12-12
Maurice Heemels, Geir Dullerud, University of Illinois at Urbana-Champaign, Andrew Teel.  2015.  A Lifting Approach to L2-gain Analysis of Periodic Event-triggered and Switching Sampled-data Control Systems. IEEE International Conference on Decision and Control (CDC 2015).

In this work we are interested in the stability and L2-gain of hybrid systems with linear flow dynamics, periodic time-triggered jumps and nonlinear possibly set-valued jump maps. This class of hybrid systems includes various interesting applications such as periodic event-triggered control. In this paper we also show that sampled-data systems with arbitrarily switching controllers can be captured in this framework by requiring the jump map to be set-valued. We provide novel conditions for the internal stability and L2-gain analysis of these systems adopting a lifting-based approach. In particular, we establish that the internal stability and contractivity in terms of an L2-gain smaller than 1 are equivalent to the internal stability and contractivity of a particular discretetime set-valued nonlinear system. Despite earlier works in this direction, these novel characterisations are the first necessary and sufficient conditions for the stability and the contractivity of this class of hybrid systems. The results are illustrated through multiple new examples.

2016-12-13
Mohammad Naghnaeian, University of Illinois at Urbana-Champaign, Petros G. Voulgaris, University of Illinois at Urbana-Champaign, Geir Dullerud, University of Illinois at Urbana-Champaign.  2016.  A Unified Frameworks for LpAnalysis and Synthesis of Linear Switched Systems.

In this paper, we develop a new framework to analyze stability and stabilizability of Linear Switched Systems (LSS) as well as their gain computations. Our approach is based on a combination of state space operator descriptions and the Youla parametrization and provides a unified way for analysis and synthesis of LSS, and in fact of Linear Time Varying (LTV) systems, in any lp induced norm sense. By specializing to the l∞ case, we show how Linear Programming (LP) can be used to test stability, stabilizability and to synthesize stabilizing controllers that guarantee a near optimal closed-loop gain.

2016-12-14
2017-01-23
Matthew Philippe, Universite Catholique de Louvain, Ray Essick, University of Illinois at Urbana-Champaig, Geir Dullerud, University of Illinois at Urbana-Champaign, Raphael M. Jungers, Unveristy of Illinois at Urbana-Champaign.  2016.  Stability of Discrete-time Switching Systems with Constrained Switching Sequences. Automatica. 72(C)

We introduce a novel framework for the stability analysis of discrete-time linear switching systems with switching sequences constrained by an automaton. The key element of the framework is the algebraic concept of multinorm, which associates a different norm per node of the automaton, and allows to exactly characterize stability. Building upon this tool, we develop the first arbitrarily accurate approximation schemes for estimating the constrained joint spectral radius ρˆ, that is the exponential growth rate of a switching system with constrained switching sequences. More precisely, given a relative accuracy r > 0, the algorithms compute an estimate of ρˆ within the range [ ˆρ, (1+r)ρˆ]. These algorithms amount to solve a well defined convex optimization program with known time-complexity, and whose size depends on the desired relative accuracy r > 0.

Matthew Philippe, Universite Catholique de Louvain, Ray Essick, University of Illinois at Urbana-Champaig, Geir Dullerud, University of Illinois at Urbana-Champaign, Raphael M. Jungers, Unveristy of Illinois at Urbana-Champaign.  2016.  Extremal Storage Functions and Minimal Realizations of Discrete-time Linear Switching Systems. 55th Conference on Decision and Control (CDC 2016).

We study the Lp induced gain of discretetime linear switching systems with graph-constrained switching sequences. We first prove that, for stable systems in a minimal realization, for every p ≥ 1, the Lp-gain is exactly characterized through switching storage functions. These functions are shown to be the pth power of a norm. In order to consider general systems, we provide an algorithm for computing minimal realizations. These realizations are rectangular systems, with a state dimension that varies according to the mode of the system. We apply our tools to the study on the of L2-gain. We provide algorithms for its approximation, and provide a converse result for the existence of quadratic switching storage functions. We finally illustrate the results with a physically motivated example.

2017-02-09
Anshuman Mishra, University of Illinois at Urbana-Champaign, Cedric Langbort, University of Illinois at Urbana-Champaign, Geir Dullerud, University of Illinois at Urbana-Champaign.  2015.  Decentralized Control of Linear Switched Nested Systms With l2-Induced Norm Performance.

This paper considers a decentralized switched control problem where exact conditions for controller synthesis are obtained in the form of semidefinite programming (SDP). The formulation involves a discrete-time switched linear plant that has a nested structure, and whose system matrices switch between a finite number of values according to finite-state automation. The goal of this paper is to synthesize a commensurately nested switched controller to achieve a desired level of 2-induced norm performance. The nested structures of both plant and controller are characterized by block lower-triangular system matrices. For this setup, exact conditions are provided for the existence of a finite path-dependent synthesis. These include conditions for the completion of scaling matrices obtained through an extended matrix completion lemma.When individual controller dimensions are chosen at least as large as the plant, these conditions reduce to a set of linear matrix inequalities. The completion lemma also provides an algorithm to complete closed-loop scaling matrices, leading to inequalities for  ontroller synthesis that are solvable either algebraically or numerically through SDP.

Published in IEEE Transactions on Control of Network Systems, volume 2, issue 4, December 2015.

2017-03-03
Zhenqi Huang, University of Illinois at Urbana-Champaign, Yu Wang, University of Illinois at Urbana-Champaign, Sayan Mitra, University of Illinois at Urbana-Champaign, Geir Dullerud, University of Illinois at Urbana-Champaign.  2015.  Analyzing the Cost of Securing Control Systems. The Next Wave: The National Security Agency's Review of Emerging Technologies. 21(1)

This article describes our recent progress on the development of rigorous analytical metrics for assessing the threat-performance trade-off in control systems. Computing systems that monitor and control physical processes are now pervasive, yet their security is frequently an afterthought rather than a first-order design consideration. We investigate a rational basis for deciding—at the design level—how much investment should be made to secure the system.

2017-04-21
Yu Wang, University of Illinois at Urbana-Champaign, Zhenqi Huang, University of Illinois at Urbana-Champaign, Sayan Mitra, University of Illinois at Urbana-Champaign, Geir Dullerud, University of Illinois at Urbana-Champaign.  2017.  Differential Privacy in Linear Distributed Control Systems: Entropy Minimizing Mechanisms and Performance Tradeoffs. IEEE Transactions on Network Control Systems. 4(1)

In distributed control systems with shared resources, participating agents can improve the overall performance of the system by sharing data about their personal references. In this paper, we formulate and study a natural tradeoff arising in these problems between the privacy of the agent’s data and the performance of the control system.We formalize privacy in terms of differential privacy of agents’ preference vectors. The overall control system consists of N agents with linear discrete-time coupled dynamics, each controlled to track its preference vector. Performance of the system is measured by the mean squared tracking error. We present a mechanism that achieves differential privacy by adding Laplace noise to the shared information in a way that depends on the sensitivity of the control system to the private data. We show that for stable systems the performance cost of using this type of privacy preserving mechanism grows as O(T/Nε2), where T is the time horizon and ε is the privacy parameter. For unstable systems, the cost grows exponentially with time. From an estimation point of view, we establish a lower-bound for the entropy of any unbiased estimator of the private data from any noise-adding mechanism that gives ε-differential privacy. We show that the mechanism achieving this lower-bound is a randomized mechanism that also uses Laplace noise.

2017-07-19
Yu Wang, University of Illinois at Urbana-Champaign, Zhenqi Huang, University of Illinois at Urbana-Champaign, Sayan Mitra, University of Illinois at Urbana-Champaign, Geir Dullerud, University of Illinois at Urbana-Champaign.  2017.  Differential Privacy and Entropy in Distributed Feedback Systems: Minimizing Mechanisms and Performance Trade-offs. IEEE Transactions on Network Control Systems. 4(1)

In distributed control systems with shared resources, participating agents can improve the overall performance of the system by sharing data about their personal preferences. In this paper, we formulate and study a natural tradeoff arising in these problems between the privacy of the agent’s data and the performance of the control system.We formalize privacy in terms of differential privacy of agents’ preference vectors. The overall control system consists of N agents with linear discrete-time coupled dynamics, each controlled to track its preference vector. Performance of the system is measured by the mean squared tracking error.We present a mechanism that achieves differential privacy by adding Laplace noise to the shared information in a way that depends on the sensitivity of the control system to the private data. We show that for stable systems the performance cost of using this type of privacy preserving mechanism grows as O(T 3/Nε2 ), where T is the time horizon and ε is the privacy parameter. For unstable systems, the cost grows exponentially with time. From an estimation point of view, we establish a lower-bound for the entropy of any unbiased estimator of the private data from any noise-adding mechanism that gives ε-differential privacy.We show that the mechanism achieving this lower-bound is a randomized mechanism that also uses Laplace noise.

Joao Jansch Porto, Geir Dullerud, University of Illinois at Urbana-Champaign.  2017.  Decentralized Control with Moving-Horizon Linear Switched Systems: Synthesis and Testbed Implementation. American Control Conference 2017.

In this paper, we improve recent results on the decentralized switched control problem to include the moving horizon case and apply it to a testbed system. Using known derivations for a centralized controller with look-ahead, we were able to extend the decentralized problem with finite memory to include receding horizon modal information. We then compare the performance of a switched controller with finite memory and look-ahead horizon to that of a linear time independent (LTI) controller using a simulation. The decentralized controller is further tested with a real-world system comprised of multiple model-sized hovercrafts.

2017-10-24
Yu Wang, University of Illinois at Urbana-Champaign, Matthew Hale, University of Illinois at Urbana-Champaign, Magnus Egerstedt, University of Illinois at Urbana-Champaign, Geir Dullerud, University of Illinois at Urbana-Champaign.  2017.  Differentially Private Objective Functions in Distributed Cloud-based Optimization. 20th World Congress of the International Federations of Automatic Control (IFAC 2017 World Congress).

Abstract—In this work, we study the problem of keeping the objective functions of individual agents "-differentially private in cloud-based distributed optimization, where agents are subject to global constraints and seek to minimize local objective functions. The communication architecture between agents is cloud-based – instead of communicating directly with each other, they oordinate by sharing states through a trusted cloud computer. In this problem, the difficulty is twofold: the objective functions are used repeatedly in every iteration, and the influence of  erturbing them extends to other agents and lasts over time. To solve the problem, we analyze the propagation of perturbations on objective functions over time, and derive an upper bound on them. With the upper bound, we design a noise-adding mechanism that randomizes the cloudbased distributed optimization algorithm to keep the individual objective functions "-differentially private. In addition, we study the trade-off between the privacy of objective functions and the performance of the new cloud-based distributed optimization algorithm with noise. We present simulation results to numerically verify the theoretical results presented.