CWI Intelligent and Autonomous Systems (IAS) Seminar

Introduction This is the webpage for the seminar of the Intelligent and Autonomous Systems (IAS) research group at CWI.


This is the webpage for the seminar of the Intelligent and Autonomous Systems (IAS) research group at CWI. For information or questions, please contact the current seminar organizer Michael Kaisers.

List of events

Date/Time/Location: February 6, 2017 / 3:30 pm / M390 

Mihail "Mike" Mihaylov
Smart Contracts for Smart Grids. A case study on NRGcoin.

Abstract: The emergence of Blockchain technology in 2009 has been compared to the rise of the Internet in the 90's. The Blockchain technology first disrupted the FinTech sector and is now making its way to the relatively new IoT and Smart Grid sectors. In 2015 a new variant emerged that allowed building decentralized software known as Smart Contracts. In this talk I will give an overview of bitcoin and blockchain technology and will explain the concept of a Smart Contract. I will then present this concept in the context of the Smart Grid, studying its advantages and drawbacks. As an example of a Smart Contract I will show a novel blockchain-based incentive mechanism, that I call NRGcoin.

Bio: Dr. Mihail Mihaylov is a senior research scientist at the Artificial Intelligence lab of the Vrije Universiteit Brussel, Belgium. His interests and work focus on renewable energy, smart grids and blockchain technology. In 2008 he obtained his M.Sc. degree in artificial intelligence with distinction from Maastricht University, The Netherlands and subsequently was awarded Leo Coolen Award for his thesis entitled "Computational Mechanism Design for Wireless Sensor Networks". In 2012 he obtained his Ph.D. degree in artificial intelligence with highest distinction from Vrije Universiteit Brussel, Belgium with his doctoral thesis "Decentralized Coordination in Multi-agent Systems". He then worked as a post-doctoral researcher in the University of Leuven in Ghent, Belgium for 1 year, and as a senior research scientist in Sensing & Control Systems in Barcelona, Spain for 2 years.

Date/Time/Location: February 1, 2017 / 3:00 pm / M390

Tim Baarslag
Pandora's Problem - a technique from search theory to deal with preference uncertainty

In this talk, I will introduce a problem from search theory called Pandora's Problem. The problem deals with optimizing reward while searching through boxes with uncertain prizes, which can be uncovered against certain costs. Pandora's Problem not only has a wide range of possible applications, it also has a surprisingly elegant and optimal solution. I will provide some intuition behind the solution and then show an application of this technique in the form of a negotiating agent that can adapt itself to the user by incrementally eliciting the user's preferences. This yields an optimal elicitation strategy that decides, at every stage of the negotiation, how much additional user information to extract while avoiding elicitation fatigue.

Date/Time/Location: January 20, 2017 / 3:00 pm / M390 

Speaker: Pablo Hernandez Leal
Title: A Survey of Learning in Multiagent Environments: Dealing with Non-Stationarity

Abstract: The key challenge in multiagent learning is learning the best response strategy that depends on the behaviour of other agents, and if these adapt their strategy the learning target moves. Disparate streams of research have approached non-stationarity from several angles, which make a variety of implicit assumptions that make it hard to keep an overview of the state of the art and to validate the innovation and significance of new works. This survey presents a coherent overview of work that addresses opponent-induced non-stationarity with tools from game theory, reinforcement learning and multi-armed bandits. Further, we reflect on the principle approaches how algorithms model and cope with this non-stationarity, arriving at five categories (in increasing order of sophistication): ignore, forget, respond to target models, learn models, and theory of mind . A wide range of state-of-the-art algorithms is classified into a taxonomy, using these categories and key characteristics of the environment (e.g., observability) and adaptation behaviour of the opponents (e.g., smooth, abrupt). To clarify even further we present illustrative variations of one domain, contrasting the strengths and limitations of each category. Finally, we discuss in which environments the different approaches yield most merit, and point to promising avenues of future research.

