Gopal
Gopal
Gopal
Gopal
Gopal
Gopal
Gopal
Gopal
Gopal
Gopal
font
Filter
×
2017
Bistaffa, Jesús Cerquides Alessandro Farinelli Filippo; Ramchurn, Sarvapali D.
Algorithms for Graph-Constrained Coalition Formation in the Real World Journal Article
In: ACM Transactions on Intelligent Systems and Technology (TIST), vol. 8, no. 4, 2017.
Links | BibTeX | Tags: Coalition Formation, Ridesharing
@article{bistaffaetal2017b,
title = {Algorithms for Graph-Constrained Coalition Formation in the Real World},
author = {Jesús Cerquides Alessandro Farinelli Filippo Bistaffa and Sarvapali D. Ramchurn},
url = {https://www.sramchurn.com/wp-content/uploads/2017/03/2017tist.pdf},
doi = {http://dx.doi.org/10.1145/3040967},
year = {2017},
date = {2017-02-11},
journal = {ACM Transactions on Intelligent Systems and Technology (TIST)},
volume = {8},
number = {4},
keywords = {Coalition Formation, Ridesharing},
pubstate = {published},
tppubtype = {article}
}
Chalkiadakis, Sarvapali Alessandro Farinelli; Ramchurn Filippo Bistaffa Georgios
A Cooperative Game-Theoretic Approach to the Social Ridesharing Problem Journal Article
In: Artificial Intelligence Journal, pp. (accepted), 2017.
Links | BibTeX | Tags: Coalition Formation, Ridesharing
@article{bistaffa:etal:2017b,
title = {A Cooperative Game-Theoretic Approach to the Social Ridesharing Problem},
author = {Sarvapali Alessandro Farinelli; Ramchurn Filippo Bistaffa Georgios Chalkiadakis},
url = {http://www.sciencedirect.com/science/article/pii/S0004370217300243},
year = {2017},
date = {2017-02-11},
journal = {Artificial Intelligence Journal},
pages = {(accepted)},
keywords = {Coalition Formation, Ridesharing},
pubstate = {published},
tppubtype = {article}
}
Farinelli, Alessandro; Bicego, Manuele; Bistaffa, Filippo; Ramchurn, Sarvapali D.
A Hierarchical Clustering Approach to Large-scale Near-optimal Coalition Formation with Quality Guarantees Journal Article
In: Engineering Applications of Artificial Intelligence (EAAI), vol. 57, pp. 170-185, 2017.
Abstract | Links | BibTeX | Tags: Coalition Formation, Energy
@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 = {Coalition Formation, Energy},
pubstate = {published},
tppubtype = {article}
}
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.
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.
Cruz, Francisco; Espinosa, Antonio; Moure, Juan C.; Cerquides, Jesus; Rodriguez-Aguilar, Juan A.; Svensson, Kim; Ramchurn, Sarvapali D.
Coalition structure generation problems: optimization and parallelization of the IDP algorithm in multicore systems Journal Article
In: Concurrency and Computation: Practice and Experience, vol. 29, no. 5, pp. e3969–n/a, 2017, ISSN: 1532-0634, (e3969 cpe.3969).
Links | BibTeX | Tags: Coalition Formation, dynamic programming, multi agent systems, multi-core systems, set partitioning problem
@article{CPE:CPE3969,
title = {Coalition structure generation problems: optimization and parallelization of the IDP algorithm in multicore systems},
author = {Francisco Cruz and Antonio Espinosa and Juan C. Moure and Jesus Cerquides and Juan A. Rodriguez-Aguilar and Kim Svensson and Sarvapali D. Ramchurn},
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 = {Coalition Formation, dynamic programming, multi agent systems, multi-core systems, set partitioning problem},
pubstate = {published},
tppubtype = {article}
}
2015
Bistaffa, Alessandro Farinelli Georgios Chalkiadakis Filippo; Ramchurn, Sarvapali D.
Recommending Fair Payments for Large-Scale Social Ridesharing Proceedings Article
In: ACM Conference on Recommender Systems (Recsys), 2015.
Links | BibTeX | Tags: Coalition Formation, mas, Ridesharing
@inproceedings{bistaffaetal2015,
title = {Recommending Fair Payments for Large-Scale Social Ridesharing},
author = {Alessandro Farinelli Georgios Chalkiadakis Filippo Bistaffa and Sarvapali D. Ramchurn},
url = {https://www.sramchurn.com/wp-content/uploads/2017/02/2015recsys.pdf},
year = {2015},
date = {2015-09-16},
booktitle = {ACM Conference on Recommender Systems (Recsys)},
keywords = {Coalition Formation, mas, Ridesharing},
pubstate = {published},
tppubtype = {inproceedings}
}
Bistaffa, Sarvapali D. Ramchurn Alessandro Farinelli Filippo
Sharing Rides with Friends: a Coalition Formation Algorithm for Ridesharing Proceedings Article
In: Proceedings of the AAAI Conference, 2015.
Abstract | Links | BibTeX | Tags: Coalition Formation, optimisation, Ridesharing, Social Networks
@inproceedings{bistaffa:etal:2015,
title = {Sharing Rides with Friends: a Coalition Formation Algorithm for Ridesharing},
author = {Sarvapali D. Ramchurn Alessandro Farinelli Filippo Bistaffa},
url = {http://eprints.soton.ac.uk/372048/},
year = {2015},
date = {2015-01-25},
booktitle = {Proceedings of the AAAI Conference},
abstract = {We consider the Social Ridesharing (SR) problem, where a set of commuters, connected through a social network, ar- range one-time rides at a very short notice. In particular, we focus on the associated optimisation problem of forming cars to minimise the travel cost of the overall system mod- elling such problem as a graph constrained coalition forma- tion (GCCF) problem, where the set of feasible coalitions is restricted by a graph (i.e., the social network). Moreover, we significantly extend the state of the art algorithm for GCCF, i.e., the CFSS algorithm, to solve our GCCF model of the SR problem. Our empirical evaluation uses a real dataset for both spatial (GeoLife) and social data (Twitter), to validate the ap- plicability of our approach in a realistic application scenario. Empirical results show that our approach computes optimal solutions for systems of medium scale (up to 100 agents) providing significant cost reductions (up to −36.22%). More- over, we can provide approximate solutions for very large systems (i.e., up to 2000 agents) and good quality guarantees (i.e., with an approximation ratio of 1.41 in the worst case) within minutes (i.e., 100 seconds).},
keywords = {Coalition Formation, optimisation, Ridesharing, Social Networks},
pubstate = {published},
tppubtype = {inproceedings}
}
We consider the Social Ridesharing (SR) problem, where a set of commuters, connected through a social network, ar- range one-time rides at a very short notice. In particular, we focus on the associated optimisation problem of forming cars to minimise the travel cost of the overall system mod- elling such problem as a graph constrained coalition forma- tion (GCCF) problem, where the set of feasible coalitions is restricted by a graph (i.e., the social network). Moreover, we significantly extend the state of the art algorithm for GCCF, i.e., the CFSS algorithm, to solve our GCCF model of the SR problem. Our empirical evaluation uses a real dataset for both spatial (GeoLife) and social data (Twitter), to validate the ap- plicability of our approach in a realistic application scenario. Empirical results show that our approach computes optimal solutions for systems of medium scale (up to 100 agents) providing significant cost reductions (up to −36.22%). More- over, we can provide approximate solutions for very large systems (i.e., up to 2000 agents) and good quality guarantees (i.e., with an approximation ratio of 1.41 in the worst case) within minutes (i.e., 100 seconds).
2014
Bistaffa, Filippo; Farinelli, Alessandro; Cerquides, Jesus; Rodriguez-Aguilar, Juan Antonio; Ramchurn, Sarvapali D
Anytime Coalition Structure Generation on Synergy Graphs Proceedings Article
In: 13th Int. Conf. on Autonomous Agents and Multi-Agent Systems, pp. 13-20, 2014.
Abstract | Links | BibTeX | Tags: Coalition Formation, Coordination
@inproceedings{orchid175,
title = {Anytime Coalition Structure Generation on Synergy Graphs},
author = {Filippo Bistaffa and Alessandro Farinelli and Jesus Cerquides and Juan Antonio Rodriguez-Aguilar and Sarvapali D Ramchurn},
url = {http://aamas2014.lip6.fr/proceedings/aamas/p13.pdf},
year = {2014},
date = {2014-01-01},
booktitle = {13th Int. Conf. on Autonomous Agents and Multi-Agent Systems},
pages = {13-20},
abstract = {We consider the coalition structure generation (CSG) problem on
synergy graphs, which arises in many practical applications where
communication constraints, social or trust relationships must be
taken into account when forming coalitions. We propose a novel
representation of this problem based on the concept of edge contraction,
and an innovative branch and bound approach (CFSS),
which is particularly efficient when applied to a general class of
characteristic functions. This new model provides a non-redundant
partition of the search space, hence allowing an effective parallelisation.
We evaluate CFSS on two benchmark functions, the edge
sum with coordination cost and the collective energy purchasing
functions, comparing its performance with the best algorithm for
CSG on synergy graphs: DyCE. The latter approach is centralised
and cannot be efficiently parallelised due to the exponential memory
requirements in the number of agents, which limits its scalability
(while CFSS memory requirements are only polynomial).
Our results show that, when the graphs are very sparse, CFSS is
4 orders of magnitude faster than DyCE. Moreover, CFSS is the
first approach to provide anytime approximate solutions with quality
guarantees for very large systems (i.e., with more than 2700
agents).},
keywords = {Coalition Formation, Coordination},
pubstate = {published},
tppubtype = {inproceedings}
}
We consider the coalition structure generation (CSG) problem on
synergy graphs, which arises in many practical applications where
communication constraints, social or trust relationships must be
taken into account when forming coalitions. We propose a novel
representation of this problem based on the concept of edge contraction,
and an innovative branch and bound approach (CFSS),
which is particularly efficient when applied to a general class of
characteristic functions. This new model provides a non-redundant
partition of the search space, hence allowing an effective parallelisation.
We evaluate CFSS on two benchmark functions, the edge
sum with coordination cost and the collective energy purchasing
functions, comparing its performance with the best algorithm for
CSG on synergy graphs: DyCE. The latter approach is centralised
and cannot be efficiently parallelised due to the exponential memory
requirements in the number of agents, which limits its scalability
(while CFSS memory requirements are only polynomial).
Our results show that, when the graphs are very sparse, CFSS is
4 orders of magnitude faster than DyCE. Moreover, CFSS is the
first approach to provide anytime approximate solutions with quality
guarantees for very large systems (i.e., with more than 2700
agents).
synergy graphs, which arises in many practical applications where
communication constraints, social or trust relationships must be
taken into account when forming coalitions. We propose a novel
representation of this problem based on the concept of edge contraction,
and an innovative branch and bound approach (CFSS),
which is particularly efficient when applied to a general class of
characteristic functions. This new model provides a non-redundant
partition of the search space, hence allowing an effective parallelisation.
We evaluate CFSS on two benchmark functions, the edge
sum with coordination cost and the collective energy purchasing
functions, comparing its performance with the best algorithm for
CSG on synergy graphs: DyCE. The latter approach is centralised
and cannot be efficiently parallelised due to the exponential memory
requirements in the number of agents, which limits its scalability
(while CFSS memory requirements are only polynomial).
Our results show that, when the graphs are very sparse, CFSS is
4 orders of magnitude faster than DyCE. Moreover, CFSS is the
first approach to provide anytime approximate solutions with quality
guarantees for very large systems (i.e., with more than 2700
agents).
2013
Svensson, Kim; Ramchurn, Sarvapali; Cruz, Francisco; Rodriguez-Aguilar, Juan-Antonio; Cerquides, Jesus
Solving the coalition structure generation problem on a GPU Proceedings Article
In: 6th International Workshop on Optimisation in Multi-Agent Systems, 2013.
Abstract | Links | BibTeX | Tags: Coalition Formation, mas, Multi-agent scheduling
@inproceedings{eps352204,
title = {Solving the coalition structure generation problem on a GPU},
author = {Kim Svensson and Sarvapali Ramchurn and Francisco Cruz and Juan-Antonio Rodriguez-Aguilar and Jesus Cerquides},
url = {http://eprints.soton.ac.uk/352204/},
year = {2013},
date = {2013-01-01},
booktitle = {6th International Workshop on Optimisation in Multi-Agent Systems},
abstract = {We develop the first parallel algorithm for Coalition Structure Generation (CSG), which is central to many multi-agent systems applications. Our approach involves distributing the key steps of a dynamic programming approach to CSG across computational nodes on a Graphics Processing Unit (GPU) such that each of the thousands of threads of computation can be used to perform small computations that speed up the overall process. In so doing, we solve important challenges that arise in solving combinatorial optimisation problems on GPUs such as the efficient allocation of memory and computational threads to every step of the algorithm. In our empirical evaluations on a standard GPU, our results show an improvement of orders of magnitude over current dynamic programming approaches with an ever increasing divergence between the CPU and GPU-based algorithms in terms of growth. Thus, our algorithm is able to solve the CSG problem for 29 agents in one hour and thirty minutes as opposed to three days for the current state of the art dynamic programming algorithms.},
keywords = {Coalition Formation, mas, Multi-agent scheduling},
pubstate = {published},
tppubtype = {inproceedings}
}
We develop the first parallel algorithm for Coalition Structure Generation (CSG), which is central to many multi-agent systems applications. Our approach involves distributing the key steps of a dynamic programming approach to CSG across computational nodes on a Graphics Processing Unit (GPU) such that each of the thousands of threads of computation can be used to perform small computations that speed up the overall process. In so doing, we solve important challenges that arise in solving combinatorial optimisation problems on GPUs such as the efficient allocation of memory and computational threads to every step of the algorithm. In our empirical evaluations on a standard GPU, our results show an improvement of orders of magnitude over current dynamic programming approaches with an ever increasing divergence between the CPU and GPU-based algorithms in terms of growth. Thus, our algorithm is able to solve the CSG problem for 29 agents in one hour and thirty minutes as opposed to three days for the current state of the art dynamic programming algorithms.
2010
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).
Abstract | Links | BibTeX | Tags: agents, Coalition Formation, Disaster Management, Multi-agent scheduling, RoboCup Rescue
@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 = {agents, Coalition Formation, Disaster Management, Multi-agent scheduling, RoboCup Rescue},
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.
2009
Rahwan, Talal; Ramchurn, Sarvapali; Jennings, Nicholas; Giovannucci, Andrea
An anytime algorithm for optimal coalition structure generation Journal Article
In: Journal of Artificial Intelligence Research, vol. 34, pp. 521–567, 2009.
Abstract | Links | BibTeX | Tags: Coalition Formation, multi-agent systems
@article{eps267179,
title = {An anytime algorithm for optimal coalition structure generation},
author = {Talal Rahwan and Sarvapali Ramchurn and Nicholas Jennings and Andrea Giovannucci},
url = {http://eprints.soton.ac.uk/267179/},
year = {2009},
date = {2009-01-01},
journal = {Journal of Artificial Intelligence Research},
volume = {34},
pages = {521–567},
abstract = {Coalition formation is a fundamental type of interaction that involves the creation of coherent groupings of distinct, autonomous, agents in order to efficiently achieve their individual or collective goals. Forming effective coalitions is a major research challenge in the field of multi-agent systems. Central to this endeavour is the problem of determining which of the many possible coalitions to form in order to achieve some goal. This usually requires calculating a value for every possible coalition, known as the coalition value, which indicates how beneficial that coalition would be if it was formed. Once these values are calculated, the agents usually need to find a combination of coalitions, in which every agent belongs to exactly one coalition, and by which the overall outcome of the system is maximized. However, this coalition structure generation problem is extremely challenging due to the number of possible solutions that need to be examined, which grows exponentially with the number of agents involved. To date, therefore, many algorithms have been proposed to solve this problem using different techniques–ranging from dynamic programming, to integer programming, to stochastic search – all of which suffer from major limitations relating to execution time, solution quality, and memory requirements. With this in mind, we develop an anytime algorithm to solve the coalition structure generation problem. Specifically, the algorithm uses a novel representation of the search space, which partitions the space of possible solutions into sub-spaces such that it is possible to compute upper and lower bounds on the values of the best coalition structures in them. These bounds are then used to identify the sub-spaces that have no potential of containing the optimal solution so that they can be pruned. The algorithm, then, searches through the remaining sub-spaces very efficiently using a branch-and-bound technique to avoid examining all the solutions within the searched subspace(s). In this setting, we prove that our algorithm enumerates all coalition structures efficiently by avoiding redundant and invalid solutions automatically. Moreover, in order to effectively test our algorithm we develop a new type of input distribution which allows us to generate more reliable benchmarks compared to the input distributions previously used in the field. Given this new distribution, we show that for 27 agents our algorithm is able to find solutions that are optimal in 0:175% of the time required by the fastest available algorithm in the literature. The algorithm is anytime, and if interrupted before it would have normally terminated, it can still provide a solution that is guaranteed to be within a bound from the optimal one. Moreover, the guarantees we provide on the quality of the solution are significantly better than those provided by the previous state of the art algorithms designed for this purpose. For example, for the worst case distribution given 25 agents, our algorithm is able to find a 90% efficient solution in around 10% of time it takes to find the optimal solution.},
keywords = {Coalition Formation, multi-agent systems},
pubstate = {published},
tppubtype = {article}
}
Coalition formation is a fundamental type of interaction that involves the creation of coherent groupings of distinct, autonomous, agents in order to efficiently achieve their individual or collective goals. Forming effective coalitions is a major research challenge in the field of multi-agent systems. Central to this endeavour is the problem of determining which of the many possible coalitions to form in order to achieve some goal. This usually requires calculating a value for every possible coalition, known as the coalition value, which indicates how beneficial that coalition would be if it was formed. Once these values are calculated, the agents usually need to find a combination of coalitions, in which every agent belongs to exactly one coalition, and by which the overall outcome of the system is maximized. However, this coalition structure generation problem is extremely challenging due to the number of possible solutions that need to be examined, which grows exponentially with the number of agents involved. To date, therefore, many algorithms have been proposed to solve this problem using different techniques–ranging from dynamic programming, to integer programming, to stochastic search – all of which suffer from major limitations relating to execution time, solution quality, and memory requirements. With this in mind, we develop an anytime algorithm to solve the coalition structure generation problem. Specifically, the algorithm uses a novel representation of the search space, which partitions the space of possible solutions into sub-spaces such that it is possible to compute upper and lower bounds on the values of the best coalition structures in them. These bounds are then used to identify the sub-spaces that have no potential of containing the optimal solution so that they can be pruned. The algorithm, then, searches through the remaining sub-spaces very efficiently using a branch-and-bound technique to avoid examining all the solutions within the searched subspace(s). In this setting, we prove that our algorithm enumerates all coalition structures efficiently by avoiding redundant and invalid solutions automatically. Moreover, in order to effectively test our algorithm we develop a new type of input distribution which allows us to generate more reliable benchmarks compared to the input distributions previously used in the field. Given this new distribution, we show that for 27 agents our algorithm is able to find solutions that are optimal in 0:175% of the time required by the fastest available algorithm in the literature. The algorithm is anytime, and if interrupted before it would have normally terminated, it can still provide a solution that is guaranteed to be within a bound from the optimal one. Moreover, the guarantees we provide on the quality of the solution are significantly better than those provided by the previous state of the art algorithms designed for this purpose. For example, for the worst case distribution given 25 agents, our algorithm is able to find a 90% efficient solution in around 10% of time it takes to find the optimal solution.
2007
Rahwan, Talal; Ramchurn, Sarvapali D.; Dang, Viet D.; Giovannucci, Andrea; Jennings, N. R.
Anytime Optimal Coalition Structure Generation Proceedings Article
In: 22nd Conference on Artificial Intelligence (AAAI), pp. 1184–1190, 2007.
Abstract | Links | BibTeX | Tags: Coalition Formation, Coalition Structure Generation, Combinatorial, multi-agent systems, Search, Set Partitioning
@inproceedings{eps263433,
title = {Anytime Optimal Coalition Structure Generation},
author = {Talal Rahwan and Sarvapali D. Ramchurn and Viet D. Dang and Andrea Giovannucci and N. R. Jennings},
url = {http://eprints.soton.ac.uk/263433/},
year = {2007},
date = {2007-01-01},
booktitle = {22nd Conference on Artificial Intelligence (AAAI)},
pages = {1184–1190},
abstract = {Forming effective coalitions is a major research challenge in the field of multi-agent systems. Central to this endeavour is the problem of determining the best groups of agents to select to achieve some goal. To this end, in this paper, we present a novel, optimal anytime algorithm for this coalition structure generation problem that is significantly faster than previous algorithms designed for this purpose. Specifically, our algorithm can generate solutions by partitioning the space of all potential coalitions into sub-spaces that contain coalition structures that are similar, according to some criterion, such that these sub-spaces can be pruned by identifying their bounds. Using this representation, the algorithm then searches through only valid and unique coalition structures and selects the best among them using a branch-and-bound technique. We empirically show that we are able to find solutions that are optimal in 0.082% of the time taken by the state of the art dynamic programming algorithm (for 27 agents) using much less memory (O(2^ n) instead of O(3^ n) for the set of n agents). Moreover, our algorithm is the first to be able to solve the coalition structure generation problem for numbers of agents bigger than 27 in reasonable time (less than 90 minutes for 27 agents as opposed to around 2 months for the best previous solution).},
keywords = {Coalition Formation, Coalition Structure Generation, Combinatorial, multi-agent systems, Search, Set Partitioning},
pubstate = {published},
tppubtype = {inproceedings}
}
Forming effective coalitions is a major research challenge in the field of multi-agent systems. Central to this endeavour is the problem of determining the best groups of agents to select to achieve some goal. To this end, in this paper, we present a novel, optimal anytime algorithm for this coalition structure generation problem that is significantly faster than previous algorithms designed for this purpose. Specifically, our algorithm can generate solutions by partitioning the space of all potential coalitions into sub-spaces that contain coalition structures that are similar, according to some criterion, such that these sub-spaces can be pruned by identifying their bounds. Using this representation, the algorithm then searches through only valid and unique coalition structures and selects the best among them using a branch-and-bound technique. We empirically show that we are able to find solutions that are optimal in 0.082% of the time taken by the state of the art dynamic programming algorithm (for 27 agents) using much less memory (O(2^ n) instead of O(3^ n) for the set of n agents). Moreover, our algorithm is the first to be able to solve the coalition structure generation problem for numbers of agents bigger than 27 in reasonable time (less than 90 minutes for 27 agents as opposed to around 2 months for the best previous solution).
0000
Bistaffa, Jesús Cerquides Alessandro Farinelli Filippo; Ramchurn, Sarvapali D.
Algorithms for Graph-Constrained Coalition Formation in the Real World Journal Article
In: ACM Transactions on Intelligent Systems and Technology (TIST), vol. 8, no. 4, 0000.
Links | BibTeX | Tags: Coalition Formation, Ridesharing
@article{bistaffaetal2017,
title = {Algorithms for Graph-Constrained Coalition Formation in the Real World},
author = {Jesús Cerquides Alessandro Farinelli Filippo Bistaffa and Sarvapali D. Ramchurn},
doi = {http://dx.doi.org/10.1145/3040967},
journal = {ACM Transactions on Intelligent Systems and Technology (TIST)},
volume = {8},
number = {4},
keywords = {Coalition Formation, Ridesharing},
pubstate = {published},
tppubtype = {article}
}
1.
Bistaffa, Jesús Cerquides Alessandro Farinelli Filippo; Ramchurn, Sarvapali D.
Algorithms for Graph-Constrained Coalition Formation in the Real World Journal Article
In: ACM Transactions on Intelligent Systems and Technology (TIST), vol. 8, no. 4, 2017.
@article{bistaffaetal2017b,
title = {Algorithms for Graph-Constrained Coalition Formation in the Real World},
author = {Jesús Cerquides Alessandro Farinelli Filippo Bistaffa and Sarvapali D. Ramchurn},
url = {https://www.sramchurn.com/wp-content/uploads/2017/03/2017tist.pdf},
doi = {http://dx.doi.org/10.1145/3040967},
year = {2017},
date = {2017-02-11},
journal = {ACM Transactions on Intelligent Systems and Technology (TIST)},
volume = {8},
number = {4},
keywords = {},
pubstate = {published},
tppubtype = {article}
}
2.
Chalkiadakis, Sarvapali Alessandro Farinelli; Ramchurn Filippo Bistaffa Georgios
A Cooperative Game-Theoretic Approach to the Social Ridesharing Problem Journal Article
In: Artificial Intelligence Journal, pp. (accepted), 2017.
@article{bistaffa:etal:2017b,
title = {A Cooperative Game-Theoretic Approach to the Social Ridesharing Problem},
author = {Sarvapali Alessandro Farinelli; Ramchurn Filippo Bistaffa Georgios Chalkiadakis},
url = {http://www.sciencedirect.com/science/article/pii/S0004370217300243},
year = {2017},
date = {2017-02-11},
journal = {Artificial Intelligence Journal},
pages = {(accepted)},
keywords = {},
pubstate = {published},
tppubtype = {article}
}
3.
Farinelli, Alessandro; Bicego, Manuele; Bistaffa, Filippo; Ramchurn, Sarvapali D.
A Hierarchical Clustering Approach to Large-scale Near-optimal Coalition Formation with Quality Guarantees Journal Article
In: Engineering Applications of Artificial Intelligence (EAAI), vol. 57, pp. 170-185, 2017.
@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}
}
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.
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.
4.
Cruz, Francisco; Espinosa, Antonio; Moure, Juan C.; Cerquides, Jesus; Rodriguez-Aguilar, Juan A.; Svensson, Kim; Ramchurn, Sarvapali D.
Coalition structure generation problems: optimization and parallelization of the IDP algorithm in multicore systems Journal Article
In: Concurrency and Computation: Practice and Experience, vol. 29, no. 5, pp. e3969–n/a, 2017, ISSN: 1532-0634, (e3969 cpe.3969).
@article{CPE:CPE3969,
title = {Coalition structure generation problems: optimization and parallelization of the IDP algorithm in multicore systems},
author = {Francisco Cruz and Antonio Espinosa and Juan C. Moure and Jesus Cerquides and Juan A. Rodriguez-Aguilar and Kim Svensson and Sarvapali D. Ramchurn},
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}
}
5.
Bistaffa, Alessandro Farinelli Georgios Chalkiadakis Filippo; Ramchurn, Sarvapali D.
Recommending Fair Payments for Large-Scale Social Ridesharing Proceedings Article
In: ACM Conference on Recommender Systems (Recsys), 2015.
@inproceedings{bistaffaetal2015,
title = {Recommending Fair Payments for Large-Scale Social Ridesharing},
author = {Alessandro Farinelli Georgios Chalkiadakis Filippo Bistaffa and Sarvapali D. Ramchurn},
url = {https://www.sramchurn.com/wp-content/uploads/2017/02/2015recsys.pdf},
year = {2015},
date = {2015-09-16},
booktitle = {ACM Conference on Recommender Systems (Recsys)},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
6.
Bistaffa, Sarvapali D. Ramchurn Alessandro Farinelli Filippo
Sharing Rides with Friends: a Coalition Formation Algorithm for Ridesharing Proceedings Article
In: Proceedings of the AAAI Conference, 2015.
@inproceedings{bistaffa:etal:2015,
title = {Sharing Rides with Friends: a Coalition Formation Algorithm for Ridesharing},
author = {Sarvapali D. Ramchurn Alessandro Farinelli Filippo Bistaffa},
url = {http://eprints.soton.ac.uk/372048/},
year = {2015},
date = {2015-01-25},
booktitle = {Proceedings of the AAAI Conference},
abstract = {We consider the Social Ridesharing (SR) problem, where a set of commuters, connected through a social network, ar- range one-time rides at a very short notice. In particular, we focus on the associated optimisation problem of forming cars to minimise the travel cost of the overall system mod- elling such problem as a graph constrained coalition forma- tion (GCCF) problem, where the set of feasible coalitions is restricted by a graph (i.e., the social network). Moreover, we significantly extend the state of the art algorithm for GCCF, i.e., the CFSS algorithm, to solve our GCCF model of the SR problem. Our empirical evaluation uses a real dataset for both spatial (GeoLife) and social data (Twitter), to validate the ap- plicability of our approach in a realistic application scenario. Empirical results show that our approach computes optimal solutions for systems of medium scale (up to 100 agents) providing significant cost reductions (up to −36.22%). More- over, we can provide approximate solutions for very large systems (i.e., up to 2000 agents) and good quality guarantees (i.e., with an approximation ratio of 1.41 in the worst case) within minutes (i.e., 100 seconds).},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
We consider the Social Ridesharing (SR) problem, where a set of commuters, connected through a social network, ar- range one-time rides at a very short notice. In particular, we focus on the associated optimisation problem of forming cars to minimise the travel cost of the overall system mod- elling such problem as a graph constrained coalition forma- tion (GCCF) problem, where the set of feasible coalitions is restricted by a graph (i.e., the social network). Moreover, we significantly extend the state of the art algorithm for GCCF, i.e., the CFSS algorithm, to solve our GCCF model of the SR problem. Our empirical evaluation uses a real dataset for both spatial (GeoLife) and social data (Twitter), to validate the ap- plicability of our approach in a realistic application scenario. Empirical results show that our approach computes optimal solutions for systems of medium scale (up to 100 agents) providing significant cost reductions (up to −36.22%). More- over, we can provide approximate solutions for very large systems (i.e., up to 2000 agents) and good quality guarantees (i.e., with an approximation ratio of 1.41 in the worst case) within minutes (i.e., 100 seconds).
7.
Bistaffa, Filippo; Farinelli, Alessandro; Cerquides, Jesus; Rodriguez-Aguilar, Juan Antonio; Ramchurn, Sarvapali D
Anytime Coalition Structure Generation on Synergy Graphs Proceedings Article
In: 13th Int. Conf. on Autonomous Agents and Multi-Agent Systems, pp. 13-20, 2014.
@inproceedings{orchid175,
title = {Anytime Coalition Structure Generation on Synergy Graphs},
author = {Filippo Bistaffa and Alessandro Farinelli and Jesus Cerquides and Juan Antonio Rodriguez-Aguilar and Sarvapali D Ramchurn},
url = {http://aamas2014.lip6.fr/proceedings/aamas/p13.pdf},
year = {2014},
date = {2014-01-01},
booktitle = {13th Int. Conf. on Autonomous Agents and Multi-Agent Systems},
pages = {13-20},
abstract = {We consider the coalition structure generation (CSG) problem on
synergy graphs, which arises in many practical applications where
communication constraints, social or trust relationships must be
taken into account when forming coalitions. We propose a novel
representation of this problem based on the concept of edge contraction,
and an innovative branch and bound approach (CFSS),
which is particularly efficient when applied to a general class of
characteristic functions. This new model provides a non-redundant
partition of the search space, hence allowing an effective parallelisation.
We evaluate CFSS on two benchmark functions, the edge
sum with coordination cost and the collective energy purchasing
functions, comparing its performance with the best algorithm for
CSG on synergy graphs: DyCE. The latter approach is centralised
and cannot be efficiently parallelised due to the exponential memory
requirements in the number of agents, which limits its scalability
(while CFSS memory requirements are only polynomial).
Our results show that, when the graphs are very sparse, CFSS is
4 orders of magnitude faster than DyCE. Moreover, CFSS is the
first approach to provide anytime approximate solutions with quality
guarantees for very large systems (i.e., with more than 2700
agents).},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
We consider the coalition structure generation (CSG) problem on
synergy graphs, which arises in many practical applications where
communication constraints, social or trust relationships must be
taken into account when forming coalitions. We propose a novel
representation of this problem based on the concept of edge contraction,
and an innovative branch and bound approach (CFSS),
which is particularly efficient when applied to a general class of
characteristic functions. This new model provides a non-redundant
partition of the search space, hence allowing an effective parallelisation.
We evaluate CFSS on two benchmark functions, the edge
sum with coordination cost and the collective energy purchasing
functions, comparing its performance with the best algorithm for
CSG on synergy graphs: DyCE. The latter approach is centralised
and cannot be efficiently parallelised due to the exponential memory
requirements in the number of agents, which limits its scalability
(while CFSS memory requirements are only polynomial).
Our results show that, when the graphs are very sparse, CFSS is
4 orders of magnitude faster than DyCE. Moreover, CFSS is the
first approach to provide anytime approximate solutions with quality
guarantees for very large systems (i.e., with more than 2700
agents).
synergy graphs, which arises in many practical applications where
communication constraints, social or trust relationships must be
taken into account when forming coalitions. We propose a novel
representation of this problem based on the concept of edge contraction,
and an innovative branch and bound approach (CFSS),
which is particularly efficient when applied to a general class of
characteristic functions. This new model provides a non-redundant
partition of the search space, hence allowing an effective parallelisation.
We evaluate CFSS on two benchmark functions, the edge
sum with coordination cost and the collective energy purchasing
functions, comparing its performance with the best algorithm for
CSG on synergy graphs: DyCE. The latter approach is centralised
and cannot be efficiently parallelised due to the exponential memory
requirements in the number of agents, which limits its scalability
(while CFSS memory requirements are only polynomial).
Our results show that, when the graphs are very sparse, CFSS is
4 orders of magnitude faster than DyCE. Moreover, CFSS is the
first approach to provide anytime approximate solutions with quality
guarantees for very large systems (i.e., with more than 2700
agents).
8.
Svensson, Kim; Ramchurn, Sarvapali; Cruz, Francisco; Rodriguez-Aguilar, Juan-Antonio; Cerquides, Jesus
Solving the coalition structure generation problem on a GPU Proceedings Article
In: 6th International Workshop on Optimisation in Multi-Agent Systems, 2013.
@inproceedings{eps352204,
title = {Solving the coalition structure generation problem on a GPU},
author = {Kim Svensson and Sarvapali Ramchurn and Francisco Cruz and Juan-Antonio Rodriguez-Aguilar and Jesus Cerquides},
url = {http://eprints.soton.ac.uk/352204/},
year = {2013},
date = {2013-01-01},
booktitle = {6th International Workshop on Optimisation in Multi-Agent Systems},
abstract = {We develop the first parallel algorithm for Coalition Structure Generation (CSG), which is central to many multi-agent systems applications. Our approach involves distributing the key steps of a dynamic programming approach to CSG across computational nodes on a Graphics Processing Unit (GPU) such that each of the thousands of threads of computation can be used to perform small computations that speed up the overall process. In so doing, we solve important challenges that arise in solving combinatorial optimisation problems on GPUs such as the efficient allocation of memory and computational threads to every step of the algorithm. In our empirical evaluations on a standard GPU, our results show an improvement of orders of magnitude over current dynamic programming approaches with an ever increasing divergence between the CPU and GPU-based algorithms in terms of growth. Thus, our algorithm is able to solve the CSG problem for 29 agents in one hour and thirty minutes as opposed to three days for the current state of the art dynamic programming algorithms.},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
We develop the first parallel algorithm for Coalition Structure Generation (CSG), which is central to many multi-agent systems applications. Our approach involves distributing the key steps of a dynamic programming approach to CSG across computational nodes on a Graphics Processing Unit (GPU) such that each of the thousands of threads of computation can be used to perform small computations that speed up the overall process. In so doing, we solve important challenges that arise in solving combinatorial optimisation problems on GPUs such as the efficient allocation of memory and computational threads to every step of the algorithm. In our empirical evaluations on a standard GPU, our results show an improvement of orders of magnitude over current dynamic programming approaches with an ever increasing divergence between the CPU and GPU-based algorithms in terms of growth. Thus, our algorithm is able to solve the CSG problem for 29 agents in one hour and thirty minutes as opposed to three days for the current state of the art dynamic programming algorithms.
9.
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.
10.
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.
11.
Rahwan, Talal; Ramchurn, Sarvapali D.; Dang, Viet D.; Giovannucci, Andrea; Jennings, N. R.
Anytime Optimal Coalition Structure Generation Proceedings Article
In: 22nd Conference on Artificial Intelligence (AAAI), pp. 1184–1190, 2007.
@inproceedings{eps263433,
title = {Anytime Optimal Coalition Structure Generation},
author = {Talal Rahwan and Sarvapali D. Ramchurn and Viet D. Dang and Andrea Giovannucci and N. R. Jennings},
url = {http://eprints.soton.ac.uk/263433/},
year = {2007},
date = {2007-01-01},
booktitle = {22nd Conference on Artificial Intelligence (AAAI)},
pages = {1184–1190},
abstract = {Forming effective coalitions is a major research challenge in the field of multi-agent systems. Central to this endeavour is the problem of determining the best groups of agents to select to achieve some goal. To this end, in this paper, we present a novel, optimal anytime algorithm for this coalition structure generation problem that is significantly faster than previous algorithms designed for this purpose. Specifically, our algorithm can generate solutions by partitioning the space of all potential coalitions into sub-spaces that contain coalition structures that are similar, according to some criterion, such that these sub-spaces can be pruned by identifying their bounds. Using this representation, the algorithm then searches through only valid and unique coalition structures and selects the best among them using a branch-and-bound technique. We empirically show that we are able to find solutions that are optimal in 0.082% of the time taken by the state of the art dynamic programming algorithm (for 27 agents) using much less memory (O(2^ n) instead of O(3^ n) for the set of n agents). Moreover, our algorithm is the first to be able to solve the coalition structure generation problem for numbers of agents bigger than 27 in reasonable time (less than 90 minutes for 27 agents as opposed to around 2 months for the best previous solution).},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
Forming effective coalitions is a major research challenge in the field of multi-agent systems. Central to this endeavour is the problem of determining the best groups of agents to select to achieve some goal. To this end, in this paper, we present a novel, optimal anytime algorithm for this coalition structure generation problem that is significantly faster than previous algorithms designed for this purpose. Specifically, our algorithm can generate solutions by partitioning the space of all potential coalitions into sub-spaces that contain coalition structures that are similar, according to some criterion, such that these sub-spaces can be pruned by identifying their bounds. Using this representation, the algorithm then searches through only valid and unique coalition structures and selects the best among them using a branch-and-bound technique. We empirically show that we are able to find solutions that are optimal in 0.082% of the time taken by the state of the art dynamic programming algorithm (for 27 agents) using much less memory (O(2^ n) instead of O(3^ n) for the set of n agents). Moreover, our algorithm is the first to be able to solve the coalition structure generation problem for numbers of agents bigger than 27 in reasonable time (less than 90 minutes for 27 agents as opposed to around 2 months for the best previous solution).
12.
Bistaffa, Jesús Cerquides Alessandro Farinelli Filippo; Ramchurn, Sarvapali D.
Algorithms for Graph-Constrained Coalition Formation in the Real World Journal Article
In: ACM Transactions on Intelligent Systems and Technology (TIST), vol. 8, no. 4, 0000.
@article{bistaffaetal2017,
title = {Algorithms for Graph-Constrained Coalition Formation in the Real World},
author = {Jesús Cerquides Alessandro Farinelli Filippo Bistaffa and Sarvapali D. Ramchurn},
doi = {http://dx.doi.org/10.1145/3040967},
journal = {ACM Transactions on Intelligent Systems and Technology (TIST)},
volume = {8},
number = {4},
keywords = {},
pubstate = {published},
tppubtype = {article}
}
2017
Bistaffa, Jesús Cerquides Alessandro Farinelli Filippo; Ramchurn, Sarvapali D.
Algorithms for Graph-Constrained Coalition Formation in the Real World Journal Article
In: ACM Transactions on Intelligent Systems and Technology (TIST), vol. 8, no. 4, 2017.
Links | BibTeX | Tags: Coalition Formation, Ridesharing
@article{bistaffaetal2017b,
title = {Algorithms for Graph-Constrained Coalition Formation in the Real World},
author = {Jesús Cerquides Alessandro Farinelli Filippo Bistaffa and Sarvapali D. Ramchurn},
url = {https://www.sramchurn.com/wp-content/uploads/2017/03/2017tist.pdf},
doi = {http://dx.doi.org/10.1145/3040967},
year = {2017},
date = {2017-02-11},
journal = {ACM Transactions on Intelligent Systems and Technology (TIST)},
volume = {8},
number = {4},
keywords = {Coalition Formation, Ridesharing},
pubstate = {published},
tppubtype = {article}
}
Chalkiadakis, Sarvapali Alessandro Farinelli; Ramchurn Filippo Bistaffa Georgios
A Cooperative Game-Theoretic Approach to the Social Ridesharing Problem Journal Article
In: Artificial Intelligence Journal, pp. (accepted), 2017.
Links | BibTeX | Tags: Coalition Formation, Ridesharing
@article{bistaffa:etal:2017b,
title = {A Cooperative Game-Theoretic Approach to the Social Ridesharing Problem},
author = {Sarvapali Alessandro Farinelli; Ramchurn Filippo Bistaffa Georgios Chalkiadakis},
url = {http://www.sciencedirect.com/science/article/pii/S0004370217300243},
year = {2017},
date = {2017-02-11},
journal = {Artificial Intelligence Journal},
pages = {(accepted)},
keywords = {Coalition Formation, Ridesharing},
pubstate = {published},
tppubtype = {article}
}
Farinelli, Alessandro; Bicego, Manuele; Bistaffa, Filippo; Ramchurn, Sarvapali D.
A Hierarchical Clustering Approach to Large-scale Near-optimal Coalition Formation with Quality Guarantees Journal Article
In: Engineering Applications of Artificial Intelligence (EAAI), vol. 57, pp. 170-185, 2017.
Abstract | Links | BibTeX | Tags: Coalition Formation, Energy
@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 = {Coalition Formation, Energy},
pubstate = {published},
tppubtype = {article}
}
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.
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.
Cruz, Francisco; Espinosa, Antonio; Moure, Juan C.; Cerquides, Jesus; Rodriguez-Aguilar, Juan A.; Svensson, Kim; Ramchurn, Sarvapali D.
Coalition structure generation problems: optimization and parallelization of the IDP algorithm in multicore systems Journal Article
In: Concurrency and Computation: Practice and Experience, vol. 29, no. 5, pp. e3969–n/a, 2017, ISSN: 1532-0634, (e3969 cpe.3969).
Links | BibTeX | Tags: Coalition Formation, dynamic programming, multi agent systems, multi-core systems, set partitioning problem
@article{CPE:CPE3969,
title = {Coalition structure generation problems: optimization and parallelization of the IDP algorithm in multicore systems},
author = {Francisco Cruz and Antonio Espinosa and Juan C. Moure and Jesus Cerquides and Juan A. Rodriguez-Aguilar and Kim Svensson and Sarvapali D. Ramchurn},
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 = {Coalition Formation, dynamic programming, multi agent systems, multi-core systems, set partitioning problem},
pubstate = {published},
tppubtype = {article}
}
2015
Bistaffa, Alessandro Farinelli Georgios Chalkiadakis Filippo; Ramchurn, Sarvapali D.
Recommending Fair Payments for Large-Scale Social Ridesharing Proceedings Article
In: ACM Conference on Recommender Systems (Recsys), 2015.
Links | BibTeX | Tags: Coalition Formation, mas, Ridesharing
@inproceedings{bistaffaetal2015,
title = {Recommending Fair Payments for Large-Scale Social Ridesharing},
author = {Alessandro Farinelli Georgios Chalkiadakis Filippo Bistaffa and Sarvapali D. Ramchurn},
url = {https://www.sramchurn.com/wp-content/uploads/2017/02/2015recsys.pdf},
year = {2015},
date = {2015-09-16},
booktitle = {ACM Conference on Recommender Systems (Recsys)},
keywords = {Coalition Formation, mas, Ridesharing},
pubstate = {published},
tppubtype = {inproceedings}
}
Bistaffa, Sarvapali D. Ramchurn Alessandro Farinelli Filippo
Sharing Rides with Friends: a Coalition Formation Algorithm for Ridesharing Proceedings Article
In: Proceedings of the AAAI Conference, 2015.
Abstract | Links | BibTeX | Tags: Coalition Formation, optimisation, Ridesharing, Social Networks
@inproceedings{bistaffa:etal:2015,
title = {Sharing Rides with Friends: a Coalition Formation Algorithm for Ridesharing},
author = {Sarvapali D. Ramchurn Alessandro Farinelli Filippo Bistaffa},
url = {http://eprints.soton.ac.uk/372048/},
year = {2015},
date = {2015-01-25},
booktitle = {Proceedings of the AAAI Conference},
abstract = {We consider the Social Ridesharing (SR) problem, where a set of commuters, connected through a social network, ar- range one-time rides at a very short notice. In particular, we focus on the associated optimisation problem of forming cars to minimise the travel cost of the overall system mod- elling such problem as a graph constrained coalition forma- tion (GCCF) problem, where the set of feasible coalitions is restricted by a graph (i.e., the social network). Moreover, we significantly extend the state of the art algorithm for GCCF, i.e., the CFSS algorithm, to solve our GCCF model of the SR problem. Our empirical evaluation uses a real dataset for both spatial (GeoLife) and social data (Twitter), to validate the ap- plicability of our approach in a realistic application scenario. Empirical results show that our approach computes optimal solutions for systems of medium scale (up to 100 agents) providing significant cost reductions (up to −36.22%). More- over, we can provide approximate solutions for very large systems (i.e., up to 2000 agents) and good quality guarantees (i.e., with an approximation ratio of 1.41 in the worst case) within minutes (i.e., 100 seconds).},
keywords = {Coalition Formation, optimisation, Ridesharing, Social Networks},
pubstate = {published},
tppubtype = {inproceedings}
}
We consider the Social Ridesharing (SR) problem, where a set of commuters, connected through a social network, ar- range one-time rides at a very short notice. In particular, we focus on the associated optimisation problem of forming cars to minimise the travel cost of the overall system mod- elling such problem as a graph constrained coalition forma- tion (GCCF) problem, where the set of feasible coalitions is restricted by a graph (i.e., the social network). Moreover, we significantly extend the state of the art algorithm for GCCF, i.e., the CFSS algorithm, to solve our GCCF model of the SR problem. Our empirical evaluation uses a real dataset for both spatial (GeoLife) and social data (Twitter), to validate the ap- plicability of our approach in a realistic application scenario. Empirical results show that our approach computes optimal solutions for systems of medium scale (up to 100 agents) providing significant cost reductions (up to −36.22%). More- over, we can provide approximate solutions for very large systems (i.e., up to 2000 agents) and good quality guarantees (i.e., with an approximation ratio of 1.41 in the worst case) within minutes (i.e., 100 seconds).
2014
Bistaffa, Filippo; Farinelli, Alessandro; Cerquides, Jesus; Rodriguez-Aguilar, Juan Antonio; Ramchurn, Sarvapali D
Anytime Coalition Structure Generation on Synergy Graphs Proceedings Article
In: 13th Int. Conf. on Autonomous Agents and Multi-Agent Systems, pp. 13-20, 2014.
Abstract | Links | BibTeX | Tags: Coalition Formation, Coordination
@inproceedings{orchid175,
title = {Anytime Coalition Structure Generation on Synergy Graphs},
author = {Filippo Bistaffa and Alessandro Farinelli and Jesus Cerquides and Juan Antonio Rodriguez-Aguilar and Sarvapali D Ramchurn},
url = {http://aamas2014.lip6.fr/proceedings/aamas/p13.pdf},
year = {2014},
date = {2014-01-01},
booktitle = {13th Int. Conf. on Autonomous Agents and Multi-Agent Systems},
pages = {13-20},
abstract = {We consider the coalition structure generation (CSG) problem on
synergy graphs, which arises in many practical applications where
communication constraints, social or trust relationships must be
taken into account when forming coalitions. We propose a novel
representation of this problem based on the concept of edge contraction,
and an innovative branch and bound approach (CFSS),
which is particularly efficient when applied to a general class of
characteristic functions. This new model provides a non-redundant
partition of the search space, hence allowing an effective parallelisation.
We evaluate CFSS on two benchmark functions, the edge
sum with coordination cost and the collective energy purchasing
functions, comparing its performance with the best algorithm for
CSG on synergy graphs: DyCE. The latter approach is centralised
and cannot be efficiently parallelised due to the exponential memory
requirements in the number of agents, which limits its scalability
(while CFSS memory requirements are only polynomial).
Our results show that, when the graphs are very sparse, CFSS is
4 orders of magnitude faster than DyCE. Moreover, CFSS is the
first approach to provide anytime approximate solutions with quality
guarantees for very large systems (i.e., with more than 2700
agents).},
keywords = {Coalition Formation, Coordination},
pubstate = {published},
tppubtype = {inproceedings}
}
We consider the coalition structure generation (CSG) problem on
synergy graphs, which arises in many practical applications where
communication constraints, social or trust relationships must be
taken into account when forming coalitions. We propose a novel
representation of this problem based on the concept of edge contraction,
and an innovative branch and bound approach (CFSS),
which is particularly efficient when applied to a general class of
characteristic functions. This new model provides a non-redundant
partition of the search space, hence allowing an effective parallelisation.
We evaluate CFSS on two benchmark functions, the edge
sum with coordination cost and the collective energy purchasing
functions, comparing its performance with the best algorithm for
CSG on synergy graphs: DyCE. The latter approach is centralised
and cannot be efficiently parallelised due to the exponential memory
requirements in the number of agents, which limits its scalability
(while CFSS memory requirements are only polynomial).
Our results show that, when the graphs are very sparse, CFSS is
4 orders of magnitude faster than DyCE. Moreover, CFSS is the
first approach to provide anytime approximate solutions with quality
guarantees for very large systems (i.e., with more than 2700
agents).
synergy graphs, which arises in many practical applications where
communication constraints, social or trust relationships must be
taken into account when forming coalitions. We propose a novel
representation of this problem based on the concept of edge contraction,
and an innovative branch and bound approach (CFSS),
which is particularly efficient when applied to a general class of
characteristic functions. This new model provides a non-redundant
partition of the search space, hence allowing an effective parallelisation.
We evaluate CFSS on two benchmark functions, the edge
sum with coordination cost and the collective energy purchasing
functions, comparing its performance with the best algorithm for
CSG on synergy graphs: DyCE. The latter approach is centralised
and cannot be efficiently parallelised due to the exponential memory
requirements in the number of agents, which limits its scalability
(while CFSS memory requirements are only polynomial).
Our results show that, when the graphs are very sparse, CFSS is
4 orders of magnitude faster than DyCE. Moreover, CFSS is the
first approach to provide anytime approximate solutions with quality
guarantees for very large systems (i.e., with more than 2700
agents).
2013
Svensson, Kim; Ramchurn, Sarvapali; Cruz, Francisco; Rodriguez-Aguilar, Juan-Antonio; Cerquides, Jesus
Solving the coalition structure generation problem on a GPU Proceedings Article
In: 6th International Workshop on Optimisation in Multi-Agent Systems, 2013.
Abstract | Links | BibTeX | Tags: Coalition Formation, mas, Multi-agent scheduling
@inproceedings{eps352204,
title = {Solving the coalition structure generation problem on a GPU},
author = {Kim Svensson and Sarvapali Ramchurn and Francisco Cruz and Juan-Antonio Rodriguez-Aguilar and Jesus Cerquides},
url = {http://eprints.soton.ac.uk/352204/},
year = {2013},
date = {2013-01-01},
booktitle = {6th International Workshop on Optimisation in Multi-Agent Systems},
abstract = {We develop the first parallel algorithm for Coalition Structure Generation (CSG), which is central to many multi-agent systems applications. Our approach involves distributing the key steps of a dynamic programming approach to CSG across computational nodes on a Graphics Processing Unit (GPU) such that each of the thousands of threads of computation can be used to perform small computations that speed up the overall process. In so doing, we solve important challenges that arise in solving combinatorial optimisation problems on GPUs such as the efficient allocation of memory and computational threads to every step of the algorithm. In our empirical evaluations on a standard GPU, our results show an improvement of orders of magnitude over current dynamic programming approaches with an ever increasing divergence between the CPU and GPU-based algorithms in terms of growth. Thus, our algorithm is able to solve the CSG problem for 29 agents in one hour and thirty minutes as opposed to three days for the current state of the art dynamic programming algorithms.},
keywords = {Coalition Formation, mas, Multi-agent scheduling},
pubstate = {published},
tppubtype = {inproceedings}
}
We develop the first parallel algorithm for Coalition Structure Generation (CSG), which is central to many multi-agent systems applications. Our approach involves distributing the key steps of a dynamic programming approach to CSG across computational nodes on a Graphics Processing Unit (GPU) such that each of the thousands of threads of computation can be used to perform small computations that speed up the overall process. In so doing, we solve important challenges that arise in solving combinatorial optimisation problems on GPUs such as the efficient allocation of memory and computational threads to every step of the algorithm. In our empirical evaluations on a standard GPU, our results show an improvement of orders of magnitude over current dynamic programming approaches with an ever increasing divergence between the CPU and GPU-based algorithms in terms of growth. Thus, our algorithm is able to solve the CSG problem for 29 agents in one hour and thirty minutes as opposed to three days for the current state of the art dynamic programming algorithms.
2010
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).
Abstract | Links | BibTeX | Tags: agents, Coalition Formation, Disaster Management, Multi-agent scheduling, RoboCup Rescue
@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 = {agents, Coalition Formation, Disaster Management, Multi-agent scheduling, RoboCup Rescue},
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.
2009
Rahwan, Talal; Ramchurn, Sarvapali; Jennings, Nicholas; Giovannucci, Andrea
An anytime algorithm for optimal coalition structure generation Journal Article
In: Journal of Artificial Intelligence Research, vol. 34, pp. 521–567, 2009.
Abstract | Links | BibTeX | Tags: Coalition Formation, multi-agent systems
@article{eps267179,
title = {An anytime algorithm for optimal coalition structure generation},
author = {Talal Rahwan and Sarvapali Ramchurn and Nicholas Jennings and Andrea Giovannucci},
url = {http://eprints.soton.ac.uk/267179/},
year = {2009},
date = {2009-01-01},
journal = {Journal of Artificial Intelligence Research},
volume = {34},
pages = {521–567},
abstract = {Coalition formation is a fundamental type of interaction that involves the creation of coherent groupings of distinct, autonomous, agents in order to efficiently achieve their individual or collective goals. Forming effective coalitions is a major research challenge in the field of multi-agent systems. Central to this endeavour is the problem of determining which of the many possible coalitions to form in order to achieve some goal. This usually requires calculating a value for every possible coalition, known as the coalition value, which indicates how beneficial that coalition would be if it was formed. Once these values are calculated, the agents usually need to find a combination of coalitions, in which every agent belongs to exactly one coalition, and by which the overall outcome of the system is maximized. However, this coalition structure generation problem is extremely challenging due to the number of possible solutions that need to be examined, which grows exponentially with the number of agents involved. To date, therefore, many algorithms have been proposed to solve this problem using different techniques–ranging from dynamic programming, to integer programming, to stochastic search – all of which suffer from major limitations relating to execution time, solution quality, and memory requirements. With this in mind, we develop an anytime algorithm to solve the coalition structure generation problem. Specifically, the algorithm uses a novel representation of the search space, which partitions the space of possible solutions into sub-spaces such that it is possible to compute upper and lower bounds on the values of the best coalition structures in them. These bounds are then used to identify the sub-spaces that have no potential of containing the optimal solution so that they can be pruned. The algorithm, then, searches through the remaining sub-spaces very efficiently using a branch-and-bound technique to avoid examining all the solutions within the searched subspace(s). In this setting, we prove that our algorithm enumerates all coalition structures efficiently by avoiding redundant and invalid solutions automatically. Moreover, in order to effectively test our algorithm we develop a new type of input distribution which allows us to generate more reliable benchmarks compared to the input distributions previously used in the field. Given this new distribution, we show that for 27 agents our algorithm is able to find solutions that are optimal in 0:175% of the time required by the fastest available algorithm in the literature. The algorithm is anytime, and if interrupted before it would have normally terminated, it can still provide a solution that is guaranteed to be within a bound from the optimal one. Moreover, the guarantees we provide on the quality of the solution are significantly better than those provided by the previous state of the art algorithms designed for this purpose. For example, for the worst case distribution given 25 agents, our algorithm is able to find a 90% efficient solution in around 10% of time it takes to find the optimal solution.},
keywords = {Coalition Formation, multi-agent systems},
pubstate = {published},
tppubtype = {article}
}
Coalition formation is a fundamental type of interaction that involves the creation of coherent groupings of distinct, autonomous, agents in order to efficiently achieve their individual or collective goals. Forming effective coalitions is a major research challenge in the field of multi-agent systems. Central to this endeavour is the problem of determining which of the many possible coalitions to form in order to achieve some goal. This usually requires calculating a value for every possible coalition, known as the coalition value, which indicates how beneficial that coalition would be if it was formed. Once these values are calculated, the agents usually need to find a combination of coalitions, in which every agent belongs to exactly one coalition, and by which the overall outcome of the system is maximized. However, this coalition structure generation problem is extremely challenging due to the number of possible solutions that need to be examined, which grows exponentially with the number of agents involved. To date, therefore, many algorithms have been proposed to solve this problem using different techniques–ranging from dynamic programming, to integer programming, to stochastic search – all of which suffer from major limitations relating to execution time, solution quality, and memory requirements. With this in mind, we develop an anytime algorithm to solve the coalition structure generation problem. Specifically, the algorithm uses a novel representation of the search space, which partitions the space of possible solutions into sub-spaces such that it is possible to compute upper and lower bounds on the values of the best coalition structures in them. These bounds are then used to identify the sub-spaces that have no potential of containing the optimal solution so that they can be pruned. The algorithm, then, searches through the remaining sub-spaces very efficiently using a branch-and-bound technique to avoid examining all the solutions within the searched subspace(s). In this setting, we prove that our algorithm enumerates all coalition structures efficiently by avoiding redundant and invalid solutions automatically. Moreover, in order to effectively test our algorithm we develop a new type of input distribution which allows us to generate more reliable benchmarks compared to the input distributions previously used in the field. Given this new distribution, we show that for 27 agents our algorithm is able to find solutions that are optimal in 0:175% of the time required by the fastest available algorithm in the literature. The algorithm is anytime, and if interrupted before it would have normally terminated, it can still provide a solution that is guaranteed to be within a bound from the optimal one. Moreover, the guarantees we provide on the quality of the solution are significantly better than those provided by the previous state of the art algorithms designed for this purpose. For example, for the worst case distribution given 25 agents, our algorithm is able to find a 90% efficient solution in around 10% of time it takes to find the optimal solution.
2007
Rahwan, Talal; Ramchurn, Sarvapali D.; Dang, Viet D.; Giovannucci, Andrea; Jennings, N. R.
Anytime Optimal Coalition Structure Generation Proceedings Article
In: 22nd Conference on Artificial Intelligence (AAAI), pp. 1184–1190, 2007.
Abstract | Links | BibTeX | Tags: Coalition Formation, Coalition Structure Generation, Combinatorial, multi-agent systems, Search, Set Partitioning
@inproceedings{eps263433,
title = {Anytime Optimal Coalition Structure Generation},
author = {Talal Rahwan and Sarvapali D. Ramchurn and Viet D. Dang and Andrea Giovannucci and N. R. Jennings},
url = {http://eprints.soton.ac.uk/263433/},
year = {2007},
date = {2007-01-01},
booktitle = {22nd Conference on Artificial Intelligence (AAAI)},
pages = {1184–1190},
abstract = {Forming effective coalitions is a major research challenge in the field of multi-agent systems. Central to this endeavour is the problem of determining the best groups of agents to select to achieve some goal. To this end, in this paper, we present a novel, optimal anytime algorithm for this coalition structure generation problem that is significantly faster than previous algorithms designed for this purpose. Specifically, our algorithm can generate solutions by partitioning the space of all potential coalitions into sub-spaces that contain coalition structures that are similar, according to some criterion, such that these sub-spaces can be pruned by identifying their bounds. Using this representation, the algorithm then searches through only valid and unique coalition structures and selects the best among them using a branch-and-bound technique. We empirically show that we are able to find solutions that are optimal in 0.082% of the time taken by the state of the art dynamic programming algorithm (for 27 agents) using much less memory (O(2^ n) instead of O(3^ n) for the set of n agents). Moreover, our algorithm is the first to be able to solve the coalition structure generation problem for numbers of agents bigger than 27 in reasonable time (less than 90 minutes for 27 agents as opposed to around 2 months for the best previous solution).},
keywords = {Coalition Formation, Coalition Structure Generation, Combinatorial, multi-agent systems, Search, Set Partitioning},
pubstate = {published},
tppubtype = {inproceedings}
}
Forming effective coalitions is a major research challenge in the field of multi-agent systems. Central to this endeavour is the problem of determining the best groups of agents to select to achieve some goal. To this end, in this paper, we present a novel, optimal anytime algorithm for this coalition structure generation problem that is significantly faster than previous algorithms designed for this purpose. Specifically, our algorithm can generate solutions by partitioning the space of all potential coalitions into sub-spaces that contain coalition structures that are similar, according to some criterion, such that these sub-spaces can be pruned by identifying their bounds. Using this representation, the algorithm then searches through only valid and unique coalition structures and selects the best among them using a branch-and-bound technique. We empirically show that we are able to find solutions that are optimal in 0.082% of the time taken by the state of the art dynamic programming algorithm (for 27 agents) using much less memory (O(2^ n) instead of O(3^ n) for the set of n agents). Moreover, our algorithm is the first to be able to solve the coalition structure generation problem for numbers of agents bigger than 27 in reasonable time (less than 90 minutes for 27 agents as opposed to around 2 months for the best previous solution).
0000
Bistaffa, Jesús Cerquides Alessandro Farinelli Filippo; Ramchurn, Sarvapali D.
Algorithms for Graph-Constrained Coalition Formation in the Real World Journal Article
In: ACM Transactions on Intelligent Systems and Technology (TIST), vol. 8, no. 4, 0000.
Links | BibTeX | Tags: Coalition Formation, Ridesharing
@article{bistaffaetal2017,
title = {Algorithms for Graph-Constrained Coalition Formation in the Real World},
author = {Jesús Cerquides Alessandro Farinelli Filippo Bistaffa and Sarvapali D. Ramchurn},
doi = {http://dx.doi.org/10.1145/3040967},
journal = {ACM Transactions on Intelligent Systems and Technology (TIST)},
volume = {8},
number = {4},
keywords = {Coalition Formation, Ridesharing},
pubstate = {published},
tppubtype = {article}
}
1.
Bistaffa, Jesús Cerquides Alessandro Farinelli Filippo; Ramchurn, Sarvapali D.
Algorithms for Graph-Constrained Coalition Formation in the Real World Journal Article
In: ACM Transactions on Intelligent Systems and Technology (TIST), vol. 8, no. 4, 2017.
@article{bistaffaetal2017b,
title = {Algorithms for Graph-Constrained Coalition Formation in the Real World},
author = {Jesús Cerquides Alessandro Farinelli Filippo Bistaffa and Sarvapali D. Ramchurn},
url = {https://www.sramchurn.com/wp-content/uploads/2017/03/2017tist.pdf},
doi = {http://dx.doi.org/10.1145/3040967},
year = {2017},
date = {2017-02-11},
journal = {ACM Transactions on Intelligent Systems and Technology (TIST)},
volume = {8},
number = {4},
keywords = {},
pubstate = {published},
tppubtype = {article}
}
2.
Chalkiadakis, Sarvapali Alessandro Farinelli; Ramchurn Filippo Bistaffa Georgios
A Cooperative Game-Theoretic Approach to the Social Ridesharing Problem Journal Article
In: Artificial Intelligence Journal, pp. (accepted), 2017.
@article{bistaffa:etal:2017b,
title = {A Cooperative Game-Theoretic Approach to the Social Ridesharing Problem},
author = {Sarvapali Alessandro Farinelli; Ramchurn Filippo Bistaffa Georgios Chalkiadakis},
url = {http://www.sciencedirect.com/science/article/pii/S0004370217300243},
year = {2017},
date = {2017-02-11},
journal = {Artificial Intelligence Journal},
pages = {(accepted)},
keywords = {},
pubstate = {published},
tppubtype = {article}
}
3.
Farinelli, Alessandro; Bicego, Manuele; Bistaffa, Filippo; Ramchurn, Sarvapali D.
A Hierarchical Clustering Approach to Large-scale Near-optimal Coalition Formation with Quality Guarantees Journal Article
In: Engineering Applications of Artificial Intelligence (EAAI), vol. 57, pp. 170-185, 2017.
@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}
}
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.
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.
4.
Cruz, Francisco; Espinosa, Antonio; Moure, Juan C.; Cerquides, Jesus; Rodriguez-Aguilar, Juan A.; Svensson, Kim; Ramchurn, Sarvapali D.
Coalition structure generation problems: optimization and parallelization of the IDP algorithm in multicore systems Journal Article
In: Concurrency and Computation: Practice and Experience, vol. 29, no. 5, pp. e3969–n/a, 2017, ISSN: 1532-0634, (e3969 cpe.3969).
@article{CPE:CPE3969,
title = {Coalition structure generation problems: optimization and parallelization of the IDP algorithm in multicore systems},
author = {Francisco Cruz and Antonio Espinosa and Juan C. Moure and Jesus Cerquides and Juan A. Rodriguez-Aguilar and Kim Svensson and Sarvapali D. Ramchurn},
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}
}
5.
Bistaffa, Alessandro Farinelli Georgios Chalkiadakis Filippo; Ramchurn, Sarvapali D.
Recommending Fair Payments for Large-Scale Social Ridesharing Proceedings Article
In: ACM Conference on Recommender Systems (Recsys), 2015.
@inproceedings{bistaffaetal2015,
title = {Recommending Fair Payments for Large-Scale Social Ridesharing},
author = {Alessandro Farinelli Georgios Chalkiadakis Filippo Bistaffa and Sarvapali D. Ramchurn},
url = {https://www.sramchurn.com/wp-content/uploads/2017/02/2015recsys.pdf},
year = {2015},
date = {2015-09-16},
booktitle = {ACM Conference on Recommender Systems (Recsys)},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
6.
Bistaffa, Sarvapali D. Ramchurn Alessandro Farinelli Filippo
Sharing Rides with Friends: a Coalition Formation Algorithm for Ridesharing Proceedings Article
In: Proceedings of the AAAI Conference, 2015.
@inproceedings{bistaffa:etal:2015,
title = {Sharing Rides with Friends: a Coalition Formation Algorithm for Ridesharing},
author = {Sarvapali D. Ramchurn Alessandro Farinelli Filippo Bistaffa},
url = {http://eprints.soton.ac.uk/372048/},
year = {2015},
date = {2015-01-25},
booktitle = {Proceedings of the AAAI Conference},
abstract = {We consider the Social Ridesharing (SR) problem, where a set of commuters, connected through a social network, ar- range one-time rides at a very short notice. In particular, we focus on the associated optimisation problem of forming cars to minimise the travel cost of the overall system mod- elling such problem as a graph constrained coalition forma- tion (GCCF) problem, where the set of feasible coalitions is restricted by a graph (i.e., the social network). Moreover, we significantly extend the state of the art algorithm for GCCF, i.e., the CFSS algorithm, to solve our GCCF model of the SR problem. Our empirical evaluation uses a real dataset for both spatial (GeoLife) and social data (Twitter), to validate the ap- plicability of our approach in a realistic application scenario. Empirical results show that our approach computes optimal solutions for systems of medium scale (up to 100 agents) providing significant cost reductions (up to −36.22%). More- over, we can provide approximate solutions for very large systems (i.e., up to 2000 agents) and good quality guarantees (i.e., with an approximation ratio of 1.41 in the worst case) within minutes (i.e., 100 seconds).},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
We consider the Social Ridesharing (SR) problem, where a set of commuters, connected through a social network, ar- range one-time rides at a very short notice. In particular, we focus on the associated optimisation problem of forming cars to minimise the travel cost of the overall system mod- elling such problem as a graph constrained coalition forma- tion (GCCF) problem, where the set of feasible coalitions is restricted by a graph (i.e., the social network). Moreover, we significantly extend the state of the art algorithm for GCCF, i.e., the CFSS algorithm, to solve our GCCF model of the SR problem. Our empirical evaluation uses a real dataset for both spatial (GeoLife) and social data (Twitter), to validate the ap- plicability of our approach in a realistic application scenario. Empirical results show that our approach computes optimal solutions for systems of medium scale (up to 100 agents) providing significant cost reductions (up to −36.22%). More- over, we can provide approximate solutions for very large systems (i.e., up to 2000 agents) and good quality guarantees (i.e., with an approximation ratio of 1.41 in the worst case) within minutes (i.e., 100 seconds).
7.
Bistaffa, Filippo; Farinelli, Alessandro; Cerquides, Jesus; Rodriguez-Aguilar, Juan Antonio; Ramchurn, Sarvapali D
Anytime Coalition Structure Generation on Synergy Graphs Proceedings Article
In: 13th Int. Conf. on Autonomous Agents and Multi-Agent Systems, pp. 13-20, 2014.
@inproceedings{orchid175,
title = {Anytime Coalition Structure Generation on Synergy Graphs},
author = {Filippo Bistaffa and Alessandro Farinelli and Jesus Cerquides and Juan Antonio Rodriguez-Aguilar and Sarvapali D Ramchurn},
url = {http://aamas2014.lip6.fr/proceedings/aamas/p13.pdf},
year = {2014},
date = {2014-01-01},
booktitle = {13th Int. Conf. on Autonomous Agents and Multi-Agent Systems},
pages = {13-20},
abstract = {We consider the coalition structure generation (CSG) problem on
synergy graphs, which arises in many practical applications where
communication constraints, social or trust relationships must be
taken into account when forming coalitions. We propose a novel
representation of this problem based on the concept of edge contraction,
and an innovative branch and bound approach (CFSS),
which is particularly efficient when applied to a general class of
characteristic functions. This new model provides a non-redundant
partition of the search space, hence allowing an effective parallelisation.
We evaluate CFSS on two benchmark functions, the edge
sum with coordination cost and the collective energy purchasing
functions, comparing its performance with the best algorithm for
CSG on synergy graphs: DyCE. The latter approach is centralised
and cannot be efficiently parallelised due to the exponential memory
requirements in the number of agents, which limits its scalability
(while CFSS memory requirements are only polynomial).
Our results show that, when the graphs are very sparse, CFSS is
4 orders of magnitude faster than DyCE. Moreover, CFSS is the
first approach to provide anytime approximate solutions with quality
guarantees for very large systems (i.e., with more than 2700
agents).},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
We consider the coalition structure generation (CSG) problem on
synergy graphs, which arises in many practical applications where
communication constraints, social or trust relationships must be
taken into account when forming coalitions. We propose a novel
representation of this problem based on the concept of edge contraction,
and an innovative branch and bound approach (CFSS),
which is particularly efficient when applied to a general class of
characteristic functions. This new model provides a non-redundant
partition of the search space, hence allowing an effective parallelisation.
We evaluate CFSS on two benchmark functions, the edge
sum with coordination cost and the collective energy purchasing
functions, comparing its performance with the best algorithm for
CSG on synergy graphs: DyCE. The latter approach is centralised
and cannot be efficiently parallelised due to the exponential memory
requirements in the number of agents, which limits its scalability
(while CFSS memory requirements are only polynomial).
Our results show that, when the graphs are very sparse, CFSS is
4 orders of magnitude faster than DyCE. Moreover, CFSS is the
first approach to provide anytime approximate solutions with quality
guarantees for very large systems (i.e., with more than 2700
agents).
synergy graphs, which arises in many practical applications where
communication constraints, social or trust relationships must be
taken into account when forming coalitions. We propose a novel
representation of this problem based on the concept of edge contraction,
and an innovative branch and bound approach (CFSS),
which is particularly efficient when applied to a general class of
characteristic functions. This new model provides a non-redundant
partition of the search space, hence allowing an effective parallelisation.
We evaluate CFSS on two benchmark functions, the edge
sum with coordination cost and the collective energy purchasing
functions, comparing its performance with the best algorithm for
CSG on synergy graphs: DyCE. The latter approach is centralised
and cannot be efficiently parallelised due to the exponential memory
requirements in the number of agents, which limits its scalability
(while CFSS memory requirements are only polynomial).
Our results show that, when the graphs are very sparse, CFSS is
4 orders of magnitude faster than DyCE. Moreover, CFSS is the
first approach to provide anytime approximate solutions with quality
guarantees for very large systems (i.e., with more than 2700
agents).
8.
Svensson, Kim; Ramchurn, Sarvapali; Cruz, Francisco; Rodriguez-Aguilar, Juan-Antonio; Cerquides, Jesus
Solving the coalition structure generation problem on a GPU Proceedings Article
In: 6th International Workshop on Optimisation in Multi-Agent Systems, 2013.
@inproceedings{eps352204,
title = {Solving the coalition structure generation problem on a GPU},
author = {Kim Svensson and Sarvapali Ramchurn and Francisco Cruz and Juan-Antonio Rodriguez-Aguilar and Jesus Cerquides},
url = {http://eprints.soton.ac.uk/352204/},
year = {2013},
date = {2013-01-01},
booktitle = {6th International Workshop on Optimisation in Multi-Agent Systems},
abstract = {We develop the first parallel algorithm for Coalition Structure Generation (CSG), which is central to many multi-agent systems applications. Our approach involves distributing the key steps of a dynamic programming approach to CSG across computational nodes on a Graphics Processing Unit (GPU) such that each of the thousands of threads of computation can be used to perform small computations that speed up the overall process. In so doing, we solve important challenges that arise in solving combinatorial optimisation problems on GPUs such as the efficient allocation of memory and computational threads to every step of the algorithm. In our empirical evaluations on a standard GPU, our results show an improvement of orders of magnitude over current dynamic programming approaches with an ever increasing divergence between the CPU and GPU-based algorithms in terms of growth. Thus, our algorithm is able to solve the CSG problem for 29 agents in one hour and thirty minutes as opposed to three days for the current state of the art dynamic programming algorithms.},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
We develop the first parallel algorithm for Coalition Structure Generation (CSG), which is central to many multi-agent systems applications. Our approach involves distributing the key steps of a dynamic programming approach to CSG across computational nodes on a Graphics Processing Unit (GPU) such that each of the thousands of threads of computation can be used to perform small computations that speed up the overall process. In so doing, we solve important challenges that arise in solving combinatorial optimisation problems on GPUs such as the efficient allocation of memory and computational threads to every step of the algorithm. In our empirical evaluations on a standard GPU, our results show an improvement of orders of magnitude over current dynamic programming approaches with an ever increasing divergence between the CPU and GPU-based algorithms in terms of growth. Thus, our algorithm is able to solve the CSG problem for 29 agents in one hour and thirty minutes as opposed to three days for the current state of the art dynamic programming algorithms.
9.
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.
10.
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.
11.
Rahwan, Talal; Ramchurn, Sarvapali D.; Dang, Viet D.; Giovannucci, Andrea; Jennings, N. R.
Anytime Optimal Coalition Structure Generation Proceedings Article
In: 22nd Conference on Artificial Intelligence (AAAI), pp. 1184–1190, 2007.
@inproceedings{eps263433,
title = {Anytime Optimal Coalition Structure Generation},
author = {Talal Rahwan and Sarvapali D. Ramchurn and Viet D. Dang and Andrea Giovannucci and N. R. Jennings},
url = {http://eprints.soton.ac.uk/263433/},
year = {2007},
date = {2007-01-01},
booktitle = {22nd Conference on Artificial Intelligence (AAAI)},
pages = {1184–1190},
abstract = {Forming effective coalitions is a major research challenge in the field of multi-agent systems. Central to this endeavour is the problem of determining the best groups of agents to select to achieve some goal. To this end, in this paper, we present a novel, optimal anytime algorithm for this coalition structure generation problem that is significantly faster than previous algorithms designed for this purpose. Specifically, our algorithm can generate solutions by partitioning the space of all potential coalitions into sub-spaces that contain coalition structures that are similar, according to some criterion, such that these sub-spaces can be pruned by identifying their bounds. Using this representation, the algorithm then searches through only valid and unique coalition structures and selects the best among them using a branch-and-bound technique. We empirically show that we are able to find solutions that are optimal in 0.082% of the time taken by the state of the art dynamic programming algorithm (for 27 agents) using much less memory (O(2^ n) instead of O(3^ n) for the set of n agents). Moreover, our algorithm is the first to be able to solve the coalition structure generation problem for numbers of agents bigger than 27 in reasonable time (less than 90 minutes for 27 agents as opposed to around 2 months for the best previous solution).},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
Forming effective coalitions is a major research challenge in the field of multi-agent systems. Central to this endeavour is the problem of determining the best groups of agents to select to achieve some goal. To this end, in this paper, we present a novel, optimal anytime algorithm for this coalition structure generation problem that is significantly faster than previous algorithms designed for this purpose. Specifically, our algorithm can generate solutions by partitioning the space of all potential coalitions into sub-spaces that contain coalition structures that are similar, according to some criterion, such that these sub-spaces can be pruned by identifying their bounds. Using this representation, the algorithm then searches through only valid and unique coalition structures and selects the best among them using a branch-and-bound technique. We empirically show that we are able to find solutions that are optimal in 0.082% of the time taken by the state of the art dynamic programming algorithm (for 27 agents) using much less memory (O(2^ n) instead of O(3^ n) for the set of n agents). Moreover, our algorithm is the first to be able to solve the coalition structure generation problem for numbers of agents bigger than 27 in reasonable time (less than 90 minutes for 27 agents as opposed to around 2 months for the best previous solution).
12.
Bistaffa, Jesús Cerquides Alessandro Farinelli Filippo; Ramchurn, Sarvapali D.
Algorithms for Graph-Constrained Coalition Formation in the Real World Journal Article
In: ACM Transactions on Intelligent Systems and Technology (TIST), vol. 8, no. 4, 0000.
@article{bistaffaetal2017,
title = {Algorithms for Graph-Constrained Coalition Formation in the Real World},
author = {Jesús Cerquides Alessandro Farinelli Filippo Bistaffa and Sarvapali D. Ramchurn},
doi = {http://dx.doi.org/10.1145/3040967},
journal = {ACM Transactions on Intelligent Systems and Technology (TIST)},
volume = {8},
number = {4},
keywords = {},
pubstate = {published},
tppubtype = {article}
}
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}
}
2017
Bistaffa, Jesús Cerquides Alessandro Farinelli Filippo; Ramchurn, Sarvapali D.
Algorithms for Graph-Constrained Coalition Formation in the Real World Journal Article
In: ACM Transactions on Intelligent Systems and Technology (TIST), vol. 8, no. 4, 2017.
@article{bistaffaetal2017b,
title = {Algorithms for Graph-Constrained Coalition Formation in the Real World},
author = {Jesús Cerquides Alessandro Farinelli Filippo Bistaffa and Sarvapali D. Ramchurn},
url = {https://www.sramchurn.com/wp-content/uploads/2017/03/2017tist.pdf},
doi = {http://dx.doi.org/10.1145/3040967},
year = {2017},
date = {2017-02-11},
journal = {ACM Transactions on Intelligent Systems and Technology (TIST)},
volume = {8},
number = {4},
keywords = {},
pubstate = {published},
tppubtype = {article}
}
Chalkiadakis, Sarvapali Alessandro Farinelli; Ramchurn Filippo Bistaffa Georgios
A Cooperative Game-Theoretic Approach to the Social Ridesharing Problem Journal Article
In: Artificial Intelligence Journal, pp. (accepted), 2017.
@article{bistaffa:etal:2017b,
title = {A Cooperative Game-Theoretic Approach to the Social Ridesharing Problem},
author = {Sarvapali Alessandro Farinelli; Ramchurn Filippo Bistaffa Georgios Chalkiadakis},
url = {http://www.sciencedirect.com/science/article/pii/S0004370217300243},
year = {2017},
date = {2017-02-11},
journal = {Artificial Intelligence Journal},
pages = {(accepted)},
keywords = {},
pubstate = {published},
tppubtype = {article}
}
Farinelli, Alessandro; Bicego, Manuele; Bistaffa, Filippo; Ramchurn, Sarvapali D.
A Hierarchical Clustering Approach to Large-scale Near-optimal Coalition Formation with Quality Guarantees Journal Article
In: Engineering Applications of Artificial Intelligence (EAAI), vol. 57, pp. 170-185, 2017.
@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}
}
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.
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.
Cruz, Francisco; Espinosa, Antonio; Moure, Juan C.; Cerquides, Jesus; Rodriguez-Aguilar, Juan A.; Svensson, Kim; Ramchurn, Sarvapali D.
Coalition structure generation problems: optimization and parallelization of the IDP algorithm in multicore systems Journal Article
In: Concurrency and Computation: Practice and Experience, vol. 29, no. 5, pp. e3969–n/a, 2017, ISSN: 1532-0634, (e3969 cpe.3969).
@article{CPE:CPE3969,
title = {Coalition structure generation problems: optimization and parallelization of the IDP algorithm in multicore systems},
author = {Francisco Cruz and Antonio Espinosa and Juan C. Moure and Jesus Cerquides and Juan A. Rodriguez-Aguilar and Kim Svensson and Sarvapali D. Ramchurn},
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}
}
2015
Bistaffa, Alessandro Farinelli Georgios Chalkiadakis Filippo; Ramchurn, Sarvapali D.
Recommending Fair Payments for Large-Scale Social Ridesharing Proceedings Article
In: ACM Conference on Recommender Systems (Recsys), 2015.
@inproceedings{bistaffaetal2015,
title = {Recommending Fair Payments for Large-Scale Social Ridesharing},
author = {Alessandro Farinelli Georgios Chalkiadakis Filippo Bistaffa and Sarvapali D. Ramchurn},
url = {https://www.sramchurn.com/wp-content/uploads/2017/02/2015recsys.pdf},
year = {2015},
date = {2015-09-16},
booktitle = {ACM Conference on Recommender Systems (Recsys)},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
Bistaffa, Sarvapali D. Ramchurn Alessandro Farinelli Filippo
Sharing Rides with Friends: a Coalition Formation Algorithm for Ridesharing Proceedings Article
In: Proceedings of the AAAI Conference, 2015.
@inproceedings{bistaffa:etal:2015,
title = {Sharing Rides with Friends: a Coalition Formation Algorithm for Ridesharing},
author = {Sarvapali D. Ramchurn Alessandro Farinelli Filippo Bistaffa},
url = {http://eprints.soton.ac.uk/372048/},
year = {2015},
date = {2015-01-25},
booktitle = {Proceedings of the AAAI Conference},
abstract = {We consider the Social Ridesharing (SR) problem, where a set of commuters, connected through a social network, ar- range one-time rides at a very short notice. In particular, we focus on the associated optimisation problem of forming cars to minimise the travel cost of the overall system mod- elling such problem as a graph constrained coalition forma- tion (GCCF) problem, where the set of feasible coalitions is restricted by a graph (i.e., the social network). Moreover, we significantly extend the state of the art algorithm for GCCF, i.e., the CFSS algorithm, to solve our GCCF model of the SR problem. Our empirical evaluation uses a real dataset for both spatial (GeoLife) and social data (Twitter), to validate the ap- plicability of our approach in a realistic application scenario. Empirical results show that our approach computes optimal solutions for systems of medium scale (up to 100 agents) providing significant cost reductions (up to −36.22%). More- over, we can provide approximate solutions for very large systems (i.e., up to 2000 agents) and good quality guarantees (i.e., with an approximation ratio of 1.41 in the worst case) within minutes (i.e., 100 seconds).},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
We consider the Social Ridesharing (SR) problem, where a set of commuters, connected through a social network, ar- range one-time rides at a very short notice. In particular, we focus on the associated optimisation problem of forming cars to minimise the travel cost of the overall system mod- elling such problem as a graph constrained coalition forma- tion (GCCF) problem, where the set of feasible coalitions is restricted by a graph (i.e., the social network). Moreover, we significantly extend the state of the art algorithm for GCCF, i.e., the CFSS algorithm, to solve our GCCF model of the SR problem. Our empirical evaluation uses a real dataset for both spatial (GeoLife) and social data (Twitter), to validate the ap- plicability of our approach in a realistic application scenario. Empirical results show that our approach computes optimal solutions for systems of medium scale (up to 100 agents) providing significant cost reductions (up to −36.22%). More- over, we can provide approximate solutions for very large systems (i.e., up to 2000 agents) and good quality guarantees (i.e., with an approximation ratio of 1.41 in the worst case) within minutes (i.e., 100 seconds).
2014
Bistaffa, Filippo; Farinelli, Alessandro; Cerquides, Jesus; Rodriguez-Aguilar, Juan Antonio; Ramchurn, Sarvapali D
Anytime Coalition Structure Generation on Synergy Graphs Proceedings Article
In: 13th Int. Conf. on Autonomous Agents and Multi-Agent Systems, pp. 13-20, 2014.
@inproceedings{orchid175,
title = {Anytime Coalition Structure Generation on Synergy Graphs},
author = {Filippo Bistaffa and Alessandro Farinelli and Jesus Cerquides and Juan Antonio Rodriguez-Aguilar and Sarvapali D Ramchurn},
url = {http://aamas2014.lip6.fr/proceedings/aamas/p13.pdf},
year = {2014},
date = {2014-01-01},
booktitle = {13th Int. Conf. on Autonomous Agents and Multi-Agent Systems},
pages = {13-20},
abstract = {We consider the coalition structure generation (CSG) problem on
synergy graphs, which arises in many practical applications where
communication constraints, social or trust relationships must be
taken into account when forming coalitions. We propose a novel
representation of this problem based on the concept of edge contraction,
and an innovative branch and bound approach (CFSS),
which is particularly efficient when applied to a general class of
characteristic functions. This new model provides a non-redundant
partition of the search space, hence allowing an effective parallelisation.
We evaluate CFSS on two benchmark functions, the edge
sum with coordination cost and the collective energy purchasing
functions, comparing its performance with the best algorithm for
CSG on synergy graphs: DyCE. The latter approach is centralised
and cannot be efficiently parallelised due to the exponential memory
requirements in the number of agents, which limits its scalability
(while CFSS memory requirements are only polynomial).
Our results show that, when the graphs are very sparse, CFSS is
4 orders of magnitude faster than DyCE. Moreover, CFSS is the
first approach to provide anytime approximate solutions with quality
guarantees for very large systems (i.e., with more than 2700
agents).},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
We consider the coalition structure generation (CSG) problem on
synergy graphs, which arises in many practical applications where
communication constraints, social or trust relationships must be
taken into account when forming coalitions. We propose a novel
representation of this problem based on the concept of edge contraction,
and an innovative branch and bound approach (CFSS),
which is particularly efficient when applied to a general class of
characteristic functions. This new model provides a non-redundant
partition of the search space, hence allowing an effective parallelisation.
We evaluate CFSS on two benchmark functions, the edge
sum with coordination cost and the collective energy purchasing
functions, comparing its performance with the best algorithm for
CSG on synergy graphs: DyCE. The latter approach is centralised
and cannot be efficiently parallelised due to the exponential memory
requirements in the number of agents, which limits its scalability
(while CFSS memory requirements are only polynomial).
Our results show that, when the graphs are very sparse, CFSS is
4 orders of magnitude faster than DyCE. Moreover, CFSS is the
first approach to provide anytime approximate solutions with quality
guarantees for very large systems (i.e., with more than 2700
agents).
synergy graphs, which arises in many practical applications where
communication constraints, social or trust relationships must be
taken into account when forming coalitions. We propose a novel
representation of this problem based on the concept of edge contraction,
and an innovative branch and bound approach (CFSS),
which is particularly efficient when applied to a general class of
characteristic functions. This new model provides a non-redundant
partition of the search space, hence allowing an effective parallelisation.
We evaluate CFSS on two benchmark functions, the edge
sum with coordination cost and the collective energy purchasing
functions, comparing its performance with the best algorithm for
CSG on synergy graphs: DyCE. The latter approach is centralised
and cannot be efficiently parallelised due to the exponential memory
requirements in the number of agents, which limits its scalability
(while CFSS memory requirements are only polynomial).
Our results show that, when the graphs are very sparse, CFSS is
4 orders of magnitude faster than DyCE. Moreover, CFSS is the
first approach to provide anytime approximate solutions with quality
guarantees for very large systems (i.e., with more than 2700
agents).
2013
Svensson, Kim; Ramchurn, Sarvapali; Cruz, Francisco; Rodriguez-Aguilar, Juan-Antonio; Cerquides, Jesus
Solving the coalition structure generation problem on a GPU Proceedings Article
In: 6th International Workshop on Optimisation in Multi-Agent Systems, 2013.
@inproceedings{eps352204,
title = {Solving the coalition structure generation problem on a GPU},
author = {Kim Svensson and Sarvapali Ramchurn and Francisco Cruz and Juan-Antonio Rodriguez-Aguilar and Jesus Cerquides},
url = {http://eprints.soton.ac.uk/352204/},
year = {2013},
date = {2013-01-01},
booktitle = {6th International Workshop on Optimisation in Multi-Agent Systems},
abstract = {We develop the first parallel algorithm for Coalition Structure Generation (CSG), which is central to many multi-agent systems applications. Our approach involves distributing the key steps of a dynamic programming approach to CSG across computational nodes on a Graphics Processing Unit (GPU) such that each of the thousands of threads of computation can be used to perform small computations that speed up the overall process. In so doing, we solve important challenges that arise in solving combinatorial optimisation problems on GPUs such as the efficient allocation of memory and computational threads to every step of the algorithm. In our empirical evaluations on a standard GPU, our results show an improvement of orders of magnitude over current dynamic programming approaches with an ever increasing divergence between the CPU and GPU-based algorithms in terms of growth. Thus, our algorithm is able to solve the CSG problem for 29 agents in one hour and thirty minutes as opposed to three days for the current state of the art dynamic programming algorithms.},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
We develop the first parallel algorithm for Coalition Structure Generation (CSG), which is central to many multi-agent systems applications. Our approach involves distributing the key steps of a dynamic programming approach to CSG across computational nodes on a Graphics Processing Unit (GPU) such that each of the thousands of threads of computation can be used to perform small computations that speed up the overall process. In so doing, we solve important challenges that arise in solving combinatorial optimisation problems on GPUs such as the efficient allocation of memory and computational threads to every step of the algorithm. In our empirical evaluations on a standard GPU, our results show an improvement of orders of magnitude over current dynamic programming approaches with an ever increasing divergence between the CPU and GPU-based algorithms in terms of growth. Thus, our algorithm is able to solve the CSG problem for 29 agents in one hour and thirty minutes as opposed to three days for the current state of the art dynamic programming algorithms.
2010
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.
2009
Rahwan, Talal; Ramchurn, Sarvapali; Jennings, Nicholas; Giovannucci, Andrea
An anytime algorithm for optimal coalition structure generation Journal Article
In: Journal of Artificial Intelligence Research, vol. 34, pp. 521–567, 2009.
@article{eps267179,
title = {An anytime algorithm for optimal coalition structure generation},
author = {Talal Rahwan and Sarvapali Ramchurn and Nicholas Jennings and Andrea Giovannucci},
url = {http://eprints.soton.ac.uk/267179/},
year = {2009},
date = {2009-01-01},
journal = {Journal of Artificial Intelligence Research},
volume = {34},
pages = {521–567},
abstract = {Coalition formation is a fundamental type of interaction that involves the creation of coherent groupings of distinct, autonomous, agents in order to efficiently achieve their individual or collective goals. Forming effective coalitions is a major research challenge in the field of multi-agent systems. Central to this endeavour is the problem of determining which of the many possible coalitions to form in order to achieve some goal. This usually requires calculating a value for every possible coalition, known as the coalition value, which indicates how beneficial that coalition would be if it was formed. Once these values are calculated, the agents usually need to find a combination of coalitions, in which every agent belongs to exactly one coalition, and by which the overall outcome of the system is maximized. However, this coalition structure generation problem is extremely challenging due to the number of possible solutions that need to be examined, which grows exponentially with the number of agents involved. To date, therefore, many algorithms have been proposed to solve this problem using different techniques–ranging from dynamic programming, to integer programming, to stochastic search – all of which suffer from major limitations relating to execution time, solution quality, and memory requirements. With this in mind, we develop an anytime algorithm to solve the coalition structure generation problem. Specifically, the algorithm uses a novel representation of the search space, which partitions the space of possible solutions into sub-spaces such that it is possible to compute upper and lower bounds on the values of the best coalition structures in them. These bounds are then used to identify the sub-spaces that have no potential of containing the optimal solution so that they can be pruned. The algorithm, then, searches through the remaining sub-spaces very efficiently using a branch-and-bound technique to avoid examining all the solutions within the searched subspace(s). In this setting, we prove that our algorithm enumerates all coalition structures efficiently by avoiding redundant and invalid solutions automatically. Moreover, in order to effectively test our algorithm we develop a new type of input distribution which allows us to generate more reliable benchmarks compared to the input distributions previously used in the field. Given this new distribution, we show that for 27 agents our algorithm is able to find solutions that are optimal in 0:175% of the time required by the fastest available algorithm in the literature. The algorithm is anytime, and if interrupted before it would have normally terminated, it can still provide a solution that is guaranteed to be within a bound from the optimal one. Moreover, the guarantees we provide on the quality of the solution are significantly better than those provided by the previous state of the art algorithms designed for this purpose. For example, for the worst case distribution given 25 agents, our algorithm is able to find a 90% efficient solution in around 10% of time it takes to find the optimal solution.},
keywords = {},
pubstate = {published},
tppubtype = {article}
}
Coalition formation is a fundamental type of interaction that involves the creation of coherent groupings of distinct, autonomous, agents in order to efficiently achieve their individual or collective goals. Forming effective coalitions is a major research challenge in the field of multi-agent systems. Central to this endeavour is the problem of determining which of the many possible coalitions to form in order to achieve some goal. This usually requires calculating a value for every possible coalition, known as the coalition value, which indicates how beneficial that coalition would be if it was formed. Once these values are calculated, the agents usually need to find a combination of coalitions, in which every agent belongs to exactly one coalition, and by which the overall outcome of the system is maximized. However, this coalition structure generation problem is extremely challenging due to the number of possible solutions that need to be examined, which grows exponentially with the number of agents involved. To date, therefore, many algorithms have been proposed to solve this problem using different techniques–ranging from dynamic programming, to integer programming, to stochastic search – all of which suffer from major limitations relating to execution time, solution quality, and memory requirements. With this in mind, we develop an anytime algorithm to solve the coalition structure generation problem. Specifically, the algorithm uses a novel representation of the search space, which partitions the space of possible solutions into sub-spaces such that it is possible to compute upper and lower bounds on the values of the best coalition structures in them. These bounds are then used to identify the sub-spaces that have no potential of containing the optimal solution so that they can be pruned. The algorithm, then, searches through the remaining sub-spaces very efficiently using a branch-and-bound technique to avoid examining all the solutions within the searched subspace(s). In this setting, we prove that our algorithm enumerates all coalition structures efficiently by avoiding redundant and invalid solutions automatically. Moreover, in order to effectively test our algorithm we develop a new type of input distribution which allows us to generate more reliable benchmarks compared to the input distributions previously used in the field. Given this new distribution, we show that for 27 agents our algorithm is able to find solutions that are optimal in 0:175% of the time required by the fastest available algorithm in the literature. The algorithm is anytime, and if interrupted before it would have normally terminated, it can still provide a solution that is guaranteed to be within a bound from the optimal one. Moreover, the guarantees we provide on the quality of the solution are significantly better than those provided by the previous state of the art algorithms designed for this purpose. For example, for the worst case distribution given 25 agents, our algorithm is able to find a 90% efficient solution in around 10% of time it takes to find the optimal solution.
2007
Rahwan, Talal; Ramchurn, Sarvapali D.; Dang, Viet D.; Giovannucci, Andrea; Jennings, N. R.
Anytime Optimal Coalition Structure Generation Proceedings Article
In: 22nd Conference on Artificial Intelligence (AAAI), pp. 1184–1190, 2007.
@inproceedings{eps263433,
title = {Anytime Optimal Coalition Structure Generation},
author = {Talal Rahwan and Sarvapali D. Ramchurn and Viet D. Dang and Andrea Giovannucci and N. R. Jennings},
url = {http://eprints.soton.ac.uk/263433/},
year = {2007},
date = {2007-01-01},
booktitle = {22nd Conference on Artificial Intelligence (AAAI)},
pages = {1184–1190},
abstract = {Forming effective coalitions is a major research challenge in the field of multi-agent systems. Central to this endeavour is the problem of determining the best groups of agents to select to achieve some goal. To this end, in this paper, we present a novel, optimal anytime algorithm for this coalition structure generation problem that is significantly faster than previous algorithms designed for this purpose. Specifically, our algorithm can generate solutions by partitioning the space of all potential coalitions into sub-spaces that contain coalition structures that are similar, according to some criterion, such that these sub-spaces can be pruned by identifying their bounds. Using this representation, the algorithm then searches through only valid and unique coalition structures and selects the best among them using a branch-and-bound technique. We empirically show that we are able to find solutions that are optimal in 0.082% of the time taken by the state of the art dynamic programming algorithm (for 27 agents) using much less memory (O(2^ n) instead of O(3^ n) for the set of n agents). Moreover, our algorithm is the first to be able to solve the coalition structure generation problem for numbers of agents bigger than 27 in reasonable time (less than 90 minutes for 27 agents as opposed to around 2 months for the best previous solution).},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
Forming effective coalitions is a major research challenge in the field of multi-agent systems. Central to this endeavour is the problem of determining the best groups of agents to select to achieve some goal. To this end, in this paper, we present a novel, optimal anytime algorithm for this coalition structure generation problem that is significantly faster than previous algorithms designed for this purpose. Specifically, our algorithm can generate solutions by partitioning the space of all potential coalitions into sub-spaces that contain coalition structures that are similar, according to some criterion, such that these sub-spaces can be pruned by identifying their bounds. Using this representation, the algorithm then searches through only valid and unique coalition structures and selects the best among them using a branch-and-bound technique. We empirically show that we are able to find solutions that are optimal in 0.082% of the time taken by the state of the art dynamic programming algorithm (for 27 agents) using much less memory (O(2^ n) instead of O(3^ n) for the set of n agents). Moreover, our algorithm is the first to be able to solve the coalition structure generation problem for numbers of agents bigger than 27 in reasonable time (less than 90 minutes for 27 agents as opposed to around 2 months for the best previous solution).
0000
Bistaffa, Jesús Cerquides Alessandro Farinelli Filippo; Ramchurn, Sarvapali D.
Algorithms for Graph-Constrained Coalition Formation in the Real World Journal Article
In: ACM Transactions on Intelligent Systems and Technology (TIST), vol. 8, no. 4, 0000.
@article{bistaffaetal2017,
title = {Algorithms for Graph-Constrained Coalition Formation in the Real World},
author = {Jesús Cerquides Alessandro Farinelli Filippo Bistaffa and Sarvapali D. Ramchurn},
doi = {http://dx.doi.org/10.1145/3040967},
journal = {ACM Transactions on Intelligent Systems and Technology (TIST)},
volume = {8},
number = {4},
keywords = {},
pubstate = {published},
tppubtype = {article}
}