Chung_07084641.pdf (1.7 MB)
A heuristic distributed task allocation method for multivehicle multitask problems and its application to search and rescue scenario
journal contribution
posted on 2015-04-22, 14:49 authored by Wanqing Zhao, Qinggang MengQinggang Meng, Paul ChungUsing distributed task allocation methods for cooperating
multivehicle systems is becoming increasingly attractive.
However, most effort is placed on various specific experimental
work and little has been done to systematically analyze the
problem of interest and the existing methods. In this paper, a
general scenario description and a system configuration are first
presented according to search and rescue scenario. The objective
of the problem is then analyzed together with its mathematical
formulation extracted from the scenario. Considering the requirement
of distributed computing, this paper then proposes a novel
heuristic distributed task allocation method for multivehicle multitask
assignment problems. The proposed method is simple and
effective. It directly aims at optimizing the mathematical objective
defined for the problem. A new concept of significance is
defined for every task and is measured by the contribution to
the local cost generated by a vehicle, which underlies the key
idea of the algorithm. The whole algorithm iterates between a
task inclusion phase, and a consensus and task removal phase,
running concurrently on all the vehicles where local communication
exists between them. The former phase is used to include
tasks into a vehicle’s task list for optimizing the overall objective,
while the latter is to reach consensus on the significance value of tasks for each vehicle and to remove the tasks that have
been assigned to other vehicles. Numerical simulations demonstrate
that the proposed method is able to provide a conflict-free
solution and can achieve outstanding performance in comparison
with the consensus-based bundle algorithm.
Funding
This work was supported by the U.K. Engineering and Physical Sciences Research Council Autonomous and Intelligent Systems Programme [grant number EP/J011525/1] with BAE Systems as the leading industrial partner.
History
School
- Science
Department
- Computer Science
Published in
IEEE Transactions of CyberneticsVolume
46Issue
4Pages
902 - 915Citation
ZHAO, W., MENG, Q. and CHUNG, P.W.H., 2016. A heuristic distributed task allocation method for multivehicle multitask problems and its application to search and rescue scenario. IEEE Transactions on Cybernetics, 46(4), pp.902-915.Publisher
IEEEVersion
- 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
2015-03-24Publication date
2015-04-13Notes
This work is licensed under a Creative Commons Attribution 3.0 License. For more information, see http://creativecommons.org/licenses/by/3.0/ISSN
2168-2267eISSN
2168-2275Publisher version
Language
- en