Task allocation strategies for multi-robot systems

Abstract

Research into multi-robot systems (MRSs) seeks to develop efficient approaches for enabling a group of autonomous robots to work together to perform complex real-world tasks. The coordination between the robots is mainly addressed using a task allocation algorithm. Distributed multi-robot task allocation (MRTA) algorithms are more robust, scalable and are suitable for the autonomous operations of robots, compared with centralised and decentralised approaches. However the scalability of distributed MRTA to large MRSs, the heterogeneity of robots, the prioritisation of tasks and the computationally efficient responses to dynamic changes have not been significantly addressed by existing MRTA algorithms.

This thesis is focussed on the conflict-free task allocations in an MRS, mainly using distributed market-based approaches to address deficiencies in current methods. In the research reported in this thesis, allocations of both single-robot (SR) tasks (tasks which can be executed by a single-task (ST) robot) and multi-robot (MR) tasks (tasks which require cooperation between robots) are addressed. Initially Multi-Robot Parallel Allocation and Execution (MRPAE), a distributed market-based ST-SR algorithm is developed for allocating a set of SR tasks in a homogeneous MRS. This algorithm is then extended to the Consensus Based Parallel Allocation and Execution (CBPAE)algorithm for allocating prioritised SR tasks in a heterogeneous MRS. The CBPAE isa novel algorithm applied to coordinate the robots in an MRS in a healthcare facility, but is also suitable for more general applications. The performance of these algorithms is evaluated in simulation and on real robots and is compared with that of existing MRTA algorithms. From these comparisons, scalability of the MRPAE and CBPAE algorithms to large MRSs and the capability in addressing dynamic changes in the environment with reduced computational complexity has been demonstrated.

In order to address the allocation of tightly-coupled MR tasks, the Centralised Co-operative Task Allocation (CeCoTA), a centralised market-based MRTA algorithm is developed. Existing ST-MR algorithms mainly address robot coalition formations and when a set of tasks has to be allocated, the tasks are allocated iteratively resulting in less efficient allocations. The CeCoTA algorithm addresses both coalition formation of heterogeneous robots and simultaneous deadlock-free allocation of multiple MR tasks to non-conflicting coalitions using an auctioneer. In a performance comparison with a Genetic Algorithm (GA) based allocation scheme in simulation, the CeCoTA algorithm achieved similar values for the main objective (aggregate coalition expertise)and a significant reduction in the distance travelled by the robots and the overall task execution time.

The CeCoTA algorithm is then extended to the Distributed Cooperative Task Allocation (DiCoTA) algorithm, by using inter-robot negotiations for conflict resolution instead of an auctioneer. The limited number of existing distributed market based ST-MR algorithms can be applied only to very specific types of tasks or cannot efficiently allocate a set of tasks. The DiCoTA algorithm addresses these deficiencies. In a performance comparison with a GA based allocation scheme in simulation, the DiCoTA algorithm achieved similar aggregate coalition expertise values and significant reduction in the distance travelled by the robots, although the overall task execution time was higher because of the additional consensus processes. Performance evaluation of the DiCoTA algorithm on real robots also demonstrated the capability of the algorithm to allocate efficiently both MR and SR tasks.

Date of Award	Feb 2015
Original language	English
Sponsors	VCRS
Supervisor	Martin Mc Ginnity (Supervisor) & Sonya Coleman (Supervisor)