Thursday, June 28th, 2018

From the Inside: Real-Time Decision Making

by Richard Karp, UC Berkeley

This program sought to develop and apply algorithmic methods for the control of systems characterized by the need to make real-time decisions based on data arriving in high volume. The program focused in particular on astronomical observation, transportation networks, online matching markets, and smart energy grids. Theoretical advances in streaming algorithms; distributed algorithms; machine learning; database management; analysis of heterogeneous, noisy and unformatted high-dimensional data; information theory; control theory; and optimization are required if we are to meet the challenges of these and related application domains. 

This program began with a boot camp intended to acquaint program participants with the key themes of the program, including applications of control theory, machine learning, streaming algorithms and sublinear algorithms to robotic astronomy, early earthquake warning, the Large Hadron Collider, urban transportation, and control of the energy grid.

Major landmarks of the program were the three week-long workshops, focusing respectively on applications in the natural sciences and physical systems, societal networks and mathematical and computational challenges. The program also featured a weekly general seminar, and a weekly energy systems seminar. In the course of the semester there were several open-problems discussions, and research groups met regularly on topics such as verification of cyber-physical systems, reinforcement learning and stochastic approximation.

Workshop 1: Applications in the Natural Sciences and Physical Systems 
This workshop focused on real-time discovery and inference from instruments such as astronomical telescopes, light sources, high-energy physics particle trackers, brain-machine interfaces, earthquake detectors and environmental sensors. Increasingly, such inferences from large volumes of complex data must be acted on with very little or no human cognition in the loop, due to the real-time requirements of the experiment or feedback from the observations. This workshop explored the computational requirements of such applications, with particular emphasis on new techniques for handling these challenges including workflow design, machine learning and novel computational architectures. One outcome of the workshop was a line of research on allocating telescope resources to maximize the probability of detecting supernovae and other astronomical phenomena.

Workshop 2: Societal Networks
Societal networks are the engineering subsystems underlying cities and nations; for example, transportation networks, energy grids, housing/hoteling systems, and water and waste management systems. They play a vital role in the daily lives of citizens and businesses. Massive trends in technology and new business models are shaping Societal Networks, redefining the way they will be built and operated in the future, which, in turn, will impact the way people live, commute, shop, trade and are entertained.

A prevalent theme of this workshop was the use of machine learning, control theory, game theory, market design, pricing and incentives in the management of these urban systems. The workshop was followed by an additional one-day symposium bringing together industry speakers and academics to share their vision of where industry is heading in the 5-6-year horizon and the technological advances as well as business innovations needed to realize the vision.

Workshop 3: Mathematical and Computational Challenges in Real-Time Decision Making
This workshop served as a capstone to the program, by exploring the mathematical disciplines that underlie the applications arising in physical systems, urban systems, transportation and energy. The focus was on optimization, machine learning and sublinear and streaming algorithms, with illustrative applications ranging from bike sharing to Internet advertisement placement.

Traffic control was a major theme of the program. In an Open Lecture, Balaji Prabhakar described a framework for designing "nudge engines," focusing on influencing commuter behavior to reduce urban congestion. The framework consists of monetarily incentivizing commuters to make off-peak trips using random, lottery-like rewards, and using data to provide "personalized nudges."  He showed how these ideas work using results from a series of pilots conducted in Bangalore, at Stanford, and in Singapore.

Hamidreza Tavafoghi and Demosthenis Teneketzis showed that it is sometimes not optimal to provide perfect information to drivers in a traffic network. They showed that overall congestion can be improved by disclosing non-identical but correlated partial imperfect information to the drivers.

A very active weekly seminar focused on management of the resources of the energy grid, where managing the supply-demand balance of electric power involves not only controllable generators but uncertainties, due to unpredictable consumer demand and volatile sources of inexpensive energy from the wind and sun.

Related Articles