A Distributed Anytime Algorithm for Dynamic Task Allocation in Multi-Agent Systems
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.
Cite
Text
Macarthur et al. "A Distributed Anytime Algorithm for Dynamic Task Allocation in Multi-Agent Systems." AAAI Conference on Artificial Intelligence, 2011. doi:10.1609/AAAI.V25I1.7866Markdown
[Macarthur et al. "A Distributed Anytime Algorithm for Dynamic Task Allocation in Multi-Agent Systems." AAAI Conference on Artificial Intelligence, 2011.](https://mlanthology.org/aaai/2011/macarthur2011aaai-distributed/) doi:10.1609/AAAI.V25I1.7866BibTeX
@inproceedings{macarthur2011aaai-distributed,
title = {{A Distributed Anytime Algorithm for Dynamic Task Allocation in Multi-Agent Systems}},
author = {Macarthur, Kathryn Sarah and Stranders, Ruben and Ramchurn, Sarvapali D. and Jennings, Nicholas R.},
booktitle = {AAAI Conference on Artificial Intelligence},
year = {2011},
pages = {701-706},
doi = {10.1609/AAAI.V25I1.7866},
url = {https://mlanthology.org/aaai/2011/macarthur2011aaai-distributed/}
}