Date/Time/Location: October 7, 2016 / 13:30 am / M390 (DATE CHANGED)

Speaker: Felix Claessen (CEO of SEITA)
Efficient balancing by effort-based activation of demand response services

In future energy systems—with increased reliance on renewable generation—storage and demand response (DR) are crucial mechanisms for providing power system flexibility and balancing power. We present a unified model for flexibility services in the power system, identify two existing categories (ramping and loading) and introduce a new category (stalling). Each service is characterised by duration, capacity and effort, with associated prices. We show that the effort of stalling, measurable in kWh², is a significant cost component for balancing through storage and DR. Existing resource allocation mechanisms are mainly based on pricing in kW (for ramping) and in kWh (for load). Simulations demonstrate that conventional pricing mechanisms yield inefficient allocations of storage and DR resources for power balancing. In contrast, we show that introducing an additional pricing component in €/kWh² (for stalling) improves the allocation efficiency.

Bio: Felix Claessen is a former researcher at Centrum Wiskunde & Informatica (CWI) and the founder and CEO of SEITA, a CWI spin-off. His main research focus is on pricing mechanisms in the context of smart energy systems. He is currently pursuing a business application by developing pricing services for renewable energy suppliers.



Date/Time/Location: June 22, 2016 / 3pm / M390
Speaker: Daan Bloembergen (Postdoc at University of Liverpool)
Title: Evolutionary Dynamics of Multi-Agent Learning

Abstract: The interaction of multiple autonomous agents gives rise to highly dynamic and nondeterministic environments, contributing to the complexity in applications such as automated financial markets, smart grids, or robotics. The past two decades have seen the emergence of reinforcement learning, both in single and multi-agent settings, as a strong, robust and adaptive learning paradigm to deal with such complex tasks. An important challenge in the domain of multi-agent learning is to gain qualitative insights into the resulting system dynamics. Recently, tools and methods from evolutionary game theory have been successfully employed to study multi-agent learning dynamics formally in strategic interactions. This talk provides an overview of the dynamical models that have been derived for various multi-agent reinforcement learning algorithms, as well as the application of these models to compare different learning algorithms and to aid in parameter tuning. Furthermore, the evolutionary models can be used to study complex strategic interactions. Examples of such analysis are given for the domains of automated trading in stock markets and collision avoidance in multi-robot systems.

Bio: Daan Bloembergen is a postdoctoral research associate at the smARTLab of the Department of Computer Science, University of Liverpool, UK. He graduated from Maastricht University (NL) with a M.Sc. in Artificial Intelligence in 2010 and a subsequent Ph.D. in May 2015, where he worked on the project Analyzing Multiagent Learning, funded by the NWO (Netherlands Organisation for Scientific Research). His current research interests include studying the learning dynamics of multi-agent systems in general and multi-agent reinforcement learning and its relation to evolutionary game theory in particular. His main research focus is on the dynamics of (strategic) interactions between multiple self-interested learning agents. The theoretical analysis of (learning in) multi-agent interactions primarily relies on evolutionary game theory, and has application in complex real-world domains such as stock market trading and multi-robot systems.

Date/Time/Location: March 31, 2016 / 11:00 am / M390
Speaker: Frans Oliehoek (Lecturer at University of Liverpool)
Title: Multiagent Learning, Planning & Influences

Abstract: Multiagent systems (MASs) hold great promise as they potentially offer more efficient, robust and reliable solutions to a great variety of real-world problems. Consequently, multiagent planning and learning have been important research topics in artificial intelligence for nearly two decades. When talking about learning, however, relatively little research has addressed stochastic, partially observable environments where agents need to act based on only their individual observations and planning for such settings remains burdened by the curse of dimensionality. In this talk, I will give an overview of some approaches to multiagent learning and planning that I have pursued in recent years. A common thread in these is the attempt to capture the locality in the way that agents may influence one another. Formalizations of such influences have lead to vast improvements in planning tractability, and I will argue that they will be critical to the advancement of multiagent learning too.

