We investigate a multi-agent patrolling problem where information is distributed alongside threats in environments with uncertainties. Specifically, the information and threat at each location are independently modelled as multi-state Markov chains, whose states are not observed until the location is visited by an agent. While agents will obtain information at a location, they may also suffer damage from the threat at that location. Therefore, the goal of the agents is to gather as much information as possible while mitigating the damage incurred. To address this challenge, we formulate the single-agent patrolling problem as a Partially Observable Markov Decision Process (POMDP) and propose a computationally efficient algorithm to solve this model. Building upon this, to compute patrols for multiple agents, the single-agent algorithm is extended for each agent with the aim of maximising its marginal contribution to the team. We empirically evaluate our algorithm on problems of multi-agent patrolling and show that it outperforms a baseline algorithm up to 44% for 10 agents and by 21% for 15 agents in large domains.

http://www.ncbi.nlm.nih.gov/pmc/articles/PMC4472811/

@article{chen:etal:2016,
title = {Multi-Agent Patrolling under Uncertainty and Threats},
author = {Chen, Shaofei and Wu, Feng and Shen, Lincheng and Chen, Jing and Ramchurn, Sarvapali D},
editor = {Deng, Yong},
url = {http://www.ncbi.nlm.nih.gov/pmc/articles/PMC4472811/},
doi = {10.1371/journal.pone.0130154},
isbn = {1932-6203},
year = {2015},
date = {2015-01-01},
journal = {PLoS ONE},
volume = {10},
number = {6},
pages = {e0130154},
publisher = {Public Library of Science},
abstract = {We investigate a multi-agent patrolling problem where information is distributed alongside threats in environments with uncertainties. Specifically, the information and threat at each location are independently modelled as multi-state Markov chains, whose states are not observed until the location is visited by an agent. While agents will obtain information at a location, they may also suffer damage from the threat at that location. Therefore, the goal of the agents is to gather as much information as possible while mitigating the damage incurred. To address this challenge, we formulate the single-agent patrolling problem as a Partially Observable Markov Decision Process (POMDP) and propose a computationally efficient algorithm to solve this model. Building upon this, to compute patrols for multiple agents, the single-agent algorithm is extended for each agent with the aim of maximising its marginal contribution to the team. We empirically evaluate our algorithm on problems of multi-agent patrolling and show that it outperforms a baseline algorithm up to 44% for 10 agents and by 21% for 15 agents in large domains.},
keywords = {},
pubstate = {published},
tppubtype = {article} }

No data available.

https://ieeexplore.ieee.org/document/7362160

@article{7362160,
title = {Decentralized Patrolling Under Constraints in Dynamic Environments},
author = {Chen, S. and Wu, F. and Shen, L. and Chen, J. and Ramchurn, S.D.},
doi = {10.1109/TCYB.2015.2505737},
issn = {2168-2267},
year = {2015},
date = {2015-01-01},
journal = {Cybernetics, IEEE Transactions on},
volume = {PP},
number = {99},
pages = {1-13},
keywords = {},
pubstate = {published},
tppubtype = {article} }

No data available.

http://dl.acm.org/citation.cfm?id=2768510

@proceedings{DBLP:conf/eenergy/2015,
title = {Proceedings of the 2015 ACM Sixth International Conference on Future Energy Systems, e-Energy 2015, Bangalore, India, July 14-17, 2015},
editor = {Shivkumar Kalyanaraman and Deva P Seetharam and Rajeev Shorey and Sarvapali D Ramchurn and Mani Srivastava},
url = {http://dl.acm.org/citation.cfm?id=2768510},
isbn = {978-1-4503-3609-3},
year = {2015},
date = {2015-01-01},
publisher = {ACM},
keywords = {},
pubstate = {published},
tppubtype = {proceedings} }

Modelling behavioural biometric patterns is a key issue for modern user centric applications, aimed at better monitoring users’ activities, understanding their habits and detecting their identity. Following this trend, this paper investigates whether the electrical energy consumption of a user can be a distinctive behavioural biometric trait. In particular we analyse daily and weekly load profiles showing that they are closely related to the identity of the users. Hence, we believe that this level of analysis can open interesting application scenarios in the field of energy management and it provides a good working framework for the continuous development of smart environments with demonstrable benefits on real-world implementations.

https://www.sramchurn.com/wp-content/uploads/2014/10/CR_v1.pdf

@article{bicego:etal:2014,
title = {Behavioural biometrics using electricity load profiles},
author = {M. Bicego, F. Recchia, A. Farinelli, S. D. Ramchurn, E. Grosso},
url = {https://www.sramchurn.com/wp-content/uploads/2014/10/CR_v1.pdf},
year = {2014},
date = {2014-08-24},
journal = {Proceedings of the International Conference on Pattern Recognition},
abstract = {Modelling behavioural biometric patterns is a key issue for modern user centric applications, aimed at better monitoring users’ activities, understanding their habits and detecting their identity. Following this trend, this paper investigates whether the electrical energy consumption of a user can be a distinctive behavioural biometric trait. In particular we analyse daily and weekly load profiles showing that they are closely related to the identity of the users. Hence, we believe that this level of analysis can open interesting application scenarios in the field of energy management and it provides a good working framework for the continuous development of smart environments with demonstrable benefits on real-world implementations.},
keywords = {},
pubstate = {published},
tppubtype = {article} }

Recently, many algorithms have been developed for autonomous agents to manage home energy use on behalf of their human owners. By so doing, it is expected that agents will be more efficient at, for example, choosing the best energy tariff to switch to when dynamically priced tariffs come about. However, to date, there has been no validation of such technologies in any field trial. In particular, it has not been shown whether users prefer fully autonomous agents as opposed to controlling their preferences manually. Hence, in this paper we describe a novel platform, called Tariff Agent, to study notions of flexible autonomy in the context of tariff switching. Tariff Agent uses real-world datasets and real-time electricity monitoring to instantiate a scenario where human participants may have to make, or delegate to their agent (in different ways), tariff switching decisions given uncertainties about their own consumption and tariff prices. We carried out a field trial with 10 participants and, from both quantitative and qualitative results, formulate novel design guidelines for systems that implement flexible autonom.

http://eprints.soton.ac.uk/360820/

@inproceedings{eps360820,
title = {A field study of human-agent interaction for electricity tariff switching},
author = {Alper Alan and Enrico Costanza and J. Fischer and Sarvapali Ramchurn and T. Rodden and N.R. Jennings},
url = {http://eprints.soton.ac.uk/360820/},
year = {2014},
date = {2014-01-01},
booktitle = {Proceedings of the 13th International Conference on Autonomous Agents and Multi-Agent Systems},
abstract = {Recently, many algorithms have been developed for autonomous agents to manage home energy use on behalf of their human owners. By so doing, it is expected that agents will be more efficient at, for example, choosing the best energy tariff to switch to when dynamically priced tariffs come about. However, to date, there has been no validation of such technologies in any field trial. In particular, it has not been shown whether users prefer fully autonomous agents as opposed to controlling their preferences manually. Hence, in this paper we describe a novel platform, called Tariff Agent, to study notions of flexible autonomy in the context of tariff switching. Tariff Agent uses real-world datasets and real-time electricity monitoring to instantiate a scenario where human participants may have to make, or delegate to their agent (in different ways), tariff switching decisions given uncertainties about their own consumption and tariff prices. We carried out a field trial with 10 participants and, from both quantitative and qualitative results, formulate novel design guidelines for systems that implement flexible autonom.},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings} }

No data available.

http://eprints.soton.ac.uk/361173/

@inproceedings{eps361173,
title = {Doing the laundry with agents: a field trial of a future smart energy system in the home},
author = {Enrico Costanza and Joel E Fischer and James A Colley and Tom Rodden and Sarvapali Ramchurn and Nicholas R. Jennings},
url = {http://eprints.soton.ac.uk/361173/},
year = {2014},
date = {2014-01-01},
booktitle = {ACM CHI Conference on Human Factors in Computing Systems 2014},
pages = {813--822},
organization = {ACM},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings} }

No data available.

http://eprints.soton.ac.uk/362321/

@inproceedings{eps362321,
title = {BudgetFix: budget limited crowdsourcing for interdependent task allocation with quality guarantees},
author = {Long Tran-Thanh and Trung Dong Huynh and A Rosenfield and Sarvapali Ramchurn and Nicholas R. Jennings},
url = {http://eprints.soton.ac.uk/362321/},
year = {2014},
date = {2014-01-01},
booktitle = {13th International Conference on Autonomous Agents and Multi-Agent Systems},
publisher = {International Foundation for Autonomous Agents and Multiagent Systems},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings} }

This paper tackles the problem of parallelizing heterogeneous computational tasks across a number of computational nodes (aka agents) where each agent may not be able to perform all the tasks and may have different computational speeds. An equivalent problem can be found in operations research, and it is known as scheduling tasks on unrelated parallel machines (also known as R?Cmax). Given this equivalence observation, we present the spanning tree decentralized task distribution algorithm (ST-DTDA), the first decentralized solution to R?Cmax. ST-DTDA achieves decomposition by means of the min?max algorithm, a member of the generalized distributive law family, that performs inference by message-passing along the edges of a graphical model (known as a junction tree). Specifically, ST-DTDA uses min?max to optimally solve an approximation of the original R?Cmax problem that results from eliminating possible agent-task allocations until it is mapped into an acyclic structure. To eliminate those allocations that are least likely to have an impact on the solution quality, ST-DTDA uses a heuristic approach. Moreover, ST-DTDA provides a per-instance approximation ratio that guarantees that the makespan of its solution (optimal in the approximated R?Cmax problem) is not more than a factor ensuremathrho times the makespan of the optimal of the original problem. In our empirical evaluation of ST-DTDA, we show that ST-DTDA, with a min-regret heuristic, converges to solutions that are between 78 and 95% optimal whilst providing approximation ratios lower than 3.

http://eprints.soton.ac.uk/360818/

@article{eps360818,
title = {A message-passing approach to decentralised parallel machine scheduling},
author = {Meritxell Vinyals and Kathryn Macarthur and Alessandro Farinelli and Sarvapali Ramchurn and Nicholas R. Jennings},
url = {http://eprints.soton.ac.uk/360818/},
year = {2014},
date = {2014-01-01},
journal = {The Computer Journal},
publisher = {Oxford University Press},
abstract = {This paper tackles the problem of parallelizing heterogeneous computational tasks across a number of computational nodes (aka agents) where each agent may not be able to perform all the tasks and may have different computational speeds. An equivalent problem can be found in operations research, and it is known as scheduling tasks on unrelated parallel machines (also known as R?Cmax). Given this equivalence observation, we present the spanning tree decentralized task distribution algorithm (ST-DTDA), the first decentralized solution to R?Cmax. ST-DTDA achieves decomposition by means of the min?max algorithm, a member of the generalized distributive law family, that performs inference by message-passing along the edges of a graphical model (known as a junction tree). Specifically, ST-DTDA uses min?max to optimally solve an approximation of the original R?Cmax problem that results from eliminating possible agent-task allocations until it is mapped into an acyclic structure. To eliminate those allocations that are least likely to have an impact on the solution quality, ST-DTDA uses a heuristic approach. Moreover, ST-DTDA provides a per-instance approximation ratio that guarantees that the makespan of its solution (optimal in the approximated R?Cmax problem) is not more than a factor ensuremathrho times the makespan of the optimal of the original problem. In our empirical evaluation of ST-DTDA, we show that ST-DTDA, with a min-regret heuristic, converges to solutions that are between 78 and 95% optimal whilst providing approximation ratios lower than 3.},
keywords = {},
pubstate = {published},
tppubtype = {article} }