DIMACS Workshop on Algorithmic Decision Theory for the Smart Grid

October 25 - 27, 2010
DIMACS Center, CoRE Building, Rutgers University

Organizers:
K. R. Krishnan, Telcordia, krk at research.telcordia.com
Linda Ness, Telcordia, lness at telcordia.com
Tom Reddington, Bell Labs, treddington at research.bell-labs.com
Presented under the auspices of the Special Focus on Algorithmic Decision Theory.


Abstracts:

Nabil Adam, DHS

Title: Cyber-physical Systems Security

Cyber-physical systems (CPS) are characterized by tight coupling and coordination among sensing, communications, computational and physical resources. CPS are typically exhibited in industrial control systems (ICS). ICS encompass several types of control systems, including supervisory control and data acquisition (SCADA) systems, and are prevalent in almost every critical infrastructure sector. It is envisioned that the complexity of the CPS of the future far exceeds today's CPS. For example, in the advance power grids of the future ? Smart Grid, a multitude of small to medium scale privately owned power generating and distribution systems, will be connected to the power grid. This talk presents a brief overview of the Department of Homeland Security's Science & Technology Directorate. Additionally, the presentation discusses DHS/S&T's Infrastructure and Geophysical Division's initiative in the emerging area of "Cyber-physical Systems Security" and some related research challenges will be presented.


Ehab Al-Shaer, University of North Carolina

Title: Non-invasive Security Evaluation of Smart Grid

Smart Grid (SG) is a complex system of many devices spanning both physical energy control and cyber systems. As complex systems usually breakdown in complex unexpected ways, it is necessary to investigate and predict attack scenarios on SG and assess their impact, in order to design security postures, countermeasures and polices that make SG resistant to new attacks. We describe our research effort to develop a tool that can statically investigate the compliance of smart grid networks (AMI) with security requirements, and determine the attack surface and impact.


Massoud Amin, University of Minnesota

Title: Non-invasive Security Evaluation of Smart Grid

Secure and reliable operation of complex interactive energy and power networks poses significant theoretical and practical challenges in sensing, analysis, modeling, simulation, prediction, control, and optimization. Mathematical models of such interactive systems are either vague or non-existent, and existing and classical methods of solution are either unavailable or not sufficiently powerful. A major R&D challenge is posed by the lack of a unified mathematical framework with robust tools for modeling, simulation, control and optimization of time-critical operations in smart electric power grids (spanning from fuel source to end-use) as complex multi-component and multi-scaled networks. Intelligent distributed control is required that would enable parts of the networks to remain operational and even automatically reconfigure in the event of local failures or threats of failure. The potential for rarely-occurring but high-impact cascading phenomena represents just one of many new science and technology concepts that are under development. We will present recent advances in distributed sensing, modeling, and control which may contribute toward the development of an effective, intelligent, distributed control of power system networks that achieve the overall objectives of efficiency, reliability, and robustness/survivability in the face of new and unanticipated operating conditions.


Sami Ayyorgun, Telcordia Technologies

Title: Cybersecurity, Modeling, and Optimization for Smart Grid

I will talk about our R&D projects focused on cybersecurity for electric power systems, modeling of Distributed Energy Resources (DERs) in the context of Smart Grid, and optimization for energy management systems. I will highlight a few use-cases to coherently bring the involved R&D to the foreground. I will also point out the some research directions concerning algorithms, control, and cyber-physical security.

Sami Ayyorgun, Telcordia Technologies

Title: Cyber Sub-Systems

I will talk about cyber sub-systems of Smart Grid broadly speaking, including those of metering, pricing, control, and management. I will highlight communications and networking involving those systems, and point out the R&D issues. I will share reflections from the perspectives of both an industry research-lab and a national organization with a cybersecurity charter (of which Telcordia is a member of the core team).


Dan Bienstock, Columbia University

Title: Continuing work on power grid vulnerability assessment

