08053456.pdf (1.33 MB)
Distributed task rescheduling with time constraints for the optimization of total task allocations in a multirobot system
journal contributionposted on 2017-09-07, 15:17 authored 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.
Q.Meng was supported by EPSRC (grant number EP/J011525/1) with BAE Systems as the leading industrial partner.
- Computer Science
Published inIEEE Transactions on Cybernetics
Pages2583 - 2597
CitationTURNER, 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.
- VoR (Version of Record)
Publisher statementThis 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/
NotesThis 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/.