Alex Rogers

AAMAS Conference 2019 Conference Paper

Multi-Agent Hierarchical Reinforcement Learning with Dynamic Termination

• Dongge Han
• Wendelin Boehmer
• Michael Wooldridge
• Alex Rogers

In a multi-agent system, an agent’s optimal policy will typically depend on the policies of other agents. Predicting the behaviours of others, and responding promptly to changes in such behaviours, is therefore a key issue in multi-agent systems research. One obvious possibility is for each agent to broadcast their current intention, for example, the currently executed option in a hierarchical RL framework. However, this approach results in inflexible agents when options have an extended duration. While adjusting the executed option at each step improves flexibility from a single-agent perspective, frequent changes in options can induce inconsistency between an agent’s actual behaviour and its broadcasted intention. In order to balance flexibility and predictability, we propose a dynamic termination Bellman equation that allows the agents to flexibly terminate their options.

TIST Journal 2017 Journal Article

A Comfort-Based Approach to Smart Heating and Air Conditioning

• Frederik Auffenberg
• Stephen Snow
• Sebastian Stein
• Alex Rogers

In this article, we address the interrelated challenges of predicting user comfort and using this to reduce energy consumption in smart heating, ventilation, and air conditioning (HVAC) systems. At present, such systems use simple models of user comfort when deciding on a set-point temperature. Being built using broad population statistics, these models generally fail to represent individual users’ preferences, resulting in poor estimates of the users’ preferred temperatures. To address this issue, we propose the Bayesian Comfort Model (BCM). This personalised thermal comfort model uses a Bayesian network to learn from a user’s feedback, allowing it to adapt to the users’ individual preferences over time. We further propose an alternative to the ASHRAE 7-point scale used to assess user comfort. Using this model, we create an optimal HVAC control algorithm that minimizes energy consumption while preserving user comfort. Through an empirical evaluation based on the ASHRAE RP-884 dataset and data collected in a separate deployment by us, we show that our model is consistently 13.2% to 25.8% more accurate than current models and how using our alternative comfort scale can increase our model’s accuracy. Through simulations we show that using this model, our HVAC control algorithm can reduce energy consumption by 7.3% to 13.5% while decreasing user discomfort by 24.8% simultaneously.

TIST Journal 2017 Journal Article

Advanced Economic Control of Electricity-Based Space Heating Systems in Domestic Coalitions with Shared Intermittent Energy Resources

• Athanasios Aris Panagopoulos
• Sasan Maleki
• Alex Rogers
• Matteo Venanzi
• Nicholas R. Jennings

Over the past few years, Domestic Heating Automation Systems (DHASs) that optimize the domestic space heating control process with minimum user input, utilizing appropriate occupancy prediction technology, have emerged as commercial products (e.g., the smart thermostats from Nest and Honeywell). At the same time, many houses are being equipped with, potentially grid-connected, Intermittent Energy Resources (IERs), such as rooftop photovoltaic systems and/or small wind turbine generators. Now, in many regions of the world, such houses can sell energy to the grid but at a lower price than the price of buying it. In this context, and given the anticipated increase in electrification of heating, the next generation DHASs need to incorporate Advanced Economic Control (AEC). Such AEC can exploit the energy buffer that heating loads provide, in order to shift the consumption of electricity-based heating systems to follow the intermittent energy generation of the house. By so doing, the energy imported from the grid can be minimized and considerable monetary gains for the household can be achieved, without affecting the occupants’ schedule. These benefits can be amplified still further in domestic coalitions, where a number of houses come together and share their IER generation to minimize their cumulative grid energy import. Given the above, in this work we extend a state-of-the-art DHAS, to propose AdaHeat+, a practical DHAS, that, for the first time, incorporates AEC. Our work is applicable to both individual houses and domestic coalitions and comes complete with an allocation mechanism to share the coalition gains. Importantly, we propose an effective heuristic heating schedule planning approach for collective AEC that (i) has a complexity that scales in a linear and parallelizable manner with the coalition size, and (ii) enables AdaHeat+ to handle the distinct preferences, in balancing heating cost and thermal discomfort, of the households. Our approach relies on stochastic IER power output predictions. In this context, we propose a simple and effective formulation for the site-specific calibration of such predictions based on adaptive Gaussian process modeling. Finally, we demonstrate the effectiveness of AdaHeat+ through real data evaluation, to show that collective AEC can improve heating cost-efficiency by up to 60%, compared to independent AEC (and even more when compared to no-AEC).

IJCAI Conference 2017 Conference Paper

Bayesian Aggregation of Categorical Distributions with Applications in Crowdsourcing

• Alexandry Augustin
• Matteo Venanzi
• Alex Rogers
• Nicholas R. Jennings

A key problem in crowdsourcing is the aggregation of judgments of proportions. For example, workers might be presented with a news article or an image, and be asked to identify the proportion of each topic, sentiment, object, or colour present in it. These varying judgments then need to be aggregated to form a consensus view of the document’s or image’s contents. Often, however, these judgments are skewed by workers who provide judgments randomly. Such spammers make the cost of acquiring judgments more expensive and degrade the accuracy of the aggregation. For such cases, we provide a new Bayesian framework for aggregating these responses (expressed in the form of categorical distributions) that for the first time accounts for spammers. We elicit 796 judgments about proportions of objects and coloursin images. Experimental results show comparable aggregation accuracy when 60% of the workers are spammers, as other state of the art approaches do when there are no spammers.

AAMAS Conference 2016 Conference Paper

Online Planning for Collaborative Search and Rescue by Heterogeneous Robot Teams

• Zoltán Beck
• Luke Teacy
• Alex Rogers
• Nicholas R. Jennings

Collaboration is essential for effective performance by groups of robots in disaster response settings. Here we are particularly interested in heterogeneous robots that collaborate in complex scenarios with incomplete, dynamically changing information. In detail, we consider a search and rescue setting, where robots with different capabilities work together to accomplish tasks (rescue) and find information about further tasks (search) at the same time. The state of the art for such collaboration is robot control based on independent planning for robots with different capabilities and typically incorporates uncertainty with only a limited scope. In contrast, in this paper, we create a joint plan to optimise all robots’ actions incorporating uncertainty about the future information gain of the robots. We evaluate our planner’s performance in settings based on real disasters and find that our approach decreases the response time by 20-25% compared to state-of-the-art approaches. In addition, practical constraints are met in terms of time and resource utilisation.

IJCAI Conference 2015 Conference Paper

A Personalised Thermal Comfort Model Using a Bayesian Network

• Frederik Auffenberg
• Sebastian Stein
• Alex Rogers

In this paper, we address the challenge of predicting optimal comfort temperatures of individual users of a smart heating system. At present, such systems use simple models of user comfort when deciding on a set point temperature. These models generally fail to adapt to an individual user’s preferences, resulting in poor estimates of a user’s preferred temperature. To address this issue, we propose a personalised thermal comfort model that uses a Bayesian network to learn and adapt to a user’s individual preferences. Through an empirical evaluation based on the ASHRAE RP-884 data set, we show that our model is consistently 17. 5- 23. 5% more accurate than current models, regardless of environmental conditions and the type of heating system used. Our model is not limited to a single metric but can also infer information about expected user feedback, optimal comfort temperature and thermal sensitivity at the same time, which can be used to reduce energy used for heating with minimal comfort loss.

IJCAI Conference 2015 Conference Paper

A Scalable Interdependent Multi-Issue Negotiation Protocol for Energy Exchange

• Muddasser Alam
• Enrico H. Gerding
• Alex Rogers
• Sarvapali D. Ramchurn

We present a novel negotiation protocol to facilitate energy exchange between off-grid homes that are equipped with renewable energy generation and electricity storage. Our protocol imposes restrictions over negotiation such that it reduces the complex interdependent multi-issue negotiation to one where agents have a strategy profile in subgame perfect Nash equilibrium. We show that our protocol is concurrent, scalable and; under certain conditions; leads to Pareto-optimal outcomes.

IJCAI Conference 2015 Conference Paper

Bayesian Modelling of Community-Based Multidimensional Trust in Participatory Sensing under Data Sparsity

• Matteo Venanzi
• Luke Teacy
• Alex Rogers
• NICK JENNINGS

We propose a new Bayesian model for reliable aggregation of crowdsourced estimates of real-valued quantities in participatory sensing applications. Existing approaches focus on probabilistic modelling of user’s reliability as the key to accurate aggregation. However, these are either limited to estimating discrete quantities, or require a significant number of reports from each user to accurately model their reliability. To mitigate these issues, we adopt a community-based approach, which reduces the data required to reliably aggregate real-valued estimates, by leveraging correlations between the reporting behaviour of users belonging to different communities. As a result, our method is up to 16. 6% more accurate than existing state-of-the-art methods and is up to 49% more effective under data sparsity when used to estimate Wi-Fi hotspot locations in a real-world crowdsourcing application.

TIST Journal 2015 Journal Article

Modeling the Thermal Dynamics of Buildings

• Siddhartha Ghosh
• Steve Reece
• Alex Rogers
• Stephen Roberts
• Areej Malibari
• Nicholas R. Jennings

Minimizing the energy consumed by heating, ventilation, and air conditioning (HVAC) systems of residential buildings without impacting occupants’ comfort has been highlighted as an important artificial intelligence (AI) challenge. Typically, approaches that seek to address this challenge use a model that captures the thermal dynamics within a building, also referred to as a thermal model. Among thermal models, gray-box models are a popular choice for modeling the thermal dynamics of buildings. They combine knowledge of the physical structure of a building with various data-driven inputs and are accurate estimators of the state (internal temperature). However, existing gray-box models require a detailed specification of all the physical elements that can affect the thermal dynamics of a building a priori. This limits their applicability, particularly in residential buildings, where additional dynamics can be induced by human activities such as cooking, which contributes additional heat, or opening of windows, which leads to additional leakage of heat. Since the incidence of these additional dynamics is rarely known, their combined effects cannot readily be accommodated within existing models. To overcome this limitation and improve the general applicability of gray-box models, we introduce a novel model, which we refer to as a latent force thermal model of the thermal dynamics of a building, or LFM-TM. Our model is derived from an existing gray-box thermal model, which is augmented with an extra term referred to as the learned residual. This term is capable of modeling the effect of any a priori unknown additional dynamic, which, if not captured, appears as a structure in a thermal model’s residual (the error induced by the model). More importantly, the learned residual can also capture the effects of physical elements such as a building’s envelope or the lags in a heating system, leading to a significant reduction in complexity compared to existing models. To evaluate the performance of LFM-TM, we apply it to two independent data sources. The first is an established dataset, referred to as the FlexHouse data, which was previously used for evaluating the efficacy of existing gray-box models [Bacher and Madsen 2011]. The second dataset consists of heating data logged within homes located on the University of Southampton campus, which were specifically instrumented to collect data for our thermal modeling experiments. On both datasets, we show that LFM-TM outperforms existing models in its ability to accurately fit the observed data, generate accurate day-ahead internal temperature predictions, and explain a large amount of the variability in the future observations. This, along with the fact that we also use a corresponding efficient sequential inference scheme for LFM-TM, makes it an ideal candidate for model-based predictive control, where having accurate online predictions of internal temperatures is essential for high-quality solutions.