In this talk we will primarily focus on the development of real-time, distributed controls for mitigating cascading blackouts. We consider the cascading blackout models of Dobson et al, where a grid experiences an initial set of faults and progressively deteriorates as overloaded lines become faulted. We assume an (initially) slowly progressing cascade, so that there is time for centralized computing at the onset of the cascade. A control is then computed, which will be applied (in the form of load shedding) as the cascade evolves. If time permits, we will also touch on continuing work on the "N-K" problem using AC power flows.


Michael Chertkov, Los Alamos Laboratories

Title: Optimization and Control Theory for Smart (Power) Grid

A research project with this name has been started at LANL in Oct of 2009. In this talk I will report on the first results (specifically related to control) derived under the auspices of the project. In particular, I will discuss local control of Plug-in-Hybrid EV charging, local control of reactive generation in a Photo-Voltaic-rich feeder line, and control of rare events over medium-to-large (transmission level) grid. More info on this project (and the talk) can be found at http://cnls.lanl.gov/~chertkov/SmarterGrids/.

Michael Chertkov, Los Alamos Laboratories

I will attempt to classify possible problems and challenges in algorithmic decision theory (and related mathematical disciplines) for the power grid that the Nation and the World are facing.-->


Francisco De Leon, New York University

Title: Viewpoint of an Electrical Power Engineer

The presentation will start by describing a few of the real life Smart Grid applications currently under development in NYU-Poly. Examples will include how Distributed Generation (DG) can be interconnected to the distribution system, the maximum amount of DG that can be added without negatively affecting the reliability of the system (with and without communications), new ways of operating networks by switching and isolating problematic sections, and the use of the high controllability of power electronics devices to damp power oscillations. A discussion of the new ways to design an operate transmission and distribution systems together with recommendations on where to direct future research from the point of view of an electrical power engineer will conclude the presentation.

I'll offer recommendations on where to direct future research from the point of view of an electrical power engineer.


John Giacona, Consolidated Edison

Title: Con Edison's Smart Grid: Applying Emerging Technologies to Improve the Electrical System

Con Edison operates the world's largest underground electric system in one of the most congested and densely populated urban areas of the country. The challenges of operating the electrical system include the amount of system condition data available and the number of disparate systems generating data. The Smart Grid Project will demonstrate enhanced monitoring and control capabilities of field assets and the development of intelligent analysis tools to assist system operators with identifying problems, prioritizing corrective actions, and optimizing assets. The project will leverage field assets which can be used to curtail system loads, such as distributed generation (DG), electric vehicles (EV), battery storage, building management systems (BMS), and home area networks (HAN), to enhance system reliability.


Daniel Hurley, Jr., Dept. of Commerce

Title: Communications and Electric Power Sectors - Need for Common Operating Picture and Tools for Situational Awareness

The Communications Dependency on Electric Power (CDEP) Report on Long-Term Outages has a section devoted to Situation Awareness tools used by either the communications or the electric power sectors. Such tools, if made available to representatives from both sectors, e.g., in a state Emergency Operations Center, could afford insights and "heads up" alerts for the other sector. The CDEP report also addresses challenges faced respectively by the two sectors, which will be exacerbated by natural disasters or man-made incidents affecting the control systems in increasingly technologically advanced networks and grids, e.g., SCADA. This talk will provide perspectives on the similarities and differences between the organization and information flows in the two sectors, assist in understanding how the awareness tools can be useful, and help these sectors respond to the challenges from such events.


Peter Jones, Yale University

Title: Some New Methodologies for Numerical Analysis of Network Data

We present two new methods for fast analysis of data arising from Networks. The first result discussed is a method for processing any temporal data (of any dimension) that is "positive", for the purpose of detecting different types of volatility, burstiness, or spikes. The second result discussed is a new, fast (approximate) nearest neighbor solver for any data set that is naturally embedded in Euclidean space. Coauthors are (1) Devasis Bassu, Linda Ness, and Vladimir Rokhlin, and (2) Andrei Osipov and Vladimir Rokhlin.


Peter Jones, Yale University

Title: Methodologies and Algorithms for the Analysis of Network Traffic

We will discuss problems and methodologies for the general problem of (rapidly) analyzing various types of network traffic. Particular stress will be put on problems where one requires fast algorithms that can function in a high dimensional, streaming environment.


