fast-consensus-fully (2).pdf (874.94 kB)
Download file

Fast consensus for fully distributed multi-agent task allocation

Download (874.94 kB)
conference contribution
posted on 12.02.2018, 13:59 authored by Joanna Turner, Qinggang MengQinggang Meng, Gerald SchaeferGerald Schaefer, Andrea SoltoggioAndrea Soltoggio
In distributed multi-agent task allocation problems, the time to find a solution and a guarantee of reaching a solution, i.e. an execution plan, is critical to ensure a fast response. The problem is made more difficult by time constraints on tasks and on agents, which may prevent some tasks from being executed. This paper proposes a new distributed consensus-based task allocation algorithm that reduces convergence time with respect to previous methods, i.e. the time required for the network of agents to agree on a task allocation, while maximising the number of allocated tasks. The novel idea is to reduce the time to reach consensus among agents by using a hierarchy or rank-based conflict resolution among agents. Unlike other existing algorithms, this method enables different agents to construct their task schedules using any insertion heuristic, and still guarantee convergence. Simulation results demonstrate that the proposed approach can allocate a greater number of tasks in a shorter time than an established baseline method. Additionally, the analysis delineates dependencies between optimal insertion strategies and number of tasks per agent, providing insights for further optimisation strategies.

History

School

  • Science

Department

  • Computer Science

Published in

The 33rd ACM Symposium On Applied Computing

Citation

TURNER, J. ... et al, 2018. Fast consensus for fully distributed multi-agent task allocation. IN: Proceedings of SAC 2018: Symposium on Applied Computing, Pau, France, 9-13 April 2018, pp.832-839.

Publisher

© ACM

Version

AM (Accepted Manuscript)

Acceptance date

17/11/2017

Publication date

2018

Notes

© ACM 2018. This is the author's version of the work. It is posted here for your personal use. Not for redistribution. The definitive Version of Record was published in Proceedings of SAC 2018: Symposium on Applied Computing, http://dx.doi.org/10.1145/3167132.3167224.

ISBN

9781450351911

Language

en

Location

Pau, France