2014 |
Fischer, J E; Jiang, W; Kerne, A; Greenhalgh, C; Ramchurn, Sarvapali D; Reece, Steven; Pantidi, N; Rodden, T Supporting Team Coordination on the Ground: Requirements from a Mixed Reality Game. Inproceedings 11th Int. Conference on the Design of Cooperative Systems (COOP ?14), 2014. @inproceedings{orchid192, title = {Supporting Team Coordination on the Ground: Requirements from a Mixed Reality Game.}, author = {J.E. Fischer and W Jiang and A Kerne and C Greenhalgh and Sarvapali D Ramchurn and Steven Reece and N Pantidi and T Rodden}, year = {2014}, date = {2014-01-01}, booktitle = {11th Int. Conference on the Design of Cooperative Systems (COOP ?14)}, howpublished = {http://www.orchid.ac.uk/eprints/192/1/COOP2014-Fischer-author-version.pdf}, keywords = {}, pubstate = {published}, tppubtype = {inproceedings} } |
Jiang, W; Fischer, J E; Greenhalgh, C; Ramchurn, Sarvapali D; Wu, Feng; Jennings, Nicholas R; Rodden, T Social Implications of Agent-based Planning Support for Human Teams. Inproceedings 2014 Int. Conference on Collaboration Technologies and Systems, 2014. @inproceedings{orchid191, title = {Social Implications of Agent-based Planning Support for Human Teams.}, author = {W Jiang and J.E. Fischer and C Greenhalgh and Sarvapali D Ramchurn and Feng Wu and Nicholas R Jennings and T Rodden}, year = {2014}, date = {2014-01-01}, booktitle = {2014 Int. Conference on Collaboration Technologies and Systems}, howpublished = {http://www.orchid.ac.uk/eprints/191/1/CTS2014-Jiang-author-version.pdf}, keywords = {}, pubstate = {published}, tppubtype = {inproceedings} } |
Pawlowski, Krzysztof; Kurach, Karol; Svensson, Kim; Ramchurn, Sarvapali D; Michalak, Tomasz; Rahwan, Talal Coalition Structure Generation with the Graphics Processing Unit Inproceedings 13th Int. Conf. on Autonomous Agents and Multi-Agent Systems, 2014. @inproceedings{orchid176, title = {Coalition Structure Generation with the Graphics Processing Unit}, author = {Krzysztof Pawlowski and Karol Kurach and Kim Svensson and Sarvapali D Ramchurn and Tomasz Michalak and Talal Rahwan}, year = {2014}, date = {2014-01-01}, booktitle = {13th Int. Conf. on Autonomous Agents and Multi-Agent Systems}, keywords = {}, pubstate = {published}, tppubtype = {inproceedings} } |
Huynh, Trung Dong; Ebden, Mark; Ramchurn, Sarvapali; Roberts, Stephen; Moreau, Luc Data quality assessment from provenance graphs Inproceedings Provenance Analytics 2014, 2014. @inproceedings{eps365510, title = {Data quality assessment from provenance graphs}, author = {Trung Dong Huynh and Mark Ebden and Sarvapali Ramchurn and Stephen Roberts and Luc Moreau}, url = {http://eprints.soton.ac.uk/365510/}, year = {2014}, date = {2014-01-01}, booktitle = {Provenance Analytics 2014}, abstract = {Provenance is a domain-independent means to represent what happened in an application, which can help verify data and infer data quality. Provenance patterns can manifest real-world phenomena such as a significant interest in a piece of content, providing an indication of its quality, or even issues such as undesirable interactions within a group of contributors. This paper presents an application-independent methodology for analyzing data based on the network metrics of provenance graphs to learn about such patterns and to relate them to data quality in an automated manner. Validating this method on the provenance records of CollabMap, an online crowdsourcing mapping application, we demonstrated an accuracy level of over 95% for the trust classification of data generated by the crowd therein.}, keywords = {}, pubstate = {published}, tppubtype = {inproceedings} } Provenance is a domain-independent means to represent what happened in an application, which can help verify data and infer data quality. Provenance patterns can manifest real-world phenomena such as a significant interest in a piece of content, providing an indication of its quality, or even issues such as undesirable interactions within a group of contributors. This paper presents an application-independent methodology for analyzing data based on the network metrics of provenance graphs to learn about such patterns and to relate them to data quality in an automated manner. Validating this method on the provenance records of CollabMap, an online crowdsourcing mapping application, we demonstrated an accuracy level of over 95% for the trust classification of data generated by the crowd therein. |
Jennings, Nicholas R; Moreau, Luc; Nicholson, D; Ramchurn, Sarvapali D; Roberts, S; Rodden, T; Rogers, Alex On human-agent collectives Journal Article Communications of the ACM, 57 (12), pp. 33-42, 2014. @article{eps364593, title = {On human-agent collectives}, author = {Nicholas R. Jennings and Luc Moreau and D Nicholson and Sarvapali D. Ramchurn and S Roberts and T Rodden and Alex Rogers}, url = {http://eprints.soton.ac.uk/364593/}, year = {2014}, date = {2014-01-01}, journal = {Communications of the ACM}, volume = {57}, number = {12}, pages = {33-42}, abstract = {We live in a world where a host of computer systems, distributed throughout our physical and information environments, are increasingly implicated in our everyday actions. Computer technologies impact all aspects of our lives and our relationship with the digital has fundamentally altered as computers have moved out of the workplace and away from the desktop. Networked computers, tablets, phones and personal devices are now commonplace, as are an increasingly diverse set of digital devices built into the world around us. Data and information is generated at unprecedented speeds and volumes from an increasingly diverse range of sources. It is then combined in unforeseen ways, limited only by human imagination. People?s activities and collaborations are becoming ever more dependent upon and intertwined with this ubiquitous information substrate. As these trends continue apace, it is becoming apparent that many endeavours involve the symbiotic interleaving of humans and computers. Moreover, the emergence of these close-knit partnerships is inducing profound change. Rather than issuing instructions to passive machines that wait until they are asked before doing anything, we will work in tandem with highly inter-connected computational components that act autonomously and intelligently (aka agents). As a consequence, greater attention needs to be given to the balance of control between people and machines. In many situations, humans will be in charge and agents will predominantly act in a supporting role. In other cases, however, the agents will be in control and humans will play the supporting role. We term this emerging class of systems human-agent collectives (HACs) to reflect the close partnership and the flexible social interactions between the humans and the computers. As well as exhibiting increased autonomy, such systems will be inherently open and social. This means the participants will need to continually and flexibly establish and manage a range of social relationships. Thus, depending on the task at hand, different constellations of people, resources, and information will need to come together, operate in a coordinated fashion, and then disband. The openness and presence of many distinct stakeholders means participation will be motivated by a broad range of incentives rather than diktat. This article outlines the key research challenges involved in developing a comprehensive understanding of HACs. To illuminate this agenda, a nascent application in the domain of disaster response is presented.}, keywords = {}, pubstate = {published}, tppubtype = {article} } We live in a world where a host of computer systems, distributed throughout our physical and information environments, are increasingly implicated in our everyday actions. Computer technologies impact all aspects of our lives and our relationship with the digital has fundamentally altered as computers have moved out of the workplace and away from the desktop. Networked computers, tablets, phones and personal devices are now commonplace, as are an increasingly diverse set of digital devices built into the world around us. Data and information is generated at unprecedented speeds and volumes from an increasingly diverse range of sources. It is then combined in unforeseen ways, limited only by human imagination. People?s activities and collaborations are becoming ever more dependent upon and intertwined with this ubiquitous information substrate. As these trends continue apace, it is becoming apparent that many endeavours involve the symbiotic interleaving of humans and computers. Moreover, the emergence of these close-knit partnerships is inducing profound change. Rather than issuing instructions to passive machines that wait until they are asked before doing anything, we will work in tandem with highly inter-connected computational components that act autonomously and intelligently (aka agents). As a consequence, greater attention needs to be given to the balance of control between people and machines. In many situations, humans will be in charge and agents will predominantly act in a supporting role. In other cases, however, the agents will be in control and humans will play the supporting role. We term this emerging class of systems human-agent collectives (HACs) to reflect the close partnership and the flexible social interactions between the humans and the computers. As well as exhibiting increased autonomy, such systems will be inherently open and social. This means the participants will need to continually and flexibly establish and manage a range of social relationships. Thus, depending on the task at hand, different constellations of people, resources, and information will need to come together, operate in a coordinated fashion, and then disband. The openness and presence of many distinct stakeholders means participation will be motivated by a broad range of incentives rather than diktat. This article outlines the key research challenges involved in developing a comprehensive understanding of HACs. To illuminate this agenda, a nascent application in the domain of disaster response is presented. |
Bistaffa, Filippo; Farinelli, Alessandro; Cerquides, Jesus; Rodriguez-Aguilar, Juan Antonio; Ramchurn, Sarvapali D Anytime Coalition Structure Generation on Synergy Graphs Inproceedings 13th Int. Conf. on Autonomous Agents and Multi-Agent Systems, pp. 13-20, 2014. @inproceedings{orchid175, title = {Anytime Coalition Structure Generation on Synergy Graphs}, author = {Filippo Bistaffa and Alessandro Farinelli and Jesus Cerquides and Juan Antonio Rodriguez-Aguilar and Sarvapali D Ramchurn}, url = {http://aamas2014.lip6.fr/proceedings/aamas/p13.pdf}, year = {2014}, date = {2014-01-01}, booktitle = {13th Int. Conf. on Autonomous Agents and Multi-Agent Systems}, pages = {13-20}, abstract = {We consider the coalition structure generation (CSG) problem on synergy graphs, which arises in many practical applications where communication constraints, social or trust relationships must be taken into account when forming coalitions. We propose a novel representation of this problem based on the concept of edge contraction, and an innovative branch and bound approach (CFSS), which is particularly efficient when applied to a general class of characteristic functions. This new model provides a non-redundant partition of the search space, hence allowing an effective parallelisation. We evaluate CFSS on two benchmark functions, the edge sum with coordination cost and the collective energy purchasing functions, comparing its performance with the best algorithm for CSG on synergy graphs: DyCE. The latter approach is centralised and cannot be efficiently parallelised due to the exponential memory requirements in the number of agents, which limits its scalability (while CFSS memory requirements are only polynomial). Our results show that, when the graphs are very sparse, CFSS is 4 orders of magnitude faster than DyCE. Moreover, CFSS is the first approach to provide anytime approximate solutions with quality guarantees for very large systems (i.e., with more than 2700 agents).}, keywords = {}, pubstate = {published}, tppubtype = {inproceedings} } We consider the coalition structure generation (CSG) problem on synergy graphs, which arises in many practical applications where communication constraints, social or trust relationships must be taken into account when forming coalitions. We propose a novel representation of this problem based on the concept of edge contraction, and an innovative branch and bound approach (CFSS), which is particularly efficient when applied to a general class of characteristic functions. This new model provides a non-redundant partition of the search space, hence allowing an effective parallelisation. We evaluate CFSS on two benchmark functions, the edge sum with coordination cost and the collective energy purchasing functions, comparing its performance with the best algorithm for CSG on synergy graphs: DyCE. The latter approach is centralised and cannot be efficiently parallelised due to the exponential memory requirements in the number of agents, which limits its scalability (while CFSS memory requirements are only polynomial). Our results show that, when the graphs are very sparse, CFSS is 4 orders of magnitude faster than DyCE. Moreover, CFSS is the first approach to provide anytime approximate solutions with quality guarantees for very large systems (i.e., with more than 2700 agents). |
2013 |
Alam, Muddasser; Alan, Alper; Rogers, Alex; Ramchurn, Sarvapali D Towards a smart home framework Inproceedings 5th ACM Workshop On Embedded Systems For Energy-Efficient Buildings (BuildSys2013), 2013. @inproceedings{eps357187, title = {Towards a smart home framework}, author = {Muddasser Alam and Alper Alan and Alex Rogers and Sarvapali D. Ramchurn}, url = {http://eprints.soton.ac.uk/357187/}, year = {2013}, date = {2013-01-01}, booktitle = {5th ACM Workshop On Embedded Systems For Energy-Efficient Buildings (BuildSys2013)}, abstract = {We present our Smart Home Framework (SHF) which simplifies the modelling, prototyping and simulation of smart infrastructure (i.e., smart home and smart communities). It provides the buildings blocks (e.g., home appliances) that can be extended and assembled together to build a smart infrastructure model to which appropriate AI techniques can be applied. This approach enables rapid modelling where new research initiatives can build on existing work.}, keywords = {}, pubstate = {published}, tppubtype = {inproceedings} } We present our Smart Home Framework (SHF) which simplifies the modelling, prototyping and simulation of smart infrastructure (i.e., smart home and smart communities). It provides the buildings blocks (e.g., home appliances) that can be extended and assembled together to build a smart infrastructure model to which appropriate AI techniques can be applied. This approach enables rapid modelling where new research initiatives can build on existing work. |
Alam, Muddasser; Ramchurn, Sarvapali; Rogers, Alex Twelfth International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2013), 2013. @inproceedings{eps346637, title = {Cooperative energy exchange for the efficient use of energy and resources in remote communities. [Winner, Best Student Paper Award at AAMAS2013]}, author = {Muddasser Alam and Sarvapali Ramchurn and Alex Rogers}, url = {http://eprints.soton.ac.uk/346637/}, year = {2013}, date = {2013-01-01}, booktitle = {Twelfth International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2013)}, keywords = {}, pubstate = {published}, tppubtype = {inproceedings} } |
Alam, Muddasser; Rogers, Alex; Ramchurn, Sarvapali Interdependent multi-issue negotiation for energy exchange in remote communities Inproceedings Twenty-Seventh AAAI Conference on Artificial Intelligence (AAAI-13), 2013. @inproceedings{eps350941, title = {Interdependent multi-issue negotiation for energy exchange in remote communities}, author = {Muddasser Alam and Alex Rogers and Sarvapali Ramchurn}, url = {http://eprints.soton.ac.uk/350941/}, year = {2013}, date = {2013-01-01}, booktitle = {Twenty-Seventh AAAI Conference on Artificial Intelligence (AAAI-13)}, abstract = {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%}, keywords = {}, pubstate = {published}, tppubtype = {inproceedings} } 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% |
Alam, Muddasser; Rogers, Alex; Ramchurn, Sarvapali D Interdependent multi-issue negotiation for energy exchange in remote communities Inproceedings International Workshop on AI Problems and Approaches for Intelligent Environments (AI4IE), 2013. @inproceedings{eps357186, title = {Interdependent multi-issue negotiation for energy exchange in remote communities}, author = {Muddasser Alam and Alex Rogers and Sarvapali D. Ramchurn}, url = {http://eprints.soton.ac.uk/357186/}, year = {2013}, date = {2013-01-01}, booktitle = {International Workshop on AI Problems and Approaches for Intelligent Environments (AI4IE)}, keywords = {}, pubstate = {published}, tppubtype = {inproceedings} } |
Cerquides, Jesus; Farinelli, Alessandro; Meseguer, Pedro; Ramchurn, Sarvapali A tutorial on optimisation for multi-agent systems Journal Article The Computer Journal, pp. 1–26, 2013. @article{eps361998, title = {A tutorial on optimisation for multi-agent systems}, author = {Jesus Cerquides and Alessandro Farinelli and Pedro Meseguer and Sarvapali Ramchurn}, url = {http://eprints.soton.ac.uk/361998/}, year = {2013}, date = {2013-01-01}, journal = {The Computer Journal}, pages = {1--26}, abstract = {Research on optimization in multi-agent systems (MASs) has contributed with a wealth of techniques to solve many of the challenges arising in a wide range of multi-agent application domains. Multi-agent optimization focuses on casting MAS problems into optimization problems. The solving of those problems could possibly involve the active participation of the agents in a MAS. Research on multi-agent optimization has rapidly become a very technical, specialized field. Moreover, the contributions to the field in the literature are largely scattered. These two factors dramatically hinder access to a basic, general view of the foundations of the field. This tutorial is intended to ease such access by providing a gentle introduction to fundamental concepts and techniques on multi-agent optimization}, keywords = {}, pubstate = {published}, tppubtype = {article} } Research on optimization in multi-agent systems (MASs) has contributed with a wealth of techniques to solve many of the challenges arising in a wide range of multi-agent application domains. Multi-agent optimization focuses on casting MAS problems into optimization problems. The solving of those problems could possibly involve the active participation of the agents in a MAS. Research on multi-agent optimization has rapidly become a very technical, specialized field. Moreover, the contributions to the field in the literature are largely scattered. These two factors dramatically hinder access to a basic, general view of the foundations of the field. This tutorial is intended to ease such access by providing a gentle introduction to fundamental concepts and techniques on multi-agent optimization |
Farinelli, Alessandro; Bicego, Manuele; Ramchurn, Sarvapali; Zuchelli, Marco C-Link: a hierarchical clustering approach to large-scale near-optimal coalition formation Inproceedings 23rd International Joint Conference on Artificial Intelligence, AAAI Press / International Joint Conferences on Artificial Intelligence, 2013. @inproceedings{eps351521, title = {C-Link: a hierarchical clustering approach to large-scale near-optimal coalition formation}, author = {Alessandro Farinelli and Manuele Bicego and Sarvapali Ramchurn and Marco Zuchelli}, url = {http://eprints.soton.ac.uk/351521/}, year = {2013}, date = {2013-01-01}, booktitle = {23rd International Joint Conference on Artificial Intelligence}, publisher = {AAAI Press / International Joint Conferences on Artificial Intelligence}, abstract = {Coalition formation is a fundamental approach to multi-agent coordination. In this paper we address the specific problem of coalition structure generation, and focus on providing good-enough solutions using a novel heuristic approach that is based on data clustering methods. In particular, we propose a hierarchical agglomerative clustering approach (C-Link), which uses a similarity criterion between coalitions based on the gain that the system achieves if two coalitions merge. We empirically evaluate C-Link on a synthetic benchmark data-set as well as in collective energy purchasing settings. Our results show that the C-link approach performs very well against an optimal benchmark based on Mixed-Integer Programming, achieving solutions which are in the worst case about 80% of the optimal (in the synthetic data-set), and 98% of the optimal (in the energy data-set). Thus we show that C-Link can return solutions for problems involving thousands of agents within minutes.}, keywords = {}, pubstate = {published}, tppubtype = {inproceedings} } Coalition formation is a fundamental approach to multi-agent coordination. In this paper we address the specific problem of coalition structure generation, and focus on providing good-enough solutions using a novel heuristic approach that is based on data clustering methods. In particular, we propose a hierarchical agglomerative clustering approach (C-Link), which uses a similarity criterion between coalitions based on the gain that the system achieves if two coalitions merge. We empirically evaluate C-Link on a synthetic benchmark data-set as well as in collective energy purchasing settings. Our results show that the C-link approach performs very well against an optimal benchmark based on Mixed-Integer Programming, achieving solutions which are in the worst case about 80% of the optimal (in the synthetic data-set), and 98% of the optimal (in the energy data-set). Thus we show that C-Link can return solutions for problems involving thousands of agents within minutes. |
Fischer, Joel E; Ramchurn, Sarvapali D; Osborne, Michael A; Parson, Oliver; Huynh, Trung Dong; Alam, Muddasser; Pantidi, Nadia; Moran, Stuart; Bachour, Khaled; Reece, Steven; Costanza, Enrico; Rodden, Tom; Jennings, Nicholas R Recommending Energy Tariffs and Load Shifting Based on Smart Household Usage Profiling Inproceedings International Conference on Intelligent User Interfaces, pp. 383–394, 2013. @inproceedings{eps346991, title = {Recommending Energy Tariffs and Load Shifting Based on Smart Household Usage Profiling}, author = {Joel E. Fischer and Sarvapali D. Ramchurn and Michael A. Osborne and Oliver Parson and Trung Dong Huynh and Muddasser Alam and Nadia Pantidi and Stuart Moran and Khaled Bachour and Steven Reece and Enrico Costanza and Tom Rodden and Nicholas R. Jennings}, url = {http://eprints.soton.ac.uk/346991/}, year = {2013}, date = {2013-01-01}, booktitle = {International Conference on Intelligent User Interfaces}, pages = {383--394}, abstract = {We present a system and study of personalized energy-related recommendation. AgentSwitch utilizes electricity usage data collected from users\' households over a period of time to realize a range of smart energy-related recommendations on energy tariffs, load detection and usage shifting. The web service is driven by a third party real-time energy tariff API (uSwitch), an energy data store, a set of algorithms for usage prediction, and appliance-level load disaggregation. We present the system design and user evaluation consisting of interviews and interface walkthroughs. We recruited participants from a previous study during which three months of their household\'s energy use was recorded to evaluate personalized recommendations in AgentSwitch. Our contributions are a) a systems architecture for personalized energy services; and b) findings from the evaluation that reveal challenges in designing energy-related recommender systems. In response to the challenges we formulate design recommendations to mitigate barriers to switching tariffs, to incentivize load shifting, and to automate energy management.}, keywords = {}, pubstate = {published}, tppubtype = {inproceedings} } We present a system and study of personalized energy-related recommendation. AgentSwitch utilizes electricity usage data collected from users' households over a period of time to realize a range of smart energy-related recommendations on energy tariffs, load detection and usage shifting. The web service is driven by a third party real-time energy tariff API (uSwitch), an energy data store, a set of algorithms for usage prediction, and appliance-level load disaggregation. We present the system design and user evaluation consisting of interviews and interface walkthroughs. We recruited participants from a previous study during which three months of their household's energy use was recorded to evaluate personalized recommendations in AgentSwitch. Our contributions are a) a systems architecture for personalized energy services; and b) findings from the evaluation that reveal challenges in designing energy-related recommender systems. In response to the challenges we formulate design recommendations to mitigate barriers to switching tariffs, to incentivize load shifting, and to automate energy management. |
Huynh, Trung Dong; Ebden, Mark; Venanzi, Matteo; Ramchurn, Sarvapali; Roberts, Stephen; Moreau, Luc Interpretation of Crowdsourced Activities Using Provenance Network Analysis Inproceedings The First AAAI Conference on Human Computation and Crowdsourcing, Association for the Advancement of Artificial Intelligence, 2013. @inproceedings{eps357199, title = {Interpretation of Crowdsourced Activities Using Provenance Network Analysis}, author = {Trung Dong Huynh and Mark Ebden and Matteo Venanzi and Sarvapali Ramchurn and Stephen Roberts and Luc Moreau}, url = {http://eprints.soton.ac.uk/357199/}, year = {2013}, date = {2013-01-01}, booktitle = {The First AAAI Conference on Human Computation and Crowdsourcing}, publisher = {Association for the Advancement of Artificial Intelligence}, abstract = {Understanding the dynamics of a crowdsourcing application and controlling the quality of the data it generates is challenging, partly due to the lack of tools to do so. Provenance is a domain-independent means to represent what happened in an application, which can help verify data and infer their quality. It can also reveal the processes that led to a data item and the interactions of contributors with it. Provenance patterns can manifest real-world phenomena such as a significant interest in a piece of content, providing an indication of its quality, or even issues such as undesirable interactions within a group of contributors. This paper presents an application-independent methodology for analysing provenance graphs, constructed from provenance records, to learn about such patterns and to use them for assessing some key properties of crowdsourced data, such as their quality, in an automated manner. Validating this method on the provenance records of CollabMap, an online crowdsourcing mapping application, we demonstrated an accuracy level of over 95% for the trust classification of data generated by the crowd therein.}, keywords = {}, pubstate = {published}, tppubtype = {inproceedings} } Understanding the dynamics of a crowdsourcing application and controlling the quality of the data it generates is challenging, partly due to the lack of tools to do so. Provenance is a domain-independent means to represent what happened in an application, which can help verify data and infer their quality. It can also reveal the processes that led to a data item and the interactions of contributors with it. Provenance patterns can manifest real-world phenomena such as a significant interest in a piece of content, providing an indication of its quality, or even issues such as undesirable interactions within a group of contributors. This paper presents an application-independent methodology for analysing provenance graphs, constructed from provenance records, to learn about such patterns and to use them for assessing some key properties of crowdsourced data, such as their quality, in an automated manner. Validating this method on the provenance records of CollabMap, an online crowdsourcing mapping application, we demonstrated an accuracy level of over 95% for the trust classification of data generated by the crowd therein. |
Kleiner, Alexander; Farinelli, Alessandro; Ramchurn, Sarvapali; Shi, Bing; Mafioletti, Fabio; Refatto, Riccardo RMASBench: a benchmarking system for multi-agent coordination in urban search and rescue Inproceedings International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS 2013), 2013. @inproceedings{eps350678, title = {RMASBench: a benchmarking system for multi-agent coordination in urban search and rescue}, author = {Alexander Kleiner and Alessandro Farinelli and Sarvapali Ramchurn and Bing Shi and Fabio Mafioletti and Riccardo Refatto}, url = {http://eprints.soton.ac.uk/350678/}, year = {2013}, date = {2013-01-01}, booktitle = {International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS 2013)}, abstract = {This demonstration paper illustrates RMASBench, a new benchmarking system based on the RoboCup Rescue Agent simulator. The aim of the system is to facilitate benchmarking of coordination approaches in controlled settings for dynamic rescue scenario. In particular, the key features of the systems are: i) programming interfaces to plug-in coordination algorithms without the need for implementing and tuning low-level agents? behaviors, ii) implementations of state-of-the art coordination approaches: DSA and MaxSum, iii) a large scale crowd simulator, which exploits GPUs parallel architecture, to simulate the behaviour of thousands of agents in real time.}, keywords = {}, pubstate = {published}, tppubtype = {inproceedings} } This demonstration paper illustrates RMASBench, a new benchmarking system based on the RoboCup Rescue Agent simulator. The aim of the system is to facilitate benchmarking of coordination approaches in controlled settings for dynamic rescue scenario. In particular, the key features of the systems are: i) programming interfaces to plug-in coordination algorithms without the need for implementing and tuning low-level agents? behaviors, ii) implementations of state-of-the art coordination approaches: DSA and MaxSum, iii) a large scale crowd simulator, which exploits GPUs parallel architecture, to simulate the behaviour of thousands of agents in real time. |
Ramchurn, Sarvapali; Osborne, Michael; Parson, Oliver; Rahwan, Talal; Maleki, Sasan; Reece, Steve; Huynh, Trung Dong; Alam, Muddasser; Fischer, Joel; Rodden, Tom; Moreau, Luc; Roberts, Sephen AgentSwitch: towards smart electricity tariff selection Inproceedings 12th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2013), International Foundation for Autonomous Agents and Multiagent Systems, 2013. @inproceedings{eps349815, title = {AgentSwitch: towards smart electricity tariff selection}, author = {Sarvapali Ramchurn and Michael Osborne and Oliver Parson and Talal Rahwan and Sasan Maleki and Steve Reece and Trung Dong Huynh and Muddasser Alam and Joel Fischer and Tom Rodden and Luc Moreau and Sephen Roberts}, url = {http://eprints.soton.ac.uk/349815/}, year = {2013}, date = {2013-01-01}, booktitle = {12th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2013)}, publisher = {International Foundation for Autonomous Agents and Multiagent Systems}, abstract = {In this paper, we present AgentSwitch, a prototype agent-based platform to solve the electricity tariff selection problem. AgentSwitch incorporates novel algorithms to make predictions of hourly energy usage as well as detect (and suggest to the user) deferrable loads that could be shifted to off-peak times to maximise savings. To take advantage of group discounts from energy retailers, we develop a new scalable collective energy purchasing mechanism, based on the Shapley value, that ensures individual members of a collective (interacting through AgentSwitch) fairly share the discounts. To demonstrate the effectiveness of our algorithms we empirically evaluate them individually on real-world data (with up to 3000 homes in the UK) and show that they outperform the state of the art in their domains. Finally, to ensure individual components are accountable in providing recommendations, we provide a novel provenance-tracking service to record the ?ow of data in the system, and therefore provide users with a means of checking the provenance of suggestions from AgentSwitch and assess their reliability.}, keywords = {}, pubstate = {published}, tppubtype = {inproceedings} } In this paper, we present AgentSwitch, a prototype agent-based platform to solve the electricity tariff selection problem. AgentSwitch incorporates novel algorithms to make predictions of hourly energy usage as well as detect (and suggest to the user) deferrable loads that could be shifted to off-peak times to maximise savings. To take advantage of group discounts from energy retailers, we develop a new scalable collective energy purchasing mechanism, based on the Shapley value, that ensures individual members of a collective (interacting through AgentSwitch) fairly share the discounts. To demonstrate the effectiveness of our algorithms we empirically evaluate them individually on real-world data (with up to 3000 homes in the UK) and show that they outperform the state of the art in their domains. Finally, to ensure individual components are accountable in providing recommendations, we provide a novel provenance-tracking service to record the ?ow of data in the system, and therefore provide users with a means of checking the provenance of suggestions from AgentSwitch and assess their reliability. |
Ramchurn, Sarvapali D; Huynh, Trung Dong; Venanzi, Matteo; Shi, Bing Collabmap: crowdsourcing maps for emergency planning Inproceedings The 5th Annual ACM Web Science Conference, pp. 326–335, 2013. @inproceedings{eps350677, title = {Collabmap: crowdsourcing maps for emergency planning}, author = {Sarvapali D. Ramchurn and Trung Dong Huynh and Matteo Venanzi and Bing Shi}, url = {http://eprints.soton.ac.uk/350677/}, year = {2013}, date = {2013-01-01}, booktitle = {The 5th Annual ACM Web Science Conference}, pages = {326--335}, abstract = {In this paper, we present a software tool to help emergency planners at Hampshire County Council in the UK to create maps for high-fidelity crowd simulations that require evacuation routes from buildings to roads. The main feature of the system is a crowdsourcing mechanism that breaks down the problem of creating evacuation routes into microtasks that a contributor to the platform can execute in less than a minute. As part of the mechanism we developed a concensus-based trust mechanism that filters out incorrect contributions and ensures that the individual tasks are complete and correct. To drive people to contribute to the platform, we experimented with different incentive mechanisms and applied these over different time scales, the aim being to evaluate what incentives work with different types of crowds, including anonymous contributors from Amazon Mechanical Turk. The results of the \'in the wild\' deployment of the system show that the system is effective at engaging contributors to perform tasks correctly and that users respond to incentives in different ways. More specifically, we show that purely social motives are not good enough to attract a large number of contributors and that contributors are averse to the uncertainty in winning rewards. When taken altogether, our results suggest that a combination of incentives may be the best approach to harnessing the maximum number of resources to get socially valuable tasks (such for planning applications) performed on a large scale.}, keywords = {}, pubstate = {published}, tppubtype = {inproceedings} } In this paper, we present a software tool to help emergency planners at Hampshire County Council in the UK to create maps for high-fidelity crowd simulations that require evacuation routes from buildings to roads. The main feature of the system is a crowdsourcing mechanism that breaks down the problem of creating evacuation routes into microtasks that a contributor to the platform can execute in less than a minute. As part of the mechanism we developed a concensus-based trust mechanism that filters out incorrect contributions and ensures that the individual tasks are complete and correct. To drive people to contribute to the platform, we experimented with different incentive mechanisms and applied these over different time scales, the aim being to evaluate what incentives work with different types of crowds, including anonymous contributors from Amazon Mechanical Turk. The results of the 'in the wild' deployment of the system show that the system is effective at engaging contributors to perform tasks correctly and that users respond to incentives in different ways. More specifically, we show that purely social motives are not good enough to attract a large number of contributors and that contributors are averse to the uncertainty in winning rewards. When taken altogether, our results suggest that a combination of incentives may be the best approach to harnessing the maximum number of resources to get socially valuable tasks (such for planning applications) performed on a large scale. |
Rigas, Emmanouil; Ramchurn, Sarvapali; Bassiliades, Nick; Koutitas, Georgios Congestion management for urban EV charging systems Inproceedings 4th IEEE International Conference on Smart Grid Communications (SmartGridComm), IEEE, 2013. @inproceedings{eps356081, title = {Congestion management for urban EV charging systems}, author = {Emmanouil Rigas and Sarvapali Ramchurn and Nick Bassiliades and Georgios Koutitas}, url = {http://eprints.soton.ac.uk/356081/}, year = {2013}, date = {2013-01-01}, booktitle = {4th IEEE International Conference on Smart Grid Communications (SmartGridComm)}, volume = {4}, publisher = {IEEE}, abstract = {We consider the problem of managing Electric Vehicle (EV) charging at charging points in a city to ensure that the load on the charging points remains within the desired limits while minimizing the inconvenience to EV owners. We develop solutions that treat charging points and EV users as self-interested agents that aim to maximize their profit and minimize the impact on their schedule. In particular, we propose variants of a decentralised and dynamic approach as well as an optimal centralised static approach. We evaluated these solutions in a real setting based on the road network and the location of parking garages of a UK city and show that the optimal centralised (non-dynamic) solution manages the congestion the best but does not scale well, while the decentralised solutions scale to thousands of agents.}, keywords = {}, pubstate = {published}, tppubtype = {inproceedings} } We consider the problem of managing Electric Vehicle (EV) charging at charging points in a city to ensure that the load on the charging points remains within the desired limits while minimizing the inconvenience to EV owners. We develop solutions that treat charging points and EV users as self-interested agents that aim to maximize their profit and minimize the impact on their schedule. In particular, we propose variants of a decentralised and dynamic approach as well as an optimal centralised static approach. We evaluated these solutions in a real setting based on the road network and the location of parking garages of a UK city and show that the optimal centralised (non-dynamic) solution manages the congestion the best but does not scale well, while the decentralised solutions scale to thousands of agents. |
Svensson, Kim; Ramchurn, Sarvapali; Cruz, Francisco; Rodriguez-Aguilar, Juan-Antonio; Cerquides, Jesus Solving the coalition structure generation problem on a GPU Inproceedings 6th International Workshop on Optimisation in Multi-Agent Systems, 2013. @inproceedings{eps352204, title = {Solving the coalition structure generation problem on a GPU}, author = {Kim Svensson and Sarvapali Ramchurn and Francisco Cruz and Juan-Antonio Rodriguez-Aguilar and Jesus Cerquides}, url = {http://eprints.soton.ac.uk/352204/}, year = {2013}, date = {2013-01-01}, booktitle = {6th International Workshop on Optimisation in Multi-Agent Systems}, abstract = {We develop the first parallel algorithm for Coalition Structure Generation (CSG), which is central to many multi-agent systems applications. Our approach involves distributing the key steps of a dynamic programming approach to CSG across computational nodes on a Graphics Processing Unit (GPU) such that each of the thousands of threads of computation can be used to perform small computations that speed up the overall process. In so doing, we solve important challenges that arise in solving combinatorial optimisation problems on GPUs such as the efficient allocation of memory and computational threads to every step of the algorithm. In our empirical evaluations on a standard GPU, our results show an improvement of orders of magnitude over current dynamic programming approaches with an ever increasing divergence between the CPU and GPU-based algorithms in terms of growth. Thus, our algorithm is able to solve the CSG problem for 29 agents in one hour and thirty minutes as opposed to three days for the current state of the art dynamic programming algorithms.}, keywords = {}, pubstate = {published}, tppubtype = {inproceedings} } We develop the first parallel algorithm for Coalition Structure Generation (CSG), which is central to many multi-agent systems applications. Our approach involves distributing the key steps of a dynamic programming approach to CSG across computational nodes on a Graphics Processing Unit (GPU) such that each of the thousands of threads of computation can be used to perform small computations that speed up the overall process. In so doing, we solve important challenges that arise in solving combinatorial optimisation problems on GPUs such as the efficient allocation of memory and computational threads to every step of the algorithm. In our empirical evaluations on a standard GPU, our results show an improvement of orders of magnitude over current dynamic programming approaches with an ever increasing divergence between the CPU and GPU-based algorithms in terms of growth. Thus, our algorithm is able to solve the CSG problem for 29 agents in one hour and thirty minutes as opposed to three days for the current state of the art dynamic programming algorithms. |
Truong, Ngoc Cuong; McInerney, James; Tran-Thanh, Long; Costanza, Enrico; Ramchurn, Sarvapali D Forecasting multi-appliance usage for smart home energy management Inproceedings 23rd International Joint Conference on Artificial Intelligence (IJCAI 2013), 2013. @inproceedings{eps351242, title = {Forecasting multi-appliance usage for smart home energy management}, author = {Ngoc Cuong Truong and James McInerney and Long Tran-Thanh and Enrico Costanza and Sarvapali D. Ramchurn}, url = {http://eprints.soton.ac.uk/351242/}, year = {2013}, date = {2013-01-01}, booktitle = {23rd International Joint Conference on Artificial Intelligence (IJCAI 2013)}, keywords = {}, pubstate = {published}, tppubtype = {inproceedings} } |
Truong, Ngoc Cuong; Tran-Thanh, Long; Costanza, Enrico; Ramchurn, Sarvapali D Activity prediction for agent-based home energy management Inproceedings Agent Technologies for Energy Systems (ATES 2013), 2013. @inproceedings{eps351238, title = {Activity prediction for agent-based home energy management}, author = {Ngoc Cuong Truong and Long Tran-Thanh and Enrico Costanza and D. Sarvapali Ramchurn}, url = {http://eprints.soton.ac.uk/351238/}, year = {2013}, date = {2013-01-01}, booktitle = {Agent Technologies for Energy Systems (ATES 2013)}, keywords = {}, pubstate = {published}, tppubtype = {inproceedings} } |
Truong, Ngoc Cuong; Tran-Thanh, Long; Costanza, Enrico; Ramchurn, Sarvapali D Towards appliance usage prediction for home energy management Inproceedings ACM E-Energy 2013, 2013. @inproceedings{eps351240, title = {Towards appliance usage prediction for home energy management}, author = {Ngoc Cuong Truong and Long Tran-Thanh and Enrico Costanza and Sarvapali D. Ramchurn}, url = {http://eprints.soton.ac.uk/351240/}, year = {2013}, date = {2013-01-01}, booktitle = {ACM E-Energy 2013}, keywords = {}, pubstate = {published}, tppubtype = {inproceedings} } |
2012 |
Costanza, Enrico; Ramchurn, Sarvapali D; Jennings, Nicholas R Understanding domestic energy consumption through interactive visualisation: a field study Inproceedings UbiComp '12. Proceedings of the 2012 ACM Conference on Ubiquitous Computing, pp. 216–225, 2012. @inproceedings{eps338804, title = {Understanding domestic energy consumption through interactive visualisation: a field study}, author = {Enrico Costanza and Sarvapali D. Ramchurn and Nicholas R. Jennings}, url = {http://eprints.soton.ac.uk/338804/}, year = {2012}, date = {2012-01-01}, booktitle = {UbiComp '12. Proceedings of the 2012 ACM Conference on Ubiquitous Computing}, pages = {216--225}, abstract = {Motivated by the need to better manage energy demand in the home, in this paper we advocate the integration into Ubicomp systems of interactive energy consumption visualisations, that allow users to engage with and understand their consumption data, relating it to concrete activities in their life. To this end, we present the design, implementation, and evaluation of FigureEnergy, a novel interactive visualisation that allows users to annotate and manipulate a graphical representation of their own electricity consumption data, and therefore make sense of their past energy usage and understand when, how, and to what end, some amount of energy was used. To validate our design, we deployed FigureEnergy ?in the wild? ? 12 participants installed meters in their homes and used the system for a period of two weeks. The results suggest that the annotation approach is successful overall: by engaging with the data users started to relate energy consumption to activities rather than just to appliances. Moreover, they were able to discover that some appliances consume more than they expected, despite having had prior experience of using other electricity displays.}, keywords = {}, pubstate = {published}, tppubtype = {inproceedings} } Motivated by the need to better manage energy demand in the home, in this paper we advocate the integration into Ubicomp systems of interactive energy consumption visualisations, that allow users to engage with and understand their consumption data, relating it to concrete activities in their life. To this end, we present the design, implementation, and evaluation of FigureEnergy, a novel interactive visualisation that allows users to annotate and manipulate a graphical representation of their own electricity consumption data, and therefore make sense of their past energy usage and understand when, how, and to what end, some amount of energy was used. To validate our design, we deployed FigureEnergy ?in the wild? ? 12 participants installed meters in their homes and used the system for a period of two weeks. The results suggest that the annotation approach is successful overall: by engaging with the data users started to relate energy consumption to activities rather than just to appliances. Moreover, they were able to discover that some appliances consume more than they expected, despite having had prior experience of using other electricity displays. |
Ebden, Mark; Huynh, Trung Dong; Moreau, Luc; Ramchurn, Sarvapali; Stephen, Roberts Network analysis on provenance graphs from a crowdsourcing application Inproceedings Groth, Paul; Frew, James (Ed.): 4th International Provenance and Annotation Workshop, pp. 168–182, 2012. @inproceedings{eps340068, title = {Network analysis on provenance graphs from a crowdsourcing application}, author = {Mark Ebden and Trung Dong Huynh and Luc Moreau and Sarvapali Ramchurn and Roberts Stephen}, editor = {Paul Groth and James Frew}, url = {http://eprints.soton.ac.uk/340068/}, year = {2012}, date = {2012-01-01}, booktitle = {4th International Provenance and Annotation Workshop}, volume = {7525}, pages = {168--182}, series = {0302-9743}, abstract = {Crowdsourcing has become a popular means for quickly achieving various tasks in large quantities. CollabMap is an online mapping application in which we crowdsource the identification of evacuation routes in residential areas to be used for planning large-scale evacuations. So far, approximately 38,000 micro-tasks have been completed by over 100 contributors. In order to assist with data verification, we introduced provenance tracking into the application, and approximately 5,000 provenance graphs have been generated. They have provided us various insights into the typical characteristics of provenance graphs in the crowdsourcing context. In particular, we have estimated probability distribution functions over three selected characteristics of these provenance graphs: the node degree, the graph diameter, and the densification exponent. We describe methods to define these three characteristics across specific combinations of node types and edge types, and present our findings in this paper. Applications of our methods include rapid comparison of one provenance graph versus another, or of one style of provenance database versus another. Our results also indicate that provenance graphs represent a suitable area of exploitation for existing network analysis tools concerned with modelling, prediction, and the inference of missing nodes and edges.}, keywords = {}, pubstate = {published}, tppubtype = {inproceedings} } Crowdsourcing has become a popular means for quickly achieving various tasks in large quantities. CollabMap is an online mapping application in which we crowdsource the identification of evacuation routes in residential areas to be used for planning large-scale evacuations. So far, approximately 38,000 micro-tasks have been completed by over 100 contributors. In order to assist with data verification, we introduced provenance tracking into the application, and approximately 5,000 provenance graphs have been generated. They have provided us various insights into the typical characteristics of provenance graphs in the crowdsourcing context. In particular, we have estimated probability distribution functions over three selected characteristics of these provenance graphs: the node degree, the graph diameter, and the densification exponent. We describe methods to define these three characteristics across specific combinations of node types and edge types, and present our findings in this paper. Applications of our methods include rapid comparison of one provenance graph versus another, or of one style of provenance database versus another. Our results also indicate that provenance graphs represent a suitable area of exploitation for existing network analysis tools concerned with modelling, prediction, and the inference of missing nodes and edges. |
Matthews, Tim; Ramchurn, Sarvapali; Chalkiadakis, Georgios Competing with humans at fantasy football: team formation in large partially-observable domains Inproceedings Proceedings of the Twenty-Sixth Conference on Artificial Intelligence, pp. 1394–1400, Association for the Advancement of Artificial Intelligence, 2012. @inproceedings{eps340382, title = {Competing with humans at fantasy football: team formation in large partially-observable domains}, author = {Tim Matthews and Sarvapali Ramchurn and Georgios Chalkiadakis}, url = {http://eprints.soton.ac.uk/340382/}, year = {2012}, date = {2012-01-01}, booktitle = {Proceedings of the Twenty-Sixth Conference on Artificial Intelligence}, pages = {1394--1400}, publisher = {Association for the Advancement of Artificial Intelligence}, abstract = {We present the first real-world benchmark for sequentially optimal team formation, working within the framework of a class of online football prediction games known as Fantasy Football. We model the problem as a Bayesian reinforcement learning one, where the action space is exponential in the number of players and where the decision maker?s beliefs are over multiple characteristics of each footballer. We then exploit domain knowledge to construct computationally tractable solution techniques in order to build a competitive automated Fantasy Football manager. Thus, we are able to establish the baseline performance in this domain, even without complete information on footballers? performances (accessible to human managers), showing that our agent is able to rank at around the top percentile when pitched against 2.5M human players}, keywords = {}, pubstate = {published}, tppubtype = {inproceedings} } We present the first real-world benchmark for sequentially optimal team formation, working within the framework of a class of online football prediction games known as Fantasy Football. We model the problem as a Bayesian reinforcement learning one, where the action space is exponential in the number of players and where the decision maker?s beliefs are over multiple characteristics of each footballer. We then exploit domain knowledge to construct computationally tractable solution techniques in order to build a competitive automated Fantasy Football manager. Thus, we are able to establish the baseline performance in this domain, even without complete information on footballers? performances (accessible to human managers), showing that our agent is able to rank at around the top percentile when pitched against 2.5M human players |
Miller, Sam; Ramchurn, Sarvapali D; Rogers, Alex Optimal Decentralised Dispatch of Embedded Generation in the Smart Grid Journal Article In Proc. 11th Int. Conference on Autonomous Agents and Multi-Agent Systems (AAMAS), 2012. @article{eps273142, title = {Optimal Decentralised Dispatch of Embedded Generation in the Smart Grid}, author = {Sam Miller and Sarvapali D Ramchurn and Alex Rogers}, url = {http://eprints.soton.ac.uk/273142/}, year = {2012}, date = {2012-01-01}, booktitle = {Proc. 11th Int. Conference on Autonomous Agents and Multi-Agent Systems (AAMAS)}, journal = {In Proc. 11th Int. Conference on Autonomous Agents and Multi-Agent Systems (AAMAS)}, abstract = {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?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 distribution network 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.}, keywords = {}, pubstate = {published}, tppubtype = {article} } 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?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 distribution network 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. |
Ramchurn, Sarvapali; Vytelingum, Perukrishnen; Rogers, Alex; Jennings, Nicholas R Putting the Smarts into the Smart Grid: A Grand Challenge for Artificial Intelligence Journal Article Communications of the ACM, 55 (4), pp. 86–97, 2012. @article{eps272606, title = {Putting the Smarts into the Smart Grid: A Grand Challenge for Artificial Intelligence}, author = {Sarvapali Ramchurn and Perukrishnen Vytelingum and Alex Rogers and Nicholas R. Jennings}, url = {http://eprints.soton.ac.uk/272606/}, year = {2012}, date = {2012-01-01}, journal = {Communications of the ACM}, volume = {55}, number = {4}, pages = {86--97}, publisher = {ACM}, abstract = {The phenomenal growth in material wealth experienced in developed countries throughout the twentieth century has largely been driven by the availability of cheap energy derived from fossil fuels (originally coal, then oil, and most recently natural gas). However, the continued availability of this cheap energy cannot be taken for granted given the growing concern that increasing demand for these fuels (and particularly, demand for oil) will outstrip our ability to produce them (so called `peak oil\'). Many mature oil and gas fields around the world have already peaked and their annual production is now steadily declining. Predictions of when world oil production will peak vary between 0-20 years into the future, but even the most conservative estimates provide little scope for complacency given the significant price increases that peak oil is likely to precipitate. Furthermore, many of the oil and gas reserves that do remain are in environmentally or politically sensitive regions of the world where threats to supply create increased price volatility (as evidenced by the 2010 Deepwater Horizon disaster and 2011 civil unrest in the Middle East). Finally, the growing consensus on the long term impact of carbon emissions from burning fossil fuels suggests that even if peak oil is avoided, and energy security assured, a future based on fossil fuel use will expose regions of the world to damaging climate change that will make the lives of many of the world\'s poorest people even harder.}, keywords = {}, pubstate = {published}, tppubtype = {article} } The phenomenal growth in material wealth experienced in developed countries throughout the twentieth century has largely been driven by the availability of cheap energy derived from fossil fuels (originally coal, then oil, and most recently natural gas). However, the continued availability of this cheap energy cannot be taken for granted given the growing concern that increasing demand for these fuels (and particularly, demand for oil) will outstrip our ability to produce them (so called `peak oil'). Many mature oil and gas fields around the world have already peaked and their annual production is now steadily declining. Predictions of when world oil production will peak vary between 0-20 years into the future, but even the most conservative estimates provide little scope for complacency given the significant price increases that peak oil is likely to precipitate. Furthermore, many of the oil and gas reserves that do remain are in environmentally or politically sensitive regions of the world where threats to supply create increased price volatility (as evidenced by the 2010 Deepwater Horizon disaster and 2011 civil unrest in the Middle East). Finally, the growing consensus on the long term impact of carbon emissions from burning fossil fuels suggests that even if peak oil is avoided, and energy security assured, a future based on fossil fuel use will expose regions of the world to damaging climate change that will make the lives of many of the world's poorest people even harder. |
Ramchurn, Sarvapali D; Gerding, Enrico; Jennings, N R; Hu, Jun Practical distributed coalition formation via heuristic negotiation in social networks Inproceedings Fifth International Workshop on Optimisation in Multi-Agent Systems (OPTMAS), 2012. @inproceedings{eps344492, title = {Practical distributed coalition formation via heuristic negotiation in social networks}, author = {Sarvapali D. Ramchurn and Enrico Gerding and N.R. Jennings and Jun Hu}, url = {http://eprints.soton.ac.uk/344492/}, year = {2012}, date = {2012-01-01}, booktitle = {Fifth International Workshop on Optimisation in Multi-Agent Systems (OPTMAS)}, abstract = {We present a novel framework for decentralised coalition formation in social networks, where agents can form coalitions through bilateral negotiations with their neighbours. Specifically, we present a practical negotiation protocol and decision functions that enable agents to form coalitions with agents beyond their peers. Building on this, we establish baseline negotiation strategies which we empirically show to be efficient (agreements are reached in few negotiation rounds) and effective (agreements have high utility compared to a centralised approach) on a variety of network topologies. Moreover, we show that the average degree of social networks can significantly affect the performance of these strategies.}, keywords = {}, pubstate = {published}, tppubtype = {inproceedings} } We present a novel framework for decentralised coalition formation in social networks, where agents can form coalitions through bilateral negotiations with their neighbours. Specifically, we present a practical negotiation protocol and decision functions that enable agents to form coalitions with agents beyond their peers. Building on this, we establish baseline negotiation strategies which we empirically show to be efficient (agreements are reached in few negotiation rounds) and effective (agreements have high utility compared to a centralised approach) on a variety of network topologies. Moreover, we show that the average degree of social networks can significantly affect the performance of these strategies. |
Richardson, Darren P; Costanza, Enrico; Ramchurn, Sarvapali D Evaluating semi-automatic annotation of domestic energy consumption as a memory aid Inproceedings UbiComp '12 Proceedings of the 2012 ACM Conference on Ubiquitous Computing, pp. 613–614, 2012. @inproceedings{eps349083, title = {Evaluating semi-automatic annotation of domestic energy consumption as a memory aid}, author = {Darren P. Richardson and Enrico Costanza and Sarvapali D. Ramchurn}, url = {http://eprints.soton.ac.uk/349083/}, year = {2012}, date = {2012-01-01}, booktitle = {UbiComp '12 Proceedings of the 2012 ACM Conference on Ubiquitous Computing}, pages = {613--614}, abstract = {Frequent feedback about energy consumption can help conservation, one of the current global challenges. Such feedback is most helpful if users can relate it to their own day-to-day activities. In earlier work we showed that manual annotation of domestic energy consumption logs aids users to make such connection and discover patterns they were not aware of. In this poster we report how we augmented manual annotation with machine learning classification techniques. We propose the design of a lab study to evaluate the system, extending methods used to evaluate context aware memory aids, and we present the results of a pilot with 5 participants.}, keywords = {}, pubstate = {published}, tppubtype = {inproceedings} } Frequent feedback about energy consumption can help conservation, one of the current global challenges. Such feedback is most helpful if users can relate it to their own day-to-day activities. In earlier work we showed that manual annotation of domestic energy consumption logs aids users to make such connection and discover patterns they were not aware of. In this poster we report how we augmented manual annotation with machine learning classification techniques. We propose the design of a lab study to evaluate the system, extending methods used to evaluate context aware memory aids, and we present the results of a pilot with 5 participants. |
Rogers, Alex; Ramchurn, Sarvapali; Jennings, Nicholas R Delivering the smart grid: Challenges for autonomous agents and multi-agent systems research Inproceedings Twenty-Sixth AAAI Conference on Artificial Intelligence (AAAI-12), pp. 2166–2172, 2012. @inproceedings{eps337560, title = {Delivering the smart grid: Challenges for autonomous agents and multi-agent systems research}, author = {Alex Rogers and Sarvapali Ramchurn and Nicholas R. Jennings}, url = {http://eprints.soton.ac.uk/337560/}, year = {2012}, date = {2012-01-01}, booktitle = {Twenty-Sixth AAAI Conference on Artificial Intelligence (AAAI-12)}, pages = {2166--2172}, abstract = {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 electric- ity grid, in which both electricity and information flow in two directions between large numbers of widely dis- tributed 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.}, keywords = {}, pubstate = {published}, tppubtype = {inproceedings} } 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 electric- ity grid, in which both electricity and information flow in two directions between large numbers of widely dis- tributed 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. |
Truong, Ngoc Cuong; Tran-Thanh, Long; Costanza, Enrico; Ramchurn, Sarvapali D Predicting energy consumption activities for home energy management Inproceedings Agent Technologies for Energy Systems (ATES 2012), 2012. @inproceedings{eps339215, title = {Predicting energy consumption activities for home energy management}, author = {Ngoc Cuong Truong and Long Tran-Thanh and Enrico Costanza and Sarvapali D. Ramchurn}, url = {http://eprints.soton.ac.uk/339215/}, year = {2012}, date = {2012-01-01}, booktitle = {Agent Technologies for Energy Systems (ATES 2012)}, keywords = {}, pubstate = {published}, tppubtype = {inproceedings} } |
Voice, Thomas; Ramchurn, Sarvapali; Jennings, Nick On coalition formation with sparse synergies Inproceedings Proc. 11th Int. Conference on Autonomous Agents and Multi-Agent Systems (AAMAS), pp. 223–230, 2012. @inproceedings{eps273083, title = {On coalition formation with sparse synergies}, author = {Thomas Voice and Sarvapali Ramchurn and Nick Jennings}, url = {http://eprints.soton.ac.uk/273083/}, year = {2012}, date = {2012-01-01}, booktitle = {Proc. 11th Int. Conference on Autonomous Agents and Multi-Agent Systems (AAMAS)}, pages = {223--230}, keywords = {}, pubstate = {published}, tppubtype = {inproceedings} } |
Simpson, Edwin; Reece, Steven; Penta, Antonio; Ramchurn, Sarvapali D Using a Bayesian Model to Combine LDA Features with Crowdsourced Responses Inproceedings Proceedings of The Twenty-First Text REtrieval Conference, TREC 2012, Gaithersburg, Maryland, USA, November 6-9, 2012, 2012. @inproceedings{DBLP:conf/trec/SimpsonRPR12, title = {Using a Bayesian Model to Combine LDA Features with Crowdsourced Responses}, author = {Edwin Simpson and Steven Reece and Antonio Penta and Sarvapali D Ramchurn}, url = {http://trec.nist.gov/pubs/trec21/papers/HAC.crowd.final.pdf}, year = {2012}, date = {2012-01-01}, booktitle = {Proceedings of The Twenty-First Text REtrieval Conference, TREC 2012, Gaithersburg, Maryland, USA, November 6-9, 2012}, crossref = {DBLP:conf/trec/2012}, keywords = {}, pubstate = {published}, tppubtype = {inproceedings} } |
2011 |
Alam, Muddasser; Rogers, Alex; Ramchurn, Sarvapali A negotiation protocol for multiple interdependent issues negotiation over energy exchange Inproceedings IJCAI Workshop on AI for an Intelligent Planet, 2011, (Event Dates: July-16). @inproceedings{eps272479, title = {A negotiation protocol for multiple interdependent issues negotiation over energy exchange}, author = {Muddasser Alam and Alex Rogers and Sarvapali Ramchurn}, url = {http://eprints.soton.ac.uk/272479/}, year = {2011}, date = {2011-01-01}, booktitle = {IJCAI Workshop on AI for an Intelligent Planet}, abstract = {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 solution imposes additional constraints on negotiation such that it reduces a complex interdependent multi-issue problem to one that is tractable. We prove that using our protocol, agents can reach a Pareto-optimal, dominant strategy equilibrium in a decentralized and timely fashion. We empirically evaluate our approach in a realistic setting. In this case, we show that energy exchange can be useful in reducing the capacity of the energy storage devices in homes by close to 40%}, note = {Event Dates: July-16}, keywords = {}, pubstate = {published}, tppubtype = {inproceedings} } 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 solution imposes additional constraints on negotiation such that it reduces a complex interdependent multi-issue problem to one that is tractable. We prove that using our protocol, agents can reach a Pareto-optimal, dominant strategy equilibrium in a decentralized and timely fashion. We empirically evaluate our approach in a realistic setting. In this case, we show that energy exchange can be useful in reducing the capacity of the energy storage devices in homes by close to 40% |
Macarthur, Kathryn; Stranders, Ruben; Ramchurn, Sarvapali; Jennings, Nick A Distributed Anytime Algorithm for Dynamic Task Allocation in Multi-Agent Systems Inproceedings Twenty-Fifth Conference on Artificial Intelligence (AAAI), pp. 701–706, AAAI Press, 2011, (Event Dates: August 7-11, 2011). @inproceedings{eps272233, title = {A Distributed Anytime Algorithm for Dynamic Task Allocation in Multi-Agent Systems}, author = {Kathryn Macarthur and Ruben Stranders and Sarvapali Ramchurn and Nick Jennings}, url = {http://eprints.soton.ac.uk/272233/}, year = {2011}, date = {2011-01-01}, booktitle = {Twenty-Fifth Conference on Artificial Intelligence (AAAI)}, pages = {701--706}, publisher = {AAAI Press}, abstract = {We introduce a novel distributed algorithm for multi-agent task allocation problems where the sets of tasks and agents constantly change over time. We build on an existing anytime algorithm (fast-max-sum), and give it significant new capa- bilities: namely, an online pruning procedure that simplifies the problem, and a branch-and-bound technique that reduces the search space. This allows us to scale to problems with hundreds of tasks and agents. We empirically evaluate our algorithm against established benchmarks and find that, even in such large environments, a solution is found up to 31% faster, and with up to 23% more utility, than state-of-the-art approximation algorithms. In addition, our algorithm sends up to 30% fewer messages than current approaches when the set of agents or tasks changes.}, note = {Event Dates: August 7-11, 2011}, keywords = {}, pubstate = {published}, tppubtype = {inproceedings} } We introduce a novel distributed algorithm for multi-agent task allocation problems where the sets of tasks and agents constantly change over time. We build on an existing anytime algorithm (fast-max-sum), and give it significant new capa- bilities: namely, an online pruning procedure that simplifies the problem, and a branch-and-bound technique that reduces the search space. This allows us to scale to problems with hundreds of tasks and agents. We empirically evaluate our algorithm against established benchmarks and find that, even in such large environments, a solution is found up to 31% faster, and with up to 23% more utility, than state-of-the-art approximation algorithms. In addition, our algorithm sends up to 30% fewer messages than current approaches when the set of agents or tasks changes. |
Macarthur, Kathryn; Vinyals, Meritxell; Farinelli, Alessandro; Ramchurn, Sarvapali; Jennings, Nick Decentralised Parallel Machine Scheduling for Multi-Agent Task Allocation Inproceedings Fourth International Workshop on Optimisation in Multi-Agent Systems, 2011, (Event Dates: May 3, 2011). @inproceedings{eps272234, title = {Decentralised Parallel Machine Scheduling for Multi-Agent Task Allocation}, author = {Kathryn Macarthur and Meritxell Vinyals and Alessandro Farinelli and Sarvapali Ramchurn and Nick Jennings}, url = {http://eprints.soton.ac.uk/272234/}, year = {2011}, date = {2011-01-01}, booktitle = {Fourth International Workshop on Optimisation in Multi-Agent Systems}, abstract = {Multi-agent task allocation problems pervade a wide range of real-world applications, such as search and rescue in disaster manage- ment, or grid computing. In these applications, where agents are given tasks to perform in parallel, it is often the case that the performance of all agents is judged based on the time taken by the slowest agent to complete its tasks. Hence, efficient distribution of tasks across het- erogeneous agents is important to ensure a short completion time. An equivalent problem to this can be found in operations research, and is known as scheduling jobs on unrelated parallel machines (also known as Rensuremath|ensuremath|Cmax). In this paper, we draw parallels between unrelated parallel machine scheduling and multi-agent task allocation problems, and, in so doing, we present the decentralised task distribution algorithm (DTDA), the first decentralised solution to Rensuremath|ensuremath|Cmax. Empirical evaluation of the DTDA is shown to generate solutions within 86?97% of the optimal on sparse graphs, in the best case, whilst providing a very good estimate (within 1%) of the global solution at each agent.}, note = {Event Dates: May 3, 2011}, keywords = {}, pubstate = {published}, tppubtype = {inproceedings} } Multi-agent task allocation problems pervade a wide range of real-world applications, such as search and rescue in disaster manage- ment, or grid computing. In these applications, where agents are given tasks to perform in parallel, it is often the case that the performance of all agents is judged based on the time taken by the slowest agent to complete its tasks. Hence, efficient distribution of tasks across het- erogeneous agents is important to ensure a short completion time. An equivalent problem to this can be found in operations research, and is known as scheduling jobs on unrelated parallel machines (also known as Rensuremath|ensuremath|Cmax). In this paper, we draw parallels between unrelated parallel machine scheduling and multi-agent task allocation problems, and, in so doing, we present the decentralised task distribution algorithm (DTDA), the first decentralised solution to Rensuremath|ensuremath|Cmax. Empirical evaluation of the DTDA is shown to generate solutions within 86?97% of the optimal on sparse graphs, in the best case, whilst providing a very good estimate (within 1%) of the global solution at each agent. |
Osborne, Michael A; Rogers, Alex; Roberts, Stephen J; Ramchurn, Sarvapali D; Jennings, Nicholas R Gaussian Processes for Time Series Prediction Incollection Bayesian Time Series Models, pp. 341–360, Cambridge University Press, 2011, (Chapter: 16). @incollection{eps272746, title = {Gaussian Processes for Time Series Prediction}, author = {Michael A. Osborne and Alex Rogers and Stephen J. Roberts and Sarvapali D. Ramchurn and Nicholas R. Jennings}, url = {http://eprints.soton.ac.uk/272746/}, year = {2011}, date = {2011-01-01}, booktitle = {Bayesian Time Series Models}, pages = {341--360}, publisher = {Cambridge University Press}, note = {Chapter: 16}, keywords = {}, pubstate = {published}, tppubtype = {incollection} } |
Ramchurn, Sarvapali; Vytelingum, Perukrishnen; Rogers, Alex; Jennings, Nick Agent-based homeostatic control for green energy in the smart grid Journal Article ACM Transactions on Intelligent Systems and Technology, 2 (4), pp. 35:1–35:28, 2011. @article{eps272015, title = {Agent-based homeostatic control for green energy in the smart grid}, author = {Sarvapali Ramchurn and Perukrishnen Vytelingum and Alex Rogers and Nick Jennings}, url = {http://eprints.soton.ac.uk/272015/}, year = {2011}, date = {2011-01-01}, journal = {ACM Transactions on Intelligent Systems and Technology}, volume = {2}, number = {4}, pages = {35:1--35:28}, abstract = {With dwindling non-renewable 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 paper, 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 optimise 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 incentivise 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 incentivised to accurately predict its green production to minimise costs.}, keywords = {}, pubstate = {published}, tppubtype = {article} } With dwindling non-renewable 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 paper, 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 optimise 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 incentivise 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 incentivised to accurately predict its green production to minimise costs. |
Ramchurn, Sarvapali; Vytelingum, Perukrishnen; Rogers, Alex; Jennings, Nick Agent-based control for decentralised demand side management in the smart grid Inproceedings The Tenth International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2011), pp. 5–12, 2011. @inproceedings{eps271985, title = {Agent-based control for decentralised demand side management in the smart grid}, author = {Sarvapali Ramchurn and Perukrishnen Vytelingum and Alex Rogers and Nick Jennings}, url = {http://eprints.soton.ac.uk/271985/}, year = {2011}, date = {2011-01-01}, booktitle = {The Tenth International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2011)}, pages = {5--12}, abstract = {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).}, keywords = {}, pubstate = {published}, tppubtype = {inproceedings} } 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). |
Stranders, Ruben; Ramchurn, Sarvapali; Shi, Bing; Jennings, Nick CollabMap: Augmenting Maps using the Wisdom of Crowds Inproceedings Third Human Computation Workshop, 2011. @inproceedings{eps272478, title = {CollabMap: Augmenting Maps using the Wisdom of Crowds}, author = {Ruben Stranders and Sarvapali Ramchurn and Bing Shi and Nick Jennings}, url = {http://eprints.soton.ac.uk/272478/}, year = {2011}, date = {2011-01-01}, booktitle = {Third Human Computation Workshop}, keywords = {}, pubstate = {published}, tppubtype = {inproceedings} } |
Voice, Thomas; Vytelingum, Perukrishnen; Ramchurn, Sarvapali; Rogers, Alex; Jennings, Nick Decentralised Control of Micro-Storage in the Smart Grid Inproceedings AAAI-11: Twenty-Fifth Conference on Artificial Intelligence, pp. 1421–1426, 2011, (Event Dates: August 7?11, 2011). @inproceedings{eps272262, title = {Decentralised Control of Micro-Storage in the Smart Grid}, author = {Thomas Voice and Perukrishnen Vytelingum and Sarvapali Ramchurn and Alex Rogers and Nick Jennings}, url = {http://eprints.soton.ac.uk/272262/}, year = {2011}, date = {2011-01-01}, booktitle = {AAAI-11: Twenty-Fifth Conference on Artificial Intelligence}, pages = {1421--1426}, abstract = {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.}, note = {Event Dates: August 7?11, 2011}, keywords = {}, pubstate = {published}, tppubtype = {inproceedings} } 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. |
Vytelingum, Perukrishnen; Voice, Thomas; Ramchurn, Sarvapali; Rogers, Alex; Jennings, Nick Theoretical and practical foundations of large-scale agent-based micro-storage in the smart grid Journal Article Journal of Artificial Intelligence Research, 42 , pp. 765–813, 2011, (AAMAS 2010 iRobot Best Paper Award). @article{eps272961, title = {Theoretical and practical foundations of large-scale agent-based micro-storage in the smart grid}, author = {Perukrishnen Vytelingum and Thomas Voice and Sarvapali Ramchurn and Alex Rogers and Nick Jennings}, url = {http://eprints.soton.ac.uk/272961/}, year = {2011}, date = {2011-01-01}, journal = {Journal of Artificial Intelligence Research}, volume = {42}, pages = {765--813}, abstract = {In this paper, we present a novel decentralised management technique that allows electricity micro-storage devices, deployed within individual homes as part of a smart electricity grid, to converge to profitable and efficient behaviours. Specifically, we propose the use of software agents, residing on the users\' smart meters, to automate and optimise the charging cycle of micro-storage devices in the home to minimise its costs, and we present a study of both the theoretical underpinnings and the implications of a practical solution, of using software agents for such micro-storage management. First, by formalising the strategic choice each agent makes in deciding when to charge its battery, we develop a game-theoretic framework within which we can analyse the competitive equilibria of an electricity grid populated by such agents and hence predict the best consumption profile for that population given their battery properties and individual load profiles. Our framework also allows us to compute theoretical bounds on the amount of storage that will be adopted by the population. Second, to analyse the practical implications of micro-storage deployments in the grid, we present a novel algorithm that each agent can use to optimise its battery storage profile in order to minimise its owner\'s costs. This algorithm uses a learning strategy that allows it to adapt as the price of electricity changes in real-time, and we show that the adoption of these strategies results in the system converging to the theoretical equilibria. Finally, we empirically evaluate the adoption of our micro-storage management technique within a complex setting, based on the UK electricity market, where agents may have widely varying load profiles, battery types, and learning rates. In this case, our approach yields savings of up to 14% in energy cost for an average consumer using a storage device with a capacity of less than 4.5 kWh and up to a 7% reduction in carbon emissions resulting from electricity generation (with only domestic consumers adopting micro-storage and, commercial and industrial consumers not changing their demand). Moreover, corroborating our theoretical bound, an equilibrium is shown to exist where no more than 48% of households would wish to own storage devices and where social welfare would also be improved (yielding overall annual savings of nearly pounds1.5B).}, note = {AAMAS 2010 iRobot Best Paper Award}, keywords = {}, pubstate = {published}, tppubtype = {article} } In this paper, we present a novel decentralised management technique that allows electricity micro-storage devices, deployed within individual homes as part of a smart electricity grid, to converge to profitable and efficient behaviours. Specifically, we propose the use of software agents, residing on the users' smart meters, to automate and optimise the charging cycle of micro-storage devices in the home to minimise its costs, and we present a study of both the theoretical underpinnings and the implications of a practical solution, of using software agents for such micro-storage management. First, by formalising the strategic choice each agent makes in deciding when to charge its battery, we develop a game-theoretic framework within which we can analyse the competitive equilibria of an electricity grid populated by such agents and hence predict the best consumption profile for that population given their battery properties and individual load profiles. Our framework also allows us to compute theoretical bounds on the amount of storage that will be adopted by the population. Second, to analyse the practical implications of micro-storage deployments in the grid, we present a novel algorithm that each agent can use to optimise its battery storage profile in order to minimise its owner's costs. This algorithm uses a learning strategy that allows it to adapt as the price of electricity changes in real-time, and we show that the adoption of these strategies results in the system converging to the theoretical equilibria. Finally, we empirically evaluate the adoption of our micro-storage management technique within a complex setting, based on the UK electricity market, where agents may have widely varying load profiles, battery types, and learning rates. In this case, our approach yields savings of up to 14% in energy cost for an average consumer using a storage device with a capacity of less than 4.5 kWh and up to a 7% reduction in carbon emissions resulting from electricity generation (with only domestic consumers adopting micro-storage and, commercial and industrial consumers not changing their demand). Moreover, corroborating our theoretical bound, an equilibrium is shown to exist where no more than 48% of households would wish to own storage devices and where social welfare would also be improved (yielding overall annual savings of nearly pounds1.5B). |
2010 |
Macarthur, Kathryn; Farinelli, Alessandro; Ramchurn, Sarvapali; Jennings, Nick Efficient, Superstabilizing Decentralised Optimisation for Dynamic Task Allocation Environments Inproceedings Third International Workshop on: Optimisation in Multi-Agent Systems (OptMas) at the Ninth Joint Conference on Autonomous and Multi-Agent Systems, pp. 25–32, 2010, (Event Dates: 10 May 2010). @inproceedings{eps268588, title = {Efficient, Superstabilizing Decentralised Optimisation for Dynamic Task Allocation Environments}, author = {Kathryn Macarthur and Alessandro Farinelli and Sarvapali Ramchurn and Nick Jennings}, url = {http://eprints.soton.ac.uk/268588/}, year = {2010}, date = {2010-01-01}, booktitle = {Third International Workshop on: Optimisation in Multi-Agent Systems (OptMas) at the Ninth Joint Conference on Autonomous and Multi-Agent Systems}, pages = {25--32}, abstract = {Decentralised optimisation is a key issue for multi-agent systems, and while many solution techniques have been developed, few provide support for dynamic environments, which change over time, such as disaster management. Given this, in this paper, we present Bounded Fast Max Sum (BFMS): a novel, dynamic, superstabilizing algorithm which provides a bounded approximate solution to certain classes of distributed constraint optimisation problems. We achieve this by eliminating dependencies in the constraint functions, according to how much impact they have on the overall solution value. In more detail, we propose iGHS, which computes a maximum spanning tree on subsections of the constraint graph, in order to reduce communication and computation overheads. Given this, we empirically evaluate BFMS, which shows that BFMS reduces communication and computation done by Bounded Max Sum by up to 99%, while obtaining 60-88% of the optimal utility.}, note = {Event Dates: 10 May 2010}, keywords = {}, pubstate = {published}, tppubtype = {inproceedings} } Decentralised optimisation is a key issue for multi-agent systems, and while many solution techniques have been developed, few provide support for dynamic environments, which change over time, such as disaster management. Given this, in this paper, we present Bounded Fast Max Sum (BFMS): a novel, dynamic, superstabilizing algorithm which provides a bounded approximate solution to certain classes of distributed constraint optimisation problems. We achieve this by eliminating dependencies in the constraint functions, according to how much impact they have on the overall solution value. In more detail, we propose iGHS, which computes a maximum spanning tree on subsections of the constraint graph, in order to reduce communication and computation overheads. Given this, we empirically evaluate BFMS, which shows that BFMS reduces communication and computation done by Bounded Max Sum by up to 99%, while obtaining 60-88% of the optimal utility. |
Ramchurn, S D; Polukarov, Mariya; Farinelli, Alessandro; Jennings, Nick; Trong, Cuong Coalition Formation with Spatial and Temporal Constraints Inproceedings International Joint Conference on Autonomous Agents and Multi-Agent Systems (AAMAS 2010), pp. 1181–1188, 2010, (Event Dates: May 2010). @inproceedings{eps268497, title = {Coalition Formation with Spatial and Temporal Constraints}, author = {S. D. Ramchurn and Mariya Polukarov and Alessandro Farinelli and Nick Jennings and Cuong Trong}, url = {http://eprints.soton.ac.uk/268497/}, year = {2010}, date = {2010-01-01}, booktitle = {International Joint Conference on Autonomous Agents and Multi-Agent Systems (AAMAS 2010)}, pages = {1181--1188}, abstract = {The coordination of emergency responders and robots to undertake a number of tasks in disaster scenarios is a grand challenge for multi-agent systems. Central to this endeavour is the problem of forming the best teams (coalitions) of responders to perform the various tasks in the area where the disaster has struck. Moreover, these teams may have to form, disband, and reform in different areas of the disaster region. This is because in most cases there will be more tasks than agents. Hence, agents need to schedule themselves to attempt each task in turn. Second, the tasks themselves can be very complex: requiring the agents to work on them for different lengths of time and having deadlines by when they need to be completed. The problem is complicated still further when different coalitions perform tasks with different levels of efficiency. Given all these facets, we define this as The Coalition Formation with Spatial and Temporal constraints problem (CFSTP).We show that this problem is NP-hard--in particular, it contains the wellknown complex combinatorial problem of Team Orienteering as a special case. Based on this, we design a Mixed Integer Program to optimally solve small-scale instances of the CFSTP and develop new anytime heuristics that can, on average, complete 97% of the tasks for large problems (20 agents and 300 tasks). In so doing, our solutions represent the first results for CFSTP.}, note = {Event Dates: May 2010}, keywords = {}, pubstate = {published}, tppubtype = {inproceedings} } The coordination of emergency responders and robots to undertake a number of tasks in disaster scenarios is a grand challenge for multi-agent systems. Central to this endeavour is the problem of forming the best teams (coalitions) of responders to perform the various tasks in the area where the disaster has struck. Moreover, these teams may have to form, disband, and reform in different areas of the disaster region. This is because in most cases there will be more tasks than agents. Hence, agents need to schedule themselves to attempt each task in turn. Second, the tasks themselves can be very complex: requiring the agents to work on them for different lengths of time and having deadlines by when they need to be completed. The problem is complicated still further when different coalitions perform tasks with different levels of efficiency. Given all these facets, we define this as The Coalition Formation with Spatial and Temporal constraints problem (CFSTP).We show that this problem is NP-hard--in particular, it contains the wellknown complex combinatorial problem of Team Orienteering as a special case. Based on this, we design a Mixed Integer Program to optimally solve small-scale instances of the CFSTP and develop new anytime heuristics that can, on average, complete 97% of the tasks for large problems (20 agents and 300 tasks). In so doing, our solutions represent the first results for CFSTP. |
Ramchurn, Sarvapali; Farinelli, Alessandro; Macarthur, Kathryn; Polukarov, Mariya; Jennings, Nick Decentralised Coordination in RoboCup Rescue Journal Article The Computer Journal, 53 (9), pp. 1–15, 2010. @article{eps268499, title = {Decentralised Coordination in RoboCup Rescue}, author = {Sarvapali Ramchurn and Alessandro Farinelli and Kathryn Macarthur and Mariya Polukarov and Nick Jennings}, url = {http://eprints.soton.ac.uk/268499/}, year = {2010}, date = {2010-01-01}, journal = {The Computer Journal}, volume = {53}, number = {9}, pages = {1--15}, publisher = {Oxford Journals}, abstract = {Emergency responders are faced with a number of significant challenges when managing major disasters. First, the number of rescue tasks posed is usually larger than the number of responders (or agents) and the resources available to them. Second, each task is likely to require a different level of effort in order to be completed by its deadline. Third, new tasks may continually appear or disappear from the environment, thus requiring the responders to quickly recompute their allocation of resources. Fourth, forming teams or coalitions of multiple agents from different agencies is vital since no single agency will have all the resources needed to save victims, unblock roads, and extinguish the ?res which might erupt in the disaster space. Given this, coalitions have to be efficiently selected and scheduled to work across the disaster space so as to maximise the number of lives and the portion of the infrastructure saved. In particular, it is important that the selection of such coalitions should be performed in a decentralised fashion in order to avoid a single point of failure in the system. Moreover, it is critical that responders communicate only locally given they are likely to have limited battery power or minimal access to long range communication devices. Against this background, we provide a novel decentralised solution to the coalition formation process that pervades disaster management. More specifically, we model the emergency management scenario defined in the RoboCup Rescue disaster simulation platform as a Coalition Formation with Spatial and Temporal constraints (CFST) problem where agents form coalitions in order to complete tasks, each with different demands. In order to design a decentralised algorithm for CFST we formulate it as a Distributed Constraint Optimisation problem and show how to solve it using the state-of-the-art Max-Sum algorithm that provides a completely decentralised message-passing solution. We then provide a novel algorithm (F-Max-Sum) that avoids sending redundant messages and efficiently adapts to changes in the environment. In empirical evaluations, our algorithm is shown to generate better solutions than other decentralised algorithms used for this problem.}, keywords = {}, pubstate = {published}, tppubtype = {article} } Emergency responders are faced with a number of significant challenges when managing major disasters. First, the number of rescue tasks posed is usually larger than the number of responders (or agents) and the resources available to them. Second, each task is likely to require a different level of effort in order to be completed by its deadline. Third, new tasks may continually appear or disappear from the environment, thus requiring the responders to quickly recompute their allocation of resources. Fourth, forming teams or coalitions of multiple agents from different agencies is vital since no single agency will have all the resources needed to save victims, unblock roads, and extinguish the ?res which might erupt in the disaster space. Given this, coalitions have to be efficiently selected and scheduled to work across the disaster space so as to maximise the number of lives and the portion of the infrastructure saved. In particular, it is important that the selection of such coalitions should be performed in a decentralised fashion in order to avoid a single point of failure in the system. Moreover, it is critical that responders communicate only locally given they are likely to have limited battery power or minimal access to long range communication devices. Against this background, we provide a novel decentralised solution to the coalition formation process that pervades disaster management. More specifically, we model the emergency management scenario defined in the RoboCup Rescue disaster simulation platform as a Coalition Formation with Spatial and Temporal constraints (CFST) problem where agents form coalitions in order to complete tasks, each with different demands. In order to design a decentralised algorithm for CFST we formulate it as a Distributed Constraint Optimisation problem and show how to solve it using the state-of-the-art Max-Sum algorithm that provides a completely decentralised message-passing solution. We then provide a novel algorithm (F-Max-Sum) that avoids sending redundant messages and efficiently adapts to changes in the environment. In empirical evaluations, our algorithm is shown to generate better solutions than other decentralised algorithms used for this problem. |
Vytelingum, Perukrishnen; Ramchurn, Sarvapali D; Voice, Thomas D; Rogers, Alex; Jennings, Nicholas R Trading agents for the smart electricity grid Inproceedings The Ninth International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2010), pp. 897–904, 2010, (Event Dates: May 10-14, 2010). @inproceedings{eps268361, title = {Trading agents for the smart electricity grid}, author = {Perukrishnen Vytelingum and Sarvapali D. Ramchurn and Thomas D. Voice and Alex Rogers and Nicholas R. Jennings}, url = {http://eprints.soton.ac.uk/268361/}, year = {2010}, date = {2010-01-01}, booktitle = {The Ninth International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2010)}, pages = {897--904}, abstract = {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 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 unforeseen demand or increased supply capacity in real time. Finally, we develop new strategies that we show achieve high market efficiency (typically over 90%).}, note = {Event Dates: May 10-14, 2010}, keywords = {}, pubstate = {published}, tppubtype = {inproceedings} } 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 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 unforeseen demand or increased supply capacity in real time. Finally, we develop new strategies that we show achieve high market efficiency (typically over 90%). |
Vytelingum, Perukrishnen; Voice, Thomas D; Ramchurn, Sarvapali D; Rogers, Alex; Jennings, Nicholas R Agent-Based Micro-Storage Management for the Smart Grid Inproceedings The Ninth International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2010) - Won the Best Paper Award, pp. 39–46, 2010, (Winner of the Best Paper Award Event Dates: May 10-14, 2010). @inproceedings{eps268360, title = {Agent-Based Micro-Storage Management for the Smart Grid}, author = {Perukrishnen Vytelingum and Thomas D. Voice and Sarvapali D. Ramchurn and Alex Rogers and Nicholas R. Jennings}, url = {http://eprints.soton.ac.uk/268360/}, year = {2010}, date = {2010-01-01}, booktitle = {The Ninth International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2010) - Won the Best Paper Award}, pages = {39--46}, abstract = {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).}, note = {Winner of the Best Paper Award Event Dates: May 10-14, 2010}, keywords = {}, pubstate = {published}, tppubtype = {inproceedings} } 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). |
2009 |
Rahwan, Talal; Ramchurn, Sarvapali; Jennings, Nicholas; Giovannucci, Andrea An anytime algorithm for optimal coalition structure generation Journal Article Journal of Artificial Intelligence Research, 34 , pp. 521–567, 2009. @article{eps267179, title = {An anytime algorithm for optimal coalition structure generation}, author = {Talal Rahwan and Sarvapali Ramchurn and Nicholas Jennings and Andrea Giovannucci}, url = {http://eprints.soton.ac.uk/267179/}, year = {2009}, date = {2009-01-01}, journal = {Journal of Artificial Intelligence Research}, volume = {34}, pages = {521--567}, abstract = {Coalition formation is a fundamental type of interaction that involves the creation of coherent groupings of distinct, autonomous, agents in order to efficiently achieve their individual or collective goals. Forming effective coalitions is a major research challenge in the field of multi-agent systems. Central to this endeavour is the problem of determining which of the many possible coalitions to form in order to achieve some goal. This usually requires calculating a value for every possible coalition, known as the coalition value, which indicates how beneficial that coalition would be if it was formed. Once these values are calculated, the agents usually need to find a combination of coalitions, in which every agent belongs to exactly one coalition, and by which the overall outcome of the system is maximized. However, this coalition structure generation problem is extremely challenging due to the number of possible solutions that need to be examined, which grows exponentially with the number of agents involved. To date, therefore, many algorithms have been proposed to solve this problem using different techniques--ranging from dynamic programming, to integer programming, to stochastic search -- all of which suffer from major limitations relating to execution time, solution quality, and memory requirements. With this in mind, we develop an anytime algorithm to solve the coalition structure generation problem. Specifically, the algorithm uses a novel representation of the search space, which partitions the space of possible solutions into sub-spaces such that it is possible to compute upper and lower bounds on the values of the best coalition structures in them. These bounds are then used to identify the sub-spaces that have no potential of containing the optimal solution so that they can be pruned. The algorithm, then, searches through the remaining sub-spaces very efficiently using a branch-and-bound technique to avoid examining all the solutions within the searched subspace(s). In this setting, we prove that our algorithm enumerates all coalition structures efficiently by avoiding redundant and invalid solutions automatically. Moreover, in order to effectively test our algorithm we develop a new type of input distribution which allows us to generate more reliable benchmarks compared to the input distributions previously used in the field. Given this new distribution, we show that for 27 agents our algorithm is able to find solutions that are optimal in 0:175% of the time required by the fastest available algorithm in the literature. The algorithm is anytime, and if interrupted before it would have normally terminated, it can still provide a solution that is guaranteed to be within a bound from the optimal one. Moreover, the guarantees we provide on the quality of the solution are significantly better than those provided by the previous state of the art algorithms designed for this purpose. For example, for the worst case distribution given 25 agents, our algorithm is able to find a 90% efficient solution in around 10% of time it takes to find the optimal solution.}, keywords = {}, pubstate = {published}, tppubtype = {article} } Coalition formation is a fundamental type of interaction that involves the creation of coherent groupings of distinct, autonomous, agents in order to efficiently achieve their individual or collective goals. Forming effective coalitions is a major research challenge in the field of multi-agent systems. Central to this endeavour is the problem of determining which of the many possible coalitions to form in order to achieve some goal. This usually requires calculating a value for every possible coalition, known as the coalition value, which indicates how beneficial that coalition would be if it was formed. Once these values are calculated, the agents usually need to find a combination of coalitions, in which every agent belongs to exactly one coalition, and by which the overall outcome of the system is maximized. However, this coalition structure generation problem is extremely challenging due to the number of possible solutions that need to be examined, which grows exponentially with the number of agents involved. To date, therefore, many algorithms have been proposed to solve this problem using different techniques--ranging from dynamic programming, to integer programming, to stochastic search -- all of which suffer from major limitations relating to execution time, solution quality, and memory requirements. With this in mind, we develop an anytime algorithm to solve the coalition structure generation problem. Specifically, the algorithm uses a novel representation of the search space, which partitions the space of possible solutions into sub-spaces such that it is possible to compute upper and lower bounds on the values of the best coalition structures in them. These bounds are then used to identify the sub-spaces that have no potential of containing the optimal solution so that they can be pruned. The algorithm, then, searches through the remaining sub-spaces very efficiently using a branch-and-bound technique to avoid examining all the solutions within the searched subspace(s). In this setting, we prove that our algorithm enumerates all coalition structures efficiently by avoiding redundant and invalid solutions automatically. Moreover, in order to effectively test our algorithm we develop a new type of input distribution which allows us to generate more reliable benchmarks compared to the input distributions previously used in the field. Given this new distribution, we show that for 27 agents our algorithm is able to find solutions that are optimal in 0:175% of the time required by the fastest available algorithm in the literature. The algorithm is anytime, and if interrupted before it would have normally terminated, it can still provide a solution that is guaranteed to be within a bound from the optimal one. Moreover, the guarantees we provide on the quality of the solution are significantly better than those provided by the previous state of the art algorithms designed for this purpose. For example, for the worst case distribution given 25 agents, our algorithm is able to find a 90% efficient solution in around 10% of time it takes to find the optimal solution. |
Ramchurn, Sarvapali D; Mezzetti, Claudio; Giovannucci, Andrea; Rodriguez, Juan A; Dash, Rajdeep K; Jennings, Nicholas R Trust-based mechanisms for robust and efficient task allocation in the presence of execution uncertainty Journal Article Journal of Artificial Intelligence Research, 35 , pp. 1–41, 2009. @article{eps267288, title = {Trust-based mechanisms for robust and efficient task allocation in the presence of execution uncertainty}, author = {Sarvapali D. Ramchurn and Claudio Mezzetti and Andrea Giovannucci and Juan A. Rodriguez and Rajdeep K. Dash and Nicholas R. Jennings}, url = {http://eprints.soton.ac.uk/267288/}, year = {2009}, date = {2009-01-01}, journal = {Journal of Artificial Intelligence Research}, volume = {35}, pages = {1--41}, abstract = {Vickrey-Clarke-Groves (VCG) mechanisms are often used to allocate tasks to selfish and rational agents. VCG mechanisms are incentive-compatible, direct mechanisms that are efficient (i.e. maximise social utility) and individually rational (i.e. agents prefer to join rather than opt out). However, an important assumption of these mechanisms is that the agents will always successfully complete their allocated tasks. Clearly, this assumption is unrealistic in many real-world applications where agents can, and often do, fail in their endeavours. Moreover, whether an agent is deemed to have failed may be perceived differently by different agents. Such subjective perceptions about an agent's probability of succeeding at a given task are often captured and reasoned about using the notion of trust. Given this background, in this paper we investigate the design of novel mechanisms that take into account the trust between agents when allocating tasks. Specifically, we develop a new class of mechanisms, called trust-based mechanisms, that can take into account multiple subjective measures of the probability of an agent succeeding at a given task and produce allocations that maximise social utility, whilst ensuring that no agent obtains a negative utility. We then show that such mechanisms pose a challenging new combinatorial optimisation problem (that is NP-complete), devise a novel representation for solving the problem, and develop an effective integer programming solution (that can solve instances with about 2x10^ 5 possible allocations in 40 seconds).}, keywords = {}, pubstate = {published}, tppubtype = {article} } Vickrey-Clarke-Groves (VCG) mechanisms are often used to allocate tasks to selfish and rational agents. VCG mechanisms are incentive-compatible, direct mechanisms that are efficient (i.e. maximise social utility) and individually rational (i.e. agents prefer to join rather than opt out). However, an important assumption of these mechanisms is that the agents will always successfully complete their allocated tasks. Clearly, this assumption is unrealistic in many real-world applications where agents can, and often do, fail in their endeavours. Moreover, whether an agent is deemed to have failed may be perceived differently by different agents. Such subjective perceptions about an agent's probability of succeeding at a given task are often captured and reasoned about using the notion of trust. Given this background, in this paper we investigate the design of novel mechanisms that take into account the trust between agents when allocating tasks. Specifically, we develop a new class of mechanisms, called trust-based mechanisms, that can take into account multiple subjective measures of the probability of an agent succeeding at a given task and produce allocations that maximise social utility, whilst ensuring that no agent obtains a negative utility. We then show that such mechanisms pose a challenging new combinatorial optimisation problem (that is NP-complete), devise a novel representation for solving the problem, and develop an effective integer programming solution (that can solve instances with about 2x10^ 5 possible allocations in 40 seconds). |
van Valkenhoef, Gert; Ramchurn, Sarvapali D; Vytelingum, Perukrishnen; Jennings, Nicholas R; Verbrugge, Rinek Continuous double auctions with execution uncertainty Inproceedings Workshop on Trading Agent Design and Analysis (TADA-09), 2009. @inproceedings{eps267329, title = {Continuous double auctions with execution uncertainty}, author = {Gert van Valkenhoef and Sarvapali D. Ramchurn and Perukrishnen Vytelingum and Nicholas R. Jennings and Rinek Verbrugge}, url = {http://eprints.soton.ac.uk/267329/}, year = {2009}, date = {2009-01-01}, booktitle = {Workshop on Trading Agent Design and Analysis (TADA-09)}, abstract = {We propose a novel variant of the Continuous Double Auction (CDA), the Trust-based CDA (T-CDA), which we demonstrate to be robust to execution uncertainty. This is desirable in a setting where traders may fail to deliver the goods, services or payments they have promised. Specifically, the TCDA provides a mechanism that allows agents to commit to trades they believe will maximize their expected utility. In this paper, we consider agents that use their trust in other agents to estimate the expected utility of a transaction. We empirically evaluate the mechanism, both against the optimal solution given perfect and complete information and against the standard CDA.We show that the T-CDA consistently outperforms the traditional CDA as execution uncertainty increases in the system. Furthermore, we investigate the robustness of the mechanism to unreliable trust information and find that performance degrades gracefully as information quality decreases.}, keywords = {}, pubstate = {published}, tppubtype = {inproceedings} } We propose a novel variant of the Continuous Double Auction (CDA), the Trust-based CDA (T-CDA), which we demonstrate to be robust to execution uncertainty. This is desirable in a setting where traders may fail to deliver the goods, services or payments they have promised. Specifically, the TCDA provides a mechanism that allows agents to commit to trades they believe will maximize their expected utility. In this paper, we consider agents that use their trust in other agents to estimate the expected utility of a transaction. We empirically evaluate the mechanism, both against the optimal solution given perfect and complete information and against the standard CDA.We show that the T-CDA consistently outperforms the traditional CDA as execution uncertainty increases in the system. Furthermore, we investigate the robustness of the mechanism to unreliable trust information and find that performance degrades gracefully as information quality decreases. |
Publications
2014 |
Supporting Team Coordination on the Ground: Requirements from a Mixed Reality Game. Inproceedings 11th Int. Conference on the Design of Cooperative Systems (COOP ?14), 2014. |
Social Implications of Agent-based Planning Support for Human Teams. Inproceedings 2014 Int. Conference on Collaboration Technologies and Systems, 2014. |
Coalition Structure Generation with the Graphics Processing Unit Inproceedings 13th Int. Conf. on Autonomous Agents and Multi-Agent Systems, 2014. |
Data quality assessment from provenance graphs Inproceedings Provenance Analytics 2014, 2014. |
On human-agent collectives Journal Article Communications of the ACM, 57 (12), pp. 33-42, 2014. |
Anytime Coalition Structure Generation on Synergy Graphs Inproceedings 13th Int. Conf. on Autonomous Agents and Multi-Agent Systems, pp. 13-20, 2014. |
2013 |
Towards a smart home framework Inproceedings 5th ACM Workshop On Embedded Systems For Energy-Efficient Buildings (BuildSys2013), 2013. |
Twelfth International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2013), 2013. |
Interdependent multi-issue negotiation for energy exchange in remote communities Inproceedings Twenty-Seventh AAAI Conference on Artificial Intelligence (AAAI-13), 2013. |
Interdependent multi-issue negotiation for energy exchange in remote communities Inproceedings International Workshop on AI Problems and Approaches for Intelligent Environments (AI4IE), 2013. |
A tutorial on optimisation for multi-agent systems Journal Article The Computer Journal, pp. 1–26, 2013. |
C-Link: a hierarchical clustering approach to large-scale near-optimal coalition formation Inproceedings 23rd International Joint Conference on Artificial Intelligence, AAAI Press / International Joint Conferences on Artificial Intelligence, 2013. |
Recommending Energy Tariffs and Load Shifting Based on Smart Household Usage Profiling Inproceedings International Conference on Intelligent User Interfaces, pp. 383–394, 2013. |
Interpretation of Crowdsourced Activities Using Provenance Network Analysis Inproceedings The First AAAI Conference on Human Computation and Crowdsourcing, Association for the Advancement of Artificial Intelligence, 2013. |
RMASBench: a benchmarking system for multi-agent coordination in urban search and rescue Inproceedings International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS 2013), 2013. |
AgentSwitch: towards smart electricity tariff selection Inproceedings 12th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2013), International Foundation for Autonomous Agents and Multiagent Systems, 2013. |
Collabmap: crowdsourcing maps for emergency planning Inproceedings The 5th Annual ACM Web Science Conference, pp. 326–335, 2013. |
Congestion management for urban EV charging systems Inproceedings 4th IEEE International Conference on Smart Grid Communications (SmartGridComm), IEEE, 2013. |
Solving the coalition structure generation problem on a GPU Inproceedings 6th International Workshop on Optimisation in Multi-Agent Systems, 2013. |
Forecasting multi-appliance usage for smart home energy management Inproceedings 23rd International Joint Conference on Artificial Intelligence (IJCAI 2013), 2013. |
Activity prediction for agent-based home energy management Inproceedings Agent Technologies for Energy Systems (ATES 2013), 2013. |
Towards appliance usage prediction for home energy management Inproceedings ACM E-Energy 2013, 2013. |
2012 |
Understanding domestic energy consumption through interactive visualisation: a field study Inproceedings UbiComp '12. Proceedings of the 2012 ACM Conference on Ubiquitous Computing, pp. 216–225, 2012. |
Network analysis on provenance graphs from a crowdsourcing application Inproceedings Groth, Paul; Frew, James (Ed.): 4th International Provenance and Annotation Workshop, pp. 168–182, 2012. |
Competing with humans at fantasy football: team formation in large partially-observable domains Inproceedings Proceedings of the Twenty-Sixth Conference on Artificial Intelligence, pp. 1394–1400, Association for the Advancement of Artificial Intelligence, 2012. |
Optimal Decentralised Dispatch of Embedded Generation in the Smart Grid Journal Article In Proc. 11th Int. Conference on Autonomous Agents and Multi-Agent Systems (AAMAS), 2012. |
Putting the Smarts into the Smart Grid: A Grand Challenge for Artificial Intelligence Journal Article Communications of the ACM, 55 (4), pp. 86–97, 2012. |
Practical distributed coalition formation via heuristic negotiation in social networks Inproceedings Fifth International Workshop on Optimisation in Multi-Agent Systems (OPTMAS), 2012. |
Evaluating semi-automatic annotation of domestic energy consumption as a memory aid Inproceedings UbiComp '12 Proceedings of the 2012 ACM Conference on Ubiquitous Computing, pp. 613–614, 2012. |
Delivering the smart grid: Challenges for autonomous agents and multi-agent systems research Inproceedings Twenty-Sixth AAAI Conference on Artificial Intelligence (AAAI-12), pp. 2166–2172, 2012. |
Predicting energy consumption activities for home energy management Inproceedings Agent Technologies for Energy Systems (ATES 2012), 2012. |
On coalition formation with sparse synergies Inproceedings Proc. 11th Int. Conference on Autonomous Agents and Multi-Agent Systems (AAMAS), pp. 223–230, 2012. |
Using a Bayesian Model to Combine LDA Features with Crowdsourced Responses Inproceedings Proceedings of The Twenty-First Text REtrieval Conference, TREC 2012, Gaithersburg, Maryland, USA, November 6-9, 2012, 2012. |
2011 |
A negotiation protocol for multiple interdependent issues negotiation over energy exchange Inproceedings IJCAI Workshop on AI for an Intelligent Planet, 2011, (Event Dates: July-16). |
A Distributed Anytime Algorithm for Dynamic Task Allocation in Multi-Agent Systems Inproceedings Twenty-Fifth Conference on Artificial Intelligence (AAAI), pp. 701–706, AAAI Press, 2011, (Event Dates: August 7-11, 2011). |
Decentralised Parallel Machine Scheduling for Multi-Agent Task Allocation Inproceedings Fourth International Workshop on Optimisation in Multi-Agent Systems, 2011, (Event Dates: May 3, 2011). |
Gaussian Processes for Time Series Prediction Incollection Bayesian Time Series Models, pp. 341–360, Cambridge University Press, 2011, (Chapter: 16). |
Agent-based homeostatic control for green energy in the smart grid Journal Article ACM Transactions on Intelligent Systems and Technology, 2 (4), pp. 35:1–35:28, 2011. |
Agent-based control for decentralised demand side management in the smart grid Inproceedings The Tenth International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2011), pp. 5–12, 2011. |
CollabMap: Augmenting Maps using the Wisdom of Crowds Inproceedings Third Human Computation Workshop, 2011. |
Decentralised Control of Micro-Storage in the Smart Grid Inproceedings AAAI-11: Twenty-Fifth Conference on Artificial Intelligence, pp. 1421–1426, 2011, (Event Dates: August 7?11, 2011). |
Theoretical and practical foundations of large-scale agent-based micro-storage in the smart grid Journal Article Journal of Artificial Intelligence Research, 42 , pp. 765–813, 2011, (AAMAS 2010 iRobot Best Paper Award). |
2010 |
Efficient, Superstabilizing Decentralised Optimisation for Dynamic Task Allocation Environments Inproceedings Third International Workshop on: Optimisation in Multi-Agent Systems (OptMas) at the Ninth Joint Conference on Autonomous and Multi-Agent Systems, pp. 25–32, 2010, (Event Dates: 10 May 2010). |
Coalition Formation with Spatial and Temporal Constraints Inproceedings International Joint Conference on Autonomous Agents and Multi-Agent Systems (AAMAS 2010), pp. 1181–1188, 2010, (Event Dates: May 2010). |
Decentralised Coordination in RoboCup Rescue Journal Article The Computer Journal, 53 (9), pp. 1–15, 2010. |
Trading agents for the smart electricity grid Inproceedings The Ninth International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2010), pp. 897–904, 2010, (Event Dates: May 10-14, 2010). |
Agent-Based Micro-Storage Management for the Smart Grid Inproceedings The Ninth International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2010) - Won the Best Paper Award, pp. 39–46, 2010, (Winner of the Best Paper Award Event Dates: May 10-14, 2010). |
2009 |
An anytime algorithm for optimal coalition structure generation Journal Article Journal of Artificial Intelligence Research, 34 , pp. 521–567, 2009. |
Trust-based mechanisms for robust and efficient task allocation in the presence of execution uncertainty Journal Article Journal of Artificial Intelligence Research, 35 , pp. 1–41, 2009. |
Continuous double auctions with execution uncertainty Inproceedings Workshop on Trading Agent Design and Analysis (TADA-09), 2009. |