Himanshu Khurana, University of Illinois

Title: Application-Driven Design for Resilient Electric Grid Systems

In this talk we explore requirements, challenges and solutions for design and development of resilient electric grid systems. This exploration studies several representative grid systems and applications ranging from SCADA and wide area measurement systems to advanced metering infrastructure. For these various applications, we consider challenges and discuss solutions in areas of authentication, key management and intrusion detection/response. In addition, we explore architectural constructs and properties that are aimed at realizing resilient grid systems.


Vladimir Kolesnikov, Bell Labs

Title: Cryptographic Tools for Smart Grid Privacy

Smart Grid promises dramatic efficiency improvements and savings by the new capability to leverage real-time data collected from sensors, AMI, homes, electric vehicles, and other grid entities. At the same time, we must be careful about how this information is collected and used, due to strong privacy violations it may cause. For example, home electricity load patterns can easily identify a person's habits and even brands and state of repair of household appliances. In this talk I will discuss several potential Smart Grid privacy issues, as well as cryptographic techniques that can be used to mitigate them.


Steven Low, Caltech

Title: Optimal Power Flow Problems

We solve the Optimal Power Flow (OPF) problem through dual relaxation. A sufficient condition under which the dual solution is exact is satisfied by standard IEEE benchmark systems with 14, 30, 57, 118 and 300 buses, when a small resistance is added to transformers originally assumed to have zero resistance. In integrating renewable energy (such as wind power) into the electric grid, difficulties due to source-intermittency, demand-fluctuations, and large distances between generation sites and users can be overcome with a transmission network with large-scale storage. For the special case of a single generator and a single load, we prove that the optimal generation schedule for the finite-horizon OPF problem with storage initially generates more than the demand, in order to charge up the battery, and then generates less than the demand and uses the battery to supplement generation in the final stages. (Joint work with Mani Chandy, Javad Lavaei, Ufuk Topcu, Mumu Xu).


Steve McLaughlin, Penn State University

Title: Multi-vendor Penetration-Testing in the Advanced Metering Infrastructure: Identifying Future Challenges

Intelligent AMI "smart meters" report real time usage data that enables efficient energy generation and use. However, new devices from a dizzying array of vendors are being introduced into grids with limited understanding of the security problems they represent. In this talk, we develop an archetypal attack-tree approach to guide penetration-testing across multiple-vendor implementations, and apply this approach to model attacker goals (such as energy fraud and denial of service) and to identify the security challenges present in AMI. We show how efforts in penetration-testing can be reused to efficiently evaluate the increasingly large body of AMI technologies being deployed in the field.


Sanjai Narain, Telcordia Technologies

Title: Towards a science of infrastructure configuration

Configuration is the glue for logically integrating components to satisfy end-to-end requirements on cyberinfrastructure. Today, the large gap between requirements and configurations is manually bridged. As a result, large numbers of configuration errors are made. It is well-documented that such errors are responsible for 50%-80% of infrastructure vulnerabilities and downtime. This talk outlines the fundamental problems to be solved for eliminating configuration errors: specification, diagnosis, repair, synthesis, verification and reconfiguration planning. The talk then outlines how modern formal methods are used to solve these problems, and how the solutions can be used to analyze and resolve vulnerabilities in cyberphysical infrastructure.


Warren Powell, Princeton University

Title: Stochastic optimization in energy systems analysis

There are a variety of problems in energy systems analysis that require that we make decisions over time about storing energy, operating generating plants, and investing in new technologies under different sources of uncertainty. A survey of the energy systems literature reveals considerable confusion when modeling the problem of making decisions over time under uncertainty, such as the subtle distinction between variability and uncertainty. The academic community does not help the matter, often burying simple ideas under a profusion of mathematics. I will offer a simple, elegant modeling and algorithmic framework that provides clear but precise modeling of stochastic optimization problems, illustrated in the context of problems in energy systems analysis. I introduce the idea of policy optimization, and describe four fundamental classes of policies that should cover the needs of any problem that arises in practice. These are illustrated in specific applications in energy systems.