AIJ Journal 2014 Journal Article

An unsupervised training method for non-intrusive appliance load monitoring

• Oliver Parson
• Siddhartha Ghosh
• Mark Weal
• Alex Rogers

Non-intrusive appliance load monitoring is the process of disaggregating a household's total electricity consumption into its contributing appliances. In this paper we propose an unsupervised training method for non-intrusive monitoring which, unlike existing supervised approaches, does not require training data to be collected by sub-metering individual appliances, nor does it require appliances to be manually labelled for the households in which disaggregation is performed. Instead, we propose an approach which combines a one-off supervised learning process over existing labelled appliance data sets, with an unsupervised learning method over unlabelled household aggregate data. First, we propose an approach which uses the Tracebase data set to build probabilistic appliance models which generalise to previously unseen households, which we empirically evaluate through cross validation. Second, we use the Reference Energy Disaggregation Data set to evaluate the accuracy with which these general models can be tuned to the appliances within a specific household using only aggregate data. Our empirical evaluation demonstrates that general appliance models can be constructed using data from only a small number of appliances (typically 3–6 appliances), and furthermore that 28–99% of the remaining behaviour which is specific to a single household can be learned using only aggregate data from existing smart meters.

AAAI Conference 2014 Conference Paper

Efficient Buyer Groups for Prediction-of-Use Electricity Tariffs

• Valentin Robu
• Meritxell Vinyals
• Alex Rogers
• Nicholas Jennings

Current electricity tariffs do not reflect the real cost that customers incur to suppliers, as units are charged at the same rate, regardless of how predictable each customer’s consumption is. A recent proposal to address this problem are prediction-of-use tariffs. In such tariffs, a customer is asked in advance to predict her future consumption, and is charged based both on her actual consumption and the deviation from her prediction. Prior work (Vinyals et al. 2014) studied the cost game induced by a single such tariff, and showed customers would have an incentive to minimize their risk, by joining together when buying electricity as a grand coalition. In this work we study the efficient (i. e. costminimizing) structure of buying groups for the more realistic setting when multiple, competing prediction-ofuse tariffs are available. We propose a polynomial time algorithm to compute efficient buyer groups, and validate our approach experimentally, using a large-scale data set of domestic electricity consumers in the UK.

AIJ Journal 2014 Journal Article

Efficient crowdsourcing of unknown experts using bounded multi-armed bandits

• Long Tran-Thanh
• Sebastian Stein
• Alex Rogers
• Nicholas R. Jennings

Increasingly, organisations flexibly outsource work on a temporary basis to a global audience of workers. This so-called crowdsourcing has been applied successfully to a range of tasks, from translating text and annotating images, to collecting information during crisis situations and hiring skilled workers to build complex software. While traditionally these tasks have been small and could be completed by non-professionals, organisations are now starting to crowdsource larger, more complex tasks to experts in their respective fields. These tasks include, for example, software development and testing, web design and product marketing. While this emerging expert crowdsourcing offers flexibility and potentially lower costs, it also raises new challenges, as workers can be highly heterogeneous, both in their costs and in the quality of the work they produce. Specifically, the utility of each outsourced task is uncertain and can vary significantly between distinct workers and even between subsequent tasks assigned to the same worker. Furthermore, in realistic settings, workers have limits on the amount of work they can perform and the employer will have a fixed budget for paying workers. Given this uncertainty and the relevant constraints, the objective of the employer is to assign tasks to workers in order to maximise the overall utility achieved. To formalise this expert crowdsourcing problem, we introduce a novel multi-armed bandit (MAB) model, the bounded MAB. Furthermore, we develop an algorithm to solve it efficiently, called bounded ε-first, which proceeds in two stages: exploration and exploitation. During exploration, it first uses εB of its total budget B to learn estimates of the workers' quality characteristics. Then, during exploitation, it uses the remaining ( 1 − ε ) B to maximise the total utility based on those estimates. Using this technique allows us to derive an O ( B 2 3 ) upper bound on its performance regret (i. e. , the expected difference in utility between our algorithm and the optimum), which means that as the budget B increases, the regret tends to 0. In addition to this theoretical advance, we apply our algorithm to real-world data from oDesk, a prominent expert crowdsourcing site. Using data from real projects, including historic project budgets, expert costs and quality ratings, we show that our algorithm outperforms existing crowdsourcing methods by up to 300%, while achieving up to 95 % of a hypothetical optimum with full information.

JMLR Journal 2014 Journal Article

Efficient State-Space Inference of Periodic Latent Force Models

• Steven Reece
• Siddhartha Ghosh
• Alex Rogers
• Stephen Roberts
• Nicholas R. Jennings

Latent force models (LFM) are principled approaches to incorporating solutions to differential equations within non- parametric inference methods. Unfortunately, the development and application of LFMs can be inhibited by their computational cost, especially when closed-form solutions for the LFM are unavailable, as is the case in many real world problems where these latent forces exhibit periodic behaviour. Given this, we develop a new sparse representation of LFMs which considerably improves their computational efficiency, as well as broadening their applicability, in a principled way, to domains with periodic or near periodic latent forces. Our approach uses a linear basis model to approximate one generative model for each periodic force. We assume that the latent forces are generated from Gaussian process priors and develop a linear basis model which fully expresses these priors. We apply our approach to model the thermal dynamics of domestic buildings and show that it is effective at predicting day-ahead temperatures within the homes. We also apply our approach within queueing theory in which quasi-periodic arrival rates are modelled as latent forces. In both cases, we demonstrate that our approach can be implemented efficiently using state-space methods which encode the linear dynamic systems via LFMs. Further, we show that state estimates obtained using periodic latent force models can reduce the root mean squared error to 17% of that from non-periodic models and 27% of the nearest rival approach which is the resonator model (Sarkka et al., 2012; Hartikainen et al. 2012). [abs] [ pdf ][ bib ] &copy JMLR 2014. ( edit, beta )

IJCAI Conference 2013 Conference Paper

A Hidden Markov Model-Based Acoustic Cicada Detector for Crowdsourced Smartphone Biodiversity Monitoring

• Davide Zilli
• Oliver Parson
• Geoff V. Merrett
• Alex Rogers

Automated acoustic recognition of species aims to provide a cost-effective method for biodiversity monitoring. This is particularly appealing for detecting endangered animals with a distinctive call, such as the New Forest cicada. To this end, we pursue a crowdsourcing approach, whereby the millions of visitors to the New Forest will help to monitor the presence of this cicada by means of a smartphone app that can detect its mating call. However, current systems for acoustic insect classification are aimed at batch processing and not suited to a realtime approach as required by this system, because they are too computationally expensive and not robust to environmental noise. To address this shortcoming we propose a novel insect detection algorithm based on a hidden Markov model to which we feed as a single feature vector the ratio of two key frequencies extracted through the Goertzel algorithm. Our results show that this novel approach, compared to the state of the art for batch insect classification, is much more robust to noise while also reducing the computational cost.

IJCAI Conference 2013 Conference Paper

An Efficient Vector-Based Representation for Coalitional Games

• Long Tran-Thanh
• Tri-Dung Nguyen
• Talal Rahwan
• Alex Rogers
• Nicholas R. Jennings

We propose a new representation for coalitional games, called the coalitional skill vector model, where there is a set of skills in the system, and each agent has a skill vector—a vector consisting of values that reflect the agents’ level in different skills. Furthermore, there is a set of goals, each with requirements expressed in terms of the minimum skill level necessary to achieve the goal. Agents can form coalitions to aggregate their skills, and achieve goals otherwise unachievable. We show that this representation is fully expressive, that is, it can represent any characteristic function game. We also show that, for some interesting classes of games, our representation is significantly more compact than the classical representation, and facilitates the development of efficient algorithms to solve the coalition structure generation problem, as well as the problem of computing the core and/or the least core. We also demonstrate that by using the coalitional skill vector representation, our solver can handle up to 500 agents.

AAAI Conference 2013 Conference Paper

Interdependent Multi-Issue Negotiation for Energy Exchange in Remote Communities

• Muddasser Alam
• Alex Rogers
• Sarvapali Ramchurn

We present a novel negotiation protocol to facilitate energy exchange between off-grid homes that are equipped with renewable energy generation and electricity storage. Our protocol imposes restrictions over negotiation such that it reduces the complex interdependent multi-issue negotiation to one where agents have a strategy profile in subgame perfect Nash equilibrium. We show that our negotiation protocol is tractable, concurrent, scalable and leads to Pareto-optimal outcomes in a decentralised manner. We empirically evaluate our protocol and show that, in this instance, a society of agents can (i) improve the overall utilities by 14% and (ii) reduce their overall use of the batteries by 37%.

UAI Conference 2013 Conference Paper

Learning Periodic Human Behaviour Models from Sparse Data for Crowdsourcing Aid Delivery in Developing Countries

• James McInerney
• Alex Rogers
• Nicholas R. Jennings

In many developing countries, half the population lives in rural locations, where access to essentials such as school materials, mosquito nets, and medical supplies is restricted. We propose an alternative method of distribution (to standard road delivery) in which the existing mobility habits of a local population are leveraged to deliver aid, which raises two technical challenges in the areas optimisation and learning. For optimisation, a standard Markov decision process applied to this problem is intractable, so we provide an exact formulation that takes advantage of the periodicities in human location behaviour. To learn such behaviour models from sparse data (i. e. , cell tower observations), we develop a Bayesian model of human mobility. Using real cell tower data of the mobility behaviour of 50, 000 individuals in Ivory Coast, we find that our model outperforms the state of the art approaches in mobility prediction by at least 25% (in held-out data likelihood). Furthermore, when incorporating mobility prediction with our MDP approach, we find a 81. 3% reduction in total delivery time versus routine planning that minimises just the number of participants in the solution path.