Bio: Frans Oliehoek is Lecturer at the Department of Computer Science of the University of Liverpool and Researcher at the University of Amsterdam, from which he also obtained his PhD. He was Assistant Professor at Maastricht University and did postdocs at MIT and MU. Frans' research focuses on decision making under uncertainty, with emphasis on decentralized or multiagent systems. This includes many topics from related fields such as planning, reinforcement learning, optimization, machine learning, probabilistic inference and game theory. In his research, Frans investigates formal models and algorithms, as well as applications of those to challenging real-world tasks such as collaboration in multi-robot systems, optimization of traffic control systems, intelligent e-commerce agents, control of pumping stations, etc.

Date/Time/Location: February 17, 2016 / 11:00 am / M390
Speaker: Aliene van der Veen (Project member at Intelligent Systems Group, CWI)
Title: Valuation and valorisation of flexibility in energy retail, ahead and balancing markets

Abstract: Renewable and decentralized generation of energy is becoming more affordable, and is therefore increasingly adopted to match local demand in microgrids. In addition, storage or demand response abilities may be added to the microgrid, which facilitates intelligent energy management, typically to reduce costs of microgrid operation. We present an assessment of the profitability of intelligent microgrid operation for three different value propositions: increasing self-sufficiency under current retail tariffs, or participating in ahead and reserve market price fluctuations, specifically in Amsterdam, Berlin and Palermo. First, an upper bound valuation of flexibility (in eurocent/kWh) for the three value propositions is given. Second, we show a technology neutral profit analysis for selected technologies. Third, impediments limiting valorisation of the flexibility value and suggestions for feasible services are discussed. We found the highest potential in bilaterally negotiated innovative tariffs between flexible microgrids and existing market players, especially retailers with an existing large portfolio that dilutes the market participation costs and alleviates requirements such as minimal bid sizes.

Date/Time/Location: December 3, 2015 / 3:00 pm / M390
Speaker: Jasper Hoogland (PhD candidate at Intelligent Systems Group, CWI)
Title: Winning in Retail Market Games: Relative Profit and Logit Demand

Abstract: We examine retailers that maximize their relative profit, which is the (absolute) profit relative to the average profit of the other retailers. Customer behavior is modelled by a multinomial logit (MNL) demand model. Although retailers with low retail prices attract more customers than retailers with high retail prices, the retailer with the lowest retail price, according to this model, does not attract all the customers. We provide first and second order derivatives, and show that the relative profit, as a function of the retailer’s own price, has a unique local maximum. Our experiments show that relative profit maximizers “beat” absolute profit maximizers, i.e. they outperform absolute profit maximizers if the goal is to make a higher profit. These results provide insight into market simulation competitions, such as the Power TAC.

Date/Time/Location: October 12, 2015 / 4:00 pm / M390
Speaker: Micha Kahlen (PhD candidate at Rotterdam School of Management (RSM), Erasmus University Rotterdam)
Title: FleetPower: An Intelligent Trading Strategy to form Virtual Power Plants in Sustainable Smart Energy Markets

Abstract: A changing energy landscape with intermittent and distributed renewable energy sources puts pressure on the balance of the electric grid. To alleviate this pressure, we design and evaluate an intelligent trading agent that turns fleets of electric vehicles into virtual power plants. The agent draws on real-time locational information from 1,100 electric carsharing cars and reacts to energy market prices (ancillary service markets) to charge or discharge the electric cars. We analyze the economic feasibility of providing regulation power from these cars to offset the increased volatility caused by the large scale adoption of renewable energy sources. The study compares the agents ability to offset volatility from these energy sources across San Diego, Amsterdam, and Stuttgart because they have a different energy mix. We find limits on the charging infrastructure density, battery technology, and energy market price which are required to economically offer balancing capacity. We show that virtual power plants of electric vehicles create sustainable new revenue streams for electric vehicle rental companies without compromising their rental business. These enhanced revenue streams arise mostly from charging electric vehicles at a cheaper rate to absorb excess energy.