Jim Reilly, Reilly Associates

Title: Real-time Data for System Protection and System Restoration

Examples of the use of real-time data from phasor measurement units for system protection and system restoration will be presented: (a) a protection scheme for islanding, utilizing phase angle measurements, which prevented a cascading outage; (b) the use of phasor measurement units for detecting and managing an electrical island. The decisions of system operators in both situations will be described, as well as possibilities for automation of the decision-making process.


Jim Reilly, Reilly Associates

Title: Challenges of Generation from Renewable Energy for Transmission and Distribution Operations

Several aspects of the smart grid will be described: integrating generation from renewable energy sources into transmission and distribution networks, and the associated operational challenges; new measurement technologies, such as synchrophasors, for state estimation and energy management; improvements to under-frequency load shedding, intentional islanding, and micro grids.


Fred Roberts, DIMACS

Title: Introduction and Overview of Algorithmic Decision Theory

Today's decision makers in fields ranging from engineering to medicine to economics to homeland security have available to them remarkable new technologies, huge amounts of information to help them reach good decisions, and the ability to share information at unprecedented speeds and quantities. These tools and resources will enable better decisions if we can surmount concomitant challenges: the massive amounts of data available are often incomplete or unreliable or distributed and there is great uncertainty in them; interoperating/distributed decision makers and decision-making devices need to be coordinated; many sources of data need to be fused into a good decision, often in a remarkably short time; decisions must be made in dynamic environments based on partial information; there is heightened risk due to extreme consequences of poor decisions; decision makers must understand complex, multi-disciplinary problems. When faced with such issues, decision makers have few highly efficient algorithms available to support decisions. There is a long tradition of algorithmic methods in logistics and planning, but algorithms to automate, speed up and improve real-time decision making are much less common. Algorithms for decision support, especially algorithms that can approximate good analytic solutions, are needed. Our objective is to improve the ability of decision makers (human or automated) in the face of these new opportunities and challenges by exploiting algorithmic methods. The goal of the field coming to be known as Algorithmic Decision Theory (ADT}) is to explore and develop algorithmic approaches to decision problems arising in a variety of application areas as motivated by the above issues. An overview of ADT will be presented, together with some comments on the connection between ADT and smart grid.


Tariq Samad, Honeywell

Title: Optimization, control, and monitoring for smart grid consumers

I will discuss the need for algorithmic approaches "beyond the meter"- for homes, buildings, and industrial consumers. Energy management systems, whether as stand-alone platforms or embedded in other systems, whether inpremises or in the cloud, would enable consumers to maximize energy efficiency, reduce energy and electricity costs, help utilities shave peak load, integrate distributed generation and storage, detect equipment failures, and more. Several such benefits are already being realized by industrial and commercial customers. With the development of the smart grid, penetration in these sectors will increase and will also reach residential consumers. Technical challenges related to optimization, control, and monitoring for energy management will be noted.


Marina Thottan, Bell Labs

Title: A Secure Decentralized Data-centric Information Infrastructure for Smart Grid

In recent years the power grid has been undergoing transformative changes due to the greater penetration of renewable energy sources and increased focus on power demand shaping. These innovative transformations on the grid require a flexible IP-based communication grid that is reliable and secure. In this talk I will describe an IP-based decentralized and data-centric information infrastructure that can reliably, securely, and cost-effectively support the operation and innovative applications of the next generation grid. The work presented here will pave the way for a future data-centric power network infrastructure.


Dave Waltz, Columbia University

Title: Using historical and real-time data to optimize reliability for power distribution

For the foreseeable future the smart grid will largely consist of components of the current grid. Reengineering, component replacement and maintenance policies are critical for maintaining -- and hopefully improving --operating reliability. This talk will describe fielded R&D work to use machine learning and data mining methods to model reliability (MTBF) for systems (feeders, secondary systems) and components (cables, joints, transformers, connectors, etc.), and systems built that use these models to generate optimal engineering plans, and identify at-risk parts of the system in real time.


Jean-Paul Watson, Sandia National Laboratories

Title: Computational Challenges in Large-Scale Optimization for Grid Operations and Planning