AAMAS Conference 2012 Conference Paper

A Scoring Rule-based Mechanism for Aggregate Demand Prediction in the Smart Grid

• Harry Rose
• Alex Rogers
• Enrico Gerding

This paper presents a novel scoring rule-based strictly dominant incentive compatible mechanism that encourages agents to produce costly estimates of future events and report them truthfully to a centre. Whereas prior work has assumed a fixed budget for payment towards agents, this work makes use of prior information held by the centre and assumes a budget that is determined by the savings made through the use of the agents' information over the centre's own prior information. This mechanism is compared to a simple benchmark mechanism wherein the savings are divided equally among all home agents, and a cooperative solution wherein agents act to maximise social welfare. Empirical analysis is performed in which the mechanism is applied to a simulation of the smart grid whereby an aggregator agent must use home agents' information to optimally purchase electricity. It is shown that this mechanism achieves up to 77% of the social welfare achieved by the cooperative solution.

AIJ Journal 2012 Journal Article

An efficient and versatile approach to trust and reputation using hierarchical Bayesian modelling

• W.T. Luke Teacy
• Michael Luck
• Alex Rogers
• Nicholas R. Jennings

In many dynamic open systems, autonomous agents must interact with one another to achieve their goals. Such agents may be self-interested and, when trusted to perform an action, may betray that trust by not performing the action as required. Due to the scale and dynamism of these systems, agents will often need to interact with other agents with which they have little or no past experience. Each agent must therefore be capable of assessing and identifying reliable interaction partners, even if it has no personal experience with them. To this end, we present HABIT, a Hierarchical And Bayesian Inferred Trust model for assessing how much an agent should trust its peers based on direct and third party information. This model is robust in environments in which third party information is malicious, noisy, or otherwise inaccurate. Although existing approaches claim to achieve this, most rely on heuristics with little theoretical foundation. In contrast, HABIT is based exclusively on principled statistical techniques: it can cope with multiple discrete or continuous aspects of trustee behaviour; it does not restrict agents to using a single shared representation of behaviour; it can improve assessment by using any observed correlation between the behaviour of similar trustees or information sources; and it provides a pragmatic solution to the whitewasher problem (in which unreliable agents assume a new identity to avoid bad reputation). In this paper, we describe the theoretical aspects of HABIT, and present experimental results that demonstrate its ability to predict agent behaviour in both a simulated environment, and one based on data from a real-world webserver domain. In particular, these experiments show that HABIT can predict trustee performance based on multiple representations of behaviour, and is up to twice as accurate as BLADE, an existing state-of-the-art trust model that is both statistically principled and has been previously shown to outperform a number of other probabilistic trust models.

AAMAS Conference 2012 Conference Paper

An Intelligent Agent for Home Heating Management

• Alex Rogers
• Sasan Maleki
• Siddhartha Ghosh
• NICK JENNINGS

Intelligent software agents are increasingly being applied within the smart grid; a future vision of an electricity distribution network where information flows in both ways between consumers and suppliers, and where electricity prices change in real-time in response to the current balance of supply and demand across the grid. In this demonstration, we show a home heating management agent that can learn the thermal characteristics of a home and predict local weather conditions, in order to provide home owners with realtime information about their daily heating costs. Furthermore, we demonstrate how the agent can then optimise heating use to minimise cost and carbon emissions whilst satisfying the home owners preferences for comfort.

AAMAS Conference 2012 Conference Paper

ARGUS: A Coordination System to Provide First Responders with Live Aerial Imagery of the Scene of a Disaster

• Francesco Maria Delle Fave
• Alex Rogers
• NICK JENNINGS

We present ARGUS, a coordination system for unmanned aerial vehicles (UAVs) deployed to support situational awareness for disaster management settings. ARGUS is based on the max-sum algorithm, a well known decentralised coordinationalgorithm for multi-agent systems. In this demonstration, we present an interactive simulation environment, where a user acting as a first responder submits imagery collection tasks to a team of UAVs, which then use max-sum to assign themselves to the tasks. We then present a set of real flight tests, in which two Hexacopter UAVs again use ARGUS to coordinate over tasks. Our tests indicate that the system responds positively to the dynamism and the heterogeneity of the real world.

AAAI Conference 2012 Conference Paper

Cooperative Virtual Power Plant Formation Using Scoring Rules

• Valentin Robu
• Ramachandra Kota
• Georgios Chalkiadakis
• Alex Rogers
• Nicholas Jennings

Virtual Power Plants (VPPs) are fast emerging as a suitable means of integrating small and distributed energy resources (DERs), like wind and solar, into the electricity supply network (Grid). VPPs are formed via the aggregation of a large number of such DERs, so that they exhibit the characteristics of a traditional generator in terms of predictability and robustness. In this work, we promote the formation of such “cooperative” VPPs (CVPPs) using multi-agent technology. In particular, we design a payment mechanism that encourages DERs to join CVPPs with large overall production. Our method is based on strictly proper scoring rules and incentivises the provision of accurate predictions from the CVPPs—and in turn, the member DERs—which aids in the planning of the supply schedule at the Grid. We empirically evaluate our approach using the real-world setting of 16 commercial wind farms in the UK. We show that our mechanism incentivises real DERs to form CVPPs, and outperforms the current state of the art payment mechanism developed for this problem.

AAMAS Conference 2012 Conference Paper

Cooperative Virtual Power Plant Formation Using Scoring Rules

• Valentin Robu
• Ramachandra Kota
• Georgios Chalkiadakis
• Alex Rogers
• NICK JENNINGS

The growing focus on sustainable and environmentally friendly energy production has resulted in the proliferation of distributed energy resources (DERs), mainly based on renewable sources like wind and sunlight. However, their small size and the intermittent nature of their supply means that such generators cannot easily be assimilated into the current electricity network (Grid) like conventional generators. Against this background, Virtual Power Plants are fast emerging as a solution to this problem whereby a large number of small energy generators may be aggregated together such that they exhibit the characteristics like a traditional generator in terms of predictability and robustness. In this work, we propose a method to promote the formation of such “cooperative” VPPs (CVPPs) using multi-agent technology. In particular, we design a payment mechanism that encourages DERs to join CVPPs with large overall production. Our method is based on strictly proper scoring rules and elicits accurate probabilistic estimates of energy production from the CVPPs—and in turn, the member DERs— which aids in the planning of the supply schedule at the Grid. We empirically evaluate our approach using the real-world setting of 16 commercial wind farms in the UK, and we show that our mechanism incentivises real DERs to form CVPPs and, moreover, it outperforms the current state of the art payment mechanism developed for this problem.

ECAI Conference 2012 Conference Paper

Cooperatives for Demand Side Management

• Ramachandra Kota
• Georgios Chalkiadakis
• Valentin Robu
• Alex Rogers
• Nicholas R. Jennings

We propose a new scheme for efficient demand side management for the Smart Grid. Specifically, we envisage and promote the formation of cooperatives of medium-large consumers and equip them (via our proposed mechanisms) with the capability of regularly participating in the existing electricity markets by providing electricity demand reduction services to the Grid. Based on mechanism design principles, we develop a model for such cooperatives by designing methods for estimating suitable reduction amounts, placing bids in the market and redistributing the obtained revenue amongst the member agents. Our mechanism is such that the member agents have no incentive to show artificial reductions with the aim of increasing their revenues.

AAMAS Conference 2012 Conference Paper

DCOPs and Bandits: Exploration and Exploitation in Decentralised Coordination

• Ruben Stranders
• Long Tran-Thanh
• Francesco Maria Delle Fave
• Alex Rogers
• NICK JENNINGS

Real life coordination problems are characterised by stochasticity and a lack of \emph{a priori} knowledge about the interactions between agents. However, decentralised constraint optimisation problems (DCOPs), a widely accepted framework for modelling decentralised coordination problems, assumes perfect knowledge, thus limiting its practical applicability. To address this shortcoming, we introduce the MAB-DCOP, in which the interactions between agents are modelled by multi-armed bandits (MABs). Unlike canonical DCOPs, a MAB-DCOP is not a single shot optimisation problem. Rather, it is a sequential one in which agents need to coordinate in order to strike a balance between acquiring knowledge about the \emph{a priori} unknown and stochastic interactions (exploration), and taking the currently believed optimal joint action (exploitation), so as to maximise the cumulative global utility over a finite time horizon. We propose \textsc{Heist}, the first asymptotically optimal algorithm for coordination under stochasticity and lack of prior knowledge. \textsc{Heist} solves MAB-DCOPs in a decentralised fashion using a generalised distributive law (GDL) message passing phase to find the joint action with the highest upper confidence bound (UCB) on global utility. We demonstrate that \textsc{Heist} outperforms other state of the art techniques from the MAB and DCOP literature by up to 1. 5 orders of magnitude on MAB-DCOPs in experimental settings.

AAMAS Conference 2012 Conference Paper

Decentralised stable coalition formation among energy consumers in the smart grid

• Filippo Bistaffa
• Alessandro Farinelli
• Meritxell Vinyals
• Alex Rogers

The vision of the Smart Grid includes demand-side peak shaving strategies, such as real-time pricing or profile's based tariffs, to encourage consumption such that the peaks on demand are flattened. Up to date, most works along this line focused on optimising via scheduling of home appliances or micro-storage the individual user consumption. Alternatively, in this demonstration we propose to exploit the consumers social side by allowing them to self-organise into coalitions of energy users with complementary needs. To this ends, we present an agent-based Java simulation of a social network of energy consumers (based on the domestic electricity market and usage patterns of homes in the UK) that uses to converge to stable energy coalitions.

AAMAS Conference 2012 Conference Paper

Decentralized Bayesian Reinforcement Learning for Online Agent Collaboration

• Luke Teacy
• Georgios Chalkiadakis
• Alessandro Farinelli
• Alex Rogers
• NICK JENNINGS
• Sally McClean
• Gerard Parr

