Gopal
Gopal
Gopal
Gopal
Gopal
Gopal
Gopal
Gopal
Gopal
Gopal
font
Filter
×
2021
Worrawichaipat, Phuriwat; Gerding, Enrico; Kaparias, Ioannis; Ramchurn, Sarvapali
Resilient intersection management with multi-vehicle collision avoidance Journal Article
In: Frontiers in Sustainable Cities, vol. 3, 2021.
Abstract | Links | BibTeX | Tags: Computer science, intersection management, multi-agent systems, simulation experiments, Transportation
@article{soton449675,
title = {Resilient intersection management with multi-vehicle collision avoidance},
author = {Phuriwat Worrawichaipat and Enrico Gerding and Ioannis Kaparias and Sarvapali Ramchurn},
url = {https://eprints.soton.ac.uk/449675/},
year = {2021},
date = {2021-06-01},
journal = {Frontiers in Sustainable Cities},
volume = {3},
abstract = {In this paper, we propose a novel decentralised agent-based mechanism for road intersection management for connected autonomous vehicles. In our work we focus on road obstructions causing major traffic delays. In doing so, we propose the first decentralised mechanism able to maximise the overall vehicle throughput at intersections in the presence of obstructions. The distributed algorithm transfers most of the computational cost from the intersection manager to the driving agents, thereby improving scalability. Our realistic empirical experiments using SUMO show that, when an obstacle is located at the entrance or in the middle of the intersection, existing state of the art algorithms and traffic lights show a reduced throughput of 65?90% from the optimal point without obstructions while our mechanism can maintain the throughput upensuremath<br/ensuremath>Q7 to 94?99%.},
keywords = {Computer science, intersection management, multi-agent systems, simulation experiments, Transportation},
pubstate = {published},
tppubtype = {article}
}
In this paper, we propose a novel decentralised agent-based mechanism for road intersection management for connected autonomous vehicles. In our work we focus on road obstructions causing major traffic delays. In doing so, we propose the first decentralised mechanism able to maximise the overall vehicle throughput at intersections in the presence of obstructions. The distributed algorithm transfers most of the computational cost from the intersection manager to the driving agents, thereby improving scalability. Our realistic empirical experiments using SUMO show that, when an obstacle is located at the entrance or in the middle of the intersection, existing state of the art algorithms and traffic lights show a reduced throughput of 65?90% from the optimal point without obstructions while our mechanism can maintain the throughput upensuremath<br/ensuremath>Q7 to 94?99%.
2015
Ramchurn, Sarvapali; Simpson, Edwin; Fischer, Joel; Huynh, Trung Dong; Ikuno, Yuki; Reece, Steven; Jiang, Wenchao; Wu, Feng; Flann, Jack; Roberts, S. J.; Moreau, Luc; Rodden, T.; Jennings, N. R.
HAC-ER: A disaster response system based on human-agent collectives Proceedings Article
In: 14th International Conference on Autonomous Agents and Multi-Agent Systems, 2015.
Abstract | Links | BibTeX | Tags: Coordination, crowdsourcing, human-agent collectives, human-agent interaction, multi-agent systems, uav
@inproceedings{eps374070,
title = {HAC-ER: A disaster response system based on human-agent collectives},
author = {Sarvapali Ramchurn and Edwin Simpson and Joel Fischer and Trung Dong Huynh and Yuki Ikuno and Steven Reece and Wenchao Jiang and Feng Wu and Jack Flann and S. J. Roberts and Luc Moreau and T. Rodden and N. R. Jennings},
url = {http://eprints.soton.ac.uk/374070/},
year = {2015},
date = {2015-01-01},
booktitle = {14th International Conference on Autonomous Agents and Multi-Agent Systems},
abstract = {This paper proposes a novel disaster management system called HAC-ER that addresses some of the challenges faced by emer- gency responders by enabling humans and agents, using state-of- the-art algorithms, to collaboratively plan and carry out tasks in teams referred to as human-agent collectives. In particular, HAC- ER utilises crowdsourcing combined with machine learning to ex- tract situational awareness information from large streams of re- ports posted by members of the public and trusted organisations. We then show how this information can inform human-agent teams in coordinating multi-UAV deployments as well as task planning for responders on the ground. Finally, HAC-ER incorporates a tool for tracking and analysing the provenance of information shared across the entire system. In summary, this paper describes a pro- totype system, validated by real-world emergency responders, that combines several state-of-the-art techniques for integrating humans and agents, and illustrates, for the first time, how such an approach can enable more effective disaster response operations.},
keywords = {Coordination, crowdsourcing, human-agent collectives, human-agent interaction, multi-agent systems, uav},
pubstate = {published},
tppubtype = {inproceedings}
}
This paper proposes a novel disaster management system called HAC-ER that addresses some of the challenges faced by emer- gency responders by enabling humans and agents, using state-of- the-art algorithms, to collaboratively plan and carry out tasks in teams referred to as human-agent collectives. In particular, HAC- ER utilises crowdsourcing combined with machine learning to ex- tract situational awareness information from large streams of re- ports posted by members of the public and trusted organisations. We then show how this information can inform human-agent teams in coordinating multi-UAV deployments as well as task planning for responders on the ground. Finally, HAC-ER incorporates a tool for tracking and analysing the provenance of information shared across the entire system. In summary, this paper describes a pro- totype system, validated by real-world emergency responders, that combines several state-of-the-art techniques for integrating humans and agents, and illustrates, for the first time, how such an approach can enable more effective disaster response operations.
2014
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.
Abstract | Links | BibTeX | Tags: mas, multi-agent systems
@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 = {mas, multi-agent systems},
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.
2013
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.
Abstract | Links | BibTeX | Tags: complex negotiation, Energy, energy exchange, interdependent issues, mas, multi-agent systems, remote communities, smart home
@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 = {complex negotiation, Energy, energy exchange, interdependent issues, mas, multi-agent systems, remote communities, smart home},
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%
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.
Abstract | Links | BibTeX | Tags: hai, mas, multi-agent systems
@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 = {hai, mas, multi-agent systems},
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 Proceedings Article
In: International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS 2013), 2013.
Abstract | Links | BibTeX | Tags: Disaster Management, mas, multi-agent systems
@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 = {Disaster Management, mas, multi-agent systems},
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.
2012
Matthews, Tim; Ramchurn, Sarvapali; Chalkiadakis, Georgios
Competing with humans at fantasy football: team formation in large partially-observable domains Proceedings Article
In: Proceedings of the Twenty-Sixth Conference on Artificial Intelligence, pp. 1394–1400, Association for the Advancement of Artificial Intelligence, 2012.
Abstract | Links | BibTeX | Tags: multi-agent systems, optimisation, sequential decision making, team formation
@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 = {multi-agent systems, optimisation, sequential decision making, team formation},
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
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.
Abstract | Links | BibTeX | Tags: mas, multi-agent systems
@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 = {mas, multi-agent systems},
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
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).
Abstract | Links | BibTeX | Tags: mas, Multi-agent scheduling, multi-agent systems
@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 = {mas, Multi-agent scheduling, multi-agent systems},
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 Proceedings Article
In: Fourth International Workshop on Optimisation in Multi-Agent Systems, 2011, (Event Dates: May 3, 2011).
Abstract | Links | BibTeX | Tags: mas, Multi-agent scheduling, multi-agent systems
@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 = {mas, Multi-agent scheduling, multi-agent systems},
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.
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.
Abstract | Links | BibTeX | Tags: Energy, mas, multi-agent systems
@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 = {Energy, mas, multi-agent systems},
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 Proceedings Article
In: The Tenth International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2011), pp. 5–12, 2011.
Abstract | Links | BibTeX | Tags: agent-based control, agents, demand-side management electricity, Energy, multi-agent systems
@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 = {agent-based control, agents, demand-side management electricity, Energy, multi-agent systems},
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 Proceedings Article
In: Third Human Computation Workshop, 2011.
Links | BibTeX | Tags: Disaster Management, human-agent interaction, mas, multi-agent systems
@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 = {Disaster Management, human-agent interaction, mas, multi-agent systems},
pubstate = {published},
tppubtype = {inproceedings}
}
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).
Abstract | Links | BibTeX | Tags: agents, Energy, mas, multi-agent systems, provenance
@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 = {agents, Energy, mas, multi-agent systems, provenance},
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 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).
Abstract | Links | BibTeX | Tags: agents, Disaster Management, mas, Multi-agent scheduling, multi-agent systems
@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 = {agents, Disaster Management, mas, Multi-agent scheduling, multi-agent systems},
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, 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.
Abstract | Links | BibTeX | Tags: Disaster Management, mas, Multi-agent scheduling, multi-agent systems
@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 = {Disaster Management, mas, Multi-agent scheduling, multi-agent systems},
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.
2009
Rahwan, Talal; Ramchurn, Sarvapali; Jennings, Nicholas; Giovannucci, Andrea
An anytime algorithm for optimal coalition structure generation Journal Article
In: Journal of Artificial Intelligence Research, vol. 34, pp. 521–567, 2009.
Abstract | Links | BibTeX | Tags: Coalition Formation, multi-agent systems
@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 = {Coalition Formation, multi-agent systems},
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.
2007
Rahwan, Talal; Ramchurn, Sarvapali D.; Dang, Viet D.; Giovannucci, Andrea; Jennings, N. R.
Anytime Optimal Coalition Structure Generation Proceedings Article
In: 22nd Conference on Artificial Intelligence (AAAI), pp. 1184–1190, 2007.
Abstract | Links | BibTeX | Tags: Coalition Formation, Coalition Structure Generation, Combinatorial, multi-agent systems, Search, Set Partitioning
@inproceedings{eps263433,
title = {Anytime Optimal Coalition Structure Generation},
author = {Talal Rahwan and Sarvapali D. Ramchurn and Viet D. Dang and Andrea Giovannucci and N. R. Jennings},
url = {http://eprints.soton.ac.uk/263433/},
year = {2007},
date = {2007-01-01},
booktitle = {22nd Conference on Artificial Intelligence (AAAI)},
pages = {1184–1190},
abstract = {Forming effective coalitions is a major research challenge in the field of multi-agent systems. Central to this endeavour is the problem of determining the best groups of agents to select to achieve some goal. To this end, in this paper, we present a novel, optimal anytime algorithm for this coalition structure generation problem that is significantly faster than previous algorithms designed for this purpose. Specifically, our algorithm can generate solutions by partitioning the space of all potential coalitions into sub-spaces that contain coalition structures that are similar, according to some criterion, such that these sub-spaces can be pruned by identifying their bounds. Using this representation, the algorithm then searches through only valid and unique coalition structures and selects the best among them using a branch-and-bound technique. We empirically show that we are able to find solutions that are optimal in 0.082% of the time taken by the state of the art dynamic programming algorithm (for 27 agents) using much less memory (O(2^ n) instead of O(3^ n) for the set of n agents). Moreover, our algorithm is the first to be able to solve the coalition structure generation problem for numbers of agents bigger than 27 in reasonable time (less than 90 minutes for 27 agents as opposed to around 2 months for the best previous solution).},
keywords = {Coalition Formation, Coalition Structure Generation, Combinatorial, multi-agent systems, Search, Set Partitioning},
pubstate = {published},
tppubtype = {inproceedings}
}
Forming effective coalitions is a major research challenge in the field of multi-agent systems. Central to this endeavour is the problem of determining the best groups of agents to select to achieve some goal. To this end, in this paper, we present a novel, optimal anytime algorithm for this coalition structure generation problem that is significantly faster than previous algorithms designed for this purpose. Specifically, our algorithm can generate solutions by partitioning the space of all potential coalitions into sub-spaces that contain coalition structures that are similar, according to some criterion, such that these sub-spaces can be pruned by identifying their bounds. Using this representation, the algorithm then searches through only valid and unique coalition structures and selects the best among them using a branch-and-bound technique. We empirically show that we are able to find solutions that are optimal in 0.082% of the time taken by the state of the art dynamic programming algorithm (for 27 agents) using much less memory (O(2^ n) instead of O(3^ n) for the set of n agents). Moreover, our algorithm is the first to be able to solve the coalition structure generation problem for numbers of agents bigger than 27 in reasonable time (less than 90 minutes for 27 agents as opposed to around 2 months for the best previous solution).
2004
Ramchurn, Sarvapali
Multi-Agent Negotiation using Trust and Persuasion PhD Thesis
University of Southampton, 2004.
Abstract | Links | BibTeX | Tags: Argumentation-based Negotiation, multi-agent systems, Negotiation, Persuasion, Trust
@phdthesis{eps260200,
title = {Multi-Agent Negotiation using Trust and Persuasion},
author = {Sarvapali Ramchurn},
url = {http://eprints.soton.ac.uk/260200/},
year = {2004},
date = {2004-01-01},
school = {University of Southampton},
abstract = {In this thesis, we propose a panoply of tools and techniques to manage inter-agent dependencies in open, distributed multi-agent systems that have significant degrees of uncertainty. In particular, we focus on situations in which agents are involved in repeated interactions where they need to negotiate to resolve conflicts that may arise between them. To this end, we endow agents with decision making models that exploit the notion of trust and use persuasive techniques during the negotiation process to reduce the level of uncertainty and achieve better deals in the long run. Firstly, we develop and evaluate a new trust model (called CREDIT) that allows agents to measure the degree of trust they should place in their opponents. This model reduces the uncertainty that agents have about their opponents' reliability. Thus, over repeated interactions, CREDIT enables agents to model their opponents' reliability using probabilistic techniques and a fuzzy reasoning mechanism that allows the combination of measures based on reputation (indirect interactions) and confidence (direct interactions). In so doing, CREDIT takes a wider range of behaviour-influencing factors into account than existing models, including the norms of the agents and the institution within which transactions occur. We then explore a novel application of trust models by showing how the measures developed in CREDIT ca be applied negotiations in multiple encounters. Specifically we show that agents that use CREDIT are able to avoid unreliable agents, both during the selection of interaction partners and during the negotiation process itself by using trust to adjust their negotiation stance. Also, we empirically show that agents are able to reach good deals with agents that are unreliable to some degree (rather than completely unreliable) and with those that try to strategically exploit their opponent. Secondly, having applied CREDIT to negotiations, we further extend the application of trust to reduce uncertainty about the reliability of agents in mechanism design (where the honesty of agents is elicited by the protocol). Thus, we develop $backslash$acftbmd that allows agents using a trust model (such as CREDIT) to reach efficient agreements that choose the most reliable agents in the long run. In particular, we show that our mechanism enforces truth-telling from the agents (i.e. it is incentive compatible), both about their perceived reliability of their opponent and their valuations for the goods to be traded. In proving the latter properties, our trust-based mechanism is shown to be the first reputation mechanism that implements individual rationality, incentive compatibility, and efficiency. Our trust-based mechanism is also empirically evaluated and shown to be better than other comparable models in reaching the outcome that maximises all the negotiating agents' utilities and in choosing the most reliable agents in the long run. Thirdly, having explored ways to reduce uncertainties about reliability and honesty, we use persuasive negotiation techniques to tackle issues associated with uncertainties that agents have about the preferences and the space of possible agreements. To this end, we propose a novel protocol and reasoning mechanism that agents can use to generate and evaluate persuasive elements, such as promises of future rewards, to support the offers they make during negotiation. These persuasive elements aim to make offers more attractive over multiple encounters given the absence of information about an opponent's discount factors or exact payoffs. Specifically, we empirically demonstrate that agents are able to achieve a larger number of agreements and a higher expected utility over repeated encounters when they are given the capability to give or ask for rewards. Moreover, we develop a novel strategy using this protocol and show that it outperforms existing state of the art heuristic negotiation models. Finally, the applicability of persuasive negotiation and CREDIT is exemplified through a practical implementation in a pervasive computing environment. In this context, the negotiation mechanism is implemented in an instant messaging platform (JABBER) and used to resolve conflicts between group and individual preferences that arise in a meeting room scenario. In particular, we show how persuasive negotiation and trust permit a flexible management of interruptions by allowing intrusions to happen at appropriate times during the meeting while still managing to satisfy the preferences of all parties present.},
keywords = {Argumentation-based Negotiation, multi-agent systems, Negotiation, Persuasion, Trust},
pubstate = {published},
tppubtype = {phdthesis}
}
In this thesis, we propose a panoply of tools and techniques to manage inter-agent dependencies in open, distributed multi-agent systems that have significant degrees of uncertainty. In particular, we focus on situations in which agents are involved in repeated interactions where they need to negotiate to resolve conflicts that may arise between them. To this end, we endow agents with decision making models that exploit the notion of trust and use persuasive techniques during the negotiation process to reduce the level of uncertainty and achieve better deals in the long run. Firstly, we develop and evaluate a new trust model (called CREDIT) that allows agents to measure the degree of trust they should place in their opponents. This model reduces the uncertainty that agents have about their opponents' reliability. Thus, over repeated interactions, CREDIT enables agents to model their opponents' reliability using probabilistic techniques and a fuzzy reasoning mechanism that allows the combination of measures based on reputation (indirect interactions) and confidence (direct interactions). In so doing, CREDIT takes a wider range of behaviour-influencing factors into account than existing models, including the norms of the agents and the institution within which transactions occur. We then explore a novel application of trust models by showing how the measures developed in CREDIT ca be applied negotiations in multiple encounters. Specifically we show that agents that use CREDIT are able to avoid unreliable agents, both during the selection of interaction partners and during the negotiation process itself by using trust to adjust their negotiation stance. Also, we empirically show that agents are able to reach good deals with agents that are unreliable to some degree (rather than completely unreliable) and with those that try to strategically exploit their opponent. Secondly, having applied CREDIT to negotiations, we further extend the application of trust to reduce uncertainty about the reliability of agents in mechanism design (where the honesty of agents is elicited by the protocol). Thus, we develop $backslash$acftbmd that allows agents using a trust model (such as CREDIT) to reach efficient agreements that choose the most reliable agents in the long run. In particular, we show that our mechanism enforces truth-telling from the agents (i.e. it is incentive compatible), both about their perceived reliability of their opponent and their valuations for the goods to be traded. In proving the latter properties, our trust-based mechanism is shown to be the first reputation mechanism that implements individual rationality, incentive compatibility, and efficiency. Our trust-based mechanism is also empirically evaluated and shown to be better than other comparable models in reaching the outcome that maximises all the negotiating agents' utilities and in choosing the most reliable agents in the long run. Thirdly, having explored ways to reduce uncertainties about reliability and honesty, we use persuasive negotiation techniques to tackle issues associated with uncertainties that agents have about the preferences and the space of possible agreements. To this end, we propose a novel protocol and reasoning mechanism that agents can use to generate and evaluate persuasive elements, such as promises of future rewards, to support the offers they make during negotiation. These persuasive elements aim to make offers more attractive over multiple encounters given the absence of information about an opponent's discount factors or exact payoffs. Specifically, we empirically demonstrate that agents are able to achieve a larger number of agreements and a higher expected utility over repeated encounters when they are given the capability to give or ask for rewards. Moreover, we develop a novel strategy using this protocol and show that it outperforms existing state of the art heuristic negotiation models. Finally, the applicability of persuasive negotiation and CREDIT is exemplified through a practical implementation in a pervasive computing environment. In this context, the negotiation mechanism is implemented in an instant messaging platform (JABBER) and used to resolve conflicts between group and individual preferences that arise in a meeting room scenario. In particular, we show how persuasive negotiation and trust permit a flexible management of interruptions by allowing intrusions to happen at appropriate times during the meeting while still managing to satisfy the preferences of all parties present.
1.
Worrawichaipat, Phuriwat; Gerding, Enrico; Kaparias, Ioannis; Ramchurn, Sarvapali
Resilient intersection management with multi-vehicle collision avoidance Journal Article
In: Frontiers in Sustainable Cities, vol. 3, 2021.
@article{soton449675,
title = {Resilient intersection management with multi-vehicle collision avoidance},
author = {Phuriwat Worrawichaipat and Enrico Gerding and Ioannis Kaparias and Sarvapali Ramchurn},
url = {https://eprints.soton.ac.uk/449675/},
year = {2021},
date = {2021-06-01},
journal = {Frontiers in Sustainable Cities},
volume = {3},
abstract = {In this paper, we propose a novel decentralised agent-based mechanism for road intersection management for connected autonomous vehicles. In our work we focus on road obstructions causing major traffic delays. In doing so, we propose the first decentralised mechanism able to maximise the overall vehicle throughput at intersections in the presence of obstructions. The distributed algorithm transfers most of the computational cost from the intersection manager to the driving agents, thereby improving scalability. Our realistic empirical experiments using SUMO show that, when an obstacle is located at the entrance or in the middle of the intersection, existing state of the art algorithms and traffic lights show a reduced throughput of 65?90% from the optimal point without obstructions while our mechanism can maintain the throughput upensuremath<br/ensuremath>Q7 to 94?99%.},
keywords = {},
pubstate = {published},
tppubtype = {article}
}
In this paper, we propose a novel decentralised agent-based mechanism for road intersection management for connected autonomous vehicles. In our work we focus on road obstructions causing major traffic delays. In doing so, we propose the first decentralised mechanism able to maximise the overall vehicle throughput at intersections in the presence of obstructions. The distributed algorithm transfers most of the computational cost from the intersection manager to the driving agents, thereby improving scalability. Our realistic empirical experiments using SUMO show that, when an obstacle is located at the entrance or in the middle of the intersection, existing state of the art algorithms and traffic lights show a reduced throughput of 65?90% from the optimal point without obstructions while our mechanism can maintain the throughput upensuremath<br/ensuremath>Q7 to 94?99%.
2.
Ramchurn, Sarvapali; Simpson, Edwin; Fischer, Joel; Huynh, Trung Dong; Ikuno, Yuki; Reece, Steven; Jiang, Wenchao; Wu, Feng; Flann, Jack; Roberts, S. J.; Moreau, Luc; Rodden, T.; Jennings, N. R.
HAC-ER: A disaster response system based on human-agent collectives Proceedings Article
In: 14th International Conference on Autonomous Agents and Multi-Agent Systems, 2015.
@inproceedings{eps374070,
title = {HAC-ER: A disaster response system based on human-agent collectives},
author = {Sarvapali Ramchurn and Edwin Simpson and Joel Fischer and Trung Dong Huynh and Yuki Ikuno and Steven Reece and Wenchao Jiang and Feng Wu and Jack Flann and S. J. Roberts and Luc Moreau and T. Rodden and N. R. Jennings},
url = {http://eprints.soton.ac.uk/374070/},
year = {2015},
date = {2015-01-01},
booktitle = {14th International Conference on Autonomous Agents and Multi-Agent Systems},
abstract = {This paper proposes a novel disaster management system called HAC-ER that addresses some of the challenges faced by emer- gency responders by enabling humans and agents, using state-of- the-art algorithms, to collaboratively plan and carry out tasks in teams referred to as human-agent collectives. In particular, HAC- ER utilises crowdsourcing combined with machine learning to ex- tract situational awareness information from large streams of re- ports posted by members of the public and trusted organisations. We then show how this information can inform human-agent teams in coordinating multi-UAV deployments as well as task planning for responders on the ground. Finally, HAC-ER incorporates a tool for tracking and analysing the provenance of information shared across the entire system. In summary, this paper describes a pro- totype system, validated by real-world emergency responders, that combines several state-of-the-art techniques for integrating humans and agents, and illustrates, for the first time, how such an approach can enable more effective disaster response operations.},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
This paper proposes a novel disaster management system called HAC-ER that addresses some of the challenges faced by emer- gency responders by enabling humans and agents, using state-of- the-art algorithms, to collaboratively plan and carry out tasks in teams referred to as human-agent collectives. In particular, HAC- ER utilises crowdsourcing combined with machine learning to ex- tract situational awareness information from large streams of re- ports posted by members of the public and trusted organisations. We then show how this information can inform human-agent teams in coordinating multi-UAV deployments as well as task planning for responders on the ground. Finally, HAC-ER incorporates a tool for tracking and analysing the provenance of information shared across the entire system. In summary, this paper describes a pro- totype system, validated by real-world emergency responders, that combines several state-of-the-art techniques for integrating humans and agents, and illustrates, for the first time, how such an approach can enable more effective disaster response operations.
3.
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.
4.
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%
5.
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.
6.
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.
7.
Matthews, Tim; Ramchurn, Sarvapali; Chalkiadakis, Georgios
Competing with humans at fantasy football: team formation in large partially-observable domains Proceedings Article
In: 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
8.
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.
9.
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.
10.
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.
11.
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.
12.
Ramchurn, Sarvapali; Vytelingum, Perukrishnen; Rogers, Alex; Jennings, Nick
Agent-based control for decentralised demand side management in the smart grid Proceedings Article
In: 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).
13.
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}
}
14.
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).
15.
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.
16.
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.
17.
Rahwan, Talal; Ramchurn, Sarvapali; Jennings, Nicholas; Giovannucci, Andrea
An anytime algorithm for optimal coalition structure generation Journal Article
In: Journal of Artificial Intelligence Research, vol. 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.
18.
Rahwan, Talal; Ramchurn, Sarvapali D.; Dang, Viet D.; Giovannucci, Andrea; Jennings, N. R.
Anytime Optimal Coalition Structure Generation Proceedings Article
In: 22nd Conference on Artificial Intelligence (AAAI), pp. 1184–1190, 2007.
@inproceedings{eps263433,
title = {Anytime Optimal Coalition Structure Generation},
author = {Talal Rahwan and Sarvapali D. Ramchurn and Viet D. Dang and Andrea Giovannucci and N. R. Jennings},
url = {http://eprints.soton.ac.uk/263433/},
year = {2007},
date = {2007-01-01},
booktitle = {22nd Conference on Artificial Intelligence (AAAI)},
pages = {1184–1190},
abstract = {Forming effective coalitions is a major research challenge in the field of multi-agent systems. Central to this endeavour is the problem of determining the best groups of agents to select to achieve some goal. To this end, in this paper, we present a novel, optimal anytime algorithm for this coalition structure generation problem that is significantly faster than previous algorithms designed for this purpose. Specifically, our algorithm can generate solutions by partitioning the space of all potential coalitions into sub-spaces that contain coalition structures that are similar, according to some criterion, such that these sub-spaces can be pruned by identifying their bounds. Using this representation, the algorithm then searches through only valid and unique coalition structures and selects the best among them using a branch-and-bound technique. We empirically show that we are able to find solutions that are optimal in 0.082% of the time taken by the state of the art dynamic programming algorithm (for 27 agents) using much less memory (O(2^ n) instead of O(3^ n) for the set of n agents). Moreover, our algorithm is the first to be able to solve the coalition structure generation problem for numbers of agents bigger than 27 in reasonable time (less than 90 minutes for 27 agents as opposed to around 2 months for the best previous solution).},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
Forming effective coalitions is a major research challenge in the field of multi-agent systems. Central to this endeavour is the problem of determining the best groups of agents to select to achieve some goal. To this end, in this paper, we present a novel, optimal anytime algorithm for this coalition structure generation problem that is significantly faster than previous algorithms designed for this purpose. Specifically, our algorithm can generate solutions by partitioning the space of all potential coalitions into sub-spaces that contain coalition structures that are similar, according to some criterion, such that these sub-spaces can be pruned by identifying their bounds. Using this representation, the algorithm then searches through only valid and unique coalition structures and selects the best among them using a branch-and-bound technique. We empirically show that we are able to find solutions that are optimal in 0.082% of the time taken by the state of the art dynamic programming algorithm (for 27 agents) using much less memory (O(2^ n) instead of O(3^ n) for the set of n agents). Moreover, our algorithm is the first to be able to solve the coalition structure generation problem for numbers of agents bigger than 27 in reasonable time (less than 90 minutes for 27 agents as opposed to around 2 months for the best previous solution).
19.
Ramchurn, Sarvapali
Multi-Agent Negotiation using Trust and Persuasion PhD Thesis
University of Southampton, 2004.
@phdthesis{eps260200,
title = {Multi-Agent Negotiation using Trust and Persuasion},
author = {Sarvapali Ramchurn},
url = {http://eprints.soton.ac.uk/260200/},
year = {2004},
date = {2004-01-01},
school = {University of Southampton},
abstract = {In this thesis, we propose a panoply of tools and techniques to manage inter-agent dependencies in open, distributed multi-agent systems that have significant degrees of uncertainty. In particular, we focus on situations in which agents are involved in repeated interactions where they need to negotiate to resolve conflicts that may arise between them. To this end, we endow agents with decision making models that exploit the notion of trust and use persuasive techniques during the negotiation process to reduce the level of uncertainty and achieve better deals in the long run. Firstly, we develop and evaluate a new trust model (called CREDIT) that allows agents to measure the degree of trust they should place in their opponents. This model reduces the uncertainty that agents have about their opponents' reliability. Thus, over repeated interactions, CREDIT enables agents to model their opponents' reliability using probabilistic techniques and a fuzzy reasoning mechanism that allows the combination of measures based on reputation (indirect interactions) and confidence (direct interactions). In so doing, CREDIT takes a wider range of behaviour-influencing factors into account than existing models, including the norms of the agents and the institution within which transactions occur. We then explore a novel application of trust models by showing how the measures developed in CREDIT ca be applied negotiations in multiple encounters. Specifically we show that agents that use CREDIT are able to avoid unreliable agents, both during the selection of interaction partners and during the negotiation process itself by using trust to adjust their negotiation stance. Also, we empirically show that agents are able to reach good deals with agents that are unreliable to some degree (rather than completely unreliable) and with those that try to strategically exploit their opponent. Secondly, having applied CREDIT to negotiations, we further extend the application of trust to reduce uncertainty about the reliability of agents in mechanism design (where the honesty of agents is elicited by the protocol). Thus, we develop $backslash$acftbmd that allows agents using a trust model (such as CREDIT) to reach efficient agreements that choose the most reliable agents in the long run. In particular, we show that our mechanism enforces truth-telling from the agents (i.e. it is incentive compatible), both about their perceived reliability of their opponent and their valuations for the goods to be traded. In proving the latter properties, our trust-based mechanism is shown to be the first reputation mechanism that implements individual rationality, incentive compatibility, and efficiency. Our trust-based mechanism is also empirically evaluated and shown to be better than other comparable models in reaching the outcome that maximises all the negotiating agents' utilities and in choosing the most reliable agents in the long run. Thirdly, having explored ways to reduce uncertainties about reliability and honesty, we use persuasive negotiation techniques to tackle issues associated with uncertainties that agents have about the preferences and the space of possible agreements. To this end, we propose a novel protocol and reasoning mechanism that agents can use to generate and evaluate persuasive elements, such as promises of future rewards, to support the offers they make during negotiation. These persuasive elements aim to make offers more attractive over multiple encounters given the absence of information about an opponent's discount factors or exact payoffs. Specifically, we empirically demonstrate that agents are able to achieve a larger number of agreements and a higher expected utility over repeated encounters when they are given the capability to give or ask for rewards. Moreover, we develop a novel strategy using this protocol and show that it outperforms existing state of the art heuristic negotiation models. Finally, the applicability of persuasive negotiation and CREDIT is exemplified through a practical implementation in a pervasive computing environment. In this context, the negotiation mechanism is implemented in an instant messaging platform (JABBER) and used to resolve conflicts between group and individual preferences that arise in a meeting room scenario. In particular, we show how persuasive negotiation and trust permit a flexible management of interruptions by allowing intrusions to happen at appropriate times during the meeting while still managing to satisfy the preferences of all parties present.},
keywords = {},
pubstate = {published},
tppubtype = {phdthesis}
}
In this thesis, we propose a panoply of tools and techniques to manage inter-agent dependencies in open, distributed multi-agent systems that have significant degrees of uncertainty. In particular, we focus on situations in which agents are involved in repeated interactions where they need to negotiate to resolve conflicts that may arise between them. To this end, we endow agents with decision making models that exploit the notion of trust and use persuasive techniques during the negotiation process to reduce the level of uncertainty and achieve better deals in the long run. Firstly, we develop and evaluate a new trust model (called CREDIT) that allows agents to measure the degree of trust they should place in their opponents. This model reduces the uncertainty that agents have about their opponents' reliability. Thus, over repeated interactions, CREDIT enables agents to model their opponents' reliability using probabilistic techniques and a fuzzy reasoning mechanism that allows the combination of measures based on reputation (indirect interactions) and confidence (direct interactions). In so doing, CREDIT takes a wider range of behaviour-influencing factors into account than existing models, including the norms of the agents and the institution within which transactions occur. We then explore a novel application of trust models by showing how the measures developed in CREDIT ca be applied negotiations in multiple encounters. Specifically we show that agents that use CREDIT are able to avoid unreliable agents, both during the selection of interaction partners and during the negotiation process itself by using trust to adjust their negotiation stance. Also, we empirically show that agents are able to reach good deals with agents that are unreliable to some degree (rather than completely unreliable) and with those that try to strategically exploit their opponent. Secondly, having applied CREDIT to negotiations, we further extend the application of trust to reduce uncertainty about the reliability of agents in mechanism design (where the honesty of agents is elicited by the protocol). Thus, we develop $backslash$acftbmd that allows agents using a trust model (such as CREDIT) to reach efficient agreements that choose the most reliable agents in the long run. In particular, we show that our mechanism enforces truth-telling from the agents (i.e. it is incentive compatible), both about their perceived reliability of their opponent and their valuations for the goods to be traded. In proving the latter properties, our trust-based mechanism is shown to be the first reputation mechanism that implements individual rationality, incentive compatibility, and efficiency. Our trust-based mechanism is also empirically evaluated and shown to be better than other comparable models in reaching the outcome that maximises all the negotiating agents' utilities and in choosing the most reliable agents in the long run. Thirdly, having explored ways to reduce uncertainties about reliability and honesty, we use persuasive negotiation techniques to tackle issues associated with uncertainties that agents have about the preferences and the space of possible agreements. To this end, we propose a novel protocol and reasoning mechanism that agents can use to generate and evaluate persuasive elements, such as promises of future rewards, to support the offers they make during negotiation. These persuasive elements aim to make offers more attractive over multiple encounters given the absence of information about an opponent's discount factors or exact payoffs. Specifically, we empirically demonstrate that agents are able to achieve a larger number of agreements and a higher expected utility over repeated encounters when they are given the capability to give or ask for rewards. Moreover, we develop a novel strategy using this protocol and show that it outperforms existing state of the art heuristic negotiation models. Finally, the applicability of persuasive negotiation and CREDIT is exemplified through a practical implementation in a pervasive computing environment. In this context, the negotiation mechanism is implemented in an instant messaging platform (JABBER) and used to resolve conflicts between group and individual preferences that arise in a meeting room scenario. In particular, we show how persuasive negotiation and trust permit a flexible management of interruptions by allowing intrusions to happen at appropriate times during the meeting while still managing to satisfy the preferences of all parties present.
2021
Worrawichaipat, Phuriwat; Gerding, Enrico; Kaparias, Ioannis; Ramchurn, Sarvapali
Resilient intersection management with multi-vehicle collision avoidance Journal Article
In: Frontiers in Sustainable Cities, vol. 3, 2021.
Abstract | Links | BibTeX | Tags: Computer science, intersection management, multi-agent systems, simulation experiments, Transportation
@article{soton449675,
title = {Resilient intersection management with multi-vehicle collision avoidance},
author = {Phuriwat Worrawichaipat and Enrico Gerding and Ioannis Kaparias and Sarvapali Ramchurn},
url = {https://eprints.soton.ac.uk/449675/},
year = {2021},
date = {2021-06-01},
journal = {Frontiers in Sustainable Cities},
volume = {3},
abstract = {In this paper, we propose a novel decentralised agent-based mechanism for road intersection management for connected autonomous vehicles. In our work we focus on road obstructions causing major traffic delays. In doing so, we propose the first decentralised mechanism able to maximise the overall vehicle throughput at intersections in the presence of obstructions. The distributed algorithm transfers most of the computational cost from the intersection manager to the driving agents, thereby improving scalability. Our realistic empirical experiments using SUMO show that, when an obstacle is located at the entrance or in the middle of the intersection, existing state of the art algorithms and traffic lights show a reduced throughput of 65?90% from the optimal point without obstructions while our mechanism can maintain the throughput upensuremath<br/ensuremath>Q7 to 94?99%.},
keywords = {Computer science, intersection management, multi-agent systems, simulation experiments, Transportation},
pubstate = {published},
tppubtype = {article}
}
In this paper, we propose a novel decentralised agent-based mechanism for road intersection management for connected autonomous vehicles. In our work we focus on road obstructions causing major traffic delays. In doing so, we propose the first decentralised mechanism able to maximise the overall vehicle throughput at intersections in the presence of obstructions. The distributed algorithm transfers most of the computational cost from the intersection manager to the driving agents, thereby improving scalability. Our realistic empirical experiments using SUMO show that, when an obstacle is located at the entrance or in the middle of the intersection, existing state of the art algorithms and traffic lights show a reduced throughput of 65?90% from the optimal point without obstructions while our mechanism can maintain the throughput upensuremath<br/ensuremath>Q7 to 94?99%.
2015
Ramchurn, Sarvapali; Simpson, Edwin; Fischer, Joel; Huynh, Trung Dong; Ikuno, Yuki; Reece, Steven; Jiang, Wenchao; Wu, Feng; Flann, Jack; Roberts, S. J.; Moreau, Luc; Rodden, T.; Jennings, N. R.
HAC-ER: A disaster response system based on human-agent collectives Proceedings Article
In: 14th International Conference on Autonomous Agents and Multi-Agent Systems, 2015.
Abstract | Links | BibTeX | Tags: Coordination, crowdsourcing, human-agent collectives, human-agent interaction, multi-agent systems, uav
@inproceedings{eps374070,
title = {HAC-ER: A disaster response system based on human-agent collectives},
author = {Sarvapali Ramchurn and Edwin Simpson and Joel Fischer and Trung Dong Huynh and Yuki Ikuno and Steven Reece and Wenchao Jiang and Feng Wu and Jack Flann and S. J. Roberts and Luc Moreau and T. Rodden and N. R. Jennings},
url = {http://eprints.soton.ac.uk/374070/},
year = {2015},
date = {2015-01-01},
booktitle = {14th International Conference on Autonomous Agents and Multi-Agent Systems},
abstract = {This paper proposes a novel disaster management system called HAC-ER that addresses some of the challenges faced by emer- gency responders by enabling humans and agents, using state-of- the-art algorithms, to collaboratively plan and carry out tasks in teams referred to as human-agent collectives. In particular, HAC- ER utilises crowdsourcing combined with machine learning to ex- tract situational awareness information from large streams of re- ports posted by members of the public and trusted organisations. We then show how this information can inform human-agent teams in coordinating multi-UAV deployments as well as task planning for responders on the ground. Finally, HAC-ER incorporates a tool for tracking and analysing the provenance of information shared across the entire system. In summary, this paper describes a pro- totype system, validated by real-world emergency responders, that combines several state-of-the-art techniques for integrating humans and agents, and illustrates, for the first time, how such an approach can enable more effective disaster response operations.},
keywords = {Coordination, crowdsourcing, human-agent collectives, human-agent interaction, multi-agent systems, uav},
pubstate = {published},
tppubtype = {inproceedings}
}
This paper proposes a novel disaster management system called HAC-ER that addresses some of the challenges faced by emer- gency responders by enabling humans and agents, using state-of- the-art algorithms, to collaboratively plan and carry out tasks in teams referred to as human-agent collectives. In particular, HAC- ER utilises crowdsourcing combined with machine learning to ex- tract situational awareness information from large streams of re- ports posted by members of the public and trusted organisations. We then show how this information can inform human-agent teams in coordinating multi-UAV deployments as well as task planning for responders on the ground. Finally, HAC-ER incorporates a tool for tracking and analysing the provenance of information shared across the entire system. In summary, this paper describes a pro- totype system, validated by real-world emergency responders, that combines several state-of-the-art techniques for integrating humans and agents, and illustrates, for the first time, how such an approach can enable more effective disaster response operations.
2014
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.
Abstract | Links | BibTeX | Tags: mas, multi-agent systems
@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 = {mas, multi-agent systems},
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.
2013
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.
Abstract | Links | BibTeX | Tags: complex negotiation, Energy, energy exchange, interdependent issues, mas, multi-agent systems, remote communities, smart home
@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 = {complex negotiation, Energy, energy exchange, interdependent issues, mas, multi-agent systems, remote communities, smart home},
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%
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.
Abstract | Links | BibTeX | Tags: hai, mas, multi-agent systems
@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 = {hai, mas, multi-agent systems},
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 Proceedings Article
In: International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS 2013), 2013.
Abstract | Links | BibTeX | Tags: Disaster Management, mas, multi-agent systems
@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 = {Disaster Management, mas, multi-agent systems},
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.
2012
Matthews, Tim; Ramchurn, Sarvapali; Chalkiadakis, Georgios
Competing with humans at fantasy football: team formation in large partially-observable domains Proceedings Article
In: Proceedings of the Twenty-Sixth Conference on Artificial Intelligence, pp. 1394–1400, Association for the Advancement of Artificial Intelligence, 2012.
Abstract | Links | BibTeX | Tags: multi-agent systems, optimisation, sequential decision making, team formation
@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 = {multi-agent systems, optimisation, sequential decision making, team formation},
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
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.
Abstract | Links | BibTeX | Tags: mas, multi-agent systems
@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 = {mas, multi-agent systems},
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
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).
Abstract | Links | BibTeX | Tags: mas, Multi-agent scheduling, multi-agent systems
@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 = {mas, Multi-agent scheduling, multi-agent systems},
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 Proceedings Article
In: Fourth International Workshop on Optimisation in Multi-Agent Systems, 2011, (Event Dates: May 3, 2011).
Abstract | Links | BibTeX | Tags: mas, Multi-agent scheduling, multi-agent systems
@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 = {mas, Multi-agent scheduling, multi-agent systems},
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.
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.
Abstract | Links | BibTeX | Tags: Energy, mas, multi-agent systems
@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 = {Energy, mas, multi-agent systems},
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 Proceedings Article
In: The Tenth International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2011), pp. 5–12, 2011.
Abstract | Links | BibTeX | Tags: agent-based control, agents, demand-side management electricity, Energy, multi-agent systems
@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 = {agent-based control, agents, demand-side management electricity, Energy, multi-agent systems},
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 Proceedings Article
In: Third Human Computation Workshop, 2011.
Links | BibTeX | Tags: Disaster Management, human-agent interaction, mas, multi-agent systems
@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 = {Disaster Management, human-agent interaction, mas, multi-agent systems},
pubstate = {published},
tppubtype = {inproceedings}
}
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).
Abstract | Links | BibTeX | Tags: agents, Energy, mas, multi-agent systems, provenance
@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 = {agents, Energy, mas, multi-agent systems, provenance},
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 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).
Abstract | Links | BibTeX | Tags: agents, Disaster Management, mas, Multi-agent scheduling, multi-agent systems
@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 = {agents, Disaster Management, mas, Multi-agent scheduling, multi-agent systems},
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, 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.
Abstract | Links | BibTeX | Tags: Disaster Management, mas, Multi-agent scheduling, multi-agent systems
@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 = {Disaster Management, mas, Multi-agent scheduling, multi-agent systems},
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.
2009
Rahwan, Talal; Ramchurn, Sarvapali; Jennings, Nicholas; Giovannucci, Andrea
An anytime algorithm for optimal coalition structure generation Journal Article
In: Journal of Artificial Intelligence Research, vol. 34, pp. 521–567, 2009.
Abstract | Links | BibTeX | Tags: Coalition Formation, multi-agent systems
@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 = {Coalition Formation, multi-agent systems},
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.
2007
Rahwan, Talal; Ramchurn, Sarvapali D.; Dang, Viet D.; Giovannucci, Andrea; Jennings, N. R.
Anytime Optimal Coalition Structure Generation Proceedings Article
In: 22nd Conference on Artificial Intelligence (AAAI), pp. 1184–1190, 2007.
Abstract | Links | BibTeX | Tags: Coalition Formation, Coalition Structure Generation, Combinatorial, multi-agent systems, Search, Set Partitioning
@inproceedings{eps263433,
title = {Anytime Optimal Coalition Structure Generation},
author = {Talal Rahwan and Sarvapali D. Ramchurn and Viet D. Dang and Andrea Giovannucci and N. R. Jennings},
url = {http://eprints.soton.ac.uk/263433/},
year = {2007},
date = {2007-01-01},
booktitle = {22nd Conference on Artificial Intelligence (AAAI)},
pages = {1184–1190},
abstract = {Forming effective coalitions is a major research challenge in the field of multi-agent systems. Central to this endeavour is the problem of determining the best groups of agents to select to achieve some goal. To this end, in this paper, we present a novel, optimal anytime algorithm for this coalition structure generation problem that is significantly faster than previous algorithms designed for this purpose. Specifically, our algorithm can generate solutions by partitioning the space of all potential coalitions into sub-spaces that contain coalition structures that are similar, according to some criterion, such that these sub-spaces can be pruned by identifying their bounds. Using this representation, the algorithm then searches through only valid and unique coalition structures and selects the best among them using a branch-and-bound technique. We empirically show that we are able to find solutions that are optimal in 0.082% of the time taken by the state of the art dynamic programming algorithm (for 27 agents) using much less memory (O(2^ n) instead of O(3^ n) for the set of n agents). Moreover, our algorithm is the first to be able to solve the coalition structure generation problem for numbers of agents bigger than 27 in reasonable time (less than 90 minutes for 27 agents as opposed to around 2 months for the best previous solution).},
keywords = {Coalition Formation, Coalition Structure Generation, Combinatorial, multi-agent systems, Search, Set Partitioning},
pubstate = {published},
tppubtype = {inproceedings}
}
Forming effective coalitions is a major research challenge in the field of multi-agent systems. Central to this endeavour is the problem of determining the best groups of agents to select to achieve some goal. To this end, in this paper, we present a novel, optimal anytime algorithm for this coalition structure generation problem that is significantly faster than previous algorithms designed for this purpose. Specifically, our algorithm can generate solutions by partitioning the space of all potential coalitions into sub-spaces that contain coalition structures that are similar, according to some criterion, such that these sub-spaces can be pruned by identifying their bounds. Using this representation, the algorithm then searches through only valid and unique coalition structures and selects the best among them using a branch-and-bound technique. We empirically show that we are able to find solutions that are optimal in 0.082% of the time taken by the state of the art dynamic programming algorithm (for 27 agents) using much less memory (O(2^ n) instead of O(3^ n) for the set of n agents). Moreover, our algorithm is the first to be able to solve the coalition structure generation problem for numbers of agents bigger than 27 in reasonable time (less than 90 minutes for 27 agents as opposed to around 2 months for the best previous solution).
2004
Ramchurn, Sarvapali
Multi-Agent Negotiation using Trust and Persuasion PhD Thesis
University of Southampton, 2004.
Abstract | Links | BibTeX | Tags: Argumentation-based Negotiation, multi-agent systems, Negotiation, Persuasion, Trust
@phdthesis{eps260200,
title = {Multi-Agent Negotiation using Trust and Persuasion},
author = {Sarvapali Ramchurn},
url = {http://eprints.soton.ac.uk/260200/},
year = {2004},
date = {2004-01-01},
school = {University of Southampton},
abstract = {In this thesis, we propose a panoply of tools and techniques to manage inter-agent dependencies in open, distributed multi-agent systems that have significant degrees of uncertainty. In particular, we focus on situations in which agents are involved in repeated interactions where they need to negotiate to resolve conflicts that may arise between them. To this end, we endow agents with decision making models that exploit the notion of trust and use persuasive techniques during the negotiation process to reduce the level of uncertainty and achieve better deals in the long run. Firstly, we develop and evaluate a new trust model (called CREDIT) that allows agents to measure the degree of trust they should place in their opponents. This model reduces the uncertainty that agents have about their opponents' reliability. Thus, over repeated interactions, CREDIT enables agents to model their opponents' reliability using probabilistic techniques and a fuzzy reasoning mechanism that allows the combination of measures based on reputation (indirect interactions) and confidence (direct interactions). In so doing, CREDIT takes a wider range of behaviour-influencing factors into account than existing models, including the norms of the agents and the institution within which transactions occur. We then explore a novel application of trust models by showing how the measures developed in CREDIT ca be applied negotiations in multiple encounters. Specifically we show that agents that use CREDIT are able to avoid unreliable agents, both during the selection of interaction partners and during the negotiation process itself by using trust to adjust their negotiation stance. Also, we empirically show that agents are able to reach good deals with agents that are unreliable to some degree (rather than completely unreliable) and with those that try to strategically exploit their opponent. Secondly, having applied CREDIT to negotiations, we further extend the application of trust to reduce uncertainty about the reliability of agents in mechanism design (where the honesty of agents is elicited by the protocol). Thus, we develop $backslash$acftbmd that allows agents using a trust model (such as CREDIT) to reach efficient agreements that choose the most reliable agents in the long run. In particular, we show that our mechanism enforces truth-telling from the agents (i.e. it is incentive compatible), both about their perceived reliability of their opponent and their valuations for the goods to be traded. In proving the latter properties, our trust-based mechanism is shown to be the first reputation mechanism that implements individual rationality, incentive compatibility, and efficiency. Our trust-based mechanism is also empirically evaluated and shown to be better than other comparable models in reaching the outcome that maximises all the negotiating agents' utilities and in choosing the most reliable agents in the long run. Thirdly, having explored ways to reduce uncertainties about reliability and honesty, we use persuasive negotiation techniques to tackle issues associated with uncertainties that agents have about the preferences and the space of possible agreements. To this end, we propose a novel protocol and reasoning mechanism that agents can use to generate and evaluate persuasive elements, such as promises of future rewards, to support the offers they make during negotiation. These persuasive elements aim to make offers more attractive over multiple encounters given the absence of information about an opponent's discount factors or exact payoffs. Specifically, we empirically demonstrate that agents are able to achieve a larger number of agreements and a higher expected utility over repeated encounters when they are given the capability to give or ask for rewards. Moreover, we develop a novel strategy using this protocol and show that it outperforms existing state of the art heuristic negotiation models. Finally, the applicability of persuasive negotiation and CREDIT is exemplified through a practical implementation in a pervasive computing environment. In this context, the negotiation mechanism is implemented in an instant messaging platform (JABBER) and used to resolve conflicts between group and individual preferences that arise in a meeting room scenario. In particular, we show how persuasive negotiation and trust permit a flexible management of interruptions by allowing intrusions to happen at appropriate times during the meeting while still managing to satisfy the preferences of all parties present.},
keywords = {Argumentation-based Negotiation, multi-agent systems, Negotiation, Persuasion, Trust},
pubstate = {published},
tppubtype = {phdthesis}
}
In this thesis, we propose a panoply of tools and techniques to manage inter-agent dependencies in open, distributed multi-agent systems that have significant degrees of uncertainty. In particular, we focus on situations in which agents are involved in repeated interactions where they need to negotiate to resolve conflicts that may arise between them. To this end, we endow agents with decision making models that exploit the notion of trust and use persuasive techniques during the negotiation process to reduce the level of uncertainty and achieve better deals in the long run. Firstly, we develop and evaluate a new trust model (called CREDIT) that allows agents to measure the degree of trust they should place in their opponents. This model reduces the uncertainty that agents have about their opponents' reliability. Thus, over repeated interactions, CREDIT enables agents to model their opponents' reliability using probabilistic techniques and a fuzzy reasoning mechanism that allows the combination of measures based on reputation (indirect interactions) and confidence (direct interactions). In so doing, CREDIT takes a wider range of behaviour-influencing factors into account than existing models, including the norms of the agents and the institution within which transactions occur. We then explore a novel application of trust models by showing how the measures developed in CREDIT ca be applied negotiations in multiple encounters. Specifically we show that agents that use CREDIT are able to avoid unreliable agents, both during the selection of interaction partners and during the negotiation process itself by using trust to adjust their negotiation stance. Also, we empirically show that agents are able to reach good deals with agents that are unreliable to some degree (rather than completely unreliable) and with those that try to strategically exploit their opponent. Secondly, having applied CREDIT to negotiations, we further extend the application of trust to reduce uncertainty about the reliability of agents in mechanism design (where the honesty of agents is elicited by the protocol). Thus, we develop $backslash$acftbmd that allows agents using a trust model (such as CREDIT) to reach efficient agreements that choose the most reliable agents in the long run. In particular, we show that our mechanism enforces truth-telling from the agents (i.e. it is incentive compatible), both about their perceived reliability of their opponent and their valuations for the goods to be traded. In proving the latter properties, our trust-based mechanism is shown to be the first reputation mechanism that implements individual rationality, incentive compatibility, and efficiency. Our trust-based mechanism is also empirically evaluated and shown to be better than other comparable models in reaching the outcome that maximises all the negotiating agents' utilities and in choosing the most reliable agents in the long run. Thirdly, having explored ways to reduce uncertainties about reliability and honesty, we use persuasive negotiation techniques to tackle issues associated with uncertainties that agents have about the preferences and the space of possible agreements. To this end, we propose a novel protocol and reasoning mechanism that agents can use to generate and evaluate persuasive elements, such as promises of future rewards, to support the offers they make during negotiation. These persuasive elements aim to make offers more attractive over multiple encounters given the absence of information about an opponent's discount factors or exact payoffs. Specifically, we empirically demonstrate that agents are able to achieve a larger number of agreements and a higher expected utility over repeated encounters when they are given the capability to give or ask for rewards. Moreover, we develop a novel strategy using this protocol and show that it outperforms existing state of the art heuristic negotiation models. Finally, the applicability of persuasive negotiation and CREDIT is exemplified through a practical implementation in a pervasive computing environment. In this context, the negotiation mechanism is implemented in an instant messaging platform (JABBER) and used to resolve conflicts between group and individual preferences that arise in a meeting room scenario. In particular, we show how persuasive negotiation and trust permit a flexible management of interruptions by allowing intrusions to happen at appropriate times during the meeting while still managing to satisfy the preferences of all parties present.
1.
Worrawichaipat, Phuriwat; Gerding, Enrico; Kaparias, Ioannis; Ramchurn, Sarvapali
Resilient intersection management with multi-vehicle collision avoidance Journal Article
In: Frontiers in Sustainable Cities, vol. 3, 2021.
@article{soton449675,
title = {Resilient intersection management with multi-vehicle collision avoidance},
author = {Phuriwat Worrawichaipat and Enrico Gerding and Ioannis Kaparias and Sarvapali Ramchurn},
url = {https://eprints.soton.ac.uk/449675/},
year = {2021},
date = {2021-06-01},
journal = {Frontiers in Sustainable Cities},
volume = {3},
abstract = {In this paper, we propose a novel decentralised agent-based mechanism for road intersection management for connected autonomous vehicles. In our work we focus on road obstructions causing major traffic delays. In doing so, we propose the first decentralised mechanism able to maximise the overall vehicle throughput at intersections in the presence of obstructions. The distributed algorithm transfers most of the computational cost from the intersection manager to the driving agents, thereby improving scalability. Our realistic empirical experiments using SUMO show that, when an obstacle is located at the entrance or in the middle of the intersection, existing state of the art algorithms and traffic lights show a reduced throughput of 65?90% from the optimal point without obstructions while our mechanism can maintain the throughput upensuremath<br/ensuremath>Q7 to 94?99%.},
keywords = {},
pubstate = {published},
tppubtype = {article}
}
In this paper, we propose a novel decentralised agent-based mechanism for road intersection management for connected autonomous vehicles. In our work we focus on road obstructions causing major traffic delays. In doing so, we propose the first decentralised mechanism able to maximise the overall vehicle throughput at intersections in the presence of obstructions. The distributed algorithm transfers most of the computational cost from the intersection manager to the driving agents, thereby improving scalability. Our realistic empirical experiments using SUMO show that, when an obstacle is located at the entrance or in the middle of the intersection, existing state of the art algorithms and traffic lights show a reduced throughput of 65?90% from the optimal point without obstructions while our mechanism can maintain the throughput upensuremath<br/ensuremath>Q7 to 94?99%.
2.
Ramchurn, Sarvapali; Simpson, Edwin; Fischer, Joel; Huynh, Trung Dong; Ikuno, Yuki; Reece, Steven; Jiang, Wenchao; Wu, Feng; Flann, Jack; Roberts, S. J.; Moreau, Luc; Rodden, T.; Jennings, N. R.
HAC-ER: A disaster response system based on human-agent collectives Proceedings Article
In: 14th International Conference on Autonomous Agents and Multi-Agent Systems, 2015.
@inproceedings{eps374070,
title = {HAC-ER: A disaster response system based on human-agent collectives},
author = {Sarvapali Ramchurn and Edwin Simpson and Joel Fischer and Trung Dong Huynh and Yuki Ikuno and Steven Reece and Wenchao Jiang and Feng Wu and Jack Flann and S. J. Roberts and Luc Moreau and T. Rodden and N. R. Jennings},
url = {http://eprints.soton.ac.uk/374070/},
year = {2015},
date = {2015-01-01},
booktitle = {14th International Conference on Autonomous Agents and Multi-Agent Systems},
abstract = {This paper proposes a novel disaster management system called HAC-ER that addresses some of the challenges faced by emer- gency responders by enabling humans and agents, using state-of- the-art algorithms, to collaboratively plan and carry out tasks in teams referred to as human-agent collectives. In particular, HAC- ER utilises crowdsourcing combined with machine learning to ex- tract situational awareness information from large streams of re- ports posted by members of the public and trusted organisations. We then show how this information can inform human-agent teams in coordinating multi-UAV deployments as well as task planning for responders on the ground. Finally, HAC-ER incorporates a tool for tracking and analysing the provenance of information shared across the entire system. In summary, this paper describes a pro- totype system, validated by real-world emergency responders, that combines several state-of-the-art techniques for integrating humans and agents, and illustrates, for the first time, how such an approach can enable more effective disaster response operations.},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
This paper proposes a novel disaster management system called HAC-ER that addresses some of the challenges faced by emer- gency responders by enabling humans and agents, using state-of- the-art algorithms, to collaboratively plan and carry out tasks in teams referred to as human-agent collectives. In particular, HAC- ER utilises crowdsourcing combined with machine learning to ex- tract situational awareness information from large streams of re- ports posted by members of the public and trusted organisations. We then show how this information can inform human-agent teams in coordinating multi-UAV deployments as well as task planning for responders on the ground. Finally, HAC-ER incorporates a tool for tracking and analysing the provenance of information shared across the entire system. In summary, this paper describes a pro- totype system, validated by real-world emergency responders, that combines several state-of-the-art techniques for integrating humans and agents, and illustrates, for the first time, how such an approach can enable more effective disaster response operations.
3.
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.
4.
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%
5.
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.
6.
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.
7.
Matthews, Tim; Ramchurn, Sarvapali; Chalkiadakis, Georgios
Competing with humans at fantasy football: team formation in large partially-observable domains Proceedings Article
In: 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
8.
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.
9.
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.
10.
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.
11.
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.
12.
Ramchurn, Sarvapali; Vytelingum, Perukrishnen; Rogers, Alex; Jennings, Nick
Agent-based control for decentralised demand side management in the smart grid Proceedings Article
In: 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).
13.
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}
}
14.
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).
15.
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.
16.
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.
17.
Rahwan, Talal; Ramchurn, Sarvapali; Jennings, Nicholas; Giovannucci, Andrea
An anytime algorithm for optimal coalition structure generation Journal Article
In: Journal of Artificial Intelligence Research, vol. 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.
18.
Rahwan, Talal; Ramchurn, Sarvapali D.; Dang, Viet D.; Giovannucci, Andrea; Jennings, N. R.
Anytime Optimal Coalition Structure Generation Proceedings Article
In: 22nd Conference on Artificial Intelligence (AAAI), pp. 1184–1190, 2007.
@inproceedings{eps263433,
title = {Anytime Optimal Coalition Structure Generation},
author = {Talal Rahwan and Sarvapali D. Ramchurn and Viet D. Dang and Andrea Giovannucci and N. R. Jennings},
url = {http://eprints.soton.ac.uk/263433/},
year = {2007},
date = {2007-01-01},
booktitle = {22nd Conference on Artificial Intelligence (AAAI)},
pages = {1184–1190},
abstract = {Forming effective coalitions is a major research challenge in the field of multi-agent systems. Central to this endeavour is the problem of determining the best groups of agents to select to achieve some goal. To this end, in this paper, we present a novel, optimal anytime algorithm for this coalition structure generation problem that is significantly faster than previous algorithms designed for this purpose. Specifically, our algorithm can generate solutions by partitioning the space of all potential coalitions into sub-spaces that contain coalition structures that are similar, according to some criterion, such that these sub-spaces can be pruned by identifying their bounds. Using this representation, the algorithm then searches through only valid and unique coalition structures and selects the best among them using a branch-and-bound technique. We empirically show that we are able to find solutions that are optimal in 0.082% of the time taken by the state of the art dynamic programming algorithm (for 27 agents) using much less memory (O(2^ n) instead of O(3^ n) for the set of n agents). Moreover, our algorithm is the first to be able to solve the coalition structure generation problem for numbers of agents bigger than 27 in reasonable time (less than 90 minutes for 27 agents as opposed to around 2 months for the best previous solution).},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
Forming effective coalitions is a major research challenge in the field of multi-agent systems. Central to this endeavour is the problem of determining the best groups of agents to select to achieve some goal. To this end, in this paper, we present a novel, optimal anytime algorithm for this coalition structure generation problem that is significantly faster than previous algorithms designed for this purpose. Specifically, our algorithm can generate solutions by partitioning the space of all potential coalitions into sub-spaces that contain coalition structures that are similar, according to some criterion, such that these sub-spaces can be pruned by identifying their bounds. Using this representation, the algorithm then searches through only valid and unique coalition structures and selects the best among them using a branch-and-bound technique. We empirically show that we are able to find solutions that are optimal in 0.082% of the time taken by the state of the art dynamic programming algorithm (for 27 agents) using much less memory (O(2^ n) instead of O(3^ n) for the set of n agents). Moreover, our algorithm is the first to be able to solve the coalition structure generation problem for numbers of agents bigger than 27 in reasonable time (less than 90 minutes for 27 agents as opposed to around 2 months for the best previous solution).
19.
Ramchurn, Sarvapali
Multi-Agent Negotiation using Trust and Persuasion PhD Thesis
University of Southampton, 2004.
@phdthesis{eps260200,
title = {Multi-Agent Negotiation using Trust and Persuasion},
author = {Sarvapali Ramchurn},
url = {http://eprints.soton.ac.uk/260200/},
year = {2004},
date = {2004-01-01},
school = {University of Southampton},
abstract = {In this thesis, we propose a panoply of tools and techniques to manage inter-agent dependencies in open, distributed multi-agent systems that have significant degrees of uncertainty. In particular, we focus on situations in which agents are involved in repeated interactions where they need to negotiate to resolve conflicts that may arise between them. To this end, we endow agents with decision making models that exploit the notion of trust and use persuasive techniques during the negotiation process to reduce the level of uncertainty and achieve better deals in the long run. Firstly, we develop and evaluate a new trust model (called CREDIT) that allows agents to measure the degree of trust they should place in their opponents. This model reduces the uncertainty that agents have about their opponents' reliability. Thus, over repeated interactions, CREDIT enables agents to model their opponents' reliability using probabilistic techniques and a fuzzy reasoning mechanism that allows the combination of measures based on reputation (indirect interactions) and confidence (direct interactions). In so doing, CREDIT takes a wider range of behaviour-influencing factors into account than existing models, including the norms of the agents and the institution within which transactions occur. We then explore a novel application of trust models by showing how the measures developed in CREDIT ca be applied negotiations in multiple encounters. Specifically we show that agents that use CREDIT are able to avoid unreliable agents, both during the selection of interaction partners and during the negotiation process itself by using trust to adjust their negotiation stance. Also, we empirically show that agents are able to reach good deals with agents that are unreliable to some degree (rather than completely unreliable) and with those that try to strategically exploit their opponent. Secondly, having applied CREDIT to negotiations, we further extend the application of trust to reduce uncertainty about the reliability of agents in mechanism design (where the honesty of agents is elicited by the protocol). Thus, we develop $backslash$acftbmd that allows agents using a trust model (such as CREDIT) to reach efficient agreements that choose the most reliable agents in the long run. In particular, we show that our mechanism enforces truth-telling from the agents (i.e. it is incentive compatible), both about their perceived reliability of their opponent and their valuations for the goods to be traded. In proving the latter properties, our trust-based mechanism is shown to be the first reputation mechanism that implements individual rationality, incentive compatibility, and efficiency. Our trust-based mechanism is also empirically evaluated and shown to be better than other comparable models in reaching the outcome that maximises all the negotiating agents' utilities and in choosing the most reliable agents in the long run. Thirdly, having explored ways to reduce uncertainties about reliability and honesty, we use persuasive negotiation techniques to tackle issues associated with uncertainties that agents have about the preferences and the space of possible agreements. To this end, we propose a novel protocol and reasoning mechanism that agents can use to generate and evaluate persuasive elements, such as promises of future rewards, to support the offers they make during negotiation. These persuasive elements aim to make offers more attractive over multiple encounters given the absence of information about an opponent's discount factors or exact payoffs. Specifically, we empirically demonstrate that agents are able to achieve a larger number of agreements and a higher expected utility over repeated encounters when they are given the capability to give or ask for rewards. Moreover, we develop a novel strategy using this protocol and show that it outperforms existing state of the art heuristic negotiation models. Finally, the applicability of persuasive negotiation and CREDIT is exemplified through a practical implementation in a pervasive computing environment. In this context, the negotiation mechanism is implemented in an instant messaging platform (JABBER) and used to resolve conflicts between group and individual preferences that arise in a meeting room scenario. In particular, we show how persuasive negotiation and trust permit a flexible management of interruptions by allowing intrusions to happen at appropriate times during the meeting while still managing to satisfy the preferences of all parties present.},
keywords = {},
pubstate = {published},
tppubtype = {phdthesis}
}
In this thesis, we propose a panoply of tools and techniques to manage inter-agent dependencies in open, distributed multi-agent systems that have significant degrees of uncertainty. In particular, we focus on situations in which agents are involved in repeated interactions where they need to negotiate to resolve conflicts that may arise between them. To this end, we endow agents with decision making models that exploit the notion of trust and use persuasive techniques during the negotiation process to reduce the level of uncertainty and achieve better deals in the long run. Firstly, we develop and evaluate a new trust model (called CREDIT) that allows agents to measure the degree of trust they should place in their opponents. This model reduces the uncertainty that agents have about their opponents' reliability. Thus, over repeated interactions, CREDIT enables agents to model their opponents' reliability using probabilistic techniques and a fuzzy reasoning mechanism that allows the combination of measures based on reputation (indirect interactions) and confidence (direct interactions). In so doing, CREDIT takes a wider range of behaviour-influencing factors into account than existing models, including the norms of the agents and the institution within which transactions occur. We then explore a novel application of trust models by showing how the measures developed in CREDIT ca be applied negotiations in multiple encounters. Specifically we show that agents that use CREDIT are able to avoid unreliable agents, both during the selection of interaction partners and during the negotiation process itself by using trust to adjust their negotiation stance. Also, we empirically show that agents are able to reach good deals with agents that are unreliable to some degree (rather than completely unreliable) and with those that try to strategically exploit their opponent. Secondly, having applied CREDIT to negotiations, we further extend the application of trust to reduce uncertainty about the reliability of agents in mechanism design (where the honesty of agents is elicited by the protocol). Thus, we develop $backslash$acftbmd that allows agents using a trust model (such as CREDIT) to reach efficient agreements that choose the most reliable agents in the long run. In particular, we show that our mechanism enforces truth-telling from the agents (i.e. it is incentive compatible), both about their perceived reliability of their opponent and their valuations for the goods to be traded. In proving the latter properties, our trust-based mechanism is shown to be the first reputation mechanism that implements individual rationality, incentive compatibility, and efficiency. Our trust-based mechanism is also empirically evaluated and shown to be better than other comparable models in reaching the outcome that maximises all the negotiating agents' utilities and in choosing the most reliable agents in the long run. Thirdly, having explored ways to reduce uncertainties about reliability and honesty, we use persuasive negotiation techniques to tackle issues associated with uncertainties that agents have about the preferences and the space of possible agreements. To this end, we propose a novel protocol and reasoning mechanism that agents can use to generate and evaluate persuasive elements, such as promises of future rewards, to support the offers they make during negotiation. These persuasive elements aim to make offers more attractive over multiple encounters given the absence of information about an opponent's discount factors or exact payoffs. Specifically, we empirically demonstrate that agents are able to achieve a larger number of agreements and a higher expected utility over repeated encounters when they are given the capability to give or ask for rewards. Moreover, we develop a novel strategy using this protocol and show that it outperforms existing state of the art heuristic negotiation models. Finally, the applicability of persuasive negotiation and CREDIT is exemplified through a practical implementation in a pervasive computing environment. In this context, the negotiation mechanism is implemented in an instant messaging platform (JABBER) and used to resolve conflicts between group and individual preferences that arise in a meeting room scenario. In particular, we show how persuasive negotiation and trust permit a flexible management of interruptions by allowing intrusions to happen at appropriate times during the meeting while still managing to satisfy the preferences of all parties present.
Selected Publications
Multi-agent signal-less intersection management with dynamic platoon formation
No data available.
https://eprints.soton.ac.uk/478647/
@inproceedings{soton478647,
title = {Multi-agent signal-less intersection management with dynamic platoon formation},
author = {Phuriwat Worrawichaipat and Enrico Gerding and Ioannis Kaparias and Sarvapali Ramchurn},
url = {https://eprints.soton.ac.uk/478647/},
year = {2023},
date = {2023-05-01},
booktitle = {22nd International Conference on Autonomous Agents and Multiagent Systems (29/05/23 - 02/06/23)},
pages = {1542--1550},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
title = {Multi-agent signal-less intersection management with dynamic platoon formation},
author = {Phuriwat Worrawichaipat and Enrico Gerding and Ioannis Kaparias and Sarvapali Ramchurn},
url = {https://eprints.soton.ac.uk/478647/},
year = {2023},
date = {2023-05-01},
booktitle = {22nd International Conference on Autonomous Agents and Multiagent Systems (29/05/23 - 02/06/23)},
pages = {1542--1550},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
AI Foundation Models: initial review, CMA Consultation, TAS Hub Response
No data available.
https://eprints.soton.ac.uk/477553/
@misc{soton477553,
title = {AI Foundation Models: initial review, CMA Consultation, TAS Hub Response},
author = {Joshua Krook and Derek McAuley and Stuart Anderson and John Downer and Peter Winter and Sarvapali D Ramchurn},
url = {https://eprints.soton.ac.uk/477553/},
year = {2023},
date = {2023-06-01},
publisher = {University of Southampton},
keywords = {},
pubstate = {published},
tppubtype = {misc}
}
title = {AI Foundation Models: initial review, CMA Consultation, TAS Hub Response},
author = {Joshua Krook and Derek McAuley and Stuart Anderson and John Downer and Peter Winter and Sarvapali D Ramchurn},
url = {https://eprints.soton.ac.uk/477553/},
year = {2023},
date = {2023-06-01},
publisher = {University of Southampton},
keywords = {},
pubstate = {published},
tppubtype = {misc}
}
The effect of data visualisation quality and task density on human-swarm interaction
No data available.
https://eprints.soton.ac.uk/479970/
@inproceedings{soton479970,
title = {The effect of data visualisation quality and task density on human-swarm interaction},
author = {Ayodeji Abioye and Mohammad Naiseh and William Hunt and Jediah R Clark and Sarvapali D Ramchurn and Mohammad Soorati},
url = {https://eprints.soton.ac.uk/479970/},
year = {2023},
date = {2023-06-01},
booktitle = {Proceedings of the 2023 32nd IEEE International Conference on Robot and Human Interactive Communication (RO-MAN)},
publisher = {IEEE},
abstract = {Despite the advantages of having robot swarms, human supervision is required for real-world applications. The performance of the human-swarm system depends on several factors including the data availability for the human operators. In this paper, we study the human factors aspect of the human-swarm interaction and investigate how having access to high-quality data can affect the performance of the human-swarm system - the number of tasks completed and the human trust level in operation. We designed an experiment where a human operator is tasked to operate a swarm to identify casualties in an area within a given time period. One group of operators had the option to request high-quality pictures while the other group had to base their decision on the available low-quality images. We performed a user study with 120 participants and recorded their success rate (directly logged via the simulation platform) as well as their workload and trust level (measured through a questionnaire after completing a human-swarm scenario). The findings from our study indicated that the group granted access to high-quality data exhibited an increased workload and placed greater trust in the swarm, thus confirming our initial hypothesis. However, we also found that the number of accurately identified casualties did not significantly vary between the two groups, suggesting that data quality had no impact on the successful completion of tasks.},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
title = {The effect of data visualisation quality and task density on human-swarm interaction},
author = {Ayodeji Abioye and Mohammad Naiseh and William Hunt and Jediah R Clark and Sarvapali D Ramchurn and Mohammad Soorati},
url = {https://eprints.soton.ac.uk/479970/},
year = {2023},
date = {2023-06-01},
booktitle = {Proceedings of the 2023 32nd IEEE International Conference on Robot and Human Interactive Communication (RO-MAN)},
publisher = {IEEE},
abstract = {Despite the advantages of having robot swarms, human supervision is required for real-world applications. The performance of the human-swarm system depends on several factors including the data availability for the human operators. In this paper, we study the human factors aspect of the human-swarm interaction and investigate how having access to high-quality data can affect the performance of the human-swarm system - the number of tasks completed and the human trust level in operation. We designed an experiment where a human operator is tasked to operate a swarm to identify casualties in an area within a given time period. One group of operators had the option to request high-quality pictures while the other group had to base their decision on the available low-quality images. We performed a user study with 120 participants and recorded their success rate (directly logged via the simulation platform) as well as their workload and trust level (measured through a questionnaire after completing a human-swarm scenario). The findings from our study indicated that the group granted access to high-quality data exhibited an increased workload and placed greater trust in the swarm, thus confirming our initial hypothesis. However, we also found that the number of accurately identified casualties did not significantly vary between the two groups, suggesting that data quality had no impact on the successful completion of tasks.},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
Demonstrating performance benefits of human-swarm teaming
Autonomous swarms of robots can bring robustness, scalability and adaptability to safety-critical tasks such as search and rescue but their application is still very limited. Using semi-autonomous swarms with human control can bring robot swarms to real-world applications. Human operators can define goals for the swarm, monitor their performance and interfere with, or overrule, the decisions and behaviour. We present the "Human And Robot Interactive Swarm'' simulator (HARIS) that allows multi-user interaction with a robot swarm and facilitates qualitative and quantitative user studies through simulation of robot swarms completing tasks, from package delivery to search and rescue, with varying levels of human control. In this demonstration, we showcase the simulator by using it to study the performance gain offered by maintaining a "human-in-the-loop'' over a fully autonomous system as an example. This is illustrated in the context of search and rescue, with an autonomous allocation of resources to those in need.
https://eprints.soton.ac.uk/479903/
@inproceedings{soton479903,
title = {Demonstrating performance benefits of human-swarm teaming},
author = {William Hunt and Jack Ryan and Ayodeji O Abioye and Sarvapali D Ramchurn and Mohammad D Soorati},
url = {https://eprints.soton.ac.uk/479903/},
year = {2023},
date = {2023-05-01},
booktitle = {Proceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems},
pages = {3062--3064},
publisher = {International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS)},
abstract = {Autonomous swarms of robots can bring robustness, scalability and adaptability to safety-critical tasks such as search and rescue but their application is still very limited. Using semi-autonomous swarms with human control can bring robot swarms to real-world applications. Human operators can define goals for the swarm, monitor their performance and interfere with, or overrule, the decisions and behaviour. We present the "Human And Robot Interactive Swarm'' simulator (HARIS) that allows multi-user interaction with a robot swarm and facilitates qualitative and quantitative user studies through simulation of robot swarms completing tasks, from package delivery to search and rescue, with varying levels of human control. In this demonstration, we showcase the simulator by using it to study the performance gain offered by maintaining a "human-in-the-loop'' over a fully autonomous system as an example. This is illustrated in the context of search and rescue, with an autonomous allocation of resources to those in need.},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
title = {Demonstrating performance benefits of human-swarm teaming},
author = {William Hunt and Jack Ryan and Ayodeji O Abioye and Sarvapali D Ramchurn and Mohammad D Soorati},
url = {https://eprints.soton.ac.uk/479903/},
year = {2023},
date = {2023-05-01},
booktitle = {Proceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems},
pages = {3062--3064},
publisher = {International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS)},
abstract = {Autonomous swarms of robots can bring robustness, scalability and adaptability to safety-critical tasks such as search and rescue but their application is still very limited. Using semi-autonomous swarms with human control can bring robot swarms to real-world applications. Human operators can define goals for the swarm, monitor their performance and interfere with, or overrule, the decisions and behaviour. We present the "Human And Robot Interactive Swarm'' simulator (HARIS) that allows multi-user interaction with a robot swarm and facilitates qualitative and quantitative user studies through simulation of robot swarms completing tasks, from package delivery to search and rescue, with varying levels of human control. In this demonstration, we showcase the simulator by using it to study the performance gain offered by maintaining a "human-in-the-loop'' over a fully autonomous system as an example. This is illustrated in the context of search and rescue, with an autonomous allocation of resources to those in need.},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
2021
Worrawichaipat, Phuriwat; Gerding, Enrico; Kaparias, Ioannis; Ramchurn, Sarvapali
Resilient intersection management with multi-vehicle collision avoidance Journal Article
In: Frontiers in Sustainable Cities, vol. 3, 2021.
@article{soton449675,
title = {Resilient intersection management with multi-vehicle collision avoidance},
author = {Phuriwat Worrawichaipat and Enrico Gerding and Ioannis Kaparias and Sarvapali Ramchurn},
url = {https://eprints.soton.ac.uk/449675/},
year = {2021},
date = {2021-06-01},
journal = {Frontiers in Sustainable Cities},
volume = {3},
abstract = {In this paper, we propose a novel decentralised agent-based mechanism for road intersection management for connected autonomous vehicles. In our work we focus on road obstructions causing major traffic delays. In doing so, we propose the first decentralised mechanism able to maximise the overall vehicle throughput at intersections in the presence of obstructions. The distributed algorithm transfers most of the computational cost from the intersection manager to the driving agents, thereby improving scalability. Our realistic empirical experiments using SUMO show that, when an obstacle is located at the entrance or in the middle of the intersection, existing state of the art algorithms and traffic lights show a reduced throughput of 65?90% from the optimal point without obstructions while our mechanism can maintain the throughput upensuremath<br/ensuremath>Q7 to 94?99%.},
keywords = {},
pubstate = {published},
tppubtype = {article}
}
In this paper, we propose a novel decentralised agent-based mechanism for road intersection management for connected autonomous vehicles. In our work we focus on road obstructions causing major traffic delays. In doing so, we propose the first decentralised mechanism able to maximise the overall vehicle throughput at intersections in the presence of obstructions. The distributed algorithm transfers most of the computational cost from the intersection manager to the driving agents, thereby improving scalability. Our realistic empirical experiments using SUMO show that, when an obstacle is located at the entrance or in the middle of the intersection, existing state of the art algorithms and traffic lights show a reduced throughput of 65?90% from the optimal point without obstructions while our mechanism can maintain the throughput upensuremath<br/ensuremath>Q7 to 94?99%.
2015
Ramchurn, Sarvapali; Simpson, Edwin; Fischer, Joel; Huynh, Trung Dong; Ikuno, Yuki; Reece, Steven; Jiang, Wenchao; Wu, Feng; Flann, Jack; Roberts, S. J.; Moreau, Luc; Rodden, T.; Jennings, N. R.
HAC-ER: A disaster response system based on human-agent collectives Proceedings Article
In: 14th International Conference on Autonomous Agents and Multi-Agent Systems, 2015.
@inproceedings{eps374070,
title = {HAC-ER: A disaster response system based on human-agent collectives},
author = {Sarvapali Ramchurn and Edwin Simpson and Joel Fischer and Trung Dong Huynh and Yuki Ikuno and Steven Reece and Wenchao Jiang and Feng Wu and Jack Flann and S. J. Roberts and Luc Moreau and T. Rodden and N. R. Jennings},
url = {http://eprints.soton.ac.uk/374070/},
year = {2015},
date = {2015-01-01},
booktitle = {14th International Conference on Autonomous Agents and Multi-Agent Systems},
abstract = {This paper proposes a novel disaster management system called HAC-ER that addresses some of the challenges faced by emer- gency responders by enabling humans and agents, using state-of- the-art algorithms, to collaboratively plan and carry out tasks in teams referred to as human-agent collectives. In particular, HAC- ER utilises crowdsourcing combined with machine learning to ex- tract situational awareness information from large streams of re- ports posted by members of the public and trusted organisations. We then show how this information can inform human-agent teams in coordinating multi-UAV deployments as well as task planning for responders on the ground. Finally, HAC-ER incorporates a tool for tracking and analysing the provenance of information shared across the entire system. In summary, this paper describes a pro- totype system, validated by real-world emergency responders, that combines several state-of-the-art techniques for integrating humans and agents, and illustrates, for the first time, how such an approach can enable more effective disaster response operations.},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
This paper proposes a novel disaster management system called HAC-ER that addresses some of the challenges faced by emer- gency responders by enabling humans and agents, using state-of- the-art algorithms, to collaboratively plan and carry out tasks in teams referred to as human-agent collectives. In particular, HAC- ER utilises crowdsourcing combined with machine learning to ex- tract situational awareness information from large streams of re- ports posted by members of the public and trusted organisations. We then show how this information can inform human-agent teams in coordinating multi-UAV deployments as well as task planning for responders on the ground. Finally, HAC-ER incorporates a tool for tracking and analysing the provenance of information shared across the entire system. In summary, this paper describes a pro- totype system, validated by real-world emergency responders, that combines several state-of-the-art techniques for integrating humans and agents, and illustrates, for the first time, how such an approach can enable more effective disaster response operations.
2014
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.
2013
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%
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.
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.
2012
Matthews, Tim; Ramchurn, Sarvapali; Chalkiadakis, Georgios
Competing with humans at fantasy football: team formation in large partially-observable domains Proceedings Article
In: 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
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
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.
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.
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.
Ramchurn, Sarvapali; Vytelingum, Perukrishnen; Rogers, Alex; Jennings, Nick
Agent-based control for decentralised demand side management in the smart grid Proceedings Article
In: 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 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}
}
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).
2010
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.
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.
2009
Rahwan, Talal; Ramchurn, Sarvapali; Jennings, Nicholas; Giovannucci, Andrea
An anytime algorithm for optimal coalition structure generation Journal Article
In: Journal of Artificial Intelligence Research, vol. 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.
2007
Rahwan, Talal; Ramchurn, Sarvapali D.; Dang, Viet D.; Giovannucci, Andrea; Jennings, N. R.
Anytime Optimal Coalition Structure Generation Proceedings Article
In: 22nd Conference on Artificial Intelligence (AAAI), pp. 1184–1190, 2007.
@inproceedings{eps263433,
title = {Anytime Optimal Coalition Structure Generation},
author = {Talal Rahwan and Sarvapali D. Ramchurn and Viet D. Dang and Andrea Giovannucci and N. R. Jennings},
url = {http://eprints.soton.ac.uk/263433/},
year = {2007},
date = {2007-01-01},
booktitle = {22nd Conference on Artificial Intelligence (AAAI)},
pages = {1184–1190},
abstract = {Forming effective coalitions is a major research challenge in the field of multi-agent systems. Central to this endeavour is the problem of determining the best groups of agents to select to achieve some goal. To this end, in this paper, we present a novel, optimal anytime algorithm for this coalition structure generation problem that is significantly faster than previous algorithms designed for this purpose. Specifically, our algorithm can generate solutions by partitioning the space of all potential coalitions into sub-spaces that contain coalition structures that are similar, according to some criterion, such that these sub-spaces can be pruned by identifying their bounds. Using this representation, the algorithm then searches through only valid and unique coalition structures and selects the best among them using a branch-and-bound technique. We empirically show that we are able to find solutions that are optimal in 0.082% of the time taken by the state of the art dynamic programming algorithm (for 27 agents) using much less memory (O(2^ n) instead of O(3^ n) for the set of n agents). Moreover, our algorithm is the first to be able to solve the coalition structure generation problem for numbers of agents bigger than 27 in reasonable time (less than 90 minutes for 27 agents as opposed to around 2 months for the best previous solution).},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
Forming effective coalitions is a major research challenge in the field of multi-agent systems. Central to this endeavour is the problem of determining the best groups of agents to select to achieve some goal. To this end, in this paper, we present a novel, optimal anytime algorithm for this coalition structure generation problem that is significantly faster than previous algorithms designed for this purpose. Specifically, our algorithm can generate solutions by partitioning the space of all potential coalitions into sub-spaces that contain coalition structures that are similar, according to some criterion, such that these sub-spaces can be pruned by identifying their bounds. Using this representation, the algorithm then searches through only valid and unique coalition structures and selects the best among them using a branch-and-bound technique. We empirically show that we are able to find solutions that are optimal in 0.082% of the time taken by the state of the art dynamic programming algorithm (for 27 agents) using much less memory (O(2^ n) instead of O(3^ n) for the set of n agents). Moreover, our algorithm is the first to be able to solve the coalition structure generation problem for numbers of agents bigger than 27 in reasonable time (less than 90 minutes for 27 agents as opposed to around 2 months for the best previous solution).
2004
Ramchurn, Sarvapali
Multi-Agent Negotiation using Trust and Persuasion PhD Thesis
University of Southampton, 2004.
@phdthesis{eps260200,
title = {Multi-Agent Negotiation using Trust and Persuasion},
author = {Sarvapali Ramchurn},
url = {http://eprints.soton.ac.uk/260200/},
year = {2004},
date = {2004-01-01},
school = {University of Southampton},
abstract = {In this thesis, we propose a panoply of tools and techniques to manage inter-agent dependencies in open, distributed multi-agent systems that have significant degrees of uncertainty. In particular, we focus on situations in which agents are involved in repeated interactions where they need to negotiate to resolve conflicts that may arise between them. To this end, we endow agents with decision making models that exploit the notion of trust and use persuasive techniques during the negotiation process to reduce the level of uncertainty and achieve better deals in the long run. Firstly, we develop and evaluate a new trust model (called CREDIT) that allows agents to measure the degree of trust they should place in their opponents. This model reduces the uncertainty that agents have about their opponents' reliability. Thus, over repeated interactions, CREDIT enables agents to model their opponents' reliability using probabilistic techniques and a fuzzy reasoning mechanism that allows the combination of measures based on reputation (indirect interactions) and confidence (direct interactions). In so doing, CREDIT takes a wider range of behaviour-influencing factors into account than existing models, including the norms of the agents and the institution within which transactions occur. We then explore a novel application of trust models by showing how the measures developed in CREDIT ca be applied negotiations in multiple encounters. Specifically we show that agents that use CREDIT are able to avoid unreliable agents, both during the selection of interaction partners and during the negotiation process itself by using trust to adjust their negotiation stance. Also, we empirically show that agents are able to reach good deals with agents that are unreliable to some degree (rather than completely unreliable) and with those that try to strategically exploit their opponent. Secondly, having applied CREDIT to negotiations, we further extend the application of trust to reduce uncertainty about the reliability of agents in mechanism design (where the honesty of agents is elicited by the protocol). Thus, we develop $backslash$acftbmd that allows agents using a trust model (such as CREDIT) to reach efficient agreements that choose the most reliable agents in the long run. In particular, we show that our mechanism enforces truth-telling from the agents (i.e. it is incentive compatible), both about their perceived reliability of their opponent and their valuations for the goods to be traded. In proving the latter properties, our trust-based mechanism is shown to be the first reputation mechanism that implements individual rationality, incentive compatibility, and efficiency. Our trust-based mechanism is also empirically evaluated and shown to be better than other comparable models in reaching the outcome that maximises all the negotiating agents' utilities and in choosing the most reliable agents in the long run. Thirdly, having explored ways to reduce uncertainties about reliability and honesty, we use persuasive negotiation techniques to tackle issues associated with uncertainties that agents have about the preferences and the space of possible agreements. To this end, we propose a novel protocol and reasoning mechanism that agents can use to generate and evaluate persuasive elements, such as promises of future rewards, to support the offers they make during negotiation. These persuasive elements aim to make offers more attractive over multiple encounters given the absence of information about an opponent's discount factors or exact payoffs. Specifically, we empirically demonstrate that agents are able to achieve a larger number of agreements and a higher expected utility over repeated encounters when they are given the capability to give or ask for rewards. Moreover, we develop a novel strategy using this protocol and show that it outperforms existing state of the art heuristic negotiation models. Finally, the applicability of persuasive negotiation and CREDIT is exemplified through a practical implementation in a pervasive computing environment. In this context, the negotiation mechanism is implemented in an instant messaging platform (JABBER) and used to resolve conflicts between group and individual preferences that arise in a meeting room scenario. In particular, we show how persuasive negotiation and trust permit a flexible management of interruptions by allowing intrusions to happen at appropriate times during the meeting while still managing to satisfy the preferences of all parties present.},
keywords = {},
pubstate = {published},
tppubtype = {phdthesis}
}
In this thesis, we propose a panoply of tools and techniques to manage inter-agent dependencies in open, distributed multi-agent systems that have significant degrees of uncertainty. In particular, we focus on situations in which agents are involved in repeated interactions where they need to negotiate to resolve conflicts that may arise between them. To this end, we endow agents with decision making models that exploit the notion of trust and use persuasive techniques during the negotiation process to reduce the level of uncertainty and achieve better deals in the long run. Firstly, we develop and evaluate a new trust model (called CREDIT) that allows agents to measure the degree of trust they should place in their opponents. This model reduces the uncertainty that agents have about their opponents' reliability. Thus, over repeated interactions, CREDIT enables agents to model their opponents' reliability using probabilistic techniques and a fuzzy reasoning mechanism that allows the combination of measures based on reputation (indirect interactions) and confidence (direct interactions). In so doing, CREDIT takes a wider range of behaviour-influencing factors into account than existing models, including the norms of the agents and the institution within which transactions occur. We then explore a novel application of trust models by showing how the measures developed in CREDIT ca be applied negotiations in multiple encounters. Specifically we show that agents that use CREDIT are able to avoid unreliable agents, both during the selection of interaction partners and during the negotiation process itself by using trust to adjust their negotiation stance. Also, we empirically show that agents are able to reach good deals with agents that are unreliable to some degree (rather than completely unreliable) and with those that try to strategically exploit their opponent. Secondly, having applied CREDIT to negotiations, we further extend the application of trust to reduce uncertainty about the reliability of agents in mechanism design (where the honesty of agents is elicited by the protocol). Thus, we develop $backslash$acftbmd that allows agents using a trust model (such as CREDIT) to reach efficient agreements that choose the most reliable agents in the long run. In particular, we show that our mechanism enforces truth-telling from the agents (i.e. it is incentive compatible), both about their perceived reliability of their opponent and their valuations for the goods to be traded. In proving the latter properties, our trust-based mechanism is shown to be the first reputation mechanism that implements individual rationality, incentive compatibility, and efficiency. Our trust-based mechanism is also empirically evaluated and shown to be better than other comparable models in reaching the outcome that maximises all the negotiating agents' utilities and in choosing the most reliable agents in the long run. Thirdly, having explored ways to reduce uncertainties about reliability and honesty, we use persuasive negotiation techniques to tackle issues associated with uncertainties that agents have about the preferences and the space of possible agreements. To this end, we propose a novel protocol and reasoning mechanism that agents can use to generate and evaluate persuasive elements, such as promises of future rewards, to support the offers they make during negotiation. These persuasive elements aim to make offers more attractive over multiple encounters given the absence of information about an opponent's discount factors or exact payoffs. Specifically, we empirically demonstrate that agents are able to achieve a larger number of agreements and a higher expected utility over repeated encounters when they are given the capability to give or ask for rewards. Moreover, we develop a novel strategy using this protocol and show that it outperforms existing state of the art heuristic negotiation models. Finally, the applicability of persuasive negotiation and CREDIT is exemplified through a practical implementation in a pervasive computing environment. In this context, the negotiation mechanism is implemented in an instant messaging platform (JABBER) and used to resolve conflicts between group and individual preferences that arise in a meeting room scenario. In particular, we show how persuasive negotiation and trust permit a flexible management of interruptions by allowing intrusions to happen at appropriate times during the meeting while still managing to satisfy the preferences of all parties present.