Stochastic optimization plays an increasingly central role in grid operations and planning models, particularly given production uncertainty surrounding renewable sources. Coupled with growing emphasis on reliability and security constraints, such models are notoriously difficult to deal with computationally. In this talk, we discuss two key computational aspects concerning the solution of these models. First, we discuss the state-of-the-art in solver scalability on representative stochastic mixed-discrete programming models, focusing on current performance limits for decomposition-based algorithms given large numbers of scenarios. Second, we explore the problem of establishing confidence intervals on obtained solution quality in these models, in an attempt to answer the question: How many scenarios are required to obtain a solution that we are reasonably confident is close to optimal?

Jean-Paul Watson, Sandia National Laboratories

I will discuss the algorithmic challenges underlying many key operations and planning models for the national grid, stemming from practical drivers including high renewables penetration, improved security, and enhanced reliability


David Wollman, NIST

Title: Smart Grid Challenges: Standards, Measurements and Security

The Smart Grid will improve the reliability and efficiency of the nation's electric power grid by incorporating communications, distributed computing, and new measurement capabilities, while enabling integration of distributed renewable energy sources and electric transportation and reducing energy usage through intelligence and automation. This talk will outline some of the challenges, such as the development of interoperability and security standards and distributed measurements for management and control, and describe NIST's multidisciplinary Smart Grid Program for coordination of interoperability standards and new metrology research for power and energy, including measurements and calibrations for Phasor Measurement Units to enable wide area situational awareness.

David Wollman, NIST

Title: Accelerating Standards to Support Smart Grid Interoperability

Under the Energy Independence and Security Act of 2007, NIST has the "primary responsibility to coordinate development of a framework that includes protocols and model standards for information management to achieve interoperability of Smart Grid devices and systems?" To support Smart Grid interoperability and security, NIST has implemented a three-phase plan to formulate an initial set of standards and to establish a robust framework for developing the additional standards and conformity testing that are needed. The Framework and Roadmap for Smart Grid Interoperability Standards, Release 1.0, was published in final form in January 2010. To support the continuing evolution of the framework, NIST has established the Smart Grid Interoperability Panel (SGIP), a public-private partnership with over 500 organizations in 22 stakeholder categories. The Cyber Security Working Group of SGIP has developed a cyber security risk mitigation strategy for the Smart Grid with identified domain-specific and common requirements to ensure interoperability of solutions across different domains/components of the infrastructure.

David Wollman, NIST

Title: Next Steps for Smart Grid Standards, Measurements and Security

To support progress toward the new Smart Grid, measurement and control infrastructure and algorithms must be developed to enable future automated secure management of the power grid with increasing use of variable renewable resources such as wind and solar. Additional emphasis is needed to increase consumer participation, to modify and reduce their energy usage based on electricity prices or demand response signals, including implementation of data exchange standards for consumer energy usage. New load-forecasting methods will be needed that take account of the ability of energy-using devices to vary their operations based on grid conditions. Strategies for managing the charging of electric vehicles will be critical, to avoid overloads on local distribution grids during peak periods. Modeling, forecasting, and control strategies that reflect these new paradigms will be essential to realizing the environmental and energy efficiency benefits of the Smart Grid.


Edmund Yeh, Yale University

Title: Cascading Failure in Power Networks: a Percolation-Based Analysis

In electrical power networks, cascading failure associated with power blackouts often result from a small number of initial line failures triggering a global failure event affecting the whole network, inflicting enormous socioeconomic cost. In spite of the increasing frequency of blackout events, there is still a shortage of understanding regarding the structures and properties which lend the network susceptible to cascading failure. We show how the theory of percolation can be used to analyze the problem of cascading failure from a network perspective. For large-scale networks modeled by random geometric graphs, we use a simple but descriptive model to show that the cascading failure problem is equivalent to a dependent percolation process. Within this context, we obtain analytical conditions for the occurrence and non-occurrence of cascading failure, respectively.


Previous: Program
Workshop Index
DIMACS Homepage
Contacting the Center
Document last modified on September 2, 2010.