creators_name: Macarthur, Kathryn S
creators_name: Stranders, Ruben
creators_name: Ramchurn, Sarvapali D
creators_name: Jennings, Nicholas R
type: conference_item
datestamp: 2011-08-10 10:26:28
lastmod: 2012-03-22 09:42:28
metadata_visibility: show
title: A Distributed Anytime Algorithm for Dynamic Task Allocation
in Multi-Agent Systems
ispublished: inpress
subjects: ABC
subjects: at
full_text_status: public
pres_type: paper
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 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
event_title: Twenty-Fifth Conference on Artificial Intelligence
event_location: San Francisco
event_dates: August 7-11, 2011
event_type: conference
refereed: TRUE
citation:   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)  
document_url: http://www.orchid.ac.uk/eprints/3/1/A_Distributed_Anytime_Algorithm_for_Dynamic_Task_Allocation.pdf