Volltext-Downloads (blau) und Frontdoor-Views (grau)

Comparison of multi-robot task allocation algorithms

  • Multi-robot systems (MRS) are capable of performing a set of tasks by dividing them among the robots in the fleet. One of the challenges of working with multirobot systems is deciding which robot should execute each task. Multi-robot task allocation (MRTA) algorithms address this problem by explicitly assigning tasks to robots with the goal of maximizing the overall performance of the system. The indoor transportation of goods is a practical application of multi-robot systems in the area of logistics. The ROPOD project works on developing multi-robot system solutions for logistics in hospital facilities. The correct selection of an MRTA algorithm is crucial for enhancing transportation tasks. Several multi-robot task allocation algorithms exist in the literature, but just few experimental comparative analysis have been performed. This project analyzes and assesses the performance of MRTA algorithms for allocating supply cart transportation tasks to a fleet of robots. We conducted a qualitative analysis of MRTA algorithms, selected the most suitable ones based on the ROPOD requirements, implemented four of them (MURDOCH, SSI, TeSSI, and TeSSIduo), and evaluated the quality of their allocations using a common experimental setup and 10 experiments. Our experiments include off-line and semi on-line allocation of tasks as well as scalability tests and use virtual robots implemented as Docker containers. This design should facilitate deployment of the system on the physical robots. Our experiments conclude that TeSSI and TeSSIduo suit best the ROPOD requirements. Both use temporal constraints to build task schedules and run in polynomial time, which allow them to scale well with the number of tasks and robots. TeSSI distributes the tasks among more robots in the fleet, while TeSSIduo tends to use a lower percentage of the available robots. Subsequently, we have integrated TeSSI and TeSSIduo to perform multi-robot task allocation for the ROPOD project.

Download full text files

Export metadata

Additional Services

Search Google Scholar Check availability


Show usage statistics
Document Type:Report
Author:Ángela Patricia Enríquez Gómez
Number of pages:xxii, 241
Supervisor:Erwin Prassler, Argentina Ortega Sainz
Publishing Institution:Hochschule Bonn-Rhein-Sieg
Contributing Corporation:Bonn-Aachen International Center for Information Technology (b-it)
Date of first publication:2019/12/02
Series (Volume):Technical Report / Hochschule Bonn-Rhein-Sieg University of Applied Sciences. Department of Computer Science (02-2019)
Keyword:Healthcare logistics; Instantaneous assignment; Multi-robot systems; Task allocation; Temporal constraints; Time extended assignment
Departments, institutes and facilities:Fachbereich Informatik
Projects:ROPOD - Ultra-flat, ultra-flexible, cost-effective robotic pods for handling legacy in logistics (EC/H2020/731848)
Dewey Decimal Classification (DDC):0 Informatik, Informationswissenschaft, allgemeine Werke / 00 Informatik, Wissen, Systeme / 004 Datenverarbeitung; Informatik
Series:Technical Report / University of Applied Sciences Bonn-Rhein-Sieg. Department of Computer Science
Entry in this database:2019/12/02
Licence (Multiple languages):License LogoIn Copyright (Urheberrechtsschutz)