Date/Time/Location: April 14, 2015 / 10:00 am / M390
Speaker: Jasper Hoogland (PhD candidate at Intelligent Systems Group, CWI)
Title: An Effective Broker for the Power TAC 2014

Abstract: The Power TAC is a competition-based simulation of an electricity market. The goal of the competition is to test retailer (broker) strategies in a competitive environment. Participants create broker agents that trade electricity. In this paper we describe our broker, which we created as a participant of the 2014 Power TAC competition. We describe the strategies for two main components of the game: the tariff market and the wholesale market. We also discuss the performance of our broker in the competition, where we were second in the final ranking.

Title: Now, Later, or Both: a Closed-Form Optimal Decision for a Risk-Averse Buyer

Abstract: Motivated by the energy domain, we examine a risk-averse buyer that has to purchase a fixed quantity of a continuous good. The buyer has two opportunities to buy: now or later. The buyer can spread the quantity over the two timeslots in any way, as long as the total quantity remains the same. The current price is known, but the future price is not. It is well known that risk neutral buyers purchase in whichever timeslot they expect to be the cheapest, regardless of the uncertainty of the future price. Research suggests, however, that most people may in fact be risk-averse. If the future price is expected to be lower than the current price, but very uncertain, then they may prefer to purchase in the present, or spread the quantity over both timeslots. We describe a formal model with a uniform price distribution and a piecewise linear risk aversion function. We provide a theorem that states the optimal behavior as a closed-form expression, and we give a proof of this theorem.

Date/Time/Location: March 19, 2015 / 3:00 pm / M390
Speaker: Peter Palensky (Professor for intelligent electric power grids, Delft University of Technology)
Title: Modeling Intelligent Energy Systems

Abstract: Integrated energy systems are the next step towards a sustainable way of generating, distributing and using energy. The holistic design and operations of renewable, distributed energy sources of various nature with a variety of distribution and storage options and the end use bears unused optimization potential but also leads to difficult engineering questions. The diversity of the involved technologies, the different time ranges, and multiple dynamic internal and external interlinks lead to an unprecedented complexity that can not be dealt with traditional tools and methods. One way to work with such heterogeneous systems is by means of co-simulation, where domain-specific models are coupled, using specialized solvers and tools. To do so, continuous models have to interact with discrete and behavioral ones, each of them described and solved in an own, specialized way. This presentation will show the main problems in combining such cyber-physical energy models and how to solve them. 

Bio: Peter Palensky is Professor for intelligent electric power grids at TU Delft (Netherlands). Before that he was Principal Scientist for complex energy systems and Head of Business Unit "Sustainable Building Technologies" at the Austrian Institute of Technology, CTO of Envidatec Corp., Hamburg, Germany, associate Professor at the University of Pretoria, South Africa, Department of Electrical, Electronic and Computer Engineering, University Assistant at the Vienna University of Technology, Austria, and researcher at the Lawrence Berkeley National Laboratory, California. He is active in international committees like ISO, IEEE and CEN. He carries a PhD (EE, 2001) from the Vienna University of Technology and is an IEEE senior member. His research field is complex energy systems and smart grids. In his research he models, (co-)simulates and optimizes heterogeneous cyber-physical energy systems. The areas of optimization are stability, robustness, efficiency and control of smart grids. Mr. Palensky is associate editor for various IEEE Transactions and organizes the annual Workshop on Modeling and Simulation of Cyber-Physical Energy Systems.

Date/Time/Location: September 9, 2014 / 10:30 am [UPDATED TIME] / M390
Speaker: José L. Rueda (Assistant professor at Department of Electrical Sustainable Energy, Delft University of Technology)
Title: Mean-Variance Mapping Optimization for the Solution of Power System Problems

