Projects
As systems based on human-agent collectives grow in scale, complexity and temporal extent, we will increasingly require a principled science that allows us to reason about the computational and human aspects of these systems if we are to avoid developments that are unsafe, unreliable and lack the appropriate safeguards to ensure societal acceptance. Delivering this science is the core research objective of this programme.
Publications
2015
Georgios Chalkiadakis Filippo Bistaffa, Alessandro Farinelli; Ramchurn, Sarvapali D.
Recommending Fair Payments for Large-Scale Social Ridesharing Proceedings Article
In: ACM Conference on Recommender Systems (Recsys), 2015.
@inproceedings{bistaffaetal2015,
title = {Recommending Fair Payments for Large-Scale Social Ridesharing},
author = {Filippo Bistaffa, Georgios Chalkiadakis, Alessandro Farinelli, and Sarvapali D. Ramchurn},
url = {http://www.sramchurn.com/wp-content/uploads/2017/02/2015recsys.pdf},
year = {2015},
date = {2015-09-16},
booktitle = {ACM Conference on Recommender Systems (Recsys)},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
2014
Tran-Thanh, Long; Huynh, Trung Dong; Rosenfield, A; Ramchurn, Sarvapali; Jennings, Nicholas R.
BudgetFix: budget limited crowdsourcing for interdependent task allocation with quality guarantees Proceedings Article
In: 13th International Conference on Autonomous Agents and Multi-Agent Systems, International Foundation for Autonomous Agents and Multiagent Systems, 2014.
@inproceedings{eps362321,
title = {BudgetFix: budget limited crowdsourcing for interdependent task allocation with quality guarantees},
author = {Long Tran-Thanh and Trung Dong Huynh and A Rosenfield and Sarvapali Ramchurn and Nicholas R. Jennings},
url = {http://eprints.soton.ac.uk/362321/},
year = {2014},
date = {2014-01-01},
booktitle = {13th International Conference on Autonomous Agents and Multi-Agent Systems},
publisher = {International Foundation for Autonomous Agents and Multiagent Systems},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
Vinyals, Meritxell; Macarthur, Kathryn; Farinelli, Alessandro; Ramchurn, Sarvapali; Jennings, Nicholas R.
A message-passing approach to decentralised parallel machine scheduling Journal Article
In: The Computer Journal, 2014.
@article{eps360818,
title = {A message-passing approach to decentralised parallel machine scheduling},
author = {Meritxell Vinyals and Kathryn Macarthur and Alessandro Farinelli and Sarvapali Ramchurn and Nicholas R. Jennings},
url = {http://eprints.soton.ac.uk/360818/},
year = {2014},
date = {2014-01-01},
journal = {The Computer Journal},
publisher = {Oxford University Press},
abstract = {This paper tackles the problem of parallelizing heterogeneous computational tasks across a number of computational nodes (aka agents) where each agent may not be able to perform all the tasks and may have different computational speeds. An equivalent problem can be found in operations research, and it is known as scheduling tasks on unrelated parallel machines (also known as R?Cmax). Given this equivalence observation, we present the spanning tree decentralized task distribution algorithm (ST-DTDA), the first decentralized solution to R?Cmax. ST-DTDA achieves decomposition by means of the min?max algorithm, a member of the generalized distributive law family, that performs inference by message-passing along the edges of a graphical model (known as a junction tree). Specifically, ST-DTDA uses min?max to optimally solve an approximation of the original R?Cmax problem that results from eliminating possible agent-task allocations until it is mapped into an acyclic structure. To eliminate those allocations that are least likely to have an impact on the solution quality, ST-DTDA uses a heuristic approach. Moreover, ST-DTDA provides a per-instance approximation ratio that guarantees that the makespan of its solution (optimal in the approximated R?Cmax problem) is not more than a factor ensuremathrho times the makespan of the optimal of the original problem. In our empirical evaluation of ST-DTDA, we show that ST-DTDA, with a min-regret heuristic, converges to solutions that are between 78 and 95% optimal whilst providing approximation ratios lower than 3.},
keywords = {},
pubstate = {published},
tppubtype = {article}
}
This paper tackles the problem of parallelizing heterogeneous computational tasks across a number of computational nodes (aka agents) where each agent may not be able to perform all the tasks and may have different computational speeds. An equivalent problem can be found in operations research, and it is known as scheduling tasks on unrelated parallel machines (also known as R?Cmax). Given this equivalence observation, we present the spanning tree decentralized task distribution algorithm (ST-DTDA), the first decentralized solution to R?Cmax. ST-DTDA achieves decomposition by means of the min?max algorithm, a member of the generalized distributive law family, that performs inference by message-passing along the edges of a graphical model (known as a junction tree). Specifically, ST-DTDA uses min?max to optimally solve an approximation of the original R?Cmax problem that results from eliminating possible agent-task allocations until it is mapped into an acyclic structure. To eliminate those allocations that are least likely to have an impact on the solution quality, ST-DTDA uses a heuristic approach. Moreover, ST-DTDA provides a per-instance approximation ratio that guarantees that the makespan of its solution (optimal in the approximated R?Cmax problem) is not more than a factor ensuremathrho times the makespan of the optimal of the original problem. In our empirical evaluation of ST-DTDA, we show that ST-DTDA, with a min-regret heuristic, converges to solutions that are between 78 and 95% optimal whilst providing approximation ratios lower than 3.
Jennings, Nicholas R.; Moreau, Luc; Nicholson, D; Ramchurn, Sarvapali D.; Roberts, S; Rodden, T; Rogers, Alex
On human-agent collectives Journal Article
In: Communications of the ACM, vol. 57, no. 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.
2013
Cerquides, Jesus; Farinelli, Alessandro; Meseguer, Pedro; Ramchurn, Sarvapali
A tutorial on optimisation for multi-agent systems Journal Article
In: 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 Proceedings Article
In: 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.
Ramchurn, Sarvapali D.; Huynh, Trung Dong; Venanzi, Matteo; Shi, Bing
Collabmap: crowdsourcing maps for emergency planning Proceedings Article
In: 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 Proceedings Article
In: 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.
Alam, Muddasser; Rogers, Alex; Ramchurn, Sarvapali
Interdependent multi-issue negotiation for energy exchange in remote communities Proceedings Article
In: 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%
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 Proceedings Article
In: 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.
Huynh, Trung Dong; Ebden, Mark; Venanzi, Matteo; Ramchurn, Sarvapali; Roberts, Stephen; Moreau, Luc
Interpretation of Crowdsourced Activities Using Provenance Network Analysis Proceedings Article
In: 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.
Svensson, Kim; Ramchurn, Sarvapali; Cruz, Francisco; Rodriguez-Aguilar, Juan-Antonio; Cerquides, Jesus
Solving the coalition structure generation problem on a GPU Proceedings Article
In: 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.
Alam, Muddasser; Rogers, Alex; Ramchurn, Sarvapali D.
Interdependent multi-issue negotiation for energy exchange in remote communities Proceedings Article
In: 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}
}
2012
Ramchurn, Sarvapali D.; Gerding, Enrico; Jennings, N. R.; Hu, Jun
Practical distributed coalition formation via heuristic negotiation in social networks Proceedings Article
In: 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.
2011
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
In: Journal of Artificial Intelligence Research, vol. 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).
Macarthur, Kathryn; Stranders, Ruben; Ramchurn, Sarvapali; Jennings, Nick
A Distributed Anytime Algorithm for Dynamic Task Allocation in Multi-Agent Systems Proceedings Article
In: 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.
Ramchurn, Sarvapali; Vytelingum, Perukrishnen; Rogers, Alex; Jennings, Nick
Agent-based homeostatic control for green energy in the smart grid Journal Article
In: ACM Transactions on Intelligent Systems and Technology, vol. 2, no. 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.
Stranders, Ruben; Ramchurn, Sarvapali; Shi, Bing; Jennings, Nick
CollabMap: Augmenting Maps using the Wisdom of Crowds Proceedings Article
In: 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}
}
Macarthur, Kathryn; Vinyals, Meritxell; Farinelli, Alessandro; Ramchurn, Sarvapali; Jennings, Nick
Decentralised Parallel Machine Scheduling for Multi-Agent Task Allocation Proceedings Article
In: 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 Book Section
In: 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}
}
2010
Ramchurn, Sarvapali; Farinelli, Alessandro; Macarthur, Kathryn; Polukarov, Mariya; Jennings, Nick
Decentralised Coordination in RoboCup Rescue Journal Article
In: The Computer Journal, vol. 53, no. 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.
Macarthur, Kathryn; Farinelli, Alessandro; Ramchurn, Sarvapali; Jennings, Nick
Efficient, Superstabilizing Decentralised Optimisation for Dynamic Task Allocation Environments Proceedings Article
In: 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.