Solving complex but structured problems in a decentralized manner via multiagent collaboration has received much attention in recent years. This is natural, as on one hand, multiagent systems usually possess a structure that determines the allowable interactions among the agents; and on the other hand, the single most pressing need in a cooperative multiagent system is to coordinate the local policies of autonomous agents with restricted capabilities to serve a system-wide goal. The presence of uncertainty makes this even more challenging, as the agents face the additional need to learn the unknown environment parameters while forming (and following) local policies in an online fashion. In this paper, we provide the first Bayesian reinforcement learning (BRL) approach for distributed coordination and learning in a cooperative multiagent system by devising two solutions to this type of problem. More specifically, we show how the Value of Perfect Information (VPI) can be used to perform efficient decentralised exploration in both model-based and model-free BRL, and in the latter case, provide a closed form solution for VPI, correcting a decade old result by Dearden, Friedman and Russell. To evaluate these solutions, we present experimental results comparing their relative merits, and demonstrate empirically that both solutions outperform an existing multiagent learning method, representative of the state-of-the-art.

AAAI Conference 2012 Conference Paper

Delivering the Smart Grid: Challenges for Autonomous Agents and Multi-Agent Systems Research

• Alex Rogers
• Sarvapali Ramchurn
• Nicholas Jennings

Restructuring electricity grids to meet the increased demand caused by the electrification of transport and heating, while making greater use of intermittent renewable energy sources, represents one of the greatest engineering challenges of our day. This modern electricity grid, in which both electricity and information flow in two directions between large numbers of widely distributed suppliers and generators — commonly termed the ‘smart grid’ — represents a radical reengineering of infrastructure which has changed little over the last hundred years. However, the autonomous behaviour expected of the smart grid, its distributed nature, and the existence of multiple stakeholders each with their own incentives and interests, challenges existing engineering approaches. In this challenge paper, we describe why we believe that artificial intelligence, and particularly, the fields of autonomous agents and multi-agent systems are essential for delivering the smart grid as it is envisioned. We present some recent work in this area and describe many of the challenges that still remain.

ICRA Conference 2012 Conference Paper

Deploying the max-sum algorithm for decentralised coordination and task allocation of unmanned aerial vehicles for live aerial imagery collection

• Francesco Maria Delle Fave
• Alex Rogers
• Z. Xu
• Salah Sukkarieh
• Nicholas R. Jennings

We introduce a new technique for coordinating teams of unmanned aerial vehicles (UAVs) when deployed to collect live aerial imagery of the scene of a disaster. We define this problem as one of task assignment where the UAVs dynamically coordinate over tasks representing the imagery collection requests. To measure the quality of the assignment of one or more UAVs to a task, we propose a novel utility function which encompasses several constraints, such as the task's importance and the UAVs' battery capacity so as to maximise performance. We then solve the resulting optimisation problem using a fully asynchronous and decentralised implementation of the max-sum algorithm, a well known message passing algorithm previously used only in simulated domains. Finally, we evaluate our approach both in simulation and on real hardware. First, we empirically evaluate our utility and show that it yields a better trade off between the quantity and quality of completed tasks than similar utilities that do not take all the constraints into account. Second, we deploy it on two hexacopters and assess its practical viability in the real world.

ECAI Conference 2012 Conference Paper

Efficient Crowdsourcing of Unknown Experts using Multi-Armed Bandits

• Long Tran-Thanh
• Sebastian Stein 0001
• Alex Rogers
• Nicholas R. Jennings

We address the expert crowdsourcing problem, in which an employer wishes to assign tasks to a set of available workers with heterogeneous working costs. Critically, as workers produce results of varying quality, the utility of each assigned task is unknown and can vary both between workers and individual tasks. Furthermore, in realistic settings, workers are likely to have limits on the number of tasks they can perform and the employer will have a fixed budget to spend on hiring workers. Given these constraints, the objective of the employer is to assign tasks to workers in order to maximise the overall utility achieved. To achieve this, we introduce a novel multi-armed bandit (MAB) model, the bounded MAB, that naturally captures the problem of expert crowdsourcing. We also propose an algorithm to solve it efficiently, called bounded ϵ -first, which uses the first ϵ B of its total budget B to derive estimates of the workers' quality characteristics (exploration), while the remaining (1− ϵ) B is used to maximise the total utility based on those estimates (exploitation). We show that using this technique allows us to derive an O( B2/3) upper bound on our algorithm's performance regret (i. e. the expected difference in utility between the moptimal and our algorithm). In addition, we demonstrate that our algorithm outperforms existing crowdsourcing methods by up to 155% in experiments based on real-world data from a prominent crowdsourcing site, while achieving up to 75% of a hypothetical optimal with full information.

AAMAS Conference 2012 Conference Paper

Efficient Opinion Sharing in Large Decentralised Teams

• Oleksandr Pryymak
• Alex Rogers
• NICK JENNINGS

In this paper we present an approach for improving the accuracy of shared opinions in a large decentralised team. Specifically, our solution optimises the opinion sharing process in order to help the majority of agents to form the correct opinion about a state of a common subject of interest, given only few agents with noisy sensors in the large team. We build on existing research that has examined models of this opinion sharing problem and shown the existence of optimal parameters where incorrect opinions are filtered out during the sharing process. In order to exploit this collective behaviour in complex networks, we present a new decentralised algorithm that allows each agent to gradually regulate the importance of its neighbours' opinions (their social influence). This leads the system to the optimised state in which agents are most likely to filter incorrect opinions, and form a correct opinion regarding the subject of interest. Crucially, our algorithm is the first that does not introduce additional communication over the opinion sharing itself. Using it 80-90% of the agents form the correct opinion, in contrast to 60-75% with the existing message-passing algorithm DACOR proposed for this setting. Moreover, our solution is adaptive to the network topology and scales to thousands of agents. Finally, the use of our algorithm allows agents to significantly improve their accuracy even when deployed by only half of the team.

AAAI Conference 2012 Conference Paper

Knapsack Based Optimal Policies for Budget–Limited Multi–Armed Bandits

• Long Tran-Thanh
• Archie Chapman
• Alex Rogers
• Nicholas Jennings

In budget–limited multi–armed bandit (MAB) problems, the learner’s actions are costly and constrained by a fixed budget. Consequently, an optimal exploitation policy may not be to pull the optimal arm repeatedly, as is the case in other variants of MAB, but rather to pull the sequence of different arms that maximises the agent’s total reward within the budget. This difference from existing MABs means that new approaches to maximising the total reward are required. Given this, we develop two pulling policies, namely: (i) KUBE; and (ii) fractional KUBE. Whereas the former provides better performance up to 40% in our experimental settings, the latter is computationally less expensive. We also prove logarithmic upper bounds for the regret of both policies, and show that these bounds are asymptotically optimal (i. e. they only differ from the best possible regret by a constant factor).

AAAI Conference 2012 Conference Paper

Non-Intrusive Load Monitoring Using Prior Models of General Appliance Types

• Oliver Parson
• Siddhartha Ghosh
• Mark Weal
• Alex Rogers

Non-intrusive appliance load monitoring is the process of disaggregating a household’s total electricity consumption into its contributing appliances. In this paper we propose an approach by which individual appliances can be iteratively separated from an aggregate load. Unlike existing approaches, our approach does not require training data to be collected by sub-metering individual appliances, nor does it assume complete knowledge of the appliances present in the household. Instead, we propose an approach in which prior models of general appliance types are tuned to specific appliance instances using only signatures extracted from the aggregate load. The tuned appliance models are then used to estimate each appliance’s load, which is subsequently subtracted from the aggregate load. This process is applied iteratively until all appliances for which prior behaviour models are known have been disaggregated. We evaluate the accuracy of our approach using the REDD data set, and show the disaggregation performance when using our training approach is comparable to when sub-metered training data is used. We also present a deployment of our system as a live application and demonstrate the potential for personalised energy saving feedback.

AAMAS Conference 2012 Conference Paper

Optimal Decentralised Dispatch of Embedded Generation in the Smart Grid

• Sam Miller
• Sarvapali Ramchurn
• Alex Rogers

Distribution network operators face a number of challenges; capacity constrained networks, and balancing electricity demand with generation from intermittent renewable resources. Thus, there is an increasing need for scalable approaches to facilitate optimal dispatch in the distribution network. To this end, we cast the optimal dispatch problem as a decentralised agent-based coordination problem and formalise it as a DCOP. We show how this can be decomposed as a factor graph and solved in a decentralised manner using algorithms based on the generalised distributive law; in particular, the max-sum algorithm. We go on to show that max-sum applied na\"{\i}vely in this setting performs a large number of redundant computations. To address this issue, we present a novel decentralised message passing algorithm using dynamic programming that outperforms max-sum by pruning the search space. We empirically evaluate our algorithm using real data, showing that it outperforms (in terms of computational time and total size of messages sent) both a centralised approach, which uses IBM's ILOG CPLEX 12. 2, and max-sum, for large networks.

KER Journal 2011 Journal Article

A unifying framework for iterative approximate best-response algorithms for distributed constraint optimization problems

• Archie C. Chapman
• Alex Rogers
• Nicholas R. Jennings
• David S. Leslie

Abstract Distributed constraint optimization problems (DCOPs) are important in many areas of computer science and optimization. In a DCOP, each variable is controlled by one of many autonomous agents, who together have the joint goal of maximizing a global objective function. A wide variety of techniques have been explored to solve such problems, and here we focus on one of the main families, namely iterative approximate best-response algorithms used as local search algorithms for DCOPs. We define these algorithms as those in which, at each iteration, agents communicate only the states of the variables under their control to their neighbours on the constraint graph, and that reason about their next state based on the messages received from their neighbours. These algorithms include the distributed stochastic algorithm and stochastic coordination algorithms, the maximum-gain messaging algorithms, the families of fictitious play and adaptive play algorithms, and algorithms that use regret-based heuristics. This family of algorithms is commonly employed in real-world systems, as they can be used in domains where communication is difficult or costly, where it is appropriate to trade timeliness off against optimality, or where hardware limitations render complete or more computationally intensive algorithms unusable. However, until now, no overarching framework has existed for analyzing this broad family of algorithms, resulting in similar and overlapping work being published independently in several different literatures. The main contribution of this paper, then, is the development of a unified analytical framework for studying such algorithms. This framework is built on our insight that when formulated as non-cooperative games, DCOPs form a subset of the class of potential games. This result allows us to prove convergence properties of iterative approximate best-response algorithms developed in the computer science literature using game-theoretic methods (which also shows that such algorithms can also be applied to the more general problem of finding Nash equilibria in potential games), and, conversely, also allows us to show that many game-theoretic algorithms can be used to solve DCOPs. By so doing, our framework can assist system designers by making the pros and cons of, and the synergies between, the various iterative approximate best-response DCOP algorithm components clear.