Abstract: Modern heuristic optimization algorithms have gained widespread use in recent years due to their conceptual simplicity and their ability to deal with different complex optimization problems. The mean-variance mapping optimization (MVMO) is a recent addition to these emerging tools. Its unique feature is a special mapping function used for mutating the offspring on the basis of mean and variance of the set comprising the n-best solutions attained so far and saved in a continually-updating archive. This presentation outlines the fundamentals behind MVMO and its possible extension from swarm intelligence viewpoint, and provides a survey of its application to four power system optimization tasks. Numerical results, which include performance comparisons with other heuristic optimizers, highlight the feasibility and effectiveness of MVMO.

Date/Time/Location: July 2, 2014 / 3:00 pm / M390
Speaker: Hoang Luong (PhD candidate at Intelligent Systems Group, CWI)
Title #1: Efficiency Enhancements for Evolutionary Capacity Planning in Distribution Grids
Title #2: Multi-objective Gene-pool Optimal Mixing Evolutionary Algorithms

Title #1: Efficiency Enhancements for Evolutionary Capacity Planning in Distribution Grids

Abstract: In this paper, we tackle the distribution network expansion planning (DNEP) problem by employing two evolutionary algorithms (EAs): the classical Genetic Algorithm (GA) and a linkage learning EA, specifically a Gene-pool Optimal Mixing Evolutionary Algorithm (GOMEA). We furthermore develop two efficiency-enhancement techniques for these two EAs for solving the DNEP problem: a restricted initialization mechanism to reduce the size of the explorable search space and a means to filter linkages (for GOMEA) to disregard linkage groups during genetic variation that are likely not useful. Experimental results on a benchmark network show that if we may assume that the optimal network will be very similar to the starting network, restricted initialization is generally useful for solving DNEP and moreover it becomes more beneficial to use the simple GA. However, in the more general setting where we cannot make the closeness assumption and the explorable search space becomes much larger, GOMEA outperforms the classical GA.

Title #2: Multi-objective Gene-pool Optimal Mixing Evolutionary Algorithms

Abstract: The recently introduced Gene-pool Optimal Mixing Evolutionary Algorithm (GOMEA), with a lean, but sufficient, linkage model and an efficient variation operator, has been shown to be a robust and efficient methodology for solving single objective (SO) optimization problems with superior performance compared to classic genetic algorithms (GAs) and estimation-of-distribution algorithms (EDAs). In this paper, we bring the strengths of GOMEAs to the multiobjective (MO) optimization realm. To this end, we modify the linkage learning procedure and the variation operator of GOMEAs to better suit the need of finding the whole Pareto-optimal front rather than a single best solution. Based on state-of-the-art studies on MOEAs, we further pinpoint and incorporate two other essential components for a scalable MO optimizer. First, the use of an elitist archive is beneficial for keeping track of non-dominated solutions when the main population size is limited. Second, clustering can be crucial if different parts of the Pareto-optimal front need to be handled differently. By combining these elements, we construct a multi-objective GOMEA (MO-GOMEA). Experimental results on various MO optimization problems confirm the capability and scalability of our MO-GOMEA that compare favorably with those of the well-known GA NSGA-II and the more recently introduced EDA mohBOA.

Date/Time/Location: June 2, 2014 / 11:00 am / M390

Speaker: Bart Liefers (Scientific Programmer at CWI)
 Market Garden: a Simulation Environment for Research and User Experience in Smart Grids
 Market Garden is a scalable research environment and demonstration tool, in which market mechanisms for smart energy systems and the interaction between end users, traders, system operators, and mar- kets can be simulated. Users can create scenarios in a user-friendly editor in which a hierarchical market architecture and a model of the physical grid can be defined. Individual market mechanisms are set up in a modular fashion, which means they can easily be coupled and interchanged. A visualiser in which the results can be explored in a graphical and intuitive way is included, making Market Garden very suitable for user experience and demonstration purposes.

