Coalition formation is a fundamental approach to multi-agent coordination, and a key challenge in this context is the coalition structure generation problem, where a set of agents must be partitioned into the best set of coalitions. This problem is NP-hard and typical optimal algorithms do not scale to more than 50 agents: efficient approximate solutions are therefore needed for hundreds or thousands of agents. In this paper we propose a novel heuristic, based on ideas and tools used in the data clustering domain. In particular, we present a coalition formation algorithm inspired by the well known class of hierarchical agglomerative clustering techniques (Linkage algorithms). We present different variants of the algorithm, which we call Coalition Linkage (C-Link) and demonstrate how such algorithm can be adapted to graph restricted coalition formation problems (where an interaction graph defined among the agents restricts the set of feasible coalitions). Moreover, we discuss how we can provide an upper bound on the value of the optimal coalition structure, and we show that for specific characteristic functions we can provide such bounds while maintaining polynomial computational costs and memory requirements. We empirically evaluate the different variants of the C-Link algorithm on two synthetic benchmark data-sets, as well as in two real world scenarios, involving a collective energy purchasing and a ridesharing application. In these settings C-Link achieves promising results providing high quality solutions and solving problem involving thousands of agents in few minutes.

https://www.sramchurn.com/wp-content/uploads/2017/02/1-s2.0-S0952197616302536-mai%5B...%5D

@article{farinelli:etal:2017,
title = {A Hierarchical Clustering Approach to Large-scale Near-optimal Coalition Formation with Quality Guarantees},
author = {Alessandro Farinelli and Manuele Bicego and Filippo Bistaffa and Sarvapali D. Ramchurn},
url = {https://www.sramchurn.com/wp-content/uploads/2017/02/1-s2.0-S0952197616302536-main.pdf},
doi = {http://dx.doi.org/10.1016/j.engappai.2016.12.018},
year = {2017},
date = {2017-02-01},
journal = {Engineering Applications of Artificial Intelligence (EAAI)},
volume = {57},
pages = {170-185},
abstract = {Coalition formation is a fundamental approach to multi-agent coordination, and a key challenge in this context is the coalition structure generation problem, where a set of agents must be partitioned into the best set of coalitions. This problem is NP-hard and typical optimal algorithms do not scale to more than 50 agents: efficient approximate solutions are therefore needed for hundreds or thousands of agents. In this paper we propose a novel heuristic, based on ideas and tools used in the data clustering domain. In particular, we present a coalition formation algorithm inspired by the well known class of hierarchical agglomerative clustering techniques (Linkage algorithms). We present different variants of the algorithm, which we call Coalition Linkage (C-Link) and demonstrate how such algorithm can be adapted to graph restricted coalition formation problems (where an interaction graph defined among the agents restricts the set of feasible coalitions). Moreover, we discuss how we can provide an upper bound on the value of the optimal coalition structure, and we show that for specific characteristic functions we can provide such bounds while maintaining polynomial computational costs and memory requirements. We empirically evaluate the different variants of the C-Link algorithm on two synthetic benchmark data-sets, as well as in two real world scenarios, involving a collective energy purchasing and a ridesharing application. In these settings C-Link achieves promising results providing high quality solutions and solving problem involving thousands of agents in few minutes.},
keywords = {},
pubstate = {published},
tppubtype = {article} }

No data available.

http://dx.doi.org/10.1002/cpe.3969

\@article{CPE:CPE3969,
title = {Coalition structure generation problems: optimization and parallelization of the IDP algorithm in multicore systems},
author = {Cruz, Francisco and Espinosa, Antonio and Moure, Juan C. and Cerquides, Jesus and Rodriguez-Aguilar, Juan A. and Svensson, Kim and Ramchurn, Sarvapali D.},
url = {http://dx.doi.org/10.1002/cpe.3969},
doi = {10.1002/cpe.3969},
issn = {1532-0634},
year = {2017},
date = {2017-01-01},
journal = {Concurrency and Computation: Practice and Experience},
volume = {29},
number = {5},
pages = {e3969--n/a},
publisher = {John Wiley & Sons, Ltd},
note = {e3969 cpe.3969},
keywords = {},
pubstate = {published},
tppubtype = {article} }

Major natural or man-made disasters such as Hurricane Katrina or the 9/11 terror attacks pose significant challenges for emergency responders. First, they have to develop an understanding of the unfolding event either using their own resources or through third-parties such as the local population and agencies. Second, based on the information gathered, they need to deploy their teams in a flexible manner, ensuring that each team performs tasks in The most effective way. Third, given the dynamic nature of a disaster space, and the uncertainties involved in performing rescue missions, information about the disaster space and the actors within it needs to be managed to ensure that responders are always acting on up-to-date and trusted information. Against this background, this paper proposes a novel disaster response system called HAC-ER. Thus HAC-ER interweaves humans and agents, both robotic and software, in social relationships that augment their individual and collective capabilities. To design HAC-ER, we involved end-users including both experts and volunteers in a several participatory design workshops, lab studies, and field trials of increasingly advanced prototypes of individual components of HAC-ER as well as the overall system. This process generated a number of new quantitative and qualitative results but also raised a number of new research questions. HAC-ER thus demonstrates how such Human-Agent Collectives (HACs) can address key challenges in disaster response. Specifically, we show how HAC-ER utilises crowdsourcing combined with machine learning to obtain most important situational awareness from large streams of reports posted by members of the public and trusted organisations. We then show how this information can inform human-agent teams in coordinating multi-UAV deployments, as well as task planning for responders on the ground. Finally, HAC-ER incorporates an infrastructure and the associated intelligence for tracking and utilising the provenance of information shared across the entire system to ensure its accountability. We individually validate each of these elements of HAC-ER and show how they perform against standard (non-HAC) baselines and also elaborate on the evaluation of the overall system.

http://www.jair.org/media/5098/live-5098-9699-jair.pdf

@article{eps374070b,
title = {A Disaster Response System based on Human-Agent Collectives},
author = {Sarvapali Ramchurn and Edwin Simpson and Joel Fischer and Trung Dong Huynh and Yuki Ikuno and Steven Reece and Wenchao Jiang and Feng Wu and Jack Flann and S.J. Roberts and Luc Moreau and T. Rodden and N.R. Jennings},
url = {http://www.jair.org/media/5098/live-5098-9699-jair.pdf},
year = {2016},
date = {2016-12-01},
journal = {Journal of Artificial Intelligence Research},
volume = {57},
pages = {661-708},
abstract = {Major natural or man-made disasters such as Hurricane Katrina or the 9/11 terror attacks pose significant challenges for emergency responders. First, they have to develop an understanding of the unfolding event either using their own resources or through third-parties such as the local population and agencies. Second, based on the information gathered, they need to deploy their teams in a flexible manner, ensuring that each team performs tasks in The most effective way. Third, given the dynamic nature of a disaster space, and the uncertainties involved in performing rescue missions, information about the disaster space and the actors within it needs to be managed to ensure that responders are always acting on up-to-date and trusted information. Against this background, this paper proposes a novel disaster response system called HAC-ER. Thus HAC-ER interweaves humans and agents, both robotic and software, in social relationships that augment their individual and collective capabilities. To design HAC-ER, we involved end-users including both experts and volunteers in a several participatory design workshops, lab studies, and field trials of increasingly advanced prototypes of individual components of HAC-ER as well as the overall system. This process generated a number of new quantitative and qualitative results but also raised a number of new research questions. HAC-ER thus demonstrates how such Human-Agent Collectives (HACs) can address key challenges in disaster response. Specifically, we show how HAC-ER utilises crowdsourcing combined with machine learning to obtain most important situational awareness from large streams of reports posted by members of the public and trusted organisations. We then show how this information can inform human-agent teams in coordinating multi-UAV deployments, as well as task planning for responders on the ground. Finally, HAC-ER incorporates an infrastructure and the associated intelligence for tracking and utilising the provenance of information shared across the entire system to ensure its accountability. We individually validate each of these elements of HAC-ER and show how they perform against standard (non-HAC) baselines and also elaborate on the evaluation of the overall system.},
keywords = {},
pubstate = {published},
tppubtype = {article} }

Autonomous robotic systems can automatically perform actions on behalf of users in the domestic environment to help people in their daily activities. Such systems aim to reduce users' cognitive and physical workload, and improve wellbeing. While the benefits of these systems are clear, recent studies suggest that users may misconstrue their performance of tasks. We see an opportunity in designing interaction techniques that improve how users perceive the performance of such systems. We report two lab studies (N=16 each) designed to investigate whether showing physical motion, which is showing the process of a system through movement (that is intrinsic to the system's task), of an autonomous system as it completes its task, affects how users perceive its performance. To ensure our studies are ecologically valid and to motivate participants to provide thoughtful responses we adopted consensus-oriented financial incentives. Our results suggest that physical presence does yield higher performance ratings.

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

@inproceedings{eps398009,
title = {The potential of physical motion cues: changing people?s perception of robots? performance},
author = {Pedro Garcia Garcia and Enrico Costanza and Jhim Verame and Sarvapali D. Ramchurn},
url = {http://eprints.soton.ac.uk/398009/},
year = {2016},
date = {2016-09-01},
booktitle = {UbiComp 2016: The 2016 ACM International Joint Conference on Pervasive and Ubiquitous Computing},
publisher = {ACM},
abstract = {Autonomous robotic systems can automatically perform actions on behalf of users in the domestic environment to help people in their daily activities. Such systems aim to reduce users' cognitive and physical workload, and improve wellbeing. While the benefits of these systems are clear, recent studies suggest that users may misconstrue their performance of tasks. We see an opportunity in designing interaction techniques that improve how users perceive the performance of such systems. We report two lab studies (N=16 each) designed to investigate whether showing physical motion, which is showing the process of a system through movement (that is intrinsic to the system's task), of an autonomous system as it completes its task, affects how users perceive its performance. To ensure our studies are ecologically valid and to motivate participants to provide thoughtful responses we adopted consensus-oriented financial incentives. Our results suggest that physical presence does yield higher performance ratings.},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings} }

We address the problem of recommending an appliance usage schedule to the homeowner which balances between maximising total savings and maintaining sufficient user convenience. An important challenge within this problem is how to elicit the the user preferences with low intrusiveness, in order to identify new schedules with high cost savings, that still lies within the user?s comfort zone. To tackle this problem we propose iDR, an interactive system for generating personalised appliance usage scheduling recommendations that maximise savings and convenience with minimal intrusiveness. In particular, our system learns when to stop interacting with the user during the preference elicitation process, in order to keep the bother cost (e.g., the amount of time the user spends, or the cognitive cost of interacting) minimal. We demonstrate through extensive empirical evaluation on real?world data that our approach improves savings by up to 35%, while maintaining a significantly lower bother cost, compared to state-of the-art benchmarks

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

@inproceedings{eps396670,
title = {Interactive scheduling of appliance usage in the home},
author = {Ngoc Cuong Truong and Tim Baarslag and Sarvapali D. Ramchurn and Long Tran-Thanh},
url = {http://eprints.soton.ac.uk/396670/},
year = {2016},
date = {2016-07-12},
booktitle = {25th International Joint Conference on Artificial Intelligence (IJCAI-16)},
pages = {869--875},
abstract = {We address the problem of recommending an appliance usage schedule to the homeowner which balances between maximising total savings and maintaining sufficient user convenience. An important challenge within this problem is how to elicit the the user preferences with low intrusiveness, in order to identify new schedules with high cost savings, that still lies within the user?s comfort zone. To tackle this problem we propose iDR, an interactive system for generating personalised appliance usage scheduling recommendations that maximise savings and convenience with minimal intrusiveness. In particular, our system learns when to stop interacting with the user during the preference elicitation process, in order to keep the bother cost (e.g., the amount of time the user spends, or the cognitive cost of interacting) minimal. We demonstrate through extensive empirical evaluation on real?world data that our approach improves savings by up to 35%, while maintaining a significantly lower bother cost, compared to state-of the-art benchmarks},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings} }

The coordination of multiple Unmanned Aerial Vehicles (UAVs) to carry out aerial surveys is a major challenge for emergency responders. In particular, UAVs have to fly over kilometre-scale areas while trying to discover casualties as quickly as possible. To aid in this process, it is desirable to exploit the increasing availability of data about a disaster from sources such as crowd reports, satellite re- mote sensing, or manned reconnaissance. In particular, such information can be a valuable resource to drive the planning of UAV flight paths over a space in order to discover people who are in danger. However challenges of computational tractability remain when planning over the very large action spaces that result. To overcome these, we introduce the survivor discovery problem and present as our solution, the first example of a continuous factored coordinated Monte Carlo tree search algorithm. Our evaluation against state of the art benchmarks show that our algorithm, Co-CMCTS, is able to localise more casualties faster than standard approaches by 7% or more on simulations with real-world data.

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

@inproceedings{eps396996,
title = {Planning search and rescue missions for UAV teams},
author = {Chris Baker and Sarvapali D. Ramchurn and Luke Teacy and Nicholas Jennings},
url = {http://eprints.soton.ac.uk/396996/},
year = {2016},
date = {2016-06-01},
booktitle = {PAIS 2016: Conference on Prestigious Applications of Intelligent Systems at ECAI 2016},
abstract = {The coordination of multiple Unmanned Aerial Vehicles (UAVs) to carry out aerial surveys is a major challenge for emergency responders. In particular, UAVs have to fly over kilometre-scale areas while trying to discover casualties as quickly as possible. To aid in this process, it is desirable to exploit the increasing availability of data about a disaster from sources such as crowd reports, satellite re- mote sensing, or manned reconnaissance. In particular, such information can be a valuable resource to drive the planning of UAV flight paths over a space in order to discover people who are in danger. However challenges of computational tractability remain when planning over the very large action spaces that result. To overcome these, we introduce the survivor discovery problem and present as our solution, the first example of a continuous factored coordinated Monte Carlo tree search algorithm. Our evaluation against state of the art benchmarks show that our algorithm, Co-CMCTS, is able to localise more casualties faster than standard approaches by 7% or more on simulations with real-world data.},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings} }

No data available.

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

@inproceedings{eps385056,
title = {"Just whack it on until it gets hot, then turn it off": Working with IoT Data in the Home},
author = {Joel Fisher and Andy Crabtree and Tom Rodden and James Colley and Enrico Costanza and Michael Jewell and Sarvapali Ramchurn},
url = {http://eprints.soton.ac.uk/385056/},
year = {2016},
date = {2016-05-01},
booktitle = {The SIGCHI Conference on Human Factors in Computing Systems},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings} }

We study a general task allocation problem, involving multiple agents that collaboratively accomplish tasks and where agents may fail to successfully complete the tasks assigned to them (known as execution uncertainty). The goal is to choose an allocation that maximises social welfare while taking their execution uncertainty into account (i.e., fault tolerant). To achieve this, we show that the post-execution verification (PEV)-based mechanism presented by Porter et al. (2008) is applicable if and only if agents' valuations are risk-neutral (i.e., the solution is almost universal). We then consider a more advanced setting where an agent's execution uncertainty is not completely predictable by the agent alone but aggregated from all agents' private opinions (known as trust). We show that PEV-based mechanism with trust is still applicable if and only if the trust aggregation is multilinear. Given this characterisation, we further demonstrate how this mechanism can be successfully applied in a real-world setting. Finally, we draw the parallels between our results and the literature of efficient mechanism design with general interdependent valuations.

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

@inproceedings{eps388365, title = {Fault tolerant mechanism design for general task allocation},
author = {Dengji Zhao and Sarvapali D. Ramchurn and Nicholas Jennings},
url = {http://eprints.soton.ac.uk/388365/},
year = {2016},
date = {2016-05-01},
booktitle = {The 15th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2016)},
publisher = {International Foundation for Autonomous Agents and Multiagent Systems},
abstract = {We study a general task allocation problem, involving multiple agents that collaboratively accomplish tasks and where agents may fail to successfully complete the tasks assigned to them (known as execution uncertainty). The goal is to choose an allocation that maximises social welfare while taking their execution uncertainty into account (i.e., fault tolerant). To achieve this, we show that the post-execution verification (PEV)-based mechanism presented by Porter et al. (2008) is applicable if and only if agents' valuations are risk-neutral (i.e., the solution is almost universal). We then consider a more advanced setting where an agent's execution uncertainty is not completely predictable by the agent alone but aggregated from all agents' private opinions (known as trust). We show that PEV-based mechanism with trust is still applicable if and only if the trust aggregation is multilinear. Given this characterisation, we further demonstrate how this mechanism can be successfully applied in a real-world setting. Finally, we draw the parallels between our results and the literature of efficient mechanism design with general interdependent valuations.},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings} }