font
Filter
×
Sorry, no publications matched your criteria.
161.
Alam, Muddasser; Rogers, Alex; Ramchurn, Sarvapali
A negotiation protocol for multiple interdependent issues negotiation over energy exchange Proceedings Article
In: IJCAI Workshop on AI for an Intelligent Planet, 2011, (Event Dates: July-16).
@inproceedings{eps272479,
title = {A negotiation protocol for multiple interdependent issues negotiation over energy exchange},
author = {Muddasser Alam and Alex Rogers and Sarvapali Ramchurn},
url = {http://eprints.soton.ac.uk/272479/},
year = {2011},
date = {2011-01-01},
booktitle = {IJCAI Workshop on AI for an Intelligent Planet},
abstract = {We present a novel negotiation protocol to facilitate energy exchange between off-grid homes that are equipped with renewable energy generation and electricity storage. Our solution imposes additional constraints on negotiation such that it reduces a complex interdependent multi-issue problem to one that is tractable. We prove that using our protocol, agents can reach a Pareto-optimal, dominant strategy equilibrium in a decentralized and timely fashion. We empirically evaluate our approach in a realistic setting. In this case, we show that energy exchange can be useful in reducing the capacity of the energy storage devices in homes by close to 40%},
note = {Event Dates: July-16},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
We present a novel negotiation protocol to facilitate energy exchange between off-grid homes that are equipped with renewable energy generation and electricity storage. Our solution imposes additional constraints on negotiation such that it reduces a complex interdependent multi-issue problem to one that is tractable. We prove that using our protocol, agents can reach a Pareto-optimal, dominant strategy equilibrium in a decentralized and timely fashion. We empirically evaluate our approach in a realistic setting. In this case, we show that energy exchange can be useful in reducing the capacity of the energy storage devices in homes by close to 40%
162.
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.
163.
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.
164.
Osborne, Michael A.; Rogers, Alex; Roberts, Stephen J.; Ramchurn, Sarvapali D.; Jennings, Nicholas R.
Gaussian Processes for Time Series Prediction Book Section
In: Bayesian Time Series Models, pp. 341–360, Cambridge University Press, 2011, (Chapter: 16).
@incollection{eps272746,
title = {Gaussian Processes for Time Series Prediction},
author = {Michael A. Osborne and Alex Rogers and Stephen J. Roberts and Sarvapali D. Ramchurn and Nicholas R. Jennings},
url = {http://eprints.soton.ac.uk/272746/},
year = {2011},
date = {2011-01-01},
booktitle = {Bayesian Time Series Models},
pages = {341–360},
publisher = {Cambridge University Press},
note = {Chapter: 16},
keywords = {},
pubstate = {published},
tppubtype = {incollection}
}
165.
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.
166.
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).
167.
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}
}
168.
Voice, Thomas; Vytelingum, Perukrishnen; Ramchurn, Sarvapali; Rogers, Alex; Jennings, Nick
Decentralised Control of Micro-Storage in the Smart Grid Proceedings Article
In: AAAI-11: Twenty-Fifth Conference on Artificial Intelligence, pp. 1421–1426, 2011, (Event Dates: August 7?11, 2011).
@inproceedings{eps272262,
title = {Decentralised Control of Micro-Storage in the Smart Grid},
author = {Thomas Voice and Perukrishnen Vytelingum and Sarvapali Ramchurn and Alex Rogers and Nick Jennings},
url = {http://eprints.soton.ac.uk/272262/},
year = {2011},
date = {2011-01-01},
booktitle = {AAAI-11: Twenty-Fifth Conference on Artificial Intelligence},
pages = {1421–1426},
abstract = {In this paper, we propose a novel decentralised control mechanism to manage micro-storage in the smart grid. Our approach uses an adaptive pricing scheme that energy suppliers apply to home smart agents controlling micro-storage devices. In particular, we prove that the interaction between a supplier using our pricing scheme and the actions of selfish micro-storage agents forms a globally stable feedback loop that converges to an efficient equilibrium. We further propose a market strategy that allows the supplier to reduce wholesale purchasing costs without increasing the uncertainty and variance for its aggregate consumer demand. Moreover, we empirically evaluate our mechanism (based on the UK grid data) and show that it yields savings of up to 16% in energy cost for consumers using storage devices with average capacity 10 kWh. Furthermore, we show that it is robust against extreme system changes.},
note = {Event Dates: August 7?11, 2011},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
In this paper, we propose a novel decentralised control mechanism to manage micro-storage in the smart grid. Our approach uses an adaptive pricing scheme that energy suppliers apply to home smart agents controlling micro-storage devices. In particular, we prove that the interaction between a supplier using our pricing scheme and the actions of selfish micro-storage agents forms a globally stable feedback loop that converges to an efficient equilibrium. We further propose a market strategy that allows the supplier to reduce wholesale purchasing costs without increasing the uncertainty and variance for its aggregate consumer demand. Moreover, we empirically evaluate our mechanism (based on the UK grid data) and show that it yields savings of up to 16% in energy cost for consumers using storage devices with average capacity 10 kWh. Furthermore, we show that it is robust against extreme system changes.
169.
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).
170.
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.
171.
Ramchurn, S. D.; Polukarov, Mariya; Farinelli, Alessandro; Jennings, Nick; Trong, Cuong
Coalition Formation with Spatial and Temporal Constraints Proceedings Article
In: International Joint Conference on Autonomous Agents and Multi-Agent Systems (AAMAS 2010), pp. 1181–1188, 2010, (Event Dates: May 2010).
@inproceedings{eps268497,
title = {Coalition Formation with Spatial and Temporal Constraints},
author = {S. D. Ramchurn and Mariya Polukarov and Alessandro Farinelli and Nick Jennings and Cuong Trong},
url = {http://eprints.soton.ac.uk/268497/},
year = {2010},
date = {2010-01-01},
booktitle = {International Joint Conference on Autonomous Agents and Multi-Agent Systems (AAMAS 2010)},
pages = {1181–1188},
abstract = {The coordination of emergency responders and robots to undertake a number of tasks in disaster scenarios is a grand challenge for multi-agent systems. Central to this endeavour is the problem of forming the best teams (coalitions) of responders to perform the various tasks in the area where the disaster has struck. Moreover, these teams may have to form, disband, and reform in different areas of the disaster region. This is because in most cases there will be more tasks than agents. Hence, agents need to schedule themselves to attempt each task in turn. Second, the tasks themselves can be very complex: requiring the agents to work on them for different lengths of time and having deadlines by when they need to be completed. The problem is complicated still further when different coalitions perform tasks with different levels of efficiency. Given all these facets, we define this as The Coalition Formation with Spatial and Temporal constraints problem (CFSTP).We show that this problem is NP-hard–in particular, it contains the wellknown complex combinatorial problem of Team Orienteering as a special case. Based on this, we design a Mixed Integer Program to optimally solve small-scale instances of the CFSTP and develop new anytime heuristics that can, on average, complete 97% of the tasks for large problems (20 agents and 300 tasks). In so doing, our solutions represent the first results for CFSTP.},
note = {Event Dates: May 2010},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
The coordination of emergency responders and robots to undertake a number of tasks in disaster scenarios is a grand challenge for multi-agent systems. Central to this endeavour is the problem of forming the best teams (coalitions) of responders to perform the various tasks in the area where the disaster has struck. Moreover, these teams may have to form, disband, and reform in different areas of the disaster region. This is because in most cases there will be more tasks than agents. Hence, agents need to schedule themselves to attempt each task in turn. Second, the tasks themselves can be very complex: requiring the agents to work on them for different lengths of time and having deadlines by when they need to be completed. The problem is complicated still further when different coalitions perform tasks with different levels of efficiency. Given all these facets, we define this as The Coalition Formation with Spatial and Temporal constraints problem (CFSTP).We show that this problem is NP-hard–in particular, it contains the wellknown complex combinatorial problem of Team Orienteering as a special case. Based on this, we design a Mixed Integer Program to optimally solve small-scale instances of the CFSTP and develop new anytime heuristics that can, on average, complete 97% of the tasks for large problems (20 agents and 300 tasks). In so doing, our solutions represent the first results for CFSTP.
172.
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.
173.
Vytelingum, Perukrishnen; Ramchurn, Sarvapali D.; Voice, Thomas D.; Rogers, Alex; Jennings, Nicholas R.
Trading agents for the smart electricity grid Proceedings Article
In: The Ninth International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2010), pp. 897–904, 2010, (Event Dates: May 10-14, 2010).
@inproceedings{eps268361,
title = {Trading agents for the smart electricity grid},
author = {Perukrishnen Vytelingum and Sarvapali D. Ramchurn and Thomas D. Voice and Alex Rogers and Nicholas R. Jennings},
url = {http://eprints.soton.ac.uk/268361/},
year = {2010},
date = {2010-01-01},
booktitle = {The Ninth International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2010)},
pages = {897–904},
abstract = {The vision of the Smart Grid includes the creation of intelligent electricity supply networks to allow efficient use of energy resources, reduce carbon emissions and are robust to failures. One of the key assumptions underlying this vision is that it will be possible to manage the trading of electricity between homes and micro-grids while coping with the inherent real-time dynamism in electricity demand and supply. The management of these trades needs to take into account the fact that most, if not all, of the actors in the system are self-interested and transmission line capacities are constrained. Against this background, we develop and evaluate a novel market-based mechanism and novel trading strategies for the Smart Grid. Our mechanism is based on the Continuous Double Auction (CDA) and automatically manages the congestion within the system by pricing the flow of electricity. We also introduce mechanisms to ensure the system can cope with unforeseen demand or increased supply capacity in real time. Finally, we develop new strategies that we show achieve high market efficiency (typically over 90%).},
note = {Event Dates: May 10-14, 2010},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
The vision of the Smart Grid includes the creation of intelligent electricity supply networks to allow efficient use of energy resources, reduce carbon emissions and are robust to failures. One of the key assumptions underlying this vision is that it will be possible to manage the trading of electricity between homes and micro-grids while coping with the inherent real-time dynamism in electricity demand and supply. The management of these trades needs to take into account the fact that most, if not all, of the actors in the system are self-interested and transmission line capacities are constrained. Against this background, we develop and evaluate a novel market-based mechanism and novel trading strategies for the Smart Grid. Our mechanism is based on the Continuous Double Auction (CDA) and automatically manages the congestion within the system by pricing the flow of electricity. We also introduce mechanisms to ensure the system can cope with unforeseen demand or increased supply capacity in real time. Finally, we develop new strategies that we show achieve high market efficiency (typically over 90%).
174.
Vytelingum, Perukrishnen; Voice, Thomas D.; Ramchurn, Sarvapali D.; Rogers, Alex; Jennings, Nicholas R.
Agent-Based Micro-Storage Management for the Smart Grid Proceedings Article
In: The Ninth International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2010) - Won the Best Paper Award, pp. 39–46, 2010, (Winner of the Best Paper Award Event Dates: May 10-14, 2010).
@inproceedings{eps268360,
title = {Agent-Based Micro-Storage Management for the Smart Grid},
author = {Perukrishnen Vytelingum and Thomas D. Voice and Sarvapali D. Ramchurn and Alex Rogers and Nicholas R. Jennings},
url = {http://eprints.soton.ac.uk/268360/},
year = {2010},
date = {2010-01-01},
booktitle = {The Ninth International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2010) - Won the Best Paper Award},
pages = {39–46},
abstract = {The use of energy storage devices in homes has been advocated as one of the main ways of saving energy and reducing the reliance on fossil fuels in the future Smart Grid. However, if micro-storage devices are all charged at the same time using power from the electricity grid, it means a higher demand and, hence, more generation capacity, more carbon emissions, and, in the worst case, breaking down the system due to over-demand. To alleviate such issues, in this paper, we present a novel agent-based micro-storage management technique that allows all (individually-owned) storage devices in the system to converge to profitable, efficient behaviour. Specifically, we provide a general framework within which to analyse the Nash equilibrium of an electricity grid and devise new agent-based storage learning strategies that adapt to market conditions. Taken altogether, our solution shows that, specifically, in the UK electricity market, it is possible to achieve savings of up to 13% on average for a consumer on his electricity bill with a storage device of 4 kWh. Moreover, we show that there exists an equilibrium where only 38% of UK households would own storage devices and where social welfare would be also maximised (with an overall annual savings of nearly GBP 1.5B at that equilibrium).},
note = {Winner of the Best Paper Award Event Dates: May 10-14, 2010},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
The use of energy storage devices in homes has been advocated as one of the main ways of saving energy and reducing the reliance on fossil fuels in the future Smart Grid. However, if micro-storage devices are all charged at the same time using power from the electricity grid, it means a higher demand and, hence, more generation capacity, more carbon emissions, and, in the worst case, breaking down the system due to over-demand. To alleviate such issues, in this paper, we present a novel agent-based micro-storage management technique that allows all (individually-owned) storage devices in the system to converge to profitable, efficient behaviour. Specifically, we provide a general framework within which to analyse the Nash equilibrium of an electricity grid and devise new agent-based storage learning strategies that adapt to market conditions. Taken altogether, our solution shows that, specifically, in the UK electricity market, it is possible to achieve savings of up to 13% on average for a consumer on his electricity bill with a storage device of 4 kWh. Moreover, we show that there exists an equilibrium where only 38% of UK households would own storage devices and where social welfare would be also maximised (with an overall annual savings of nearly GBP 1.5B at that equilibrium).
175.
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.
176.
Ramchurn, Sarvapali D.; Mezzetti, Claudio; Giovannucci, Andrea; Rodriguez, Juan A.; Dash, Rajdeep K.; Jennings, Nicholas R.
Trust-based mechanisms for robust and efficient task allocation in the presence of execution uncertainty Journal Article
In: Journal of Artificial Intelligence Research, vol. 35, pp. 1–41, 2009.
@article{eps267288,
title = {Trust-based mechanisms for robust and efficient task allocation in the presence of execution uncertainty},
author = {Sarvapali D. Ramchurn and Claudio Mezzetti and Andrea Giovannucci and Juan A. Rodriguez and Rajdeep K. Dash and Nicholas R. Jennings},
url = {http://eprints.soton.ac.uk/267288/},
year = {2009},
date = {2009-01-01},
journal = {Journal of Artificial Intelligence Research},
volume = {35},
pages = {1–41},
abstract = {Vickrey-Clarke-Groves (VCG) mechanisms are often used to allocate tasks to selfish and rational agents. VCG mechanisms are incentive-compatible, direct mechanisms that are efficient (i.e. maximise social utility) and individually rational (i.e. agents prefer to join rather than opt out). However, an important assumption of these mechanisms is that the agents will always successfully complete their allocated tasks. Clearly, this assumption is unrealistic in many real-world applications where agents can, and often do, fail in their endeavours. Moreover, whether an agent is deemed to have failed may be perceived differently by different agents. Such subjective perceptions about an agent's probability of succeeding at a given task are often captured and reasoned about using the notion of trust. Given this background, in this paper we investigate the design of novel mechanisms that take into account the trust between agents when allocating tasks. Specifically, we develop a new class of mechanisms, called trust-based mechanisms, that can take into account multiple subjective measures of the probability of an agent succeeding at a given task and produce allocations that maximise social utility, whilst ensuring that no agent obtains a negative utility. We then show that such mechanisms pose a challenging new combinatorial optimisation problem (that is NP-complete), devise a novel representation for solving the problem, and develop an effective integer programming solution (that can solve instances with about 2x10^ 5 possible allocations in 40 seconds).},
keywords = {},
pubstate = {published},
tppubtype = {article}
}
Vickrey-Clarke-Groves (VCG) mechanisms are often used to allocate tasks to selfish and rational agents. VCG mechanisms are incentive-compatible, direct mechanisms that are efficient (i.e. maximise social utility) and individually rational (i.e. agents prefer to join rather than opt out). However, an important assumption of these mechanisms is that the agents will always successfully complete their allocated tasks. Clearly, this assumption is unrealistic in many real-world applications where agents can, and often do, fail in their endeavours. Moreover, whether an agent is deemed to have failed may be perceived differently by different agents. Such subjective perceptions about an agent's probability of succeeding at a given task are often captured and reasoned about using the notion of trust. Given this background, in this paper we investigate the design of novel mechanisms that take into account the trust between agents when allocating tasks. Specifically, we develop a new class of mechanisms, called trust-based mechanisms, that can take into account multiple subjective measures of the probability of an agent succeeding at a given task and produce allocations that maximise social utility, whilst ensuring that no agent obtains a negative utility. We then show that such mechanisms pose a challenging new combinatorial optimisation problem (that is NP-complete), devise a novel representation for solving the problem, and develop an effective integer programming solution (that can solve instances with about 2x10^ 5 possible allocations in 40 seconds).
177.
Valkenhoef, Gert; Ramchurn, Sarvapali D.; Vytelingum, Perukrishnen; Jennings, Nicholas R.; Verbrugge, Rinek
Continuous double auctions with execution uncertainty Proceedings Article
In: Workshop on Trading Agent Design and Analysis (TADA-09), 2009.
@inproceedings{eps267329,
title = {Continuous double auctions with execution uncertainty},
author = {Gert Valkenhoef and Sarvapali D. Ramchurn and Perukrishnen Vytelingum and Nicholas R. Jennings and Rinek Verbrugge},
url = {http://eprints.soton.ac.uk/267329/},
year = {2009},
date = {2009-01-01},
booktitle = {Workshop on Trading Agent Design and Analysis (TADA-09)},
abstract = {We propose a novel variant of the Continuous Double Auction (CDA), the Trust-based CDA (T-CDA), which we demonstrate to be robust to execution uncertainty. This is desirable in a setting where traders may fail to deliver the goods, services or payments they have promised. Specifically, the TCDA provides a mechanism that allows agents to commit to trades they believe will maximize their expected utility. In this paper, we consider agents that use their trust in other agents to estimate the expected utility of a transaction. We empirically evaluate the mechanism, both against the optimal solution given perfect and complete information and against the standard CDA.We show that the T-CDA consistently outperforms the traditional CDA as execution uncertainty increases in the system. Furthermore, we investigate the robustness of the mechanism to unreliable trust information and find that performance degrades gracefully as information quality decreases.},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
We propose a novel variant of the Continuous Double Auction (CDA), the Trust-based CDA (T-CDA), which we demonstrate to be robust to execution uncertainty. This is desirable in a setting where traders may fail to deliver the goods, services or payments they have promised. Specifically, the TCDA provides a mechanism that allows agents to commit to trades they believe will maximize their expected utility. In this paper, we consider agents that use their trust in other agents to estimate the expected utility of a transaction. We empirically evaluate the mechanism, both against the optimal solution given perfect and complete information and against the standard CDA.We show that the T-CDA consistently outperforms the traditional CDA as execution uncertainty increases in the system. Furthermore, we investigate the robustness of the mechanism to unreliable trust information and find that performance degrades gracefully as information quality decreases.
178.
Adams, Niall; Field, Martin; Gelenbe, Erol; Hand, David; Jennings, Nicholas; Leslie, David; Nicholson, David; Ramchurn, Sarvapali; Rogers, Alex
Intelligent Agents for Disaster Management Proceedings Article
In: Proceedings of the IARP/EURON Workshop on Robotics for Risky Interventions and Environmental Surveillance (RISE), 2008.
@inproceedings{eps272011,
title = {Intelligent Agents for Disaster Management},
author = {Niall Adams and Martin Field and Erol Gelenbe and David Hand and Nicholas Jennings and David Leslie and David Nicholson and Sarvapali Ramchurn and Alex Rogers},
url = {http://eprints.soton.ac.uk/272011/},
year = {2008},
date = {2008-01-01},
booktitle = {Proceedings of the IARP/EURON Workshop on Robotics for Risky Interventions and Environmental Surveillance (RISE)},
abstract = {ALADDIN [1] is a multi-disciplinary project that is developing novel techniques, architectures, and mechanisms for multi-agent systems in uncertain and dynamic environments. The application focus of the project is disaster management. Research within a number of themes is being pursued and this is considering different aspects of the interaction between autonomous agents and the decentralised system architectures that support those interactions. The aim of the research is to contribute to building more robust multi-agent systems for future applications in disaster management and other similar domains.},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
ALADDIN [1] is a multi-disciplinary project that is developing novel techniques, architectures, and mechanisms for multi-agent systems in uncertain and dynamic environments. The application focus of the project is disaster management. Research within a number of themes is being pursued and this is considering different aspects of the interaction between autonomous agents and the decentralised system architectures that support those interactions. The aim of the research is to contribute to building more robust multi-agent systems for future applications in disaster management and other similar domains.
179.
Osborne, Michael A; Rogers, Alex; Ramchurn, Sarvapali; Roberts, Stephen J; Jennings, N. R.
Towards Real-Time Information Processing of Sensor Network Data using Computationally Efficient Multi-output Gaussian Processes Proceedings Article
In: International Conference on Information Processing in Sensor Networks (IPSN 2008), pp. 109–120, 2008, (Event Dates: April 2008).
@inproceedings{eps265122,
title = {Towards Real-Time Information Processing of Sensor Network Data using Computationally Efficient Multi-output Gaussian Processes},
author = {Michael A Osborne and Alex Rogers and Sarvapali Ramchurn and Stephen J Roberts and N. R. Jennings},
url = {http://eprints.soton.ac.uk/265122/},
year = {2008},
date = {2008-01-01},
booktitle = {International Conference on Information Processing in Sensor Networks (IPSN 2008)},
pages = {109–120},
abstract = {In this paper, we describe a novel, computationally efficient algorithm that facilitates the autonomous acquisition of readings from sensor networks (deciding when and which sensor to acquire readings from at any time), and which can, with minimal domain knowledge, perform a range of information processing tasks including modelling the accuracy of the sensor readings, predicting the value of missing sensor readings, and predicting how the monitored environmental variables will evolve into the future. Our motivating scenario is the need to provide situational awareness support to first responders at the scene of a large scale incident, and to this end, we describe a novel iterative formulation of a multi-output Gaussian process that can build and exploit a probabilistic model of the environmental variables being measured (including the correlations and delays that exist between them). We validate our approach using data collected from a network of weather sensors located on the south coast of England.},
note = {Event Dates: April 2008},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
In this paper, we describe a novel, computationally efficient algorithm that facilitates the autonomous acquisition of readings from sensor networks (deciding when and which sensor to acquire readings from at any time), and which can, with minimal domain knowledge, perform a range of information processing tasks including modelling the accuracy of the sensor readings, predicting the value of missing sensor readings, and predicting how the monitored environmental variables will evolve into the future. Our motivating scenario is the need to provide situational awareness support to first responders at the scene of a large scale incident, and to this end, we describe a novel iterative formulation of a multi-output Gaussian process that can build and exploit a probabilistic model of the environmental variables being measured (including the correlations and delays that exist between them). We validate our approach using data collected from a network of weather sensors located on the south coast of England.
180.
Rogers, Alex; Osborne, Michael A; Ramchurn, Sarvapali; Roberts, Stephen J; Jennings, N. R.
Information Agents for Pervasive Sensor Networks Proceedings Article
In: Sixth Annual IEEE International Conference on Pervasive Computing and Communications (PerCom 2008), pp. 294–299, 2008, (Event Dates: March 2008).
@inproceedings{eps264967,
title = {Information Agents for Pervasive Sensor Networks},
author = {Alex Rogers and Michael A Osborne and Sarvapali Ramchurn and Stephen J Roberts and N. R. Jennings},
url = {http://eprints.soton.ac.uk/264967/},
year = {2008},
date = {2008-01-01},
booktitle = {Sixth Annual IEEE International Conference on Pervasive Computing and Communications (PerCom 2008)},
pages = {294–299},
abstract = {In this paper, we describe an information agent, that resides on a mobile computer or personal digital assistant (PDA), that can autonomously acquire sensor readings from pervasive sensor networks (deciding when and which sensor to acquire readings from at any time). Moreover, it can perform a range of information processing tasks including modelling the accuracy of the sensor readings, predicting the value of missing sensor readings, and predicting how the monitored environmental parameters will evolve into the future. Our motivating scenario is the need to provide situational awareness support to first responders at the scene of a large scale incident, and we describe how we use an iterative formulation of a multi-output Gaussian process to build a probabilistic model of the environmental parameters being measured by local sensors, and the correlations and delays that exist between them. We validate our approach using data collected from a network of weather sensors located on the south coast of England.},
note = {Event Dates: March 2008},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
In this paper, we describe an information agent, that resides on a mobile computer or personal digital assistant (PDA), that can autonomously acquire sensor readings from pervasive sensor networks (deciding when and which sensor to acquire readings from at any time). Moreover, it can perform a range of information processing tasks including modelling the accuracy of the sensor readings, predicting the value of missing sensor readings, and predicting how the monitored environmental parameters will evolve into the future. Our motivating scenario is the need to provide situational awareness support to first responders at the scene of a large scale incident, and we describe how we use an iterative formulation of a multi-output Gaussian process to build a probabilistic model of the environmental parameters being measured by local sensors, and the correlations and delays that exist between them. We validate our approach using data collected from a network of weather sensors located on the south coast of England.
Sorry, no publications matched your criteria.
161.
Alam, Muddasser; Rogers, Alex; Ramchurn, Sarvapali
A negotiation protocol for multiple interdependent issues negotiation over energy exchange Proceedings Article
In: IJCAI Workshop on AI for an Intelligent Planet, 2011, (Event Dates: July-16).
@inproceedings{eps272479,
title = {A negotiation protocol for multiple interdependent issues negotiation over energy exchange},
author = {Muddasser Alam and Alex Rogers and Sarvapali Ramchurn},
url = {http://eprints.soton.ac.uk/272479/},
year = {2011},
date = {2011-01-01},
booktitle = {IJCAI Workshop on AI for an Intelligent Planet},
abstract = {We present a novel negotiation protocol to facilitate energy exchange between off-grid homes that are equipped with renewable energy generation and electricity storage. Our solution imposes additional constraints on negotiation such that it reduces a complex interdependent multi-issue problem to one that is tractable. We prove that using our protocol, agents can reach a Pareto-optimal, dominant strategy equilibrium in a decentralized and timely fashion. We empirically evaluate our approach in a realistic setting. In this case, we show that energy exchange can be useful in reducing the capacity of the energy storage devices in homes by close to 40%},
note = {Event Dates: July-16},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
We present a novel negotiation protocol to facilitate energy exchange between off-grid homes that are equipped with renewable energy generation and electricity storage. Our solution imposes additional constraints on negotiation such that it reduces a complex interdependent multi-issue problem to one that is tractable. We prove that using our protocol, agents can reach a Pareto-optimal, dominant strategy equilibrium in a decentralized and timely fashion. We empirically evaluate our approach in a realistic setting. In this case, we show that energy exchange can be useful in reducing the capacity of the energy storage devices in homes by close to 40%
162.
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.
163.
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.
164.
Osborne, Michael A.; Rogers, Alex; Roberts, Stephen J.; Ramchurn, Sarvapali D.; Jennings, Nicholas R.
Gaussian Processes for Time Series Prediction Book Section
In: Bayesian Time Series Models, pp. 341–360, Cambridge University Press, 2011, (Chapter: 16).
@incollection{eps272746,
title = {Gaussian Processes for Time Series Prediction},
author = {Michael A. Osborne and Alex Rogers and Stephen J. Roberts and Sarvapali D. Ramchurn and Nicholas R. Jennings},
url = {http://eprints.soton.ac.uk/272746/},
year = {2011},
date = {2011-01-01},
booktitle = {Bayesian Time Series Models},
pages = {341–360},
publisher = {Cambridge University Press},
note = {Chapter: 16},
keywords = {},
pubstate = {published},
tppubtype = {incollection}
}
165.
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.
166.
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).
167.
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}
}
168.
Voice, Thomas; Vytelingum, Perukrishnen; Ramchurn, Sarvapali; Rogers, Alex; Jennings, Nick
Decentralised Control of Micro-Storage in the Smart Grid Proceedings Article
In: AAAI-11: Twenty-Fifth Conference on Artificial Intelligence, pp. 1421–1426, 2011, (Event Dates: August 7?11, 2011).
@inproceedings{eps272262,
title = {Decentralised Control of Micro-Storage in the Smart Grid},
author = {Thomas Voice and Perukrishnen Vytelingum and Sarvapali Ramchurn and Alex Rogers and Nick Jennings},
url = {http://eprints.soton.ac.uk/272262/},
year = {2011},
date = {2011-01-01},
booktitle = {AAAI-11: Twenty-Fifth Conference on Artificial Intelligence},
pages = {1421–1426},
abstract = {In this paper, we propose a novel decentralised control mechanism to manage micro-storage in the smart grid. Our approach uses an adaptive pricing scheme that energy suppliers apply to home smart agents controlling micro-storage devices. In particular, we prove that the interaction between a supplier using our pricing scheme and the actions of selfish micro-storage agents forms a globally stable feedback loop that converges to an efficient equilibrium. We further propose a market strategy that allows the supplier to reduce wholesale purchasing costs without increasing the uncertainty and variance for its aggregate consumer demand. Moreover, we empirically evaluate our mechanism (based on the UK grid data) and show that it yields savings of up to 16% in energy cost for consumers using storage devices with average capacity 10 kWh. Furthermore, we show that it is robust against extreme system changes.},
note = {Event Dates: August 7?11, 2011},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
In this paper, we propose a novel decentralised control mechanism to manage micro-storage in the smart grid. Our approach uses an adaptive pricing scheme that energy suppliers apply to home smart agents controlling micro-storage devices. In particular, we prove that the interaction between a supplier using our pricing scheme and the actions of selfish micro-storage agents forms a globally stable feedback loop that converges to an efficient equilibrium. We further propose a market strategy that allows the supplier to reduce wholesale purchasing costs without increasing the uncertainty and variance for its aggregate consumer demand. Moreover, we empirically evaluate our mechanism (based on the UK grid data) and show that it yields savings of up to 16% in energy cost for consumers using storage devices with average capacity 10 kWh. Furthermore, we show that it is robust against extreme system changes.
169.
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).
170.
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.
171.
Ramchurn, S. D.; Polukarov, Mariya; Farinelli, Alessandro; Jennings, Nick; Trong, Cuong
Coalition Formation with Spatial and Temporal Constraints Proceedings Article
In: International Joint Conference on Autonomous Agents and Multi-Agent Systems (AAMAS 2010), pp. 1181–1188, 2010, (Event Dates: May 2010).
@inproceedings{eps268497,
title = {Coalition Formation with Spatial and Temporal Constraints},
author = {S. D. Ramchurn and Mariya Polukarov and Alessandro Farinelli and Nick Jennings and Cuong Trong},
url = {http://eprints.soton.ac.uk/268497/},
year = {2010},
date = {2010-01-01},
booktitle = {International Joint Conference on Autonomous Agents and Multi-Agent Systems (AAMAS 2010)},
pages = {1181–1188},
abstract = {The coordination of emergency responders and robots to undertake a number of tasks in disaster scenarios is a grand challenge for multi-agent systems. Central to this endeavour is the problem of forming the best teams (coalitions) of responders to perform the various tasks in the area where the disaster has struck. Moreover, these teams may have to form, disband, and reform in different areas of the disaster region. This is because in most cases there will be more tasks than agents. Hence, agents need to schedule themselves to attempt each task in turn. Second, the tasks themselves can be very complex: requiring the agents to work on them for different lengths of time and having deadlines by when they need to be completed. The problem is complicated still further when different coalitions perform tasks with different levels of efficiency. Given all these facets, we define this as The Coalition Formation with Spatial and Temporal constraints problem (CFSTP).We show that this problem is NP-hard–in particular, it contains the wellknown complex combinatorial problem of Team Orienteering as a special case. Based on this, we design a Mixed Integer Program to optimally solve small-scale instances of the CFSTP and develop new anytime heuristics that can, on average, complete 97% of the tasks for large problems (20 agents and 300 tasks). In so doing, our solutions represent the first results for CFSTP.},
note = {Event Dates: May 2010},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
The coordination of emergency responders and robots to undertake a number of tasks in disaster scenarios is a grand challenge for multi-agent systems. Central to this endeavour is the problem of forming the best teams (coalitions) of responders to perform the various tasks in the area where the disaster has struck. Moreover, these teams may have to form, disband, and reform in different areas of the disaster region. This is because in most cases there will be more tasks than agents. Hence, agents need to schedule themselves to attempt each task in turn. Second, the tasks themselves can be very complex: requiring the agents to work on them for different lengths of time and having deadlines by when they need to be completed. The problem is complicated still further when different coalitions perform tasks with different levels of efficiency. Given all these facets, we define this as The Coalition Formation with Spatial and Temporal constraints problem (CFSTP).We show that this problem is NP-hard–in particular, it contains the wellknown complex combinatorial problem of Team Orienteering as a special case. Based on this, we design a Mixed Integer Program to optimally solve small-scale instances of the CFSTP and develop new anytime heuristics that can, on average, complete 97% of the tasks for large problems (20 agents and 300 tasks). In so doing, our solutions represent the first results for CFSTP.
172.
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.
173.
Vytelingum, Perukrishnen; Ramchurn, Sarvapali D.; Voice, Thomas D.; Rogers, Alex; Jennings, Nicholas R.
Trading agents for the smart electricity grid Proceedings Article
In: The Ninth International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2010), pp. 897–904, 2010, (Event Dates: May 10-14, 2010).
@inproceedings{eps268361,
title = {Trading agents for the smart electricity grid},
author = {Perukrishnen Vytelingum and Sarvapali D. Ramchurn and Thomas D. Voice and Alex Rogers and Nicholas R. Jennings},
url = {http://eprints.soton.ac.uk/268361/},
year = {2010},
date = {2010-01-01},
booktitle = {The Ninth International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2010)},
pages = {897–904},
abstract = {The vision of the Smart Grid includes the creation of intelligent electricity supply networks to allow efficient use of energy resources, reduce carbon emissions and are robust to failures. One of the key assumptions underlying this vision is that it will be possible to manage the trading of electricity between homes and micro-grids while coping with the inherent real-time dynamism in electricity demand and supply. The management of these trades needs to take into account the fact that most, if not all, of the actors in the system are self-interested and transmission line capacities are constrained. Against this background, we develop and evaluate a novel market-based mechanism and novel trading strategies for the Smart Grid. Our mechanism is based on the Continuous Double Auction (CDA) and automatically manages the congestion within the system by pricing the flow of electricity. We also introduce mechanisms to ensure the system can cope with unforeseen demand or increased supply capacity in real time. Finally, we develop new strategies that we show achieve high market efficiency (typically over 90%).},
note = {Event Dates: May 10-14, 2010},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
The vision of the Smart Grid includes the creation of intelligent electricity supply networks to allow efficient use of energy resources, reduce carbon emissions and are robust to failures. One of the key assumptions underlying this vision is that it will be possible to manage the trading of electricity between homes and micro-grids while coping with the inherent real-time dynamism in electricity demand and supply. The management of these trades needs to take into account the fact that most, if not all, of the actors in the system are self-interested and transmission line capacities are constrained. Against this background, we develop and evaluate a novel market-based mechanism and novel trading strategies for the Smart Grid. Our mechanism is based on the Continuous Double Auction (CDA) and automatically manages the congestion within the system by pricing the flow of electricity. We also introduce mechanisms to ensure the system can cope with unforeseen demand or increased supply capacity in real time. Finally, we develop new strategies that we show achieve high market efficiency (typically over 90%).
174.
Vytelingum, Perukrishnen; Voice, Thomas D.; Ramchurn, Sarvapali D.; Rogers, Alex; Jennings, Nicholas R.
Agent-Based Micro-Storage Management for the Smart Grid Proceedings Article
In: The Ninth International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2010) - Won the Best Paper Award, pp. 39–46, 2010, (Winner of the Best Paper Award Event Dates: May 10-14, 2010).
@inproceedings{eps268360,
title = {Agent-Based Micro-Storage Management for the Smart Grid},
author = {Perukrishnen Vytelingum and Thomas D. Voice and Sarvapali D. Ramchurn and Alex Rogers and Nicholas R. Jennings},
url = {http://eprints.soton.ac.uk/268360/},
year = {2010},
date = {2010-01-01},
booktitle = {The Ninth International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2010) - Won the Best Paper Award},
pages = {39–46},
abstract = {The use of energy storage devices in homes has been advocated as one of the main ways of saving energy and reducing the reliance on fossil fuels in the future Smart Grid. However, if micro-storage devices are all charged at the same time using power from the electricity grid, it means a higher demand and, hence, more generation capacity, more carbon emissions, and, in the worst case, breaking down the system due to over-demand. To alleviate such issues, in this paper, we present a novel agent-based micro-storage management technique that allows all (individually-owned) storage devices in the system to converge to profitable, efficient behaviour. Specifically, we provide a general framework within which to analyse the Nash equilibrium of an electricity grid and devise new agent-based storage learning strategies that adapt to market conditions. Taken altogether, our solution shows that, specifically, in the UK electricity market, it is possible to achieve savings of up to 13% on average for a consumer on his electricity bill with a storage device of 4 kWh. Moreover, we show that there exists an equilibrium where only 38% of UK households would own storage devices and where social welfare would be also maximised (with an overall annual savings of nearly GBP 1.5B at that equilibrium).},
note = {Winner of the Best Paper Award Event Dates: May 10-14, 2010},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
The use of energy storage devices in homes has been advocated as one of the main ways of saving energy and reducing the reliance on fossil fuels in the future Smart Grid. However, if micro-storage devices are all charged at the same time using power from the electricity grid, it means a higher demand and, hence, more generation capacity, more carbon emissions, and, in the worst case, breaking down the system due to over-demand. To alleviate such issues, in this paper, we present a novel agent-based micro-storage management technique that allows all (individually-owned) storage devices in the system to converge to profitable, efficient behaviour. Specifically, we provide a general framework within which to analyse the Nash equilibrium of an electricity grid and devise new agent-based storage learning strategies that adapt to market conditions. Taken altogether, our solution shows that, specifically, in the UK electricity market, it is possible to achieve savings of up to 13% on average for a consumer on his electricity bill with a storage device of 4 kWh. Moreover, we show that there exists an equilibrium where only 38% of UK households would own storage devices and where social welfare would be also maximised (with an overall annual savings of nearly GBP 1.5B at that equilibrium).
175.
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.
176.
Ramchurn, Sarvapali D.; Mezzetti, Claudio; Giovannucci, Andrea; Rodriguez, Juan A.; Dash, Rajdeep K.; Jennings, Nicholas R.
Trust-based mechanisms for robust and efficient task allocation in the presence of execution uncertainty Journal Article
In: Journal of Artificial Intelligence Research, vol. 35, pp. 1–41, 2009.
@article{eps267288,
title = {Trust-based mechanisms for robust and efficient task allocation in the presence of execution uncertainty},
author = {Sarvapali D. Ramchurn and Claudio Mezzetti and Andrea Giovannucci and Juan A. Rodriguez and Rajdeep K. Dash and Nicholas R. Jennings},
url = {http://eprints.soton.ac.uk/267288/},
year = {2009},
date = {2009-01-01},
journal = {Journal of Artificial Intelligence Research},
volume = {35},
pages = {1–41},
abstract = {Vickrey-Clarke-Groves (VCG) mechanisms are often used to allocate tasks to selfish and rational agents. VCG mechanisms are incentive-compatible, direct mechanisms that are efficient (i.e. maximise social utility) and individually rational (i.e. agents prefer to join rather than opt out). However, an important assumption of these mechanisms is that the agents will always successfully complete their allocated tasks. Clearly, this assumption is unrealistic in many real-world applications where agents can, and often do, fail in their endeavours. Moreover, whether an agent is deemed to have failed may be perceived differently by different agents. Such subjective perceptions about an agent's probability of succeeding at a given task are often captured and reasoned about using the notion of trust. Given this background, in this paper we investigate the design of novel mechanisms that take into account the trust between agents when allocating tasks. Specifically, we develop a new class of mechanisms, called trust-based mechanisms, that can take into account multiple subjective measures of the probability of an agent succeeding at a given task and produce allocations that maximise social utility, whilst ensuring that no agent obtains a negative utility. We then show that such mechanisms pose a challenging new combinatorial optimisation problem (that is NP-complete), devise a novel representation for solving the problem, and develop an effective integer programming solution (that can solve instances with about 2x10^ 5 possible allocations in 40 seconds).},
keywords = {},
pubstate = {published},
tppubtype = {article}
}
Vickrey-Clarke-Groves (VCG) mechanisms are often used to allocate tasks to selfish and rational agents. VCG mechanisms are incentive-compatible, direct mechanisms that are efficient (i.e. maximise social utility) and individually rational (i.e. agents prefer to join rather than opt out). However, an important assumption of these mechanisms is that the agents will always successfully complete their allocated tasks. Clearly, this assumption is unrealistic in many real-world applications where agents can, and often do, fail in their endeavours. Moreover, whether an agent is deemed to have failed may be perceived differently by different agents. Such subjective perceptions about an agent's probability of succeeding at a given task are often captured and reasoned about using the notion of trust. Given this background, in this paper we investigate the design of novel mechanisms that take into account the trust between agents when allocating tasks. Specifically, we develop a new class of mechanisms, called trust-based mechanisms, that can take into account multiple subjective measures of the probability of an agent succeeding at a given task and produce allocations that maximise social utility, whilst ensuring that no agent obtains a negative utility. We then show that such mechanisms pose a challenging new combinatorial optimisation problem (that is NP-complete), devise a novel representation for solving the problem, and develop an effective integer programming solution (that can solve instances with about 2x10^ 5 possible allocations in 40 seconds).
177.
Valkenhoef, Gert; Ramchurn, Sarvapali D.; Vytelingum, Perukrishnen; Jennings, Nicholas R.; Verbrugge, Rinek
Continuous double auctions with execution uncertainty Proceedings Article
In: Workshop on Trading Agent Design and Analysis (TADA-09), 2009.
@inproceedings{eps267329,
title = {Continuous double auctions with execution uncertainty},
author = {Gert Valkenhoef and Sarvapali D. Ramchurn and Perukrishnen Vytelingum and Nicholas R. Jennings and Rinek Verbrugge},
url = {http://eprints.soton.ac.uk/267329/},
year = {2009},
date = {2009-01-01},
booktitle = {Workshop on Trading Agent Design and Analysis (TADA-09)},
abstract = {We propose a novel variant of the Continuous Double Auction (CDA), the Trust-based CDA (T-CDA), which we demonstrate to be robust to execution uncertainty. This is desirable in a setting where traders may fail to deliver the goods, services or payments they have promised. Specifically, the TCDA provides a mechanism that allows agents to commit to trades they believe will maximize their expected utility. In this paper, we consider agents that use their trust in other agents to estimate the expected utility of a transaction. We empirically evaluate the mechanism, both against the optimal solution given perfect and complete information and against the standard CDA.We show that the T-CDA consistently outperforms the traditional CDA as execution uncertainty increases in the system. Furthermore, we investigate the robustness of the mechanism to unreliable trust information and find that performance degrades gracefully as information quality decreases.},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
We propose a novel variant of the Continuous Double Auction (CDA), the Trust-based CDA (T-CDA), which we demonstrate to be robust to execution uncertainty. This is desirable in a setting where traders may fail to deliver the goods, services or payments they have promised. Specifically, the TCDA provides a mechanism that allows agents to commit to trades they believe will maximize their expected utility. In this paper, we consider agents that use their trust in other agents to estimate the expected utility of a transaction. We empirically evaluate the mechanism, both against the optimal solution given perfect and complete information and against the standard CDA.We show that the T-CDA consistently outperforms the traditional CDA as execution uncertainty increases in the system. Furthermore, we investigate the robustness of the mechanism to unreliable trust information and find that performance degrades gracefully as information quality decreases.
178.
Adams, Niall; Field, Martin; Gelenbe, Erol; Hand, David; Jennings, Nicholas; Leslie, David; Nicholson, David; Ramchurn, Sarvapali; Rogers, Alex
Intelligent Agents for Disaster Management Proceedings Article
In: Proceedings of the IARP/EURON Workshop on Robotics for Risky Interventions and Environmental Surveillance (RISE), 2008.
@inproceedings{eps272011,
title = {Intelligent Agents for Disaster Management},
author = {Niall Adams and Martin Field and Erol Gelenbe and David Hand and Nicholas Jennings and David Leslie and David Nicholson and Sarvapali Ramchurn and Alex Rogers},
url = {http://eprints.soton.ac.uk/272011/},
year = {2008},
date = {2008-01-01},
booktitle = {Proceedings of the IARP/EURON Workshop on Robotics for Risky Interventions and Environmental Surveillance (RISE)},
abstract = {ALADDIN [1] is a multi-disciplinary project that is developing novel techniques, architectures, and mechanisms for multi-agent systems in uncertain and dynamic environments. The application focus of the project is disaster management. Research within a number of themes is being pursued and this is considering different aspects of the interaction between autonomous agents and the decentralised system architectures that support those interactions. The aim of the research is to contribute to building more robust multi-agent systems for future applications in disaster management and other similar domains.},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
ALADDIN [1] is a multi-disciplinary project that is developing novel techniques, architectures, and mechanisms for multi-agent systems in uncertain and dynamic environments. The application focus of the project is disaster management. Research within a number of themes is being pursued and this is considering different aspects of the interaction between autonomous agents and the decentralised system architectures that support those interactions. The aim of the research is to contribute to building more robust multi-agent systems for future applications in disaster management and other similar domains.
179.
Osborne, Michael A; Rogers, Alex; Ramchurn, Sarvapali; Roberts, Stephen J; Jennings, N. R.
Towards Real-Time Information Processing of Sensor Network Data using Computationally Efficient Multi-output Gaussian Processes Proceedings Article
In: International Conference on Information Processing in Sensor Networks (IPSN 2008), pp. 109–120, 2008, (Event Dates: April 2008).
@inproceedings{eps265122,
title = {Towards Real-Time Information Processing of Sensor Network Data using Computationally Efficient Multi-output Gaussian Processes},
author = {Michael A Osborne and Alex Rogers and Sarvapali Ramchurn and Stephen J Roberts and N. R. Jennings},
url = {http://eprints.soton.ac.uk/265122/},
year = {2008},
date = {2008-01-01},
booktitle = {International Conference on Information Processing in Sensor Networks (IPSN 2008)},
pages = {109–120},
abstract = {In this paper, we describe a novel, computationally efficient algorithm that facilitates the autonomous acquisition of readings from sensor networks (deciding when and which sensor to acquire readings from at any time), and which can, with minimal domain knowledge, perform a range of information processing tasks including modelling the accuracy of the sensor readings, predicting the value of missing sensor readings, and predicting how the monitored environmental variables will evolve into the future. Our motivating scenario is the need to provide situational awareness support to first responders at the scene of a large scale incident, and to this end, we describe a novel iterative formulation of a multi-output Gaussian process that can build and exploit a probabilistic model of the environmental variables being measured (including the correlations and delays that exist between them). We validate our approach using data collected from a network of weather sensors located on the south coast of England.},
note = {Event Dates: April 2008},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
In this paper, we describe a novel, computationally efficient algorithm that facilitates the autonomous acquisition of readings from sensor networks (deciding when and which sensor to acquire readings from at any time), and which can, with minimal domain knowledge, perform a range of information processing tasks including modelling the accuracy of the sensor readings, predicting the value of missing sensor readings, and predicting how the monitored environmental variables will evolve into the future. Our motivating scenario is the need to provide situational awareness support to first responders at the scene of a large scale incident, and to this end, we describe a novel iterative formulation of a multi-output Gaussian process that can build and exploit a probabilistic model of the environmental variables being measured (including the correlations and delays that exist between them). We validate our approach using data collected from a network of weather sensors located on the south coast of England.
180.
Rogers, Alex; Osborne, Michael A; Ramchurn, Sarvapali; Roberts, Stephen J; Jennings, N. R.
Information Agents for Pervasive Sensor Networks Proceedings Article
In: Sixth Annual IEEE International Conference on Pervasive Computing and Communications (PerCom 2008), pp. 294–299, 2008, (Event Dates: March 2008).
@inproceedings{eps264967,
title = {Information Agents for Pervasive Sensor Networks},
author = {Alex Rogers and Michael A Osborne and Sarvapali Ramchurn and Stephen J Roberts and N. R. Jennings},
url = {http://eprints.soton.ac.uk/264967/},
year = {2008},
date = {2008-01-01},
booktitle = {Sixth Annual IEEE International Conference on Pervasive Computing and Communications (PerCom 2008)},
pages = {294–299},
abstract = {In this paper, we describe an information agent, that resides on a mobile computer or personal digital assistant (PDA), that can autonomously acquire sensor readings from pervasive sensor networks (deciding when and which sensor to acquire readings from at any time). Moreover, it can perform a range of information processing tasks including modelling the accuracy of the sensor readings, predicting the value of missing sensor readings, and predicting how the monitored environmental parameters will evolve into the future. Our motivating scenario is the need to provide situational awareness support to first responders at the scene of a large scale incident, and we describe how we use an iterative formulation of a multi-output Gaussian process to build a probabilistic model of the environmental parameters being measured by local sensors, and the correlations and delays that exist between them. We validate our approach using data collected from a network of weather sensors located on the south coast of England.},
note = {Event Dates: March 2008},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
In this paper, we describe an information agent, that resides on a mobile computer or personal digital assistant (PDA), that can autonomously acquire sensor readings from pervasive sensor networks (deciding when and which sensor to acquire readings from at any time). Moreover, it can perform a range of information processing tasks including modelling the accuracy of the sensor readings, predicting the value of missing sensor readings, and predicting how the monitored environmental parameters will evolve into the future. Our motivating scenario is the need to provide situational awareness support to first responders at the scene of a large scale incident, and we describe how we use an iterative formulation of a multi-output Gaussian process to build a probabilistic model of the environmental parameters being measured by local sensors, and the correlations and delays that exist between them. We validate our approach using data collected from a network of weather sensors located on the south coast of England.
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}
}
Sorry, no publications matched your criteria.