Game theory for electric vehicle charging

Electric vehicles (EVs) will play a vital role in decarbonizing road transportation. As society moves toward a more sustainable energy future, we anticipate that the population of EVs will steadily increase. So too will the energy requirements for charging all these vehicles, placing great strain on the electricity generation and supply infrastructure. We addressed an important aspect of this challenge by establishing a decentralized approach to optimally schedule EV charging, making the best use of the fleet of generators that supply the electricity grid. Namely, EV charging should be distributed across the overnight “valley” in electricity demand.

The total load of a power system varies continually throughout the day: low overnight, when most people are asleep, and high during the day’s commercial and industrial activities. The shape of this daily load variation differs from day to day, and across seasons and regions, but typically displays a peak around 6 to 8 p.m. when most people arrive home and enjoy their electricity-intensive evening activities. This peak
demand determines the number and size of power stations, or amount
of generation, that is needed.

It would be tempting for EV owners to start charging their vehicles as soon as they arrived home from their evening commute. However, that would add even more load to the evening peak, requiring more expensive generation to be brought into service. Many utilities currently offer incentives for EV owners to postpone charging until around 10 p.m., for example. This helps spread the total demand and achieves better utilization of generation, but as the number of EVs grows, this strategy may have the undesirable consequence of inducing a second peak. The ideal solution minimizes electricity generation cost by scheduling EV charging to exactly fill the overnight load valley.

One way of achieving the optimal valley-filling strategy would be for a central controller to tell every EV when it could charge and at what rate. Not only would this approach be computationally challenging, it would not likely be embraced by EV owners, who would probably prefer more autonomy. Instead, we have established a decentralized process in which the EV owners make autonomous charging decisions but do so in a way that exactly achieves the ideal solution, minimizing generation cost and stabilizing demand.

The decentralized EV charging control problem that we studied can be thought of as a form of non-cooperative game, in which a large number of self-interested EVs share electricity resources over the charging horizon (the evening hours). Our proposed process involves an iterative exchange between a central utility and each EV. The utility initially broadcasts a prediction of the non-EV base demand over the charging horizon. With this broadcast information available, each EV  independently determines its minimum-cost charging strategy. The utility collects these tentative charging strategies from all EVs, sums them to give the total aggregate EV demand over the horizon, and broadcasts that updated demand information back to all the EVs. This process repeats until the optimal charging strategies proposed by all the EVs no longer change.

In our process, the EVs interact through the common electricity price signal. We established conditions for the existence of a Nash equilibrium and proved that the decentralized (iterative) optimization process converges to the unique Nash equilibrium. Furthermore, we showed that this Nash equilibrium is, in fact, the optimal valley-filling strategy given by central optimization. A range of examples illustrates our main results, in particular the fast convergence rate of the iterative algorithm.

In order to establish rigorous results, we considered a fairly abstract version of the large-scale EV charging problem. In doing so, though, we laid a foundation for designing and analyzing emerging decentralized processes for determining optimal EV charging strategies. Future EV drivers may be able to provide their preferred charging hours to a system that optimizes for lowest cost, obtaining the best possible rates while also helping the overall grid by filling the demand valley efficiently.

“Decentralized Charging Control of Large Populations of Plugin Electric Vehicles,” published in the January 2013 issue of IEEE Transactions on Control Systems Technology, is the journal’s most  highly cited paper over the past five years.