Links: Paper, more background information

Date/Time/Location: May 7, 2014 / 3:00 pm / M390

Speaker: Rachael Morgan (PhD Candidate at The University of Queensland, Australia)
 Analysing and Characterising Optimization Problems with Length Scale
 Analysis of optimization problem landscapes is fundamental in the understanding and characterisation of problems and the subsequent practical performance of algorithms. In this talk I will be discussing a general framework for characterising black-box optimization problems based on the notion of length scale, which measures the change in objective function with respect to the distance between pairs of candidate solutions. Both discrete and continuous problems can be analysed using the framework, however in this talk I will present results on continuous problems from the Black-Box Optimization Benchmarking (BBOB) set and Circle-Packing.  In particular, I will compare the length scale framework with seven well-known landscape analysis techniques: Correlation Length, two variants of Fitness Distance Correlation, Dispersion, Information Content, Partial Information Content and Information Stability. I will also illustrate how the framework can be used to quantitatively asses problem similarity, as well as discuss potential extensions to the framework that may be used to compare algorithm performance/behaviour.

Date/Time/Location: April 23, 2013 / 3:00 pm / M390

Speaker: Jasper Hoogland (PhD candidate at Intelligent Systems Group, CWI)
 A Successful Broker Agent for Power TAC
The Power TAC simulates a smart grid energy market. In this simulation, broker agents compete for customers on a tariff market and trade energy on a wholesale market. It provides a platform for testing strategies of broker agents against other strategies. In this paper we describe the strategies of our broker agent. Amongst others, due to a beneficial trading technique related to equilibria in continuous auctions on the wholesale market and a strategy inspired by Tit-for-Tat in the Iterated Prisoner's Dilemma game on the tariff market, our broker ended second in the 2013 Power TAC.

Published at the 16th International Workshop on AgentMediated Electronic Commerce and Trading Agents Design and Analysis, held in conjunction with the Thirteenth International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS-2014), in Paris, France, on 5 May 2014.

Date/Time/Location: December 17, 2013 / 11:00 am / M390
Nicolas Honing (PhD candidate at Intelligent Systems Group, CWI)
Reducing electricity consumption peaks with parametrised dynamic pricing strategies given maximal unit prices
Demand response is a crucial mechanism for flattening of peak loads. For its implementation, we not only require consumers who react to price changes, but also intelligent strategies to select prices. We propose a parametrised meta-strategy for dynamic pricing and identify suitable strategies for given scenarios through offline optimisation using a population model. We also model an important and novel constraint: a price cap (a maximal unit price) for consumer protection. We show in computational simulations that the maximal unit price influences the peak reduction potential of dynamic pricing. We compare our dynamic pricing approach with a constant pricing approach and show that our approach, used by a profit-optimising seller, is both peak-reducing and equally profitable.

Date/Time/Location: June 28, 2013 / 15:00 / M390
Krzysztof Sadowski (Utrecht University & Intelligent Systems Group, CWI)
On the usefulness of linkage processing for solving MAX-SAT
 Mixing of partial solutions is a key mechanism used for creating new solutions in many Genetic Algorithms (GAs). However, this mixing can often be disruptive and generate improved solutions inefficiently. Exploring a problem's structure can help in establishing less disruptive operators, leading to more efficient mixing. One way of using a problem's structure is considering variable linkage information. Once a proper linkage model for a problem is obtained, mixing becomes more efficient. This paper focuses on exploring different methods of building family of subsets (FOS) linkage models, which are then used with the Gene-pool Optimal Mixing Evolutionary Algorithm (GOMEA) to solve MAX-SAT problems. Individual algorithms from the GOMEA family are distinguished by how the FOS linkage models are constructed. The Linkage Tree Genetic Algorithm (LTGA) is a GOMEA instance which learns the linkage between problem variables by building a linkage tree in every generation. In this paper, we introduce SAT-GOMEA. This algorithm uses a predetermined FOS linkage model based on the SAT-problem's definition. Both algorithms use linkage information. We show that because of this information they are capable of performing significantly better than other algorithms from the GOMEA family which do not explore linkage. In a black-box (BBO) setting, LTGA performs well. We further study the use of linkage models outside of the typical BBO approach by examining the behavior of LTGA and the problem-specific SAT-GOMEA in a white-box setting, where more of the problem information is known. We show that with this white-box optimization (WBO) approach, exploring linkage information can still be beneficial. We further compare the performance of these algorithms with a selection of non-GOMEA based algorithms. From the BBO perspective, we compare LTGA with the well-known hBOA. In the WBO setting, many very efficient problem-specific local search (LS) algorithm exist. We specifically consider Walksat and GSAT and show that combining LS with LTGA or SAT-GOMEA increases their performance.

