The Control Theory Seminar is at 3:30pm in Bechtel 240
|Sep-29||Paulo Tabuada, University of California, Los Angeles|
|Secure state-estimation and control for dynamical systems under adversarial attacks|
Control systems work silently in the background to support much of the critical infrastructure we have grown used to. Water distribution networks, sewer networks, gas and oil networks, and the power grid are just a few examples of critical infrastructure that rely on control systems for its normal operation. These systems are becoming increasingly networked both for distributed control and sensing, as well as for remote monitoring and reconfiguration. Unfortunately, once these systems become connected to the internet they become vulnerable to attacks that, although launched in the cyber domain, have for objective the manipulation of the physical domain. In this talk I will discuss the problem of state-estimation and control for linear dynamical systems when some of the sensor measurements are subject to an adversarial attack. I will show that a separation result holds so that controlling physical systems under active adversaries can be reduced to a state-estimation problem under active adversaries. I will characterize the maximal number of attacked sensors under which state estimation is possible and propose computationally feasible estimation algorithms. For this, I will use ideas from compressed sensing and error correction over the reals while exploiting the dynamical nature of the problem.
Paulo Tabuada was born in Lisbon, Portugal, one year after the Carnation Revolution. He received his "Licenciatura" degree in Aerospace Engineering from Instituto Superior Tecnico, Lisbon, Portugal in 1998 and his Ph.D. degree in Electrical and Computer Engineering in 2002 from the Institute for Systems and Robotics, a private research institute associated with Instituto Superior Tecnico. Between January 2002 and July 2003 he was a postdoctoral researcher at the University of Pennsylvania. After spending three years at the University of Notre Dame, as an Assistant Professor, he joined the Electrical Engineering Department at the University of California, Los Angeles, where he established and directs the Cyber-Physical Systems Laboratory.
Paulo Tabuada's contributions to cyber-physical systems have been recognized by multiple awards including the NSF CAREER award in 2005, the Donald P. Eckman award in 2009 and the George S. Axelby award in 2011. In 2009 he co-chaired the International Conference Hybrid Systems: Computation and Control (HSCC'09) and in 2012 he was program co-chair for the 3rd IFAC Workshop on Distributed Estimation and Control in Networked Systems (NecSys'12). He also served on the editorial board of the IEEE Embedded Systems Letters and the IEEE Transactions on Automatic Control. His latest book, on verification and control of hybrid systems, was published by Springer in 2009.
|Oct-6||Javad Lavaei, Columbia|
|Graph-Theoretic Algorithm for Arbitrary Polynomial Optimization Problems with Applications to Distributed Control, Power Systems, and Matrix Completion|
Optimization theory plays a crucial role in the design, analysis, control, and operation of real-world systems. The development of efficient optimization techniques and numerical algorithms for nonlinear optimization problems has been an active area of research for many years. The goal is to design an efficient, robust and scalable method for finding a global or near-global solution. This still remains as an open problem for the general class of polynomial optimization, including combinatorial optimization.
In this talk, we study a general polynomial optimization using a semidefinite programming (SDP) relaxation. The existence of a rank-1 matrix solution to the SDP relaxation enables the recovery of a global solution of the original problem. We propose a graph-theoretic technique to sparsify the optimization problem of interest such that its SDP relaxation will have a guaranteed low-rank solution. As a by-product, we show that every arbitrary polynomial optimization admits a sparse quadratic representation whose SDP relaxation has a matrix solution with rank at most 3. This result provides a basis for finding a near-global solution by approximating the rank-3 SDP solution with a rank-1 matrix.
In this talk, we apply our technique to three long-standing problems: optimal distributed control, power optimization problem, and low-rank matrix completion. We also offer more than 100K simulations for control and optimization over real-world power systems (such as Polish and New England systems). We verify that our algorithm usually finds solutions with global optimality degrees close to 99.9%. Since general-purpose SDP solvers can hardly accommodate sparse SDP problems with millions of parameters, we also propose a distributed algorithm whose iterations consist of only simple multiplication and eigenvalue decomposition over small-sized matrices.
|Oct-13||Lalitha Sankar, Arizona State University|
|Consequences of Cyber-attacks on the Electric Power System|
The electric power system is a complex network that is monitored and controlled by a distributed network of human-machine interfaced control systems. These cyber systems are just as vulnerable to sophisticated cyberattacks as are traditional networked information systems; however, the consequences of such attacks can be much severe for such critical infrastructure. Recent results on cyberattacks on the electric grid have demonstrated the design of unobservable attacks within the context of specific (cyber) processing units, notably state estimators. However, very little is known of the consequences of sophisticated and well-designed cyberattacks on the electric power system as a whole. Furthermore, a related open question is that of whether such attacks can be detected when the end-to-end cyber control system is taken into account. In this talk, we highlight our recent results towards addressing these questions including: (i) development of a time-progression model for cyber-functionalities in the electric power system that is essential for sophisticated and realistic attack and countermeasure design and testing; (ii) design of sophisticated unobservable attacks on state estimation with only local knowledge of the network topology; (iii) consequences of such unobservable attacks on real-time dispatch and control operations; and (iv) effect of such attacks on distributed EMSs.
Joint work with Jingwen Liang, Jiazi Zhang, Oliver Kosut, and Kory Hedman
|Oct-20||Pablo Parrilo, MIT|
|Partial facial reduction: simplified, equivalent SDPs via approximations of the PSD cone|
Many convex optimization problems arising in practice (particularly instances automatically generated by parsers) are not strictly feasible, i.e., the feasible set does not have an interior point. To this end, we develop a practical semidefinite programming (SDP) facial reduction procedure that utilizes computationally efficient approximations of the positive semidefinite cone. The proposed method simplifies SDPs with no strictly feasible solution (a frequent output of parsers like YALMIP or SOSTOOLS) by solving a sequence of easier optimization problems, and serves as a useful pre-processing technique for general SDP solvers. We demonstrate effectiveness of the method on SDPs from the literature, and describe our publicly-available software implementation. Joint work with Frank Permenter (MIT).
Preprint available at arXiv:1408.4685.
|Oct-27||Sayan Mitra, University of Illinois at Urbana-Champaign|
|From Simulations to Proofs|
Combining simulations with formal analysis can improve the design, verification, and validation processes for embedded and cyberphysical systems. In this talk, I will present an overview of the algorithms we have developed to derive bounded-time formal guarantees from numerical simulations and static analysis of models. These algorithms are targeted for hybrid models of distributed and cyberphysical systems and they require either implicit or explicit annotations. They are always sound and also complete for robust safety and temporal precedence properties. For large networked models, the annotations can be derived compositionally. I will mention the lessons learned and the outstanding challenges in applying them to verify a parallel landing protocol and a cardiac cell-pacemaker network.
Sayan an Associate Professor of Electrical and Computer Engineering at the University of Illinois at Urbana-Champaign. His research is onalgorithmic and software tools for design and analysis of distributed, embedded and cyber-physical systems. Sayan graduated from MIT in 2007 and spent one year as a post-doctoral researcher at CalTech. His received several Best paper awards, National Science Foundation's CAREER award, AFOSR Young Investigator Research Program Award, IEEE HKN Best paper award and IEEE-HKN C. Holmes MacDonald Outstanding Teaching Award.
|Nov-3||Ramesh Johari, Stanford|
|Can I Take a Peek? Continuous Monitoring of Online A/B Tests|
A/B testing is a hallmark of Internet services: from e-commerce sites to social networks to marketplaces, nearly all online services use randomized experiments as a mechanism to make better business decisions. Such tests are generally analyzed using classical frequentist statistical measures: p-values and confidence intervals. Despite their ubiquity, these reported values are computed under the assumption that the experimenter will not continuously monitor their test---in other words, there should be no repeated “peeking” at the results that affects the decision of whether to continue the test. On the other hand, one of the greatest benefits of advances in information technology, computational power, and visualization is precisely the fact that experimenters can watch experiments in progress, with greater granularity and insight over time than ever before.
We ask the question: if users will continuously monitor experiments, then what statistical methodology is appropriate for hypothesis testing, significance, and confidence intervals? We present recent work addressing this question. In particular, building from results in sequential hypothesis testing, we present analogues of classical frequentist statistical measures that are valid even though users are continuously monitoring the results. We also extend our results to multiple hypothesis testing.
Joint work with Leo Pekelis and David Walsh. (This work was carried out with Optimizely, a leading A/B testing platform.)
|Nov-10||Steven Low, Caltech|
|Design and Stability of Load-side Frequency Control|
Frequency control maintains the frequency of a power system tightly around its nominal value when demand or supply fluctuates. It is traditionally implemented on the generation side though load-side participation can offer advantages in fuel, emission, and responsiveness. We present a systematic method to design ubiquitous continuous fast-acting distributed load control for frequency regulation in power networks, by formulating an optimal load control (OLC) problem where the objective is to minimize the aggregate cost of tracking an operating point subject to power balance over the network. We prove that the swing dynamics and the branch power flows, coupled with frequency-based load control, serve as a distributed primal-dual algorithm to solve OLC. We show that load-side primary frequency control that rebalance power and resynchronize frequency can be implemented in a completely decentralized manner because the local frequency deviations at each bus convey exactly the right information about the global power imbalance for the loads to make individual decisions that turn out to be globally optimal. Load-side secondary frequency control that restores the nominal frequency can be implemented in a distributed manner using message passing among neighbors. Simulations show that the proposed algorithms also improve the transient performance.
(Joint work with Changhong Zhao, Enrique Mallada (Caltech), Ufuk Topcu (UPenn), Lina Li (Harvard))
|Nov-17||Kevin Murphy, Google|
|Extracting declarative and procedural knowledge from documents and videos on the web|
We describe how we built a very large probabilistic database of declarative facts, called "Knowledge Vault", by applying "machine reading" to the web. This approach extends previous work, such as NELL and YAGO, by leveraging existing knowledge bases as a form of "prior". We also discuss our new nascent efforts to extract procedural knowledge from videos on the web. This requires training visual detectors from weakly labeled data. We give an example where we attempt to interpret cooking videos by aligning the frames to the steps of a recipe.
Kevin Murphy is a research scientist at Google in Mountain View, California. Before joining Google in 2011, he was an associate professor of computer science and statistics at the University of British Columbia in Vancouver, Canada. Before starting at UBC in 2004, he was a postdoc at MIT. Kevin got his BA from U. Cambridge, his MEng from U. Pennsylvania, and his PhD from UC Berkeley. He has published over 80 papers in refereed conferences and journals related to machine learning and graphical models, as well as an 1100-page textbook called "Machine Learning: a Probabilistic Perspective" (MIT Press, 2012), which was awarded the 2013 DeGroot Prize. Kevin is also the (co) Editor-in-Chief of the Journal of Machine Learning Research.
|Nov-24||Marija Ilić, Carnegie Mellon University|
|Toward standards for dynamics in future electric energy systems: The basis for plug-and-play industry paradigm|
In this talk we propose that by revisiting the fundamental physics of interconnected electric power systems one can begin to think systematically about the role of both competitive and cooperative control, and their pros and cons for these rapidly evolving systems. We introduce somewhat new, dynamic systems view, of physical operation in several qualitatively different power grids (bulk power regulated; bulk power with markets; hybrid mix of emerging grids; micro-girds for developing countries; and micro-grids for developed countries). The physical operation dictates how to define internal states of given (groups of) physical components and the interaction variables between different (groups of) physical components. Based on understanding physical principles, we propose a new state space model of an interconnected grid comprising (groups of) different physical components. This model has a transparent physical interpretation, and, it is, therefore used as the basis for explicit performance specifications in terms of interactions of components. Performance specifications become standards for plug-and-play dynamic interactions of components (behavior) over several time horizons within an otherwise complex dynamical grid, which, when followed, ensure system-wide performance. We emphasize that the proposed approach is a framework for thinking about the necessary specifications in future electric energy systems, which enables both choice of technology at the (groups of) component levels and, minimal interaction specifications to align these with the performance of the over overall system. It is not a specific method. This framework could possibly overcome the roadblock of integrating distributed local grid technologies with the bulk power grid without running into major coordinating complexity. Specific proposed approaches to distributed control for smart grids are interpreted.
Dr. Marija Ilić holds a joint appointment at Carnegie Mellon as Professor of Electrical & Computer Engineering and Engineering & Public Policy, where she has been a tenured faculty member since October 2002. Dr. Ilić received her M.Sc. and D.Sc. degrees in Systems Science and Mathematics fromWashington University in St. Louis and earned her MEE and Dip. Ing. at the University of Belgrade. She is an IEEE Fellow and an IEEE distinguished lecturer, as well as a recipient of the First Presidential Young Investigator Award for Power Systems. In addition to her academic work, Dr. Ilić is a consultant for the electric power industry and the founder of New Electricity Transmission Software Solution, Inc. (NETSS, Inc.). From September 1999 until March 2001, Dr. Ilić was a Program Director for Control, Networks and Computational Intelligence at the National Science Foundation. Prior to her arrival at Carnegie Mellon, Dr. Ilić held the positions of Visiting Associate Professor and Senior Research Scientist at Massachusetts Institute of Technology. From 1986 to 1989, she was a tenured faculty member at the University of Illinois at Urbana-Champaign, where she taught since 1984. She has also taught at Cornell and Drexel. She has worked as a visiting researcher at General Electric and as a principal research engineer in Belgrade.
|Control Theory Seminar Series, Spring 2014|
|Control Theory Seminar Series, Fall 2013|