Gopal
Gopal
Gopal
Gopal
Gopal
Gopal
Gopal
Gopal
Gopal
Gopal
font
Filter
×
2015
Rigas, Nick Bassiliades Sarvapali D. Ramchurn Emmanouil
Managing Electric Vehicles in the Smart Grid Using Artificial Intelligence: A Survey Journal Article
In: IEEE Transactions on Intelligent Transportation Systems, 2015.
Abstract | Links | BibTeX | Tags: Electric Vehicles, electricity, Energy, Multi-agent scheduling, Survey
@article{rigas:etal:2015,
title = {Managing Electric Vehicles in the Smart Grid Using Artificial Intelligence: A Survey},
author = {Nick Bassiliades Sarvapali D. Ramchurn Emmanouil Rigas},
url = {http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=7000557&filter%3DAND%28p_IS_Number%3A7174612%29},
year = {2015},
date = {2015-01-16},
journal = {IEEE Transactions on Intelligent Transportation Systems},
abstract = {Along with the development of Smart Grids, the wide adoption of Electric Vehicles (EVs) is seen as a catalyst to the reduction of CO2 emissions and more intelligent transportation systems. In particular, EVs augment the grid with the ability to store energy at some points in the network and give it back at others and therefore help optimise the use of energy from intermittent renewable energy sources and let users refill their cars in a variety of locations. However, a number of challenges need to be addressed if such benefits are to be achieved. On the one hand, given their limited range and costs involved in charging EV batteries, it is important to design algorithms that will minimise costs while avoid users being stranded. On the other hand, collectives of EVs need to be organized in such a way as to avoid peaks on the grid that may result in high electricity prices and overload local distribution grids. In order to meet such challenges, a number of technological solutions have been proposed. In this paper, we focus on those that utilise artificial intelligence techniques to render EVs and the systems that manage collectives of EVs smarter. In particular, we provide a survey of the literature and identify the commonalities and key differences in the approaches. This allows us to develop a classification of key techniques and benchmarks that can be used to advance the state-of-the art in this space.},
keywords = {Electric Vehicles, electricity, Energy, Multi-agent scheduling, Survey},
pubstate = {published},
tppubtype = {article}
}
Along with the development of Smart Grids, the wide adoption of Electric Vehicles (EVs) is seen as a catalyst to the reduction of CO2 emissions and more intelligent transportation systems. In particular, EVs augment the grid with the ability to store energy at some points in the network and give it back at others and therefore help optimise the use of energy from intermittent renewable energy sources and let users refill their cars in a variety of locations. However, a number of challenges need to be addressed if such benefits are to be achieved. On the one hand, given their limited range and costs involved in charging EV batteries, it is important to design algorithms that will minimise costs while avoid users being stranded. On the other hand, collectives of EVs need to be organized in such a way as to avoid peaks on the grid that may result in high electricity prices and overload local distribution grids. In order to meet such challenges, a number of technological solutions have been proposed. In this paper, we focus on those that utilise artificial intelligence techniques to render EVs and the systems that manage collectives of EVs smarter. In particular, we provide a survey of the literature and identify the commonalities and key differences in the approaches. This allows us to develop a classification of key techniques and benchmarks that can be used to advance the state-of-the art in this space.
2013
Alam, Muddasser; Rogers, Alex; Ramchurn, Sarvapali D.
Interdependent multi-issue negotiation for energy exchange in remote communities Proceedings Article
In: International Workshop on AI Problems and Approaches for Intelligent Environments (AI4IE), 2013.
Links | BibTeX | Tags: cooperative exchange, Energy, home energy management, mas, Multi-agent scheduling, smart home
@inproceedings{eps357186,
title = {Interdependent multi-issue negotiation for energy exchange in remote communities},
author = {Muddasser Alam and Alex Rogers and Sarvapali D. Ramchurn},
url = {http://eprints.soton.ac.uk/357186/},
year = {2013},
date = {2013-01-01},
booktitle = {International Workshop on AI Problems and Approaches for Intelligent Environments (AI4IE)},
keywords = {cooperative exchange, Energy, home energy management, mas, Multi-agent scheduling, smart home},
pubstate = {published},
tppubtype = {inproceedings}
}
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.
2011
Macarthur, Kathryn; Stranders, Ruben; Ramchurn, Sarvapali; Jennings, Nick
A Distributed Anytime Algorithm for Dynamic Task Allocation in Multi-Agent Systems Proceedings Article
In: Twenty-Fifth Conference on Artificial Intelligence (AAAI), pp. 701–706, AAAI Press, 2011, (Event Dates: August 7-11, 2011).
Abstract | Links | BibTeX | Tags: mas, Multi-agent scheduling, multi-agent systems
@inproceedings{eps272233,
title = {A Distributed Anytime Algorithm for Dynamic Task Allocation in Multi-Agent Systems},
author = {Kathryn Macarthur and Ruben Stranders and Sarvapali Ramchurn and Nick Jennings},
url = {http://eprints.soton.ac.uk/272233/},
year = {2011},
date = {2011-01-01},
booktitle = {Twenty-Fifth Conference on Artificial Intelligence (AAAI)},
pages = {701–706},
publisher = {AAAI Press},
abstract = {We introduce a novel distributed algorithm for multi-agent task allocation problems where the sets of tasks and agents constantly change over time. We build on an existing anytime algorithm (fast-max-sum), and give it significant new capa- bilities: namely, an online pruning procedure that simplifies the problem, and a branch-and-bound technique that reduces the search space. This allows us to scale to problems with hundreds of tasks and agents. We empirically evaluate our algorithm against established benchmarks and find that, even in such large environments, a solution is found up to 31% faster, and with up to 23% more utility, than state-of-the-art approximation algorithms. In addition, our algorithm sends up to 30% fewer messages than current approaches when the set of agents or tasks changes.},
note = {Event Dates: August 7-11, 2011},
keywords = {mas, Multi-agent scheduling, multi-agent systems},
pubstate = {published},
tppubtype = {inproceedings}
}
We introduce a novel distributed algorithm for multi-agent task allocation problems where the sets of tasks and agents constantly change over time. We build on an existing anytime algorithm (fast-max-sum), and give it significant new capa- bilities: namely, an online pruning procedure that simplifies the problem, and a branch-and-bound technique that reduces the search space. This allows us to scale to problems with hundreds of tasks and agents. We empirically evaluate our algorithm against established benchmarks and find that, even in such large environments, a solution is found up to 31% faster, and with up to 23% more utility, than state-of-the-art approximation algorithms. In addition, our algorithm sends up to 30% fewer messages than current approaches when the set of agents or tasks changes.
Macarthur, Kathryn; Vinyals, Meritxell; Farinelli, Alessandro; Ramchurn, Sarvapali; Jennings, Nick
Decentralised Parallel Machine Scheduling for Multi-Agent Task Allocation Proceedings Article
In: Fourth International Workshop on Optimisation in Multi-Agent Systems, 2011, (Event Dates: May 3, 2011).
Abstract | Links | BibTeX | Tags: mas, Multi-agent scheduling, multi-agent systems
@inproceedings{eps272234,
title = {Decentralised Parallel Machine Scheduling for Multi-Agent Task Allocation},
author = {Kathryn Macarthur and Meritxell Vinyals and Alessandro Farinelli and Sarvapali Ramchurn and Nick Jennings},
url = {http://eprints.soton.ac.uk/272234/},
year = {2011},
date = {2011-01-01},
booktitle = {Fourth International Workshop on Optimisation in Multi-Agent Systems},
abstract = {Multi-agent task allocation problems pervade a wide range of real-world applications, such as search and rescue in disaster manage- ment, or grid computing. In these applications, where agents are given tasks to perform in parallel, it is often the case that the performance of all agents is judged based on the time taken by the slowest agent to complete its tasks. Hence, efficient distribution of tasks across het- erogeneous agents is important to ensure a short completion time. An equivalent problem to this can be found in operations research, and is known as scheduling jobs on unrelated parallel machines (also known as Rensuremath|ensuremath|Cmax). In this paper, we draw parallels between unrelated parallel machine scheduling and multi-agent task allocation problems, and, in so doing, we present the decentralised task distribution algorithm (DTDA), the first decentralised solution to Rensuremath|ensuremath|Cmax. Empirical evaluation of the DTDA is shown to generate solutions within 86?97% of the optimal on sparse graphs, in the best case, whilst providing a very good estimate (within 1%) of the global solution at each agent.},
note = {Event Dates: May 3, 2011},
keywords = {mas, Multi-agent scheduling, multi-agent systems},
pubstate = {published},
tppubtype = {inproceedings}
}
Multi-agent task allocation problems pervade a wide range of real-world applications, such as search and rescue in disaster manage- ment, or grid computing. In these applications, where agents are given tasks to perform in parallel, it is often the case that the performance of all agents is judged based on the time taken by the slowest agent to complete its tasks. Hence, efficient distribution of tasks across het- erogeneous agents is important to ensure a short completion time. An equivalent problem to this can be found in operations research, and is known as scheduling jobs on unrelated parallel machines (also known as Rensuremath|ensuremath|Cmax). In this paper, we draw parallels between unrelated parallel machine scheduling and multi-agent task allocation problems, and, in so doing, we present the decentralised task distribution algorithm (DTDA), the first decentralised solution to Rensuremath|ensuremath|Cmax. Empirical evaluation of the DTDA is shown to generate solutions within 86?97% of the optimal on sparse graphs, in the best case, whilst providing a very good estimate (within 1%) of the global solution at each agent.
2010
Macarthur, Kathryn; Farinelli, Alessandro; Ramchurn, Sarvapali; Jennings, Nick
Efficient, Superstabilizing Decentralised Optimisation for Dynamic Task Allocation Environments Proceedings Article
In: Third International Workshop on: Optimisation in Multi-Agent Systems (OptMas) at the Ninth Joint Conference on Autonomous and Multi-Agent Systems, pp. 25–32, 2010, (Event Dates: 10 May 2010).
Abstract | Links | BibTeX | Tags: agents, Disaster Management, mas, Multi-agent scheduling, multi-agent systems
@inproceedings{eps268588,
title = {Efficient, Superstabilizing Decentralised Optimisation for Dynamic Task Allocation Environments},
author = {Kathryn Macarthur and Alessandro Farinelli and Sarvapali Ramchurn and Nick Jennings},
url = {http://eprints.soton.ac.uk/268588/},
year = {2010},
date = {2010-01-01},
booktitle = {Third International Workshop on: Optimisation in Multi-Agent Systems (OptMas) at the Ninth Joint Conference on Autonomous and Multi-Agent Systems},
pages = {25–32},
abstract = {Decentralised optimisation is a key issue for multi-agent systems, and while many solution techniques have been developed, few provide support for dynamic environments, which change over time, such as disaster management. Given this, in this paper, we present Bounded Fast Max Sum (BFMS): a novel, dynamic, superstabilizing algorithm which provides a bounded approximate solution to certain classes of distributed constraint optimisation problems. We achieve this by eliminating dependencies in the constraint functions, according to how much impact they have on the overall solution value. In more detail, we propose iGHS, which computes a maximum spanning tree on subsections of the constraint graph, in order to reduce communication and computation overheads. Given this, we empirically evaluate BFMS, which shows that BFMS reduces communication and computation done by Bounded Max Sum by up to 99%, while obtaining 60-88% of the optimal utility.},
note = {Event Dates: 10 May 2010},
keywords = {agents, Disaster Management, mas, Multi-agent scheduling, multi-agent systems},
pubstate = {published},
tppubtype = {inproceedings}
}
Decentralised optimisation is a key issue for multi-agent systems, and while many solution techniques have been developed, few provide support for dynamic environments, which change over time, such as disaster management. Given this, in this paper, we present Bounded Fast Max Sum (BFMS): a novel, dynamic, superstabilizing algorithm which provides a bounded approximate solution to certain classes of distributed constraint optimisation problems. We achieve this by eliminating dependencies in the constraint functions, according to how much impact they have on the overall solution value. In more detail, we propose iGHS, which computes a maximum spanning tree on subsections of the constraint graph, in order to reduce communication and computation overheads. Given this, we empirically evaluate BFMS, which shows that BFMS reduces communication and computation done by Bounded Max Sum by up to 99%, while obtaining 60-88% of the optimal utility.
Ramchurn, 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.
Ramchurn, Sarvapali; Farinelli, Alessandro; Macarthur, Kathryn; Polukarov, Mariya; Jennings, Nick
Decentralised Coordination in RoboCup Rescue Journal Article
In: The Computer Journal, vol. 53, no. 9, pp. 1–15, 2010.
Abstract | Links | BibTeX | Tags: Disaster Management, mas, Multi-agent scheduling, multi-agent systems
@article{eps268499,
title = {Decentralised Coordination in RoboCup Rescue},
author = {Sarvapali Ramchurn and Alessandro Farinelli and Kathryn Macarthur and Mariya Polukarov and Nick Jennings},
url = {http://eprints.soton.ac.uk/268499/},
year = {2010},
date = {2010-01-01},
journal = {The Computer Journal},
volume = {53},
number = {9},
pages = {1–15},
publisher = {Oxford Journals},
abstract = {Emergency responders are faced with a number of significant challenges when managing major disasters. First, the number of rescue tasks posed is usually larger than the number of responders (or agents) and the resources available to them. Second, each task is likely to require a different level of effort in order to be completed by its deadline. Third, new tasks may continually appear or disappear from the environment, thus requiring the responders to quickly recompute their allocation of resources. Fourth, forming teams or coalitions of multiple agents from different agencies is vital since no single agency will have all the resources needed to save victims, unblock roads, and extinguish the ?res which might erupt in the disaster space. Given this, coalitions have to be efficiently selected and scheduled to work across the disaster space so as to maximise the number of lives and the portion of the infrastructure saved. In particular, it is important that the selection of such coalitions should be performed in a decentralised fashion in order to avoid a single point of failure in the system. Moreover, it is critical that responders communicate only locally given they are likely to have limited battery power or minimal access to long range communication devices. Against this background, we provide a novel decentralised solution to the coalition formation process that pervades disaster management. More specifically, we model the emergency management scenario defined in the RoboCup Rescue disaster simulation platform as a Coalition Formation with Spatial and Temporal constraints (CFST) problem where agents form coalitions in order to complete tasks, each with different demands. In order to design a decentralised algorithm for CFST we formulate it as a Distributed Constraint Optimisation problem and show how to solve it using the state-of-the-art Max-Sum algorithm that provides a completely decentralised message-passing solution. We then provide a novel algorithm (F-Max-Sum) that avoids sending redundant messages and efficiently adapts to changes in the environment. In empirical evaluations, our algorithm is shown to generate better solutions than other decentralised algorithms used for this problem.},
keywords = {Disaster Management, mas, Multi-agent scheduling, multi-agent systems},
pubstate = {published},
tppubtype = {article}
}
Emergency responders are faced with a number of significant challenges when managing major disasters. First, the number of rescue tasks posed is usually larger than the number of responders (or agents) and the resources available to them. Second, each task is likely to require a different level of effort in order to be completed by its deadline. Third, new tasks may continually appear or disappear from the environment, thus requiring the responders to quickly recompute their allocation of resources. Fourth, forming teams or coalitions of multiple agents from different agencies is vital since no single agency will have all the resources needed to save victims, unblock roads, and extinguish the ?res which might erupt in the disaster space. Given this, coalitions have to be efficiently selected and scheduled to work across the disaster space so as to maximise the number of lives and the portion of the infrastructure saved. In particular, it is important that the selection of such coalitions should be performed in a decentralised fashion in order to avoid a single point of failure in the system. Moreover, it is critical that responders communicate only locally given they are likely to have limited battery power or minimal access to long range communication devices. Against this background, we provide a novel decentralised solution to the coalition formation process that pervades disaster management. More specifically, we model the emergency management scenario defined in the RoboCup Rescue disaster simulation platform as a Coalition Formation with Spatial and Temporal constraints (CFST) problem where agents form coalitions in order to complete tasks, each with different demands. In order to design a decentralised algorithm for CFST we formulate it as a Distributed Constraint Optimisation problem and show how to solve it using the state-of-the-art Max-Sum algorithm that provides a completely decentralised message-passing solution. We then provide a novel algorithm (F-Max-Sum) that avoids sending redundant messages and efficiently adapts to changes in the environment. In empirical evaluations, our algorithm is shown to generate better solutions than other decentralised algorithms used for this problem.
1.
Rigas, Nick Bassiliades Sarvapali D. Ramchurn Emmanouil
Managing Electric Vehicles in the Smart Grid Using Artificial Intelligence: A Survey Journal Article
In: IEEE Transactions on Intelligent Transportation Systems, 2015.
@article{rigas:etal:2015,
title = {Managing Electric Vehicles in the Smart Grid Using Artificial Intelligence: A Survey},
author = {Nick Bassiliades Sarvapali D. Ramchurn Emmanouil Rigas},
url = {http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=7000557&filter%3DAND%28p_IS_Number%3A7174612%29},
year = {2015},
date = {2015-01-16},
journal = {IEEE Transactions on Intelligent Transportation Systems},
abstract = {Along with the development of Smart Grids, the wide adoption of Electric Vehicles (EVs) is seen as a catalyst to the reduction of CO2 emissions and more intelligent transportation systems. In particular, EVs augment the grid with the ability to store energy at some points in the network and give it back at others and therefore help optimise the use of energy from intermittent renewable energy sources and let users refill their cars in a variety of locations. However, a number of challenges need to be addressed if such benefits are to be achieved. On the one hand, given their limited range and costs involved in charging EV batteries, it is important to design algorithms that will minimise costs while avoid users being stranded. On the other hand, collectives of EVs need to be organized in such a way as to avoid peaks on the grid that may result in high electricity prices and overload local distribution grids. In order to meet such challenges, a number of technological solutions have been proposed. In this paper, we focus on those that utilise artificial intelligence techniques to render EVs and the systems that manage collectives of EVs smarter. In particular, we provide a survey of the literature and identify the commonalities and key differences in the approaches. This allows us to develop a classification of key techniques and benchmarks that can be used to advance the state-of-the art in this space.},
keywords = {},
pubstate = {published},
tppubtype = {article}
}
Along with the development of Smart Grids, the wide adoption of Electric Vehicles (EVs) is seen as a catalyst to the reduction of CO2 emissions and more intelligent transportation systems. In particular, EVs augment the grid with the ability to store energy at some points in the network and give it back at others and therefore help optimise the use of energy from intermittent renewable energy sources and let users refill their cars in a variety of locations. However, a number of challenges need to be addressed if such benefits are to be achieved. On the one hand, given their limited range and costs involved in charging EV batteries, it is important to design algorithms that will minimise costs while avoid users being stranded. On the other hand, collectives of EVs need to be organized in such a way as to avoid peaks on the grid that may result in high electricity prices and overload local distribution grids. In order to meet such challenges, a number of technological solutions have been proposed. In this paper, we focus on those that utilise artificial intelligence techniques to render EVs and the systems that manage collectives of EVs smarter. In particular, we provide a survey of the literature and identify the commonalities and key differences in the approaches. This allows us to develop a classification of key techniques and benchmarks that can be used to advance the state-of-the art in this space.
2.
Alam, Muddasser; Rogers, Alex; Ramchurn, Sarvapali D.
Interdependent multi-issue negotiation for energy exchange in remote communities Proceedings Article
In: International Workshop on AI Problems and Approaches for Intelligent Environments (AI4IE), 2013.
@inproceedings{eps357186,
title = {Interdependent multi-issue negotiation for energy exchange in remote communities},
author = {Muddasser Alam and Alex Rogers and Sarvapali D. Ramchurn},
url = {http://eprints.soton.ac.uk/357186/},
year = {2013},
date = {2013-01-01},
booktitle = {International Workshop on AI Problems and Approaches for Intelligent Environments (AI4IE)},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
3.
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.
4.
Macarthur, Kathryn; Stranders, Ruben; Ramchurn, Sarvapali; Jennings, Nick
A Distributed Anytime Algorithm for Dynamic Task Allocation in Multi-Agent Systems Proceedings Article
In: Twenty-Fifth Conference on Artificial Intelligence (AAAI), pp. 701–706, AAAI Press, 2011, (Event Dates: August 7-11, 2011).
@inproceedings{eps272233,
title = {A Distributed Anytime Algorithm for Dynamic Task Allocation in Multi-Agent Systems},
author = {Kathryn Macarthur and Ruben Stranders and Sarvapali Ramchurn and Nick Jennings},
url = {http://eprints.soton.ac.uk/272233/},
year = {2011},
date = {2011-01-01},
booktitle = {Twenty-Fifth Conference on Artificial Intelligence (AAAI)},
pages = {701–706},
publisher = {AAAI Press},
abstract = {We introduce a novel distributed algorithm for multi-agent task allocation problems where the sets of tasks and agents constantly change over time. We build on an existing anytime algorithm (fast-max-sum), and give it significant new capa- bilities: namely, an online pruning procedure that simplifies the problem, and a branch-and-bound technique that reduces the search space. This allows us to scale to problems with hundreds of tasks and agents. We empirically evaluate our algorithm against established benchmarks and find that, even in such large environments, a solution is found up to 31% faster, and with up to 23% more utility, than state-of-the-art approximation algorithms. In addition, our algorithm sends up to 30% fewer messages than current approaches when the set of agents or tasks changes.},
note = {Event Dates: August 7-11, 2011},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
We introduce a novel distributed algorithm for multi-agent task allocation problems where the sets of tasks and agents constantly change over time. We build on an existing anytime algorithm (fast-max-sum), and give it significant new capa- bilities: namely, an online pruning procedure that simplifies the problem, and a branch-and-bound technique that reduces the search space. This allows us to scale to problems with hundreds of tasks and agents. We empirically evaluate our algorithm against established benchmarks and find that, even in such large environments, a solution is found up to 31% faster, and with up to 23% more utility, than state-of-the-art approximation algorithms. In addition, our algorithm sends up to 30% fewer messages than current approaches when the set of agents or tasks changes.
5.
Macarthur, Kathryn; Vinyals, Meritxell; Farinelli, Alessandro; Ramchurn, Sarvapali; Jennings, Nick
Decentralised Parallel Machine Scheduling for Multi-Agent Task Allocation Proceedings Article
In: Fourth International Workshop on Optimisation in Multi-Agent Systems, 2011, (Event Dates: May 3, 2011).
@inproceedings{eps272234,
title = {Decentralised Parallel Machine Scheduling for Multi-Agent Task Allocation},
author = {Kathryn Macarthur and Meritxell Vinyals and Alessandro Farinelli and Sarvapali Ramchurn and Nick Jennings},
url = {http://eprints.soton.ac.uk/272234/},
year = {2011},
date = {2011-01-01},
booktitle = {Fourth International Workshop on Optimisation in Multi-Agent Systems},
abstract = {Multi-agent task allocation problems pervade a wide range of real-world applications, such as search and rescue in disaster manage- ment, or grid computing. In these applications, where agents are given tasks to perform in parallel, it is often the case that the performance of all agents is judged based on the time taken by the slowest agent to complete its tasks. Hence, efficient distribution of tasks across het- erogeneous agents is important to ensure a short completion time. An equivalent problem to this can be found in operations research, and is known as scheduling jobs on unrelated parallel machines (also known as Rensuremath|ensuremath|Cmax). In this paper, we draw parallels between unrelated parallel machine scheduling and multi-agent task allocation problems, and, in so doing, we present the decentralised task distribution algorithm (DTDA), the first decentralised solution to Rensuremath|ensuremath|Cmax. Empirical evaluation of the DTDA is shown to generate solutions within 86?97% of the optimal on sparse graphs, in the best case, whilst providing a very good estimate (within 1%) of the global solution at each agent.},
note = {Event Dates: May 3, 2011},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
Multi-agent task allocation problems pervade a wide range of real-world applications, such as search and rescue in disaster manage- ment, or grid computing. In these applications, where agents are given tasks to perform in parallel, it is often the case that the performance of all agents is judged based on the time taken by the slowest agent to complete its tasks. Hence, efficient distribution of tasks across het- erogeneous agents is important to ensure a short completion time. An equivalent problem to this can be found in operations research, and is known as scheduling jobs on unrelated parallel machines (also known as Rensuremath|ensuremath|Cmax). In this paper, we draw parallels between unrelated parallel machine scheduling and multi-agent task allocation problems, and, in so doing, we present the decentralised task distribution algorithm (DTDA), the first decentralised solution to Rensuremath|ensuremath|Cmax. Empirical evaluation of the DTDA is shown to generate solutions within 86?97% of the optimal on sparse graphs, in the best case, whilst providing a very good estimate (within 1%) of the global solution at each agent.
6.
Macarthur, Kathryn; Farinelli, Alessandro; Ramchurn, Sarvapali; Jennings, Nick
Efficient, Superstabilizing Decentralised Optimisation for Dynamic Task Allocation Environments Proceedings Article
In: Third International Workshop on: Optimisation in Multi-Agent Systems (OptMas) at the Ninth Joint Conference on Autonomous and Multi-Agent Systems, pp. 25–32, 2010, (Event Dates: 10 May 2010).
@inproceedings{eps268588,
title = {Efficient, Superstabilizing Decentralised Optimisation for Dynamic Task Allocation Environments},
author = {Kathryn Macarthur and Alessandro Farinelli and Sarvapali Ramchurn and Nick Jennings},
url = {http://eprints.soton.ac.uk/268588/},
year = {2010},
date = {2010-01-01},
booktitle = {Third International Workshop on: Optimisation in Multi-Agent Systems (OptMas) at the Ninth Joint Conference on Autonomous and Multi-Agent Systems},
pages = {25–32},
abstract = {Decentralised optimisation is a key issue for multi-agent systems, and while many solution techniques have been developed, few provide support for dynamic environments, which change over time, such as disaster management. Given this, in this paper, we present Bounded Fast Max Sum (BFMS): a novel, dynamic, superstabilizing algorithm which provides a bounded approximate solution to certain classes of distributed constraint optimisation problems. We achieve this by eliminating dependencies in the constraint functions, according to how much impact they have on the overall solution value. In more detail, we propose iGHS, which computes a maximum spanning tree on subsections of the constraint graph, in order to reduce communication and computation overheads. Given this, we empirically evaluate BFMS, which shows that BFMS reduces communication and computation done by Bounded Max Sum by up to 99%, while obtaining 60-88% of the optimal utility.},
note = {Event Dates: 10 May 2010},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
Decentralised optimisation is a key issue for multi-agent systems, and while many solution techniques have been developed, few provide support for dynamic environments, which change over time, such as disaster management. Given this, in this paper, we present Bounded Fast Max Sum (BFMS): a novel, dynamic, superstabilizing algorithm which provides a bounded approximate solution to certain classes of distributed constraint optimisation problems. We achieve this by eliminating dependencies in the constraint functions, according to how much impact they have on the overall solution value. In more detail, we propose iGHS, which computes a maximum spanning tree on subsections of the constraint graph, in order to reduce communication and computation overheads. Given this, we empirically evaluate BFMS, which shows that BFMS reduces communication and computation done by Bounded Max Sum by up to 99%, while obtaining 60-88% of the optimal utility.
7.
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.
8.
Ramchurn, Sarvapali; Farinelli, Alessandro; Macarthur, Kathryn; Polukarov, Mariya; Jennings, Nick
Decentralised Coordination in RoboCup Rescue Journal Article
In: The Computer Journal, vol. 53, no. 9, pp. 1–15, 2010.
@article{eps268499,
title = {Decentralised Coordination in RoboCup Rescue},
author = {Sarvapali Ramchurn and Alessandro Farinelli and Kathryn Macarthur and Mariya Polukarov and Nick Jennings},
url = {http://eprints.soton.ac.uk/268499/},
year = {2010},
date = {2010-01-01},
journal = {The Computer Journal},
volume = {53},
number = {9},
pages = {1–15},
publisher = {Oxford Journals},
abstract = {Emergency responders are faced with a number of significant challenges when managing major disasters. First, the number of rescue tasks posed is usually larger than the number of responders (or agents) and the resources available to them. Second, each task is likely to require a different level of effort in order to be completed by its deadline. Third, new tasks may continually appear or disappear from the environment, thus requiring the responders to quickly recompute their allocation of resources. Fourth, forming teams or coalitions of multiple agents from different agencies is vital since no single agency will have all the resources needed to save victims, unblock roads, and extinguish the ?res which might erupt in the disaster space. Given this, coalitions have to be efficiently selected and scheduled to work across the disaster space so as to maximise the number of lives and the portion of the infrastructure saved. In particular, it is important that the selection of such coalitions should be performed in a decentralised fashion in order to avoid a single point of failure in the system. Moreover, it is critical that responders communicate only locally given they are likely to have limited battery power or minimal access to long range communication devices. Against this background, we provide a novel decentralised solution to the coalition formation process that pervades disaster management. More specifically, we model the emergency management scenario defined in the RoboCup Rescue disaster simulation platform as a Coalition Formation with Spatial and Temporal constraints (CFST) problem where agents form coalitions in order to complete tasks, each with different demands. In order to design a decentralised algorithm for CFST we formulate it as a Distributed Constraint Optimisation problem and show how to solve it using the state-of-the-art Max-Sum algorithm that provides a completely decentralised message-passing solution. We then provide a novel algorithm (F-Max-Sum) that avoids sending redundant messages and efficiently adapts to changes in the environment. In empirical evaluations, our algorithm is shown to generate better solutions than other decentralised algorithms used for this problem.},
keywords = {},
pubstate = {published},
tppubtype = {article}
}
Emergency responders are faced with a number of significant challenges when managing major disasters. First, the number of rescue tasks posed is usually larger than the number of responders (or agents) and the resources available to them. Second, each task is likely to require a different level of effort in order to be completed by its deadline. Third, new tasks may continually appear or disappear from the environment, thus requiring the responders to quickly recompute their allocation of resources. Fourth, forming teams or coalitions of multiple agents from different agencies is vital since no single agency will have all the resources needed to save victims, unblock roads, and extinguish the ?res which might erupt in the disaster space. Given this, coalitions have to be efficiently selected and scheduled to work across the disaster space so as to maximise the number of lives and the portion of the infrastructure saved. In particular, it is important that the selection of such coalitions should be performed in a decentralised fashion in order to avoid a single point of failure in the system. Moreover, it is critical that responders communicate only locally given they are likely to have limited battery power or minimal access to long range communication devices. Against this background, we provide a novel decentralised solution to the coalition formation process that pervades disaster management. More specifically, we model the emergency management scenario defined in the RoboCup Rescue disaster simulation platform as a Coalition Formation with Spatial and Temporal constraints (CFST) problem where agents form coalitions in order to complete tasks, each with different demands. In order to design a decentralised algorithm for CFST we formulate it as a Distributed Constraint Optimisation problem and show how to solve it using the state-of-the-art Max-Sum algorithm that provides a completely decentralised message-passing solution. We then provide a novel algorithm (F-Max-Sum) that avoids sending redundant messages and efficiently adapts to changes in the environment. In empirical evaluations, our algorithm is shown to generate better solutions than other decentralised algorithms used for this problem.
2015
Rigas, Nick Bassiliades Sarvapali D. Ramchurn Emmanouil
Managing Electric Vehicles in the Smart Grid Using Artificial Intelligence: A Survey Journal Article
In: IEEE Transactions on Intelligent Transportation Systems, 2015.
Abstract | Links | BibTeX | Tags: Electric Vehicles, electricity, Energy, Multi-agent scheduling, Survey
@article{rigas:etal:2015,
title = {Managing Electric Vehicles in the Smart Grid Using Artificial Intelligence: A Survey},
author = {Nick Bassiliades Sarvapali D. Ramchurn Emmanouil Rigas},
url = {http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=7000557&filter%3DAND%28p_IS_Number%3A7174612%29},
year = {2015},
date = {2015-01-16},
journal = {IEEE Transactions on Intelligent Transportation Systems},
abstract = {Along with the development of Smart Grids, the wide adoption of Electric Vehicles (EVs) is seen as a catalyst to the reduction of CO2 emissions and more intelligent transportation systems. In particular, EVs augment the grid with the ability to store energy at some points in the network and give it back at others and therefore help optimise the use of energy from intermittent renewable energy sources and let users refill their cars in a variety of locations. However, a number of challenges need to be addressed if such benefits are to be achieved. On the one hand, given their limited range and costs involved in charging EV batteries, it is important to design algorithms that will minimise costs while avoid users being stranded. On the other hand, collectives of EVs need to be organized in such a way as to avoid peaks on the grid that may result in high electricity prices and overload local distribution grids. In order to meet such challenges, a number of technological solutions have been proposed. In this paper, we focus on those that utilise artificial intelligence techniques to render EVs and the systems that manage collectives of EVs smarter. In particular, we provide a survey of the literature and identify the commonalities and key differences in the approaches. This allows us to develop a classification of key techniques and benchmarks that can be used to advance the state-of-the art in this space.},
keywords = {Electric Vehicles, electricity, Energy, Multi-agent scheduling, Survey},
pubstate = {published},
tppubtype = {article}
}
Along with the development of Smart Grids, the wide adoption of Electric Vehicles (EVs) is seen as a catalyst to the reduction of CO2 emissions and more intelligent transportation systems. In particular, EVs augment the grid with the ability to store energy at some points in the network and give it back at others and therefore help optimise the use of energy from intermittent renewable energy sources and let users refill their cars in a variety of locations. However, a number of challenges need to be addressed if such benefits are to be achieved. On the one hand, given their limited range and costs involved in charging EV batteries, it is important to design algorithms that will minimise costs while avoid users being stranded. On the other hand, collectives of EVs need to be organized in such a way as to avoid peaks on the grid that may result in high electricity prices and overload local distribution grids. In order to meet such challenges, a number of technological solutions have been proposed. In this paper, we focus on those that utilise artificial intelligence techniques to render EVs and the systems that manage collectives of EVs smarter. In particular, we provide a survey of the literature and identify the commonalities and key differences in the approaches. This allows us to develop a classification of key techniques and benchmarks that can be used to advance the state-of-the art in this space.
2013
Alam, Muddasser; Rogers, Alex; Ramchurn, Sarvapali D.
Interdependent multi-issue negotiation for energy exchange in remote communities Proceedings Article
In: International Workshop on AI Problems and Approaches for Intelligent Environments (AI4IE), 2013.
Links | BibTeX | Tags: cooperative exchange, Energy, home energy management, mas, Multi-agent scheduling, smart home
@inproceedings{eps357186,
title = {Interdependent multi-issue negotiation for energy exchange in remote communities},
author = {Muddasser Alam and Alex Rogers and Sarvapali D. Ramchurn},
url = {http://eprints.soton.ac.uk/357186/},
year = {2013},
date = {2013-01-01},
booktitle = {International Workshop on AI Problems and Approaches for Intelligent Environments (AI4IE)},
keywords = {cooperative exchange, Energy, home energy management, mas, Multi-agent scheduling, smart home},
pubstate = {published},
tppubtype = {inproceedings}
}
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.
2011
Macarthur, Kathryn; Stranders, Ruben; Ramchurn, Sarvapali; Jennings, Nick
A Distributed Anytime Algorithm for Dynamic Task Allocation in Multi-Agent Systems Proceedings Article
In: Twenty-Fifth Conference on Artificial Intelligence (AAAI), pp. 701–706, AAAI Press, 2011, (Event Dates: August 7-11, 2011).
Abstract | Links | BibTeX | Tags: mas, Multi-agent scheduling, multi-agent systems
@inproceedings{eps272233,
title = {A Distributed Anytime Algorithm for Dynamic Task Allocation in Multi-Agent Systems},
author = {Kathryn Macarthur and Ruben Stranders and Sarvapali Ramchurn and Nick Jennings},
url = {http://eprints.soton.ac.uk/272233/},
year = {2011},
date = {2011-01-01},
booktitle = {Twenty-Fifth Conference on Artificial Intelligence (AAAI)},
pages = {701–706},
publisher = {AAAI Press},
abstract = {We introduce a novel distributed algorithm for multi-agent task allocation problems where the sets of tasks and agents constantly change over time. We build on an existing anytime algorithm (fast-max-sum), and give it significant new capa- bilities: namely, an online pruning procedure that simplifies the problem, and a branch-and-bound technique that reduces the search space. This allows us to scale to problems with hundreds of tasks and agents. We empirically evaluate our algorithm against established benchmarks and find that, even in such large environments, a solution is found up to 31% faster, and with up to 23% more utility, than state-of-the-art approximation algorithms. In addition, our algorithm sends up to 30% fewer messages than current approaches when the set of agents or tasks changes.},
note = {Event Dates: August 7-11, 2011},
keywords = {mas, Multi-agent scheduling, multi-agent systems},
pubstate = {published},
tppubtype = {inproceedings}
}
We introduce a novel distributed algorithm for multi-agent task allocation problems where the sets of tasks and agents constantly change over time. We build on an existing anytime algorithm (fast-max-sum), and give it significant new capa- bilities: namely, an online pruning procedure that simplifies the problem, and a branch-and-bound technique that reduces the search space. This allows us to scale to problems with hundreds of tasks and agents. We empirically evaluate our algorithm against established benchmarks and find that, even in such large environments, a solution is found up to 31% faster, and with up to 23% more utility, than state-of-the-art approximation algorithms. In addition, our algorithm sends up to 30% fewer messages than current approaches when the set of agents or tasks changes.
Macarthur, Kathryn; Vinyals, Meritxell; Farinelli, Alessandro; Ramchurn, Sarvapali; Jennings, Nick
Decentralised Parallel Machine Scheduling for Multi-Agent Task Allocation Proceedings Article
In: Fourth International Workshop on Optimisation in Multi-Agent Systems, 2011, (Event Dates: May 3, 2011).
Abstract | Links | BibTeX | Tags: mas, Multi-agent scheduling, multi-agent systems
@inproceedings{eps272234,
title = {Decentralised Parallel Machine Scheduling for Multi-Agent Task Allocation},
author = {Kathryn Macarthur and Meritxell Vinyals and Alessandro Farinelli and Sarvapali Ramchurn and Nick Jennings},
url = {http://eprints.soton.ac.uk/272234/},
year = {2011},
date = {2011-01-01},
booktitle = {Fourth International Workshop on Optimisation in Multi-Agent Systems},
abstract = {Multi-agent task allocation problems pervade a wide range of real-world applications, such as search and rescue in disaster manage- ment, or grid computing. In these applications, where agents are given tasks to perform in parallel, it is often the case that the performance of all agents is judged based on the time taken by the slowest agent to complete its tasks. Hence, efficient distribution of tasks across het- erogeneous agents is important to ensure a short completion time. An equivalent problem to this can be found in operations research, and is known as scheduling jobs on unrelated parallel machines (also known as Rensuremath|ensuremath|Cmax). In this paper, we draw parallels between unrelated parallel machine scheduling and multi-agent task allocation problems, and, in so doing, we present the decentralised task distribution algorithm (DTDA), the first decentralised solution to Rensuremath|ensuremath|Cmax. Empirical evaluation of the DTDA is shown to generate solutions within 86?97% of the optimal on sparse graphs, in the best case, whilst providing a very good estimate (within 1%) of the global solution at each agent.},
note = {Event Dates: May 3, 2011},
keywords = {mas, Multi-agent scheduling, multi-agent systems},
pubstate = {published},
tppubtype = {inproceedings}
}
Multi-agent task allocation problems pervade a wide range of real-world applications, such as search and rescue in disaster manage- ment, or grid computing. In these applications, where agents are given tasks to perform in parallel, it is often the case that the performance of all agents is judged based on the time taken by the slowest agent to complete its tasks. Hence, efficient distribution of tasks across het- erogeneous agents is important to ensure a short completion time. An equivalent problem to this can be found in operations research, and is known as scheduling jobs on unrelated parallel machines (also known as Rensuremath|ensuremath|Cmax). In this paper, we draw parallels between unrelated parallel machine scheduling and multi-agent task allocation problems, and, in so doing, we present the decentralised task distribution algorithm (DTDA), the first decentralised solution to Rensuremath|ensuremath|Cmax. Empirical evaluation of the DTDA is shown to generate solutions within 86?97% of the optimal on sparse graphs, in the best case, whilst providing a very good estimate (within 1%) of the global solution at each agent.
2010
Macarthur, Kathryn; Farinelli, Alessandro; Ramchurn, Sarvapali; Jennings, Nick
Efficient, Superstabilizing Decentralised Optimisation for Dynamic Task Allocation Environments Proceedings Article
In: Third International Workshop on: Optimisation in Multi-Agent Systems (OptMas) at the Ninth Joint Conference on Autonomous and Multi-Agent Systems, pp. 25–32, 2010, (Event Dates: 10 May 2010).
Abstract | Links | BibTeX | Tags: agents, Disaster Management, mas, Multi-agent scheduling, multi-agent systems
@inproceedings{eps268588,
title = {Efficient, Superstabilizing Decentralised Optimisation for Dynamic Task Allocation Environments},
author = {Kathryn Macarthur and Alessandro Farinelli and Sarvapali Ramchurn and Nick Jennings},
url = {http://eprints.soton.ac.uk/268588/},
year = {2010},
date = {2010-01-01},
booktitle = {Third International Workshop on: Optimisation in Multi-Agent Systems (OptMas) at the Ninth Joint Conference on Autonomous and Multi-Agent Systems},
pages = {25–32},
abstract = {Decentralised optimisation is a key issue for multi-agent systems, and while many solution techniques have been developed, few provide support for dynamic environments, which change over time, such as disaster management. Given this, in this paper, we present Bounded Fast Max Sum (BFMS): a novel, dynamic, superstabilizing algorithm which provides a bounded approximate solution to certain classes of distributed constraint optimisation problems. We achieve this by eliminating dependencies in the constraint functions, according to how much impact they have on the overall solution value. In more detail, we propose iGHS, which computes a maximum spanning tree on subsections of the constraint graph, in order to reduce communication and computation overheads. Given this, we empirically evaluate BFMS, which shows that BFMS reduces communication and computation done by Bounded Max Sum by up to 99%, while obtaining 60-88% of the optimal utility.},
note = {Event Dates: 10 May 2010},
keywords = {agents, Disaster Management, mas, Multi-agent scheduling, multi-agent systems},
pubstate = {published},
tppubtype = {inproceedings}
}
Decentralised optimisation is a key issue for multi-agent systems, and while many solution techniques have been developed, few provide support for dynamic environments, which change over time, such as disaster management. Given this, in this paper, we present Bounded Fast Max Sum (BFMS): a novel, dynamic, superstabilizing algorithm which provides a bounded approximate solution to certain classes of distributed constraint optimisation problems. We achieve this by eliminating dependencies in the constraint functions, according to how much impact they have on the overall solution value. In more detail, we propose iGHS, which computes a maximum spanning tree on subsections of the constraint graph, in order to reduce communication and computation overheads. Given this, we empirically evaluate BFMS, which shows that BFMS reduces communication and computation done by Bounded Max Sum by up to 99%, while obtaining 60-88% of the optimal utility.
Ramchurn, 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.
Ramchurn, Sarvapali; Farinelli, Alessandro; Macarthur, Kathryn; Polukarov, Mariya; Jennings, Nick
Decentralised Coordination in RoboCup Rescue Journal Article
In: The Computer Journal, vol. 53, no. 9, pp. 1–15, 2010.
Abstract | Links | BibTeX | Tags: Disaster Management, mas, Multi-agent scheduling, multi-agent systems
@article{eps268499,
title = {Decentralised Coordination in RoboCup Rescue},
author = {Sarvapali Ramchurn and Alessandro Farinelli and Kathryn Macarthur and Mariya Polukarov and Nick Jennings},
url = {http://eprints.soton.ac.uk/268499/},
year = {2010},
date = {2010-01-01},
journal = {The Computer Journal},
volume = {53},
number = {9},
pages = {1–15},
publisher = {Oxford Journals},
abstract = {Emergency responders are faced with a number of significant challenges when managing major disasters. First, the number of rescue tasks posed is usually larger than the number of responders (or agents) and the resources available to them. Second, each task is likely to require a different level of effort in order to be completed by its deadline. Third, new tasks may continually appear or disappear from the environment, thus requiring the responders to quickly recompute their allocation of resources. Fourth, forming teams or coalitions of multiple agents from different agencies is vital since no single agency will have all the resources needed to save victims, unblock roads, and extinguish the ?res which might erupt in the disaster space. Given this, coalitions have to be efficiently selected and scheduled to work across the disaster space so as to maximise the number of lives and the portion of the infrastructure saved. In particular, it is important that the selection of such coalitions should be performed in a decentralised fashion in order to avoid a single point of failure in the system. Moreover, it is critical that responders communicate only locally given they are likely to have limited battery power or minimal access to long range communication devices. Against this background, we provide a novel decentralised solution to the coalition formation process that pervades disaster management. More specifically, we model the emergency management scenario defined in the RoboCup Rescue disaster simulation platform as a Coalition Formation with Spatial and Temporal constraints (CFST) problem where agents form coalitions in order to complete tasks, each with different demands. In order to design a decentralised algorithm for CFST we formulate it as a Distributed Constraint Optimisation problem and show how to solve it using the state-of-the-art Max-Sum algorithm that provides a completely decentralised message-passing solution. We then provide a novel algorithm (F-Max-Sum) that avoids sending redundant messages and efficiently adapts to changes in the environment. In empirical evaluations, our algorithm is shown to generate better solutions than other decentralised algorithms used for this problem.},
keywords = {Disaster Management, mas, Multi-agent scheduling, multi-agent systems},
pubstate = {published},
tppubtype = {article}
}
Emergency responders are faced with a number of significant challenges when managing major disasters. First, the number of rescue tasks posed is usually larger than the number of responders (or agents) and the resources available to them. Second, each task is likely to require a different level of effort in order to be completed by its deadline. Third, new tasks may continually appear or disappear from the environment, thus requiring the responders to quickly recompute their allocation of resources. Fourth, forming teams or coalitions of multiple agents from different agencies is vital since no single agency will have all the resources needed to save victims, unblock roads, and extinguish the ?res which might erupt in the disaster space. Given this, coalitions have to be efficiently selected and scheduled to work across the disaster space so as to maximise the number of lives and the portion of the infrastructure saved. In particular, it is important that the selection of such coalitions should be performed in a decentralised fashion in order to avoid a single point of failure in the system. Moreover, it is critical that responders communicate only locally given they are likely to have limited battery power or minimal access to long range communication devices. Against this background, we provide a novel decentralised solution to the coalition formation process that pervades disaster management. More specifically, we model the emergency management scenario defined in the RoboCup Rescue disaster simulation platform as a Coalition Formation with Spatial and Temporal constraints (CFST) problem where agents form coalitions in order to complete tasks, each with different demands. In order to design a decentralised algorithm for CFST we formulate it as a Distributed Constraint Optimisation problem and show how to solve it using the state-of-the-art Max-Sum algorithm that provides a completely decentralised message-passing solution. We then provide a novel algorithm (F-Max-Sum) that avoids sending redundant messages and efficiently adapts to changes in the environment. In empirical evaluations, our algorithm is shown to generate better solutions than other decentralised algorithms used for this problem.
1.
Rigas, Nick Bassiliades Sarvapali D. Ramchurn Emmanouil
Managing Electric Vehicles in the Smart Grid Using Artificial Intelligence: A Survey Journal Article
In: IEEE Transactions on Intelligent Transportation Systems, 2015.
@article{rigas:etal:2015,
title = {Managing Electric Vehicles in the Smart Grid Using Artificial Intelligence: A Survey},
author = {Nick Bassiliades Sarvapali D. Ramchurn Emmanouil Rigas},
url = {http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=7000557&filter%3DAND%28p_IS_Number%3A7174612%29},
year = {2015},
date = {2015-01-16},
journal = {IEEE Transactions on Intelligent Transportation Systems},
abstract = {Along with the development of Smart Grids, the wide adoption of Electric Vehicles (EVs) is seen as a catalyst to the reduction of CO2 emissions and more intelligent transportation systems. In particular, EVs augment the grid with the ability to store energy at some points in the network and give it back at others and therefore help optimise the use of energy from intermittent renewable energy sources and let users refill their cars in a variety of locations. However, a number of challenges need to be addressed if such benefits are to be achieved. On the one hand, given their limited range and costs involved in charging EV batteries, it is important to design algorithms that will minimise costs while avoid users being stranded. On the other hand, collectives of EVs need to be organized in such a way as to avoid peaks on the grid that may result in high electricity prices and overload local distribution grids. In order to meet such challenges, a number of technological solutions have been proposed. In this paper, we focus on those that utilise artificial intelligence techniques to render EVs and the systems that manage collectives of EVs smarter. In particular, we provide a survey of the literature and identify the commonalities and key differences in the approaches. This allows us to develop a classification of key techniques and benchmarks that can be used to advance the state-of-the art in this space.},
keywords = {},
pubstate = {published},
tppubtype = {article}
}
Along with the development of Smart Grids, the wide adoption of Electric Vehicles (EVs) is seen as a catalyst to the reduction of CO2 emissions and more intelligent transportation systems. In particular, EVs augment the grid with the ability to store energy at some points in the network and give it back at others and therefore help optimise the use of energy from intermittent renewable energy sources and let users refill their cars in a variety of locations. However, a number of challenges need to be addressed if such benefits are to be achieved. On the one hand, given their limited range and costs involved in charging EV batteries, it is important to design algorithms that will minimise costs while avoid users being stranded. On the other hand, collectives of EVs need to be organized in such a way as to avoid peaks on the grid that may result in high electricity prices and overload local distribution grids. In order to meet such challenges, a number of technological solutions have been proposed. In this paper, we focus on those that utilise artificial intelligence techniques to render EVs and the systems that manage collectives of EVs smarter. In particular, we provide a survey of the literature and identify the commonalities and key differences in the approaches. This allows us to develop a classification of key techniques and benchmarks that can be used to advance the state-of-the art in this space.
2.
Alam, Muddasser; Rogers, Alex; Ramchurn, Sarvapali D.
Interdependent multi-issue negotiation for energy exchange in remote communities Proceedings Article
In: International Workshop on AI Problems and Approaches for Intelligent Environments (AI4IE), 2013.
@inproceedings{eps357186,
title = {Interdependent multi-issue negotiation for energy exchange in remote communities},
author = {Muddasser Alam and Alex Rogers and Sarvapali D. Ramchurn},
url = {http://eprints.soton.ac.uk/357186/},
year = {2013},
date = {2013-01-01},
booktitle = {International Workshop on AI Problems and Approaches for Intelligent Environments (AI4IE)},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
3.
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.
4.
Macarthur, Kathryn; Stranders, Ruben; Ramchurn, Sarvapali; Jennings, Nick
A Distributed Anytime Algorithm for Dynamic Task Allocation in Multi-Agent Systems Proceedings Article
In: Twenty-Fifth Conference on Artificial Intelligence (AAAI), pp. 701–706, AAAI Press, 2011, (Event Dates: August 7-11, 2011).
@inproceedings{eps272233,
title = {A Distributed Anytime Algorithm for Dynamic Task Allocation in Multi-Agent Systems},
author = {Kathryn Macarthur and Ruben Stranders and Sarvapali Ramchurn and Nick Jennings},
url = {http://eprints.soton.ac.uk/272233/},
year = {2011},
date = {2011-01-01},
booktitle = {Twenty-Fifth Conference on Artificial Intelligence (AAAI)},
pages = {701–706},
publisher = {AAAI Press},
abstract = {We introduce a novel distributed algorithm for multi-agent task allocation problems where the sets of tasks and agents constantly change over time. We build on an existing anytime algorithm (fast-max-sum), and give it significant new capa- bilities: namely, an online pruning procedure that simplifies the problem, and a branch-and-bound technique that reduces the search space. This allows us to scale to problems with hundreds of tasks and agents. We empirically evaluate our algorithm against established benchmarks and find that, even in such large environments, a solution is found up to 31% faster, and with up to 23% more utility, than state-of-the-art approximation algorithms. In addition, our algorithm sends up to 30% fewer messages than current approaches when the set of agents or tasks changes.},
note = {Event Dates: August 7-11, 2011},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
We introduce a novel distributed algorithm for multi-agent task allocation problems where the sets of tasks and agents constantly change over time. We build on an existing anytime algorithm (fast-max-sum), and give it significant new capa- bilities: namely, an online pruning procedure that simplifies the problem, and a branch-and-bound technique that reduces the search space. This allows us to scale to problems with hundreds of tasks and agents. We empirically evaluate our algorithm against established benchmarks and find that, even in such large environments, a solution is found up to 31% faster, and with up to 23% more utility, than state-of-the-art approximation algorithms. In addition, our algorithm sends up to 30% fewer messages than current approaches when the set of agents or tasks changes.
5.
Macarthur, Kathryn; Vinyals, Meritxell; Farinelli, Alessandro; Ramchurn, Sarvapali; Jennings, Nick
Decentralised Parallel Machine Scheduling for Multi-Agent Task Allocation Proceedings Article
In: Fourth International Workshop on Optimisation in Multi-Agent Systems, 2011, (Event Dates: May 3, 2011).
@inproceedings{eps272234,
title = {Decentralised Parallel Machine Scheduling for Multi-Agent Task Allocation},
author = {Kathryn Macarthur and Meritxell Vinyals and Alessandro Farinelli and Sarvapali Ramchurn and Nick Jennings},
url = {http://eprints.soton.ac.uk/272234/},
year = {2011},
date = {2011-01-01},
booktitle = {Fourth International Workshop on Optimisation in Multi-Agent Systems},
abstract = {Multi-agent task allocation problems pervade a wide range of real-world applications, such as search and rescue in disaster manage- ment, or grid computing. In these applications, where agents are given tasks to perform in parallel, it is often the case that the performance of all agents is judged based on the time taken by the slowest agent to complete its tasks. Hence, efficient distribution of tasks across het- erogeneous agents is important to ensure a short completion time. An equivalent problem to this can be found in operations research, and is known as scheduling jobs on unrelated parallel machines (also known as Rensuremath|ensuremath|Cmax). In this paper, we draw parallels between unrelated parallel machine scheduling and multi-agent task allocation problems, and, in so doing, we present the decentralised task distribution algorithm (DTDA), the first decentralised solution to Rensuremath|ensuremath|Cmax. Empirical evaluation of the DTDA is shown to generate solutions within 86?97% of the optimal on sparse graphs, in the best case, whilst providing a very good estimate (within 1%) of the global solution at each agent.},
note = {Event Dates: May 3, 2011},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
Multi-agent task allocation problems pervade a wide range of real-world applications, such as search and rescue in disaster manage- ment, or grid computing. In these applications, where agents are given tasks to perform in parallel, it is often the case that the performance of all agents is judged based on the time taken by the slowest agent to complete its tasks. Hence, efficient distribution of tasks across het- erogeneous agents is important to ensure a short completion time. An equivalent problem to this can be found in operations research, and is known as scheduling jobs on unrelated parallel machines (also known as Rensuremath|ensuremath|Cmax). In this paper, we draw parallels between unrelated parallel machine scheduling and multi-agent task allocation problems, and, in so doing, we present the decentralised task distribution algorithm (DTDA), the first decentralised solution to Rensuremath|ensuremath|Cmax. Empirical evaluation of the DTDA is shown to generate solutions within 86?97% of the optimal on sparse graphs, in the best case, whilst providing a very good estimate (within 1%) of the global solution at each agent.
6.
Macarthur, Kathryn; Farinelli, Alessandro; Ramchurn, Sarvapali; Jennings, Nick
Efficient, Superstabilizing Decentralised Optimisation for Dynamic Task Allocation Environments Proceedings Article
In: Third International Workshop on: Optimisation in Multi-Agent Systems (OptMas) at the Ninth Joint Conference on Autonomous and Multi-Agent Systems, pp. 25–32, 2010, (Event Dates: 10 May 2010).
@inproceedings{eps268588,
title = {Efficient, Superstabilizing Decentralised Optimisation for Dynamic Task Allocation Environments},
author = {Kathryn Macarthur and Alessandro Farinelli and Sarvapali Ramchurn and Nick Jennings},
url = {http://eprints.soton.ac.uk/268588/},
year = {2010},
date = {2010-01-01},
booktitle = {Third International Workshop on: Optimisation in Multi-Agent Systems (OptMas) at the Ninth Joint Conference on Autonomous and Multi-Agent Systems},
pages = {25–32},
abstract = {Decentralised optimisation is a key issue for multi-agent systems, and while many solution techniques have been developed, few provide support for dynamic environments, which change over time, such as disaster management. Given this, in this paper, we present Bounded Fast Max Sum (BFMS): a novel, dynamic, superstabilizing algorithm which provides a bounded approximate solution to certain classes of distributed constraint optimisation problems. We achieve this by eliminating dependencies in the constraint functions, according to how much impact they have on the overall solution value. In more detail, we propose iGHS, which computes a maximum spanning tree on subsections of the constraint graph, in order to reduce communication and computation overheads. Given this, we empirically evaluate BFMS, which shows that BFMS reduces communication and computation done by Bounded Max Sum by up to 99%, while obtaining 60-88% of the optimal utility.},
note = {Event Dates: 10 May 2010},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
Decentralised optimisation is a key issue for multi-agent systems, and while many solution techniques have been developed, few provide support for dynamic environments, which change over time, such as disaster management. Given this, in this paper, we present Bounded Fast Max Sum (BFMS): a novel, dynamic, superstabilizing algorithm which provides a bounded approximate solution to certain classes of distributed constraint optimisation problems. We achieve this by eliminating dependencies in the constraint functions, according to how much impact they have on the overall solution value. In more detail, we propose iGHS, which computes a maximum spanning tree on subsections of the constraint graph, in order to reduce communication and computation overheads. Given this, we empirically evaluate BFMS, which shows that BFMS reduces communication and computation done by Bounded Max Sum by up to 99%, while obtaining 60-88% of the optimal utility.
7.
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.
8.
Ramchurn, Sarvapali; Farinelli, Alessandro; Macarthur, Kathryn; Polukarov, Mariya; Jennings, Nick
Decentralised Coordination in RoboCup Rescue Journal Article
In: The Computer Journal, vol. 53, no. 9, pp. 1–15, 2010.
@article{eps268499,
title = {Decentralised Coordination in RoboCup Rescue},
author = {Sarvapali Ramchurn and Alessandro Farinelli and Kathryn Macarthur and Mariya Polukarov and Nick Jennings},
url = {http://eprints.soton.ac.uk/268499/},
year = {2010},
date = {2010-01-01},
journal = {The Computer Journal},
volume = {53},
number = {9},
pages = {1–15},
publisher = {Oxford Journals},
abstract = {Emergency responders are faced with a number of significant challenges when managing major disasters. First, the number of rescue tasks posed is usually larger than the number of responders (or agents) and the resources available to them. Second, each task is likely to require a different level of effort in order to be completed by its deadline. Third, new tasks may continually appear or disappear from the environment, thus requiring the responders to quickly recompute their allocation of resources. Fourth, forming teams or coalitions of multiple agents from different agencies is vital since no single agency will have all the resources needed to save victims, unblock roads, and extinguish the ?res which might erupt in the disaster space. Given this, coalitions have to be efficiently selected and scheduled to work across the disaster space so as to maximise the number of lives and the portion of the infrastructure saved. In particular, it is important that the selection of such coalitions should be performed in a decentralised fashion in order to avoid a single point of failure in the system. Moreover, it is critical that responders communicate only locally given they are likely to have limited battery power or minimal access to long range communication devices. Against this background, we provide a novel decentralised solution to the coalition formation process that pervades disaster management. More specifically, we model the emergency management scenario defined in the RoboCup Rescue disaster simulation platform as a Coalition Formation with Spatial and Temporal constraints (CFST) problem where agents form coalitions in order to complete tasks, each with different demands. In order to design a decentralised algorithm for CFST we formulate it as a Distributed Constraint Optimisation problem and show how to solve it using the state-of-the-art Max-Sum algorithm that provides a completely decentralised message-passing solution. We then provide a novel algorithm (F-Max-Sum) that avoids sending redundant messages and efficiently adapts to changes in the environment. In empirical evaluations, our algorithm is shown to generate better solutions than other decentralised algorithms used for this problem.},
keywords = {},
pubstate = {published},
tppubtype = {article}
}
Emergency responders are faced with a number of significant challenges when managing major disasters. First, the number of rescue tasks posed is usually larger than the number of responders (or agents) and the resources available to them. Second, each task is likely to require a different level of effort in order to be completed by its deadline. Third, new tasks may continually appear or disappear from the environment, thus requiring the responders to quickly recompute their allocation of resources. Fourth, forming teams or coalitions of multiple agents from different agencies is vital since no single agency will have all the resources needed to save victims, unblock roads, and extinguish the ?res which might erupt in the disaster space. Given this, coalitions have to be efficiently selected and scheduled to work across the disaster space so as to maximise the number of lives and the portion of the infrastructure saved. In particular, it is important that the selection of such coalitions should be performed in a decentralised fashion in order to avoid a single point of failure in the system. Moreover, it is critical that responders communicate only locally given they are likely to have limited battery power or minimal access to long range communication devices. Against this background, we provide a novel decentralised solution to the coalition formation process that pervades disaster management. More specifically, we model the emergency management scenario defined in the RoboCup Rescue disaster simulation platform as a Coalition Formation with Spatial and Temporal constraints (CFST) problem where agents form coalitions in order to complete tasks, each with different demands. In order to design a decentralised algorithm for CFST we formulate it as a Distributed Constraint Optimisation problem and show how to solve it using the state-of-the-art Max-Sum algorithm that provides a completely decentralised message-passing solution. We then provide a novel algorithm (F-Max-Sum) that avoids sending redundant messages and efficiently adapts to changes in the environment. In empirical evaluations, our algorithm is shown to generate better solutions than other decentralised algorithms used for this problem.
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}
}
2015
Rigas, Nick Bassiliades Sarvapali D. Ramchurn Emmanouil
Managing Electric Vehicles in the Smart Grid Using Artificial Intelligence: A Survey Journal Article
In: IEEE Transactions on Intelligent Transportation Systems, 2015.
@article{rigas:etal:2015,
title = {Managing Electric Vehicles in the Smart Grid Using Artificial Intelligence: A Survey},
author = {Nick Bassiliades Sarvapali D. Ramchurn Emmanouil Rigas},
url = {http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=7000557&filter%3DAND%28p_IS_Number%3A7174612%29},
year = {2015},
date = {2015-01-16},
journal = {IEEE Transactions on Intelligent Transportation Systems},
abstract = {Along with the development of Smart Grids, the wide adoption of Electric Vehicles (EVs) is seen as a catalyst to the reduction of CO2 emissions and more intelligent transportation systems. In particular, EVs augment the grid with the ability to store energy at some points in the network and give it back at others and therefore help optimise the use of energy from intermittent renewable energy sources and let users refill their cars in a variety of locations. However, a number of challenges need to be addressed if such benefits are to be achieved. On the one hand, given their limited range and costs involved in charging EV batteries, it is important to design algorithms that will minimise costs while avoid users being stranded. On the other hand, collectives of EVs need to be organized in such a way as to avoid peaks on the grid that may result in high electricity prices and overload local distribution grids. In order to meet such challenges, a number of technological solutions have been proposed. In this paper, we focus on those that utilise artificial intelligence techniques to render EVs and the systems that manage collectives of EVs smarter. In particular, we provide a survey of the literature and identify the commonalities and key differences in the approaches. This allows us to develop a classification of key techniques and benchmarks that can be used to advance the state-of-the art in this space.},
keywords = {},
pubstate = {published},
tppubtype = {article}
}
Along with the development of Smart Grids, the wide adoption of Electric Vehicles (EVs) is seen as a catalyst to the reduction of CO2 emissions and more intelligent transportation systems. In particular, EVs augment the grid with the ability to store energy at some points in the network and give it back at others and therefore help optimise the use of energy from intermittent renewable energy sources and let users refill their cars in a variety of locations. However, a number of challenges need to be addressed if such benefits are to be achieved. On the one hand, given their limited range and costs involved in charging EV batteries, it is important to design algorithms that will minimise costs while avoid users being stranded. On the other hand, collectives of EVs need to be organized in such a way as to avoid peaks on the grid that may result in high electricity prices and overload local distribution grids. In order to meet such challenges, a number of technological solutions have been proposed. In this paper, we focus on those that utilise artificial intelligence techniques to render EVs and the systems that manage collectives of EVs smarter. In particular, we provide a survey of the literature and identify the commonalities and key differences in the approaches. This allows us to develop a classification of key techniques and benchmarks that can be used to advance the state-of-the art in this space.
2013
Alam, Muddasser; Rogers, Alex; Ramchurn, Sarvapali D.
Interdependent multi-issue negotiation for energy exchange in remote communities Proceedings Article
In: International Workshop on AI Problems and Approaches for Intelligent Environments (AI4IE), 2013.
@inproceedings{eps357186,
title = {Interdependent multi-issue negotiation for energy exchange in remote communities},
author = {Muddasser Alam and Alex Rogers and Sarvapali D. Ramchurn},
url = {http://eprints.soton.ac.uk/357186/},
year = {2013},
date = {2013-01-01},
booktitle = {International Workshop on AI Problems and Approaches for Intelligent Environments (AI4IE)},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
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.
2011
Macarthur, Kathryn; Stranders, Ruben; Ramchurn, Sarvapali; Jennings, Nick
A Distributed Anytime Algorithm for Dynamic Task Allocation in Multi-Agent Systems Proceedings Article
In: Twenty-Fifth Conference on Artificial Intelligence (AAAI), pp. 701–706, AAAI Press, 2011, (Event Dates: August 7-11, 2011).
@inproceedings{eps272233,
title = {A Distributed Anytime Algorithm for Dynamic Task Allocation in Multi-Agent Systems},
author = {Kathryn Macarthur and Ruben Stranders and Sarvapali Ramchurn and Nick Jennings},
url = {http://eprints.soton.ac.uk/272233/},
year = {2011},
date = {2011-01-01},
booktitle = {Twenty-Fifth Conference on Artificial Intelligence (AAAI)},
pages = {701–706},
publisher = {AAAI Press},
abstract = {We introduce a novel distributed algorithm for multi-agent task allocation problems where the sets of tasks and agents constantly change over time. We build on an existing anytime algorithm (fast-max-sum), and give it significant new capa- bilities: namely, an online pruning procedure that simplifies the problem, and a branch-and-bound technique that reduces the search space. This allows us to scale to problems with hundreds of tasks and agents. We empirically evaluate our algorithm against established benchmarks and find that, even in such large environments, a solution is found up to 31% faster, and with up to 23% more utility, than state-of-the-art approximation algorithms. In addition, our algorithm sends up to 30% fewer messages than current approaches when the set of agents or tasks changes.},
note = {Event Dates: August 7-11, 2011},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
We introduce a novel distributed algorithm for multi-agent task allocation problems where the sets of tasks and agents constantly change over time. We build on an existing anytime algorithm (fast-max-sum), and give it significant new capa- bilities: namely, an online pruning procedure that simplifies the problem, and a branch-and-bound technique that reduces the search space. This allows us to scale to problems with hundreds of tasks and agents. We empirically evaluate our algorithm against established benchmarks and find that, even in such large environments, a solution is found up to 31% faster, and with up to 23% more utility, than state-of-the-art approximation algorithms. In addition, our algorithm sends up to 30% fewer messages than current approaches when the set of agents or tasks changes.
Macarthur, Kathryn; Vinyals, Meritxell; Farinelli, Alessandro; Ramchurn, Sarvapali; Jennings, Nick
Decentralised Parallel Machine Scheduling for Multi-Agent Task Allocation Proceedings Article
In: Fourth International Workshop on Optimisation in Multi-Agent Systems, 2011, (Event Dates: May 3, 2011).
@inproceedings{eps272234,
title = {Decentralised Parallel Machine Scheduling for Multi-Agent Task Allocation},
author = {Kathryn Macarthur and Meritxell Vinyals and Alessandro Farinelli and Sarvapali Ramchurn and Nick Jennings},
url = {http://eprints.soton.ac.uk/272234/},
year = {2011},
date = {2011-01-01},
booktitle = {Fourth International Workshop on Optimisation in Multi-Agent Systems},
abstract = {Multi-agent task allocation problems pervade a wide range of real-world applications, such as search and rescue in disaster manage- ment, or grid computing. In these applications, where agents are given tasks to perform in parallel, it is often the case that the performance of all agents is judged based on the time taken by the slowest agent to complete its tasks. Hence, efficient distribution of tasks across het- erogeneous agents is important to ensure a short completion time. An equivalent problem to this can be found in operations research, and is known as scheduling jobs on unrelated parallel machines (also known as Rensuremath|ensuremath|Cmax). In this paper, we draw parallels between unrelated parallel machine scheduling and multi-agent task allocation problems, and, in so doing, we present the decentralised task distribution algorithm (DTDA), the first decentralised solution to Rensuremath|ensuremath|Cmax. Empirical evaluation of the DTDA is shown to generate solutions within 86?97% of the optimal on sparse graphs, in the best case, whilst providing a very good estimate (within 1%) of the global solution at each agent.},
note = {Event Dates: May 3, 2011},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
Multi-agent task allocation problems pervade a wide range of real-world applications, such as search and rescue in disaster manage- ment, or grid computing. In these applications, where agents are given tasks to perform in parallel, it is often the case that the performance of all agents is judged based on the time taken by the slowest agent to complete its tasks. Hence, efficient distribution of tasks across het- erogeneous agents is important to ensure a short completion time. An equivalent problem to this can be found in operations research, and is known as scheduling jobs on unrelated parallel machines (also known as Rensuremath|ensuremath|Cmax). In this paper, we draw parallels between unrelated parallel machine scheduling and multi-agent task allocation problems, and, in so doing, we present the decentralised task distribution algorithm (DTDA), the first decentralised solution to Rensuremath|ensuremath|Cmax. Empirical evaluation of the DTDA is shown to generate solutions within 86?97% of the optimal on sparse graphs, in the best case, whilst providing a very good estimate (within 1%) of the global solution at each agent.
2010
Macarthur, Kathryn; Farinelli, Alessandro; Ramchurn, Sarvapali; Jennings, Nick
Efficient, Superstabilizing Decentralised Optimisation for Dynamic Task Allocation Environments Proceedings Article
In: Third International Workshop on: Optimisation in Multi-Agent Systems (OptMas) at the Ninth Joint Conference on Autonomous and Multi-Agent Systems, pp. 25–32, 2010, (Event Dates: 10 May 2010).
@inproceedings{eps268588,
title = {Efficient, Superstabilizing Decentralised Optimisation for Dynamic Task Allocation Environments},
author = {Kathryn Macarthur and Alessandro Farinelli and Sarvapali Ramchurn and Nick Jennings},
url = {http://eprints.soton.ac.uk/268588/},
year = {2010},
date = {2010-01-01},
booktitle = {Third International Workshop on: Optimisation in Multi-Agent Systems (OptMas) at the Ninth Joint Conference on Autonomous and Multi-Agent Systems},
pages = {25–32},
abstract = {Decentralised optimisation is a key issue for multi-agent systems, and while many solution techniques have been developed, few provide support for dynamic environments, which change over time, such as disaster management. Given this, in this paper, we present Bounded Fast Max Sum (BFMS): a novel, dynamic, superstabilizing algorithm which provides a bounded approximate solution to certain classes of distributed constraint optimisation problems. We achieve this by eliminating dependencies in the constraint functions, according to how much impact they have on the overall solution value. In more detail, we propose iGHS, which computes a maximum spanning tree on subsections of the constraint graph, in order to reduce communication and computation overheads. Given this, we empirically evaluate BFMS, which shows that BFMS reduces communication and computation done by Bounded Max Sum by up to 99%, while obtaining 60-88% of the optimal utility.},
note = {Event Dates: 10 May 2010},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
Decentralised optimisation is a key issue for multi-agent systems, and while many solution techniques have been developed, few provide support for dynamic environments, which change over time, such as disaster management. Given this, in this paper, we present Bounded Fast Max Sum (BFMS): a novel, dynamic, superstabilizing algorithm which provides a bounded approximate solution to certain classes of distributed constraint optimisation problems. We achieve this by eliminating dependencies in the constraint functions, according to how much impact they have on the overall solution value. In more detail, we propose iGHS, which computes a maximum spanning tree on subsections of the constraint graph, in order to reduce communication and computation overheads. Given this, we empirically evaluate BFMS, which shows that BFMS reduces communication and computation done by Bounded Max Sum by up to 99%, while obtaining 60-88% of the optimal utility.
Ramchurn, 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.
Ramchurn, Sarvapali; Farinelli, Alessandro; Macarthur, Kathryn; Polukarov, Mariya; Jennings, Nick
Decentralised Coordination in RoboCup Rescue Journal Article
In: The Computer Journal, vol. 53, no. 9, pp. 1–15, 2010.
@article{eps268499,
title = {Decentralised Coordination in RoboCup Rescue},
author = {Sarvapali Ramchurn and Alessandro Farinelli and Kathryn Macarthur and Mariya Polukarov and Nick Jennings},
url = {http://eprints.soton.ac.uk/268499/},
year = {2010},
date = {2010-01-01},
journal = {The Computer Journal},
volume = {53},
number = {9},
pages = {1–15},
publisher = {Oxford Journals},
abstract = {Emergency responders are faced with a number of significant challenges when managing major disasters. First, the number of rescue tasks posed is usually larger than the number of responders (or agents) and the resources available to them. Second, each task is likely to require a different level of effort in order to be completed by its deadline. Third, new tasks may continually appear or disappear from the environment, thus requiring the responders to quickly recompute their allocation of resources. Fourth, forming teams or coalitions of multiple agents from different agencies is vital since no single agency will have all the resources needed to save victims, unblock roads, and extinguish the ?res which might erupt in the disaster space. Given this, coalitions have to be efficiently selected and scheduled to work across the disaster space so as to maximise the number of lives and the portion of the infrastructure saved. In particular, it is important that the selection of such coalitions should be performed in a decentralised fashion in order to avoid a single point of failure in the system. Moreover, it is critical that responders communicate only locally given they are likely to have limited battery power or minimal access to long range communication devices. Against this background, we provide a novel decentralised solution to the coalition formation process that pervades disaster management. More specifically, we model the emergency management scenario defined in the RoboCup Rescue disaster simulation platform as a Coalition Formation with Spatial and Temporal constraints (CFST) problem where agents form coalitions in order to complete tasks, each with different demands. In order to design a decentralised algorithm for CFST we formulate it as a Distributed Constraint Optimisation problem and show how to solve it using the state-of-the-art Max-Sum algorithm that provides a completely decentralised message-passing solution. We then provide a novel algorithm (F-Max-Sum) that avoids sending redundant messages and efficiently adapts to changes in the environment. In empirical evaluations, our algorithm is shown to generate better solutions than other decentralised algorithms used for this problem.},
keywords = {},
pubstate = {published},
tppubtype = {article}
}
Emergency responders are faced with a number of significant challenges when managing major disasters. First, the number of rescue tasks posed is usually larger than the number of responders (or agents) and the resources available to them. Second, each task is likely to require a different level of effort in order to be completed by its deadline. Third, new tasks may continually appear or disappear from the environment, thus requiring the responders to quickly recompute their allocation of resources. Fourth, forming teams or coalitions of multiple agents from different agencies is vital since no single agency will have all the resources needed to save victims, unblock roads, and extinguish the ?res which might erupt in the disaster space. Given this, coalitions have to be efficiently selected and scheduled to work across the disaster space so as to maximise the number of lives and the portion of the infrastructure saved. In particular, it is important that the selection of such coalitions should be performed in a decentralised fashion in order to avoid a single point of failure in the system. Moreover, it is critical that responders communicate only locally given they are likely to have limited battery power or minimal access to long range communication devices. Against this background, we provide a novel decentralised solution to the coalition formation process that pervades disaster management. More specifically, we model the emergency management scenario defined in the RoboCup Rescue disaster simulation platform as a Coalition Formation with Spatial and Temporal constraints (CFST) problem where agents form coalitions in order to complete tasks, each with different demands. In order to design a decentralised algorithm for CFST we formulate it as a Distributed Constraint Optimisation problem and show how to solve it using the state-of-the-art Max-Sum algorithm that provides a completely decentralised message-passing solution. We then provide a novel algorithm (F-Max-Sum) that avoids sending redundant messages and efficiently adapts to changes in the environment. In empirical evaluations, our algorithm is shown to generate better solutions than other decentralised algorithms used for this problem.