Date/Time/Location: April 8, 2013 / 15:30 / M390
 Hado van Hasselt (Intelligent Systems Group, CWI)
Stacking Under Uncertainty: We Know How To Predict, But How Should We Act?
 We consider the problem of stacking containers in a given set of stacks of fixed maximum capacity when the pick-up times are stochastic with unknown probability distributions. The goal is to minimize the expected number of times a container is picked up while it is not at the top of its stack. We formulate several algorithms under varying assumptions about the available knowledge about the pick-up-time distributions. We distinguish four qualitatively different settings: 1) we know nothing about the actual distributions, 2) we have point estimates of the means, 3) we have point estimates of means and variances, or 4) we have historical samples of actual pick-up times. For each assumption we propose one or more algorithms. We test the algorithms empirically in many different scenarios, considering both sequential and concurrent arrivals. Additionally, we consider the computational complexity and ease of use of each algorithm.

Date/Time/Location: April 8, 2013 / 15:00 / M390
Speaker: Nicolas Höning (Intelligent Systems Group, CWI)
Title: Fast and revenue-oriented protection of radial LV cables with smart battery operation
Abstract: Low-voltage radial electricity cables will have more and more difficulties to carry the increasing load of novel consumption devices (e.g. electric vehicles) and the expected generated input of decentrally-generated power (e.g. from photovoltaic cells). One solution to avoid replacement is to install a battery at the end of a cable which is expected to be overloaded frequently. The intelligent operation of this battery needs to combine the protection of the cable with optimizing its revenue, in order to be economically viable. This paper formulates the offline optimization problem and proposes two robust heuristic online strategies. We show in computer simulations that these heuristics, which make fast just-in-time responses, reliably deliver good results. Our second heuristic reaches up to 83% of the approximated theoretical optimum.

Date/Time/Location: November 22, 2012 / 15:00 / L016
Speaker: Valentin Robu (Agents, Intelligence, Multimedia Research Group, University of Southampton)
Title: Online Mechanism Design for Dynamic Electric Vehicle Charging
Abstract: Plug-in hybrid electric vehicles are expected to place a considerable strain on local electricity distribution networks, requiring charging to be coordinated in order to accommodate capacity constraints. We design a novel online auction protocol for this problem, wherein vehicle owners use agents to bid for power and also state time windows in which a vehicle is available for charging. This is a multi-dimensional mechanism design domain, with owners having non-increasing marginal valuations for each subsequent unit of electricity. In our design, we couple a greedy allocation algorithm with the occasional cancellation of allocated power, in order to achieve monotonicity and thus truthfulness. We consider two variations: burning at each time step or on-departure. Both mechanisms are evaluated in depth, using data from a real-world trial of electric vehicles in the UK to simulate system dynamics and valuations. The mechanisms provide higher allocative efficiency than a fixed price system, are almost competitive with a standard scheduling heuristic which assumes non-strategic agents, and can sustain a substantially larger number of vehicles at the same per-owner fuel cost saving than a simple random scheme.