AAMAS Conference 2011 Conference Paper

Agent-Based Control for Decentralised Demand Side Management in the Smart Grid

• Sarvapali D. Ramchurn
• Perukrishnen Vytelingum
• Alex Rogers
• Nicholas R. Jennings

Central to the vision of the smart grid is the deployment of smart meters that will allow autonomous software agents, representing the consumers, to optimise their use of devices and heating in the smart home while interacting with the grid. However, without some form of coordination, the population of agents may end up with overly-homogeneous optimised consumption patterns that may generate significant peaks in demand in the grid. These peaks, in turn, reduce the efficiency of the overall system, increase carbon emissions, and may even, in the worst case, cause blackouts. Hence, in this paper, we introduce a novel model of a Decentralised Demand Side Management (DDSM) mechanism that allows agents, by adapting the deferment of their loads based on grid prices, to coordinate in a decentralised manner. Specifically, using average UK consumption profiles for 26M homes, we demonstrate that, through an emergent coordination of the agents, the peak demand of domestic consumers in the grid can be reduced by up to 17% and carbon emissions by up to 6%. We also show that our DDSM mechanism is robust to the increasing electrification of heating in UK homes (i. e. , it exhibits a similar efficiency).

TIST Journal 2011 Journal Article

Agent-based homeostatic control for green energy in the smart grid

• Sarvapali D. Ramchurn
• Perukrishnen Vytelingum
• Alex Rogers
• Nicholas R. Jennings

With dwindling nonrenewable energy reserves and the adverse effects of climate change, the development of the smart electricity grid is seen as key to solving global energy security issues and to reducing carbon emissions. In this respect, there is a growing need to integrate renewable (or green) energy sources in the grid. However, the intermittency of these energy sources requires that demand must also be made more responsive to changes in supply, and a number of smart grid technologies are being developed, such as high-capacity batteries and smart meters for the home, to enable consumers to be more responsive to conditions on the grid in real time. Traditional solutions based on these technologies, however, tend to ignore the fact that individual consumers will behave in such a way that best satisfies their own preferences to use or store energy (as opposed to that of the supplier or the grid operator). Hence, in practice, it is unclear how these solutions will cope with large numbers of consumers using their devices in this way. Against this background, in this article, we develop novel control mechanisms based on the use of autonomous agents to better incorporate consumer preferences in managing demand. These agents, residing on consumers' smart meters, can both communicate with the grid and optimize their owner's energy consumption to satisfy their preferences. More specifically, we provide a novel control mechanism that models and controls a system comprising of a green energy supplier operating within the grid and a number of individual homes (each possibly owning a storage device). This control mechanism is based on the concept of homeostasis whereby control signals are sent to individual components of a system, based on their continuous feedback, in order to change their state so that the system may reach a stable equilibrium. Thus, we define a new carbon-based pricing mechanism for this green energy supplier that takes advantage of carbon-intensity signals available on the Internet in order to provide real-time pricing. The pricing scheme is designed in such a way that it can be readily implemented using existing communication technologies and is easily understandable by consumers. Building upon this, we develop new control signals that the supplier can use to incentivize agents to shift demand (using their storage device) to times when green energy is available. Moreover, we show how these signals can be adapted according to changes in supply and to various degrees of penetration of storage in the system. We empirically evaluate our system and show that, when all homes are equipped with storage devices, the supplier can significantly reduce its reliance on other carbon-emitting power sources to cater for its own shortfalls. By so doing, the supplier reduces the carbon emission of the system by up to 25% while the consumer reduces its costs by up to 14.5%. Finally, we demonstrate that our homeostatic control mechanism is not sensitive to small prediction errors and the supplier is incentivized to accurately predict its green production to minimize costs.

AAMAS Conference 2011 Conference Paper

Bounded Decentralised Coordination over Multiple Objectives

• Francesco M. Delle Fave
• Ruben Stranders
• Alex Rogers
• Nicholas R. Jennings

We propose the bounded multi-objective max-sum algorithm (B-MOMS), the first decentralised coordination algorithm for multi-objective optimisation problems. B-MOMS extends the max-sum message-passing algorithm for decentralised coordination to compute bounded approximate solutions to multi-objective decentralised constraint optimisation problems (MO-DCOPs). Specifically, we prove the optimality of B-MOMS in acyclic constraint graphs, and derive problem dependent bounds on its approximation ratio when these graphs contain cycles. Furthermore, we empirically evaluate its performance on a multi-objective extension of the canonical graph colouring problem. In so doing, we demonstrate that, for the settings we consider, the approximation ratio never exceeds 2, and is typically less than 1. 5 for less-constrained graphs. Moreover, the runtime required by B-MOMS on the problem instances we considered never exceeds 30 minutes, even for maximally constrained graphs with 100 agents. Thus, B-MOMS brings the problem of multi-objective optimisation well within the boundaries of the limited capabilities of embedded agents.

AAMAS Conference 2011 Conference Paper

Consensus Acceleration in Multiagent Systems with the Chebyshev Semi-Iterative Method

• Renato L. G. Cavalcante
• Alex Rogers
• Nicholas R. Jennings

We consider the fundamental problem of reaching consensus in multiagent systems; an operation required in many applications such as, among others, vehicle formation and coordination, shape formation in modular robotics, distributed target tracking, and environmental modeling. To date, the consensus problem (the problem where agents have to agree on their reported values) has been typically solved with iterative decentralized algorithms based on graph Laplacians. However, the convergence of these existing consensus algorithms is often too slow for many important multiagent applications, and thus they are increasingly being combined with acceleration methods. Unfortunately, state-of-the- art acceleration techniques require parameters that can be optimally selected only if complete information about the network topology is available, which is rarely the case in practice. We address this limitation by deriving two novel acceleration methods that can deliver good performance even if little information about the network is available. The first proposed algorithm is based on the Chebyshev semi-iterative method and is optimal in a well defined sense; it maximizes the worst-case convergence speed (in the mean sense) given that only rough bounds on the extremal eigenvalues of the network matrix are available. It can be applied to systems where agents use unreliable communication links, and its computational complexity is similar to those of simple Laplacian-based methods. This algorithm requires synchronization among agents, so we also propose an asynchronous version that approximates the output of the synchronous algorithm. Mathematical analysis and numerical simulations show that the convergence speed of the proposed acceleration methods decrease gracefully in scenarios where the sole use of Laplacian-based methods is known to be impractical.

AAMAS Conference 2011 Conference Paper

Cooperatives of Distributed Energy Resources for Efficient Virtual Power Plants

• Georgios Chalkiadakis
• Valentin Robu
• Ramachandra Kota
• Alex Rogers
• Nicholas R. Jennings

The creation of Virtual Power Plants (VPPs) has been suggested in recent years as the means for achieving the cost-efficient integration of the many distributed energy resources (DERs) that are starting to emerge in the electricity network. In this work, we contribute to the development of VPPs by offering a game-theoretic perspective to the problem. Specifically, we design cooperatives (or "cooperative VPPs"-CVPPs) of rational autonomous DER-agents representing small-to-medium size renewable electricity producers, which coalesce to profitably sell their energy to the electricity grid. By so doing, we help to counter the fact that individual DERs are often excluded from the wholesale energy market due to their perceived inefficiency and unreliability. We discuss the issues surrounding the emergence of such cooperatives, and propose a pricing mechanism with certain desirable properties. Specifically, our mechanism guarantees that CVPPs have the incentive to truthfully report to the grid accurate estimates of their electricity production, and that larger rather than smaller CVPPs form; this promotes CVPP efficiency and reliability. In addition, we propose a scheme to allocate payments within the cooperative, and show that, given this scheme and the pricing mechanism, the allocation is in the core and, as such, no subset of members has a financial incentive to break away from the CVPP. Moreover, we develop an analytical tool for quantifying the uncertainty about DER production estimates, and distinguishing among different types of errors regarding such estimates. We then utilize this tool to devise protocols to manage CVPP membership. Finally, we demonstrate these ideas through a simulation that uses real-world data.

AAAI Conference 2011 Conference Paper

Decentralised Control of Micro-Storage in the Smart Grid

• Thomas Voice
• Perukrishnen Vytelingum
• Sarvapali Ramchurn
• Alex Rogers
• Nicholas Jennings

In this paper, we propose a novel decentralised control mechanism to manage micro-storage in the smart grid. Our approach uses an adaptive pricing scheme that energy suppliers apply to home smart agents controlling micro-storage devices. In particular, we prove that the interaction between a supplier using our pricing scheme and the actions of selfish micro-storage agents forms a globally stable feedback loop that converges to an efficient equilibrium. We further propose a market strategy that allows the supplier to reduce wholesale purchasing costs without increasing the uncertainty and variance for its aggregate consumer demand. Moreover, we empirically evaluate our mechanism (based on the UK grid data) and show that it yields savings of up to 16% in energy cost for consumers using storage devices with average capacity 10 kWh. Furthermore, we show that it is robust against extreme system changes.

JAAMAS Journal 2011 Journal Article

Long-term information collection with energy harvesting wireless sensors: a multi-armed bandit based approach

• Long Tran-Thanh
• Alex Rogers
• Nicholas R. Jennings

Abstract This paper reports on the development of a multi-agent approach to long-term information collection in networks of energy harvesting wireless sensors. In particular, we focus on developing energy management and data routing policies that adapt their behaviour according to the energy that is harvested, in order to maximise the amount of information collected given the available energy budget. In so doing, we introduce a new energy management technique, based on multi-armed bandit learning, that allows each agent to adaptively allocate its energy budget across the tasks of data sampling, receiving and transmitting. By using this approach, each agent can learn the optimal energy budget settings that give it efficient information collection in the long run. Then, we propose two novel decentralised multi-hop algorithms for data routing. The first proveably maximises the information throughput in the network, but can sometimes involve high communication cost. The second algorithm provides near-optimal performance, but with reduced computational and communication costs. Finally, we demonstrate that, by using our approaches for energy management and routing, we can achieve a 120% improvement in long-term information collection against state-of-the-art benchmarks.

AIJ Journal 2011 Journal Article

Mechanism design for the truthful elicitation of costly probabilistic estimates in distributed information systems

• Athanasios Papakonstantinou
• Alex Rogers
• Enrico H. Gerding
• Nicholas R. Jennings

This paper reports on the design of a novel two-stage mechanism, based on strictly proper scoring rules, that allows a centre to acquire a costly forecast of a future event (such as a meteorological phenomenon) or a probabilistic estimate of a specific parameter (such as the quality of an expected service), with a specified minimum precision, from one or more agents. In the first stage, the centre elicits the agents' true costs and identifies the agent that can provide an estimate of the specified precision at the lowest cost. Then, in the second stage, the centre uses an appropriately scaled strictly proper scoring rule to incentivise this agent to generate the estimate with the required precision, and to truthfully report it. In particular, this is the first mechanism that can be applied to settings in which the centre has no knowledge about the actual costs involved in the generation an agents' estimates and also has no external means of evaluating the quality and accuracy of the estimates it receives. En route to this mechanism, we first consider a setting in which any single agent can provide an estimate of the required precision, and the centre can evaluate this estimate by comparing it with the outcome which is observed at a later stage. This mechanism is then extended, so that it can be applied in a setting where the agents' different capabilities are reflected in the maximum precision of the estimates that they can provide, potentially requiring the centre to select multiple agents and combine their individual results in order to obtain an estimate of the required precision. For all three mechanisms (the original and the two extensions), we prove their economic properties (i. e. incentive compatibility and individual rationality) and then perform a number of numerical simulations. For the single agent mechanism we compare the quadratic, spherical and logarithmic scoring rules with a parametric family of scoring rules. We show that although the logarithmic scoring rule minimises both the mean and variance of the centre's total payments, using this rule means that an agent may face an unbounded penalty if it provides an estimate of extremely poor quality. We show that this is not the case for the parametric family, and thus, we suggest that the parametric scoring rule is the best candidate in our setting. Furthermore, we show that the ‘multiple agent’ extension describes a family of possible approaches to select agents in the first stage of our mechanism, and we show empirically and prove analytically that there is one approach that dominates all others. Finally, we compare our mechanism to the peer prediction mechanism introduced by Miller et al. (2007) [29] and show that the centre's total expected payment is the same in both mechanisms (and is equal to total expected payment in the case that the estimates can be compared to the actual outcome), while the variance in these payments is significantly reduced within our mechanism.

AAMAS Conference 2011 Conference Paper

Online Mechanism Design for Electric Vehicle Charging

• Enrico H. Gerding
• Valentin Robu
• Sebastian Stein
• David C. Parkes
• Alex Rogers
• Nicholas R. Jennings

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 "burning" of allocated power, leaving it unallocated, in order to adjust an allocation and 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.

AAMAS Conference 2011 Conference Paper

Resource-Aware Junction Trees for Efficient Multi-Agent Coordination

• N. Stefanovitch
• A. Farinelli
• Alex Rogers
• Nicholas R. Jennings

In this paper we address efficient decentralised coordination of cooperative multi-agent systems by taking into account the actual computation and communication capabilities of the agents. We consider coordination problems that can be framed as Distributed Constraint Optimisation Problems, and as such, are suitable to be deployed on large scale multi-agent systems such as sensor networks or multiple unmanned aerial vehicles. Specifically, we focus on techniques that exploit structural independence among agents' actions to provide optimal solutions to the coordination problem, and, in particular, we use the Generalized Distributive Law (GDL) algorithm. In this settings, we propose a novel resource aware heuristic to build junction trees and to schedule GDL computations across the agents. Our goal is to minimise the total running time of the coordination process, rather than the theoretical complexity of the computation, by explicitly considering the computation and communication capabilities of agents. We evaluate our proposed approach against DPOP, RDPI and a centralized solver on a number of benchmark coordination problems, and show that our approach is able to provide optimal solutions for DCOPs faster than previous approaches. Specifically, in the settings considered, when resources are scarce our approach is up to three times faster than DPOP (which proved to be the best among the competitors in our settings).

AAMAS Conference 2010 Conference Paper

A Decentralised Coordination Algorithm for Minimising Conflict and Maximising Coverage in Sensor Networks

• Ruben Stranders
• Alex Rogers
• Nicholas R. Jennings

In large wireless sensor networks, the problem of assigning radiofrequencies to sensing agents such that no two connected sensorsare assigned the same value (and will thus interfere with one another) is a major challenge. To tackle this problem, we developa novel decentralised coordination algorithm that activates only asubset of the deployed agents, subject to the connectivity graphof this subset being provably 3-colourable in linear time, henceallowing the use of a simple decentralised graph colouring algorithm. Crucially, while doing this, our algorithm maximises thesensing coverage achieved by the selected sensing agents, whichis given by an arbitrary non-decreasing submodular set function. We empirically evaluate our algorithm by benchmarking it againsta centralised greedy algorithm and an optimal one, and show thatthe selected sensing agents manage to achieve 90\% of the coverage provided by the optimal algorithm, and 85\% of the coverageprovided by activating all sensors. Moreover, we use a simple decentralised graph colouring algorithm to show the frequency assignment problem is easy in the resulting graphs; in all consideredproblem instances, this algorithm managed to find a colouring inless than 5 iterations on average. We then show how the algorithmcan be used in dynamic settings, in which sensors can fail or newsensors can be deployed. In this setting, our algorithm provides250\% more coverage over time compared to activating all availablesensors simultaneously.

AAAI Conference 2010 Conference Paper

A Decentralised Coordination Algorithm for Mobile Sensors

• Ruben Stranders
• Francesco Delle Fave
• Alex Rogers
• Nicholas Jennings

We present an on-line decentralised algorithm for coordinating mobile sensors for a broad class of information gathering tasks. These sensors can be deployed in unknown and possibly hostile environments, where uncertainty and dynamism are endemic. Such environments are common in the areas of disaster response and military surveillance. Our coordination approach itself is based on work by Stranders et al. (2009), that uses the max-sum algorithm to coordinate mobile sensors for monitoring spatial phenomena. In particular, we generalise and extend their approach to any domain where measurements can be valued. Also, we introduce a clustering approach that allows sensors to negotiate over paths to the most relevant locations, as opposed to a set of fixed directions, which results in a significantly improved performance. We demonstrate our algorithm by applying it to two challenging and distinct information gathering tasks. In the first–pursuit-evasion (PE)–sensors need to capture a target whose movement might be unknown. In the second– patrolling (P)–sensors need to minimise loss from intrusions that occur within their environment. In doing so, we obtain the first decentralised coordination algorithms for these domains. Finally, in each domain, we empirically evaluate our approach in a simulated environment, and show that it outperforms two state of the art greedy algorithms by 30% (PE) and 44% (P), and an existing approach based on the Travelling Salesman Problem by 52% (PE) and 30% (P).

AAAI Conference 2010 Conference Paper

A Distributed Algorithm for Optimising over Pure Strategy Nash Equilibria

• Archie Chapman
• Alessandro Farinelli
• Enrique Munoz de Cote
• Alex Rogers
• Nicholas Jennings

We develop an efficient algorithm for computing pure strategy Nash equilibria that satisfy various criteria (such as the utilitarian or Nash–Bernoulli social welfare functions) in games with sparse interaction structure. Our algorithm, called Valued Nash Propagation (VNP), integrates the optimisation problem of maximising a criterion with the constraint satisfaction problem of finding a game’s equilibria to construct a criterion that defines a c–semiring. Given a suitably compact game structure, this criterion can be efficiently optimised using message–passing. To this end, we first show that VNP is complete in games whose interaction structure forms a hypertree. Then, we go on to provide theoretic and empirical results justifying its use on games with arbitrary structure; in particular, we show that it computes the optimum >82% of the time and otherwise selects an equilibrium that is always within 2% of the optimum on average.

ECAI Conference 2010 Conference Paper

A Hybrid Continuous Max-Sum Algorithm for Decentralised Coordination

• Thomas Voice
• Ruben Stranders
• Alex Rogers
• Nicholas R. Jennings

In this paper we tackle the problem of coordinating multiple decentralised agents with continuous state variables. Specifically we propose a hybrid approach, which combines the max-sum algorithm with continuous non-linear optimisation methods. We show that, for problems with acyclic factor graph representations, for suitable parameter choices and sufficiently fine state space discretisations, our proposed algorithm converges to a state with utility close to the global optimum. We empirically evaluate our approach for cyclic constraint graphs in a multi-sensor target classification problem, and compare its performance to the discrete max-sum algorithm, as well as a non-oordinated approach and the distributed stochastic algorithm (DSA). We show that our hybrid max-sum algorithm outperforms the non-coordinated algorithm, DSA and discrete max-sum by up to 40% in this problem domain. Furthermore, the improvements in outcome over discrete max-sum come without significant increases in running time nor communication cost.

AAMAS Conference 2010 Conference Paper

Agent-based Micro-Storage Management for the Smart Grid

• Perukrishnen Vytelingum
• Thomas D. Voice
• Sarvapali D. Ramchurn
• Alex Rogers
• Nicholas R. Jennings

The use of energy storage devices in homes has been advocated as one of the main ways of saving energy and reducing the reliance on fossil fuels in the future Smart Grid. However, if micro-storage devices are all charged at the same time using power from the electricity grid, it means a higher demand and, hence, more generation capacity, more carbon emissions, and, in the worst case, breaking down the system due to over-demand. To alleviate such issues, in this paper, we present a novel agent-based micro-storage management technique that allows all (individually-owned) storage devices in the system to converge to profitable, efficient behaviour. Specifically, we provide a general framework within which to analyse the Nash equilibrium of an electricity grid and devise new agent-based storage learning strategies that adapt to market conditions. Taken altogether, our solution shows that, specifically, in the UK electricity market, it is possible to achieve savings of up to 13\% on average for a consumer on his electricity bill with a storage device of 4 kWh. Moreover, we show that there exists an equilibrium where only 38\% of UK households would own storage devices and where social welfare would be also maximised (with an overall annual savings of nearly GBP 1. 5B at that equilibrium).

JAAMAS Journal 2010 Journal Article

Benchmarking hybrid algorithms for distributed constraint optimisation games

• Archie C. Chapman
• Alex Rogers
• Nicholas R. Jennings

Abstract In this paper, we consider algorithms for distributed constraint optimisation problems (DCOPs). Using a potential game characterisation of DCOPs, we decompose eight DCOP algorithms, taken from the game theory and computer science literatures, into their salient components. We then use these components to construct three novel hybrid algorithms. Finally, we empirical evaluate all eleven algorithms, in terms of solution quality, timeliness and communication resources used, in a series of graph colouring experiments. Our experimental results show the existence of several performance trade-offs (such as quick convergence to a solution, but with a cost of high communication needs), which may be exploited by a system designer to tailor a DCOP algorithm to suit their mix of requirements.

AAMAS Conference 2010 Conference Paper

Distributed Multiagent Learning with a Broadcast Adaptive Subgradient Method

• Renato Cavalcante
• Alex Rogers
• Nicholas R. Jennings
• Isao Yamada

Many applications in multiagent learning are essentially convex optimization problems in which agents have only limited communication and partial information about the function being minimized (examples of such applications include, among others, coordinated sensor localization, distributed adaptive filtering, control, and coordination). Given this observation, we propose a new non-hierarchical decentralized algorithm for the asymptotic minimization of possibly time-varying convex functions. In our method each agent has knowledge of a time-varying local cost function, and the objective is to minimize asymptotically a global cost function defined by the sum of the local functions. At each iteration of our algorithm, agents improve their estimates of a minimizer of the global function by applying a particular version of the adaptive projected subgradient method to their local functions. Then the agents exchange and mix their improved estimates using a probabilistic model based on recent results in weighted average consensus algorithms. The resulting algorithm is provably optimal and reproduces as particular cases many existing algorithms (such as consensus algorithms and recent methods based on the adaptive projected subgradient method). To illustrate one possible application, we show how our algorithm can be applied to coordinated acoustic source localization in sensor networks.

AAMAS Conference 2010 Conference Paper

Efficient Multi-Agent Coordination Using Resource-Aware Junction Trees

• Nicolas Stefanovitch
• Alessandro Farinelli
• Alex Rogers
• Nicholas R. Jennings

In this paper we address efficient decentralised coordination for cooperative multi-agent systems (framed as DCOPs) by taking intoaccount the communication and computational resources of the system. We focus on techniques that exploit structural independenceamong agents' actions to provide optimal solutions to the coordination problem, and, in particular, we use the Generalized DistributedLaw (GDL) algorithm. In this settings, we propose a novel resourceaware heuristic to build junction trees and to schedule GDL computations across the agents. Our approach aims at minimising directlythe total running time of the coordination process, rather than thetheoretical complexity of the computation, by considering computational and communication capabilities of agents.

AAAI Conference 2010 Conference Paper

Epsilon–First Policies for Budget–Limited Multi-Armed Bandits

• Long Tran-Thanh
• Archie Chapman
• Enrique Munoz de Cote
• Alex Rogers
• Nicholas R. Jennings

We introduce the budget–limited multi–armed bandit (MAB), which captures situations where a learner’s actions are costly and constrained by a fixed budget that is incommensurable with the rewards earned from the bandit machine, and then describe a first algorithm for solving it. Since the learner has a budget, the problem’s duration is finite. Consequently an optimal exploitation policy is not to pull the optimal arm repeatedly, but to pull the combination of arms that maximises the agent’s total reward within the budget. As such, the rewards for all arms must be estimated, because any of them may appear in the optimal combination. This di erence from existing MABs means that new approaches to maximising the total reward are required. To this end, we propose an –first algorithm, in which the first of the budget is used solely to learn the arms’ rewards (exploration), while the remaining 1 is used to maximise the received reward based on those estimates (exploitation). We derive bounds on the algorithm’s loss for generic and uniform exploration methods, and compare its performance with traditional MAB algorithms under various distributions of rewards and costs, showing that it outperforms the others by up to 50%.

AAMAS Conference 2010 Conference Paper

Intelligent Agents for the Smart Grid

• Perukrishnen Vytelingum
• Thomas D. Voice
• Sarvapali D. Ramchurn
• Alex Rogers
• Nicholas R. Jennings

The Intelligent Decentralised Energy-Aware Systems (iDEaS) projectat the University of Southampton (see www. ideasproject. info) isdeveloping and demonstrating the application of intelligent agentswithin the smart grid; a future vision of an electricity distributionnetwork capable of autonomous and intelligent configuration, robust and flexible operation, and two-way information flow betweenconsumers and suppliers. In this demonstration, we show howagent technologies can assist in realising three key components ofthis vision, specifically: (i) how a home energy management agentis capable of monitoring, visualising and coordinating energy usewithin the home, (ii) how micro-storage of electricity, coordinatedby intelligent agents, can flattern demand across the grid and reduceboth costs and carbon emissions, and (iii) how trading agents operating within a novel market mechanism can effectively and robustlydistribute energy within the smart grid whilst explicitly accountingfor the capacity constraints of the transmission lines.

AAMAS Conference 2010 Conference Paper

Scalable Mechanism Design for the Procurement of Services with Uncertain Durations

• Enrico Gerding
• Sebastian Stein
• Kate Larson
• Alex Rogers
• Nicholas R. Jennings

In this paper, we study a service procurement problem with uncertainty as to whether service providers are capable of completing agiven task within a specified deadline. This type of setting is often encountered in large and dynamic multi-agent systems, such ascomputational Grids or clouds. To effectively deal with this uncertainty, the consumer may dynamically and redundantly procuremultiple services over time, in order to increase the probability ofsuccess, while at the same time balancing this with the additionalprocurement costs. However, in order to do this optimally, the consumer requires information about the providers' costs and their success probabilities over time. This information is typically held privately by the providers and they may have incentives to misreportthis, so as to increase their own profits. To address this problem, weintroduce a novel mechanism that incentivises self-interested providers to reveal their true costs and capabilities, and we show thatthis mechanism is ex-post incentive compatible, efficient and individually rational. However, for these properties to hold, it generallyneeds to compute the optimal solution, which can be intractable inlarge settings. Therefore, we show how we can generate approximate solutions while maintaining the economic properties of themechanism. This approximation admits a polynomial-time solution that can be computed in seconds even for hundreds of providers, and we demonstrate empirically that it performs as well as theoptimal in typical scenarios. In particularly challenging settings, we show that it still achieves 97\% or more of the optimal.

AAMAS Conference 2010 Conference Paper

Trading Agents for the Smart Electricity Grid

• Perukrishnen Vytelingum
• Sarvapali D. Ramchurn
• Thomas D. Voice
• Alex Rogers
• Nicholas R. Jennings

The vision of the Smart Grid includes the creation of intelligent electricity supply networks to allow efficient use of energy resources, reduce carbon emissions and are robust to failures. One of the key assumptions underlying this vision is that it will be possible to manage the \emph{trading} of electricity between homes and micro-grids while coping with the inherent real-time dynamism in electricity demand and supply. The management of these trades needs to take into account the fact that most, if not all, of the actors in the system are self-interested and transmission line capacities are constrained. Against this background, we develop and evaluate a novel market-based mechanism and novel trading strategies for the Smart Grid. Our mechanism is based on the Continuous Double Auction (CDA) and automatically manages the congestion within the system by pricing the flow of electricity. We also introduce mechanisms to ensure the system can cope with unforseen demand or increased supply capacity in real time. Finally, we develop new strategies that we show achieve high market efficiency (typically over 90\%).

IJCAI Conference 2009 Conference Paper

• Sebastian Stein
• Enrico Gerding
• Alex Rogers
• Kate Larson
• Nicholas R. Jennings

Emerging service-oriented technologies allow software agents to automatically procure distributed services to complete complex tasks. However, in many application scenarios, service providers demand financial remuneration, execution times are uncertain and consumers have deadlines for their tasks. In this paper, we address these issues by developing a novel approach that dynamically procures multiple, redundant services over time, in order to ensure success by the deadline. Specifically, we first present an algorithm for finding optimal procurement solutions, as well as a heuristic algorithm that achieves over 99% of the optimal and is capable of handling thousands of providers. Using experiments, we show that these algorithms achieve an improvement of up to 130% over current strategies that procure only single services. Finally, we consider settings where service costs are not known to the consumer, and introduce several mechanisms that incentivise providers to reveal their costs truthfully and that still achieve up to 95% efficiency.

IJCAI Conference 2009 Conference Paper

• Ruben Stranders
• Alessandro Farinelli
• Alex Rogers
• Nicholas R. Jennings

In this paper, we introduce an on-line, decentralised coordination algorithm for monitoring and predicting the state of spatial phenomena by a team of mobile sensors. These sensors have their application domain in disaster response, where strict time constraints prohibit path planning in advance. The algorithm enables sensors to coordinate their movements with their direct neighbours to maximise the collective information gain, while predicting measurements at unobserved locations using a Gaussian process. It builds upon the max-sum message passing algorithm for decentralised coordination, for which we present two new generic pruning techniques that result in speed-up of up to 92% for 5 sensors. We empirically evaluate our algorithm against several on-line adaptive coordination mechanisms, and report a reduction in root mean squared error up to 50% compared to a greedy strategy.

AAMAS Conference 2008 Conference Paper

A Multi-Agent Simulation System for Prediction and Scheduling of Aero Engine Overhaul

• Armin Stranjak
• Partha Sarathi Dutta
• Mark Ebden
• Alex Rogers
• Perukrishnen Vytelingum

The Aero Repair and Overhaul industry is facing an increasing challenge of prediction and scheduling of engine overhauls to remain competitive in a complex business arena. An appropriate technology solution is required to achieve efficient schedules while satisfying multiple opposing constraints in a highly dynamic environment. In this paper, we describe Overhaul Prediction and Scheduling, an agentbased simulator developed to tackle this challenge. Using negotiation strategies, it deals with the multi-dimensional scheduling optimisation problem by trading off repair costs, capacity and capability of overhaul bases, among others, in light of in-service unforseen events. It supports effective strategic decision-making via business scenario modelling.

ECAI Conference 2008 Conference Paper

A Truthful Two-Stage Mechanism for Eliciting Probabilistic Estimates with Unknown Costs

• Athanasios Papakonstantinou
• Alex Rogers
• Enrico H. Gerding
• Nicholas R. Jennings

This paper reports on the design of a novel two-stage mechanism, based on strictly proper scoring rules, that motivates selfish rational agents to make a costly probabilistic estimate or forecast of a specified precision and report it truthfully to a centre. Our mechanism is applied in a setting where the centre is faced with multiple agents, and has no knowledge about their costs. Thus, in the first stage of the mechanism, the centre uses a reverse second price auction to allocate the estimation task to the agent who reveals the lowest cost. While, in the second stage, the centre issues a payment based on a strictly proper scoring rule. When taken together, the two stages motivate agents to reveal their true costs, and then to truthfully reveal their estimate. We prove that this mechanism is incentive compatible and individually rational, and then present empirical results comparing the performance of the well known quadratic, spherical and logarithmic scoring rules. We show that the quadratic and the logarithmic rules result in the centre making the highest and the lowest expected payment to agents respectively. At the same time, however, the payments of the latter rule are unbounded, and thus the spherical rule proves to be the best candidate in this setting.

AAMAS Conference 2008 Conference Paper

Agent-Based Coordination Technologies in Disaster Management

• Sarvapali D. Ramchurn
• Alex Rogers
• Kathryn Macarthur
• Alessandro Farinelli
• Perukrishnen Vytelingum
• Ioannis Vetsikas
• Nicholas. R. Jennings

AAMAS Conference 2008 Conference Paper

Decentralised Coordination of Low-Power Embedded Devices Using the Max-Sum Algorithm

• Alessandro Farinelli
• Alex Rogers
• Adrian Petcu
• NICK JENNINGS

This paper considers the problem of performing decentralised coordination of low-power embedded devices (as is required within many environmental sensing and surveillance applications). Specifically, we address the generic problem of maximising social welfare within a group of interacting agents. We propose a novel representation of the problem, as a cyclic bipartite factor graph, composed of variable and function nodes (representing the agents’ states and utilities respectively). We show that such representation allows us to use an extension of the max-sum algorithm to generate approximate solutions to this global optimisation problem through local decentralised message passing. We empirically evaluate this approach on a canonical coordination problem (graph colouring), and benchmark it against state of the art approximate and complete algorithms (DSA and DPOP). We show that our approach is robust to lossy communication, that it generates solutions closer to those of DPOP than DSA is able to, and that it does so with a communication cost (in terms of total messages size) that scales very well with the number of agents in the system (compared to the exponential increase of DPOP). Finally, we describe a hardware implementation of our algorithm operating on low-power Chipcon CC2431 System-on-Chip sensor nodes.

AAMAS Conference 2008 Conference Paper

Learn While You Earn: Two Approaches to Learning Auction Parameters in Take-it-or-leave-it Auctions

• Archie Chapman
• Alex Rogers
• NICK JENNINGS

Much of the research in auction theory assumes that the auctioneer knows the distribution of participants’ valuations with complete certainty. However, this is unrealistic. Thus, we analyse cases in which the auctioneer is uncertain about the valuation distributions; specifically, we consider a repeated auction setting in which the auctioneer can learn these distributions. Using take-it-or-leave-it auctions (Sandholm and Gilpin, 2006) as an exemplar auction format, we consider two auction design criteria. Firstly, an auctioneer could maximise expected revenue each time the auction is held. Secondly, an auctioneer could maximise the information gained in earlier auctions (as measured by the Kullback-Liebler divergence between its posterior and prior) to develop good estimates of the unknowns, which are later exploited to improve the revenue earned in the long-run. Simulation results comparing the two criteria indicate that setting offers to maximise revenue does not significantly detract from learning performance, but optimising offers for information gain substantially reduces expected revenue while not producing significantly better parameter estimates.

AAMAS Conference 2008 Conference Paper

Sequential Decision Making with Untrustworthy Service Providers

• Luke Teacy
• Georgios Chalkiadakis
• Alex Rogers
• NICK JENNINGS

In this paper, we deal with the sequential decision making problem of agents operating in computational economies, where there is uncertainty regarding the trustworthiness of service providers populating the environment. Specifically, we propose a generic Bayesian trust model, and formulate the optimal Bayesian solution to the exploration-exploitation problem facing the agents when repeatedly interacting with others in such environments. We then present a computationally tractable Bayesian reinforcement learning algorithm to approximate that solution by taking into account the expected value of perfect information of an agent’s actions. Our algorithm is shown to dramatically outperform all previous finalists of the international Agent Reputation and Trust (ART) competition, including the winner from both years the competition has been run.

IJCAI Conference 2007 Conference Paper

• Enrico H. Gerding
• Alex Rogers
• Rajdeep K. Dash
• Nicholas R. Jennings

We consider competition between sellers offering similar items in concurrent online auctions through a mediating auction institution, where each seller must set its individual auction parameters (such as the reserve price) in such a way as to attract buyers. We show that in the case of two sellers with asymmetric production costs, there exists a pure Nash equilibrium in which both sellers set reserve prices above their production costs. In addition, we show that, rather than setting a reserve price, a seller can further improve its utility by shill bidding (i. e. , bidding as a buyer in its own auction). This shill bidding is undesirable as it introduces inefficiencies within the market. However, through the use of an evolutionary simulation, we extend the analytical results beyond the two-seller case, and we then show that these inefficiencies can be effectively reduced when the mediating auction institution uses auction fees based on the difference between the auction closing and reserve prices.

AAMAS Conference 2007 Conference Paper

An Advanced Bidding Agent for Advertisement Selection on Public Displays

• Alex Rogers
• Esther David
• TERRY R. PAYNE
• Nicholas R. Jennings

In this paper we present an advanced bidding agent that participates in first-price sealed bid auctions to allocate advertising space on BluScreen – an experimental public advertisement system that detects users through the presence of their Bluetooth enabled devices. Our bidding agent is able to build probabilistic models of both the behaviour of users who view the adverts, and the auctions that it participates within. It then uses these models to maximise the exposure that its adverts receive. We evaluate the effectiveness of this bidding agent through simulation against a range of alternative selection mechanisms including a simple bidding strategy, random allocation, and a centralised optimal allocation with perfect foresight. Our bidding agent significantly outperforms both the simple bidding strategy and the random allocation, and in a mixed population of agents it is able to expose its adverts to 25% more users than the simple bidding strategy. Moreover, its performance is within 7. 5% of that of the centralised optimal allocation despite the highly uncertain environment in which it must operate.

AAMAS Conference 2007 Conference Paper

Rumours and Reputation: Evaluating Multi-Dimensional Trust within a Decentralised Reputation System

• Steven Reece
• Alex Rogers
• Stephen Roberts
• Nicholas R. Jennings

In this paper we develop a novel probabilistic model of computational trust that explicitly deals with correlated multi-dimensional contracts. Our starting point is to consider an agent attempting to estimate the utility of a contract, and we show that this leads to a model of computational trust whereby an agent must determine a vector of estimates that represent the probability that any dimension of the contract will be successfully fulfilled, and a covariance matrix that describes the uncertainty and correlations in these probabilities. We present a formalism based on the Dirichlet distribution that allows an agent to calculate these probabilities and correlations from their direct experience of contract outcomes, and we show that this leads to superior estimates compared to an alternative approach using multiple independent beta distributions. We then show how agents may use the sufficient statistics of this Dirichlet distribution to communicate and fuse reputation within a decentralised reputation system. Finally, we present a novel solution to the problem of rumour propagation within such systems. This solution uses the notion of private and shared information, and provides estimates consistent with a centralised reputation system, whilst maintaining the anonymity of the agents, and avoiding bias and overconfidence.

AAMAS Conference 2006 Conference Paper

Competing Sellers in Online Markets: Reserve Prices, Shill Bidding, and Auction Fees

• Enrico Gerding
• Alex Rogers
• Rajdeep Dash
• NICK JENNINGS

AAMAS Conference 2006 Conference Paper

Designing a Successful Trading Agent for Supply Chain Management

• Minghua He
• Alex Rogers
• NICK JENNINGS
• Xudong Luo

AAAI Conference 2006 Conference Paper

Overlapping Coalition Formation for Efficient Data Fusion in Multi-Sensor Networks

• Dung V. Dang
• Alex Rogers

This paper develops new algorithms for coalition formation within multi-sensor networks tasked with performing widearea surveillance. Specifically, we cast this application as an instance of coalition formation, with overlapping coalitions. We show that within this application area sub-additive coalition valuations are typical, and we thus use this structural property of the problem to derive two novel algorithms (an approximate greedy one that operates in polynomial time and has a calculated bound to the optimum, and an optimal branch-and-bound one) to find the optimal coalition structure in this instance. We empirically evaluate the performance of these algorithms within a generic model of a multi-sensor network performing wide area surveillance. These results show that the polynomial algorithm typically generated solutions much closer to the optimal than the theoretical bound, and prove the effectiveness of our pruning procedure.

TCS Journal 2006 Journal Article

Phase transitions and symmetry breaking in genetic algorithms with crossover

• Alex Rogers
• Adam Prügel-Bennett
• Nicholas R. Jennings

In this paper, we consider the role of the crossover operator in genetic algorithms. Specifically, we study optimisation problems that exhibit many local optima and consider how crossover affects the rate at which the population breaks the symmetry of the problem. As an example of such a problem, we consider the subset sum problem. In doing so, we demonstrate a previously unobserved phenomenon, whereby the genetic algorithm with crossover exhibits a critical mutation rate, at which its performance sharply diverges from that of the genetic algorithm without crossover. At this critical mutation rate, the genetic algorithm with crossover exhibits a rapid increase in population diversity. We calculate the details of this phenomenon on a simple instance of the subset sum problem and show that it is a classic phase transition between ordered and disordered populations. Finally, we show that this critical mutation rate corresponds to the transition between the genetic algorithm accelerating or preventing symmetry breaking and that the critical mutation rate represents an optimum in terms of the balance of exploration and exploitation within the algorithm.

EUMAS Conference 2006 Conference Paper

Sellers Competing for Buyers in Online Markets: Reserve Prices, Shill Bids, and Auction Fees

• Enrico H. Gerding
• Alex Rogers
• Rajdeep K. Dash
• Nicholas R. Jennings