title: A Distributed Anytime Algorithm for Dynamic Task Allocation  in Multi-Agent Systems
creator: Macarthur, Kathryn S
creator: Stranders, Ruben
creator: Ramchurn, Sarvapali D
creator: Jennings, Nicholas R
subject: Agent-based Computing
subject: Agile Teaming
description: 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 capabilities:  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.
date: 2011
type: Conference or Workshop Item
type: PeerReviewed
format: application/pdf
identifier: http://www.orchid.ac.uk/eprints/3/1/A_Distributed_Anytime_Algorithm_for_Dynamic_Task_Allocation.pdf
identifier:   Macarthur, Kathryn S and Stranders, Ruben and Ramchurn, Sarvapali D and Jennings, Nicholas R  (2011) A Distributed Anytime Algorithm for Dynamic Task Allocation in Multi-Agent Systems.  In: Twenty-Fifth Conference on Artificial Intelligence, August 7-11, 2011, San Francisco.    (In Press)  
relation: http://www.orchid.ac.uk/eprints/3/