08053456.pdf (1.33 MB)
Download file

Distributed task rescheduling with time constraints for the optimization of total task allocations in a multirobot system

Download (1.33 MB)
journal contribution
posted on 07.09.2017, 15:17 by Joanna Turner, Qinggang MengQinggang Meng, Gerald SchaeferGerald Schaefer, Amanda Whitbrook, Andrea SoltoggioAndrea Soltoggio
This paper considers the problem of maximising the number of task allocations in a distributed multi-robot system under strict time constraints, where other optimisation objectives need also be considered. This study builds upon existing distributed task allocation algorithms, extending them with a novel method for maximising the number of task assignments. The fundamental idea is that a task assignment to a robot has a high cost if its reassignment to another robot creates a feasible time slot for unallocated tasks. Multiple reassignments among networked robots may be required to create a feasible time slot and an upper limit to this number of reassignments can be adjusted according to performance requirements. A simulated rescue scenario with task deadlines and fuel limits is used to demonstrate the performance of the proposed method compared with existing methods, the Consensus-Based Bundle Algorithm (CBBA) and the Performance Impact algorithm (PI). Starting from existing (PI-generated) solutions, results show an up to 20% increase in task allocations using the proposed method.

Funding

Q.Meng was supported by EPSRC (grant number EP/J011525/1) with BAE Systems as the leading industrial partner.

History

School

  • Science

Department

  • Computer Science

Published in

IEEE Transactions on Cybernetics

Volume

48

Issue

9

Pages

2583 - 2597

Citation

TURNER, J. ... et al, 2018. Distributed task rescheduling with time constraints for the optimization of total task allocations in a multirobot system. IEEE Transactions on Cybernetics, 48(9), pp.2583-2597.

Publisher

IEEE

Version

VoR (Version of Record)

Publisher statement

This work is made available according to the conditions of the Creative Commons Attribution 3.0 Unported (CC BY 3.0) licence. Full details of this licence are available at: http://creativecommons.org/licenses/by/3.0/

Acceptance date

07/08/2017

Publication date

2017-09-28

Notes

This is an Open Access Article. It is published by IEEE under the Creative Commons Attribution 3.0 Licence (CC BY). Full details of this licence are available at: http://creativecommons.org/licenses/by/3.0/.

ISSN

2168-2267

eISSN

2168-2275

Language

en