Quick links: Dual dynamic programmingPolynomial optimizationMobility systemsPower systems

Duality in dynamic programming theory

Collaborators: Paul Beuchat, Ben Flamm, Annika Eichler, Marc Hohmann, John Lygeros

Dynamic programming problems become exponentially more expensive to solve as the dimension of the state and action spaces grow. In continuous spaces, most existing methods rely either on discretization of the spaces or on approximating the value function as a linear combination of pre-selected basis functions.

This work has focused on solving nonlinear optimal control problems by finding novel applications of the long-established generalized Benders decomposition. This theory allows information learnt from a single simulation to be generalized to the rest of the state space. The result is a value function approximation expressed as a pointwise maximum – an approach commonly encountered in so-called dual dynamic programming, and typically applied in complex hydro power planning problems.

Relevant publications

  • Learning continuous Q-functions using generalized Benders cuts, European Control Conference in Naples, Italy, June 2019. Available on arXiv.
  • Generalized Dual Dynamic Programming for Infinite Horizon Problems on Continuous State and Action Spaces, IEEE Transations on Automatic Control, 2019. Available on arXiv. Publisher link
  • Point-wise maximum approach to approximate dynamic programming, CDC, 2017. Publisher link

Polynomial/moment optimization for energy systems

Collaborators: Marc Hohmann, John Lygeros

Many energy systems, such as electrical power grids and district heating networks, can be modelled as systems subject to polynomial constraints. For example, a transmission line’s voltages and currents are related by quadratic equality constraints, and a water pipe’s energy transfer is governed by the product of the mass flow rate and the temperature drop.

Decision problems involving polynomial constraints are generally very difficult to solve, and only recently has the theory of polynomial optimization, particularly the so-called moment/sum-of-squares (MSOS) hierarchy, been applied to energy systems. This theory allows a polynomial decision problem to be converted into a convex optimization problem in a larger number of variables, rendering it tractable. Many exciting problems can be cast in the MSOS framework.

This work, driven by Marc Hohmann’s PhD research, has (i) developed MSOS-based approaches to creating high-fidelity linearized models of power systems, which explicitly account for uncertainty of the operating conditions of the network; and (ii) derived optimal operating policies for district heating networks.

Relevant publications

  • Optimal linearizations of power systems with uncertain supply and demand, IEEE Transactions on Power Systems, 2019. Available on arXiv. Publisher link
  • A two-stage polynomial approach to stochastic optimization of district heating networks Sustainable Energy, Grids and Networks (SEGAN), 2019. Available on arXiv. Publisher link

Real-time control of smart mobility systems

Map of bike sharing stations of Philadelphia

Collaborators: Dominik Ruchti, Julius Pfrommer, Georg Schildbach, Claudio Ruch

A new generation of shared mobility systems, including bicycles, cars, and scooters, offers flexible, low-cost transport options to consumers in urban areas. However, they must be managed actively using paid personnel to overcome imbalances between supply and demand. By shifting shared vehicles from overcrowded locations to areas where they are in short supply, known as “rebalancing,” the operator can maximize the number of customers able to make use of the service. The same principle applies in the emerging area of autonomous mobility systems, where a fleet of self-driving cars positions itself around a city in order to serve ride-hailing customers.

This work has devised new algorithms for making these rebalancing decisions in real time, given an estimate of the current state of the system and an uncertain forecast of future demand. We studied the design of user incentives to make “system friendly” journeys, by paying a user travelling from location A to B to instead end the journey at some other nearby flocation C. The aggregate effect of these incentives was shown to be competitive with conventional staff-based rebalancing, particularly at weekends in a large city like London.

More recently, we have used two-stage stochastic approximation to deal with a fully stochastic model of customer actions, and derived a real-time computable policy based on approximating the value of adding or subtracting shared vehicles in different locations at different times. This so-called approximate value function was then used to determine near-optimal rebalancing actions on the part of staff.

Relevant publications

  • Two-stage stochastic approximation for dynamic rebalancing of shared mobility systems, to appear in Transportation Research Part C in 2019. Available on arXiv.
  • Dynamic vehicle redistribution and online price incentives in shared mobility systems, IEEE Transactions on Intelligent Transportation Systems, 2014. Publisher link

Real-time power system optimization under uncertainty

UK Met Office probabilistic wind speed forecast

Collaborators: Tyler Summers, Daniel Drew, Paul Goulart, Manfred Morari

Electrical power systems are operated in the face of high-dimensional uncertainty arising from fluctuating wind and solar power infeeds, in addition to demand. Modern numerical weather forecasts generate gigabytes of data every few hours, which should in principle help predict the range of renewable power to be accommodated. However, feeding this large quantity of forecast data through to power system operations is challenging.

This work has devised new algorithms for capturing ranges and correlations in raw “ensemble” weather forecast data, in which multiple equally plausible scenarios are generated from a probabilistic weather model. The forecast atmospheric behaviour is condensed into low-dimensional modes, which then form a parameterization of the way conventional generators should react to the weather as it unfolds. The effect is a generalization of the well-known Automatic Generator Control signal into a superposition of several regional signals.

Earlier work from my PhD defined the concept of a multistage reserve policy, which is a multi-hour look-ahead plan governing each generator’s response to shortfalls or excesses of energy on the system. The approach is particularly beneficial when controlling batteries and hydro power facilities, as the capture and release of energy is planned in a more rigorous manner against forecasts.

Relevant publications

  • Low-dimensional space- and time-coupled power system control policies driven by high-dimensional ensemble weather forecasts, IEEE Control Systems Letters, 2018. Publisher link
  • Policy-based reserves for power systems, IEEE Transactions on Power Systems, 2013. Publisher link
  • Stochastic optimal power flow based on conditional value at risk and distributional robustness, International Journal of Electrical Power and Energy Systems, 2015. Publisher link