Mechanism Selection for Multi-Robot Task Allocation

Schneider, E ORCID: 0000-0002-2354-126X (2018) Mechanism Selection for Multi-Robot Task Allocation. Doctor of Philosophy thesis, University of Liverpool.

Text 200986513_Feb2018.pdf - Unspecified Download (9MB)

Abstract

There is increasing interest in fielding multi-robot teams for applications such as search and rescue, warehouse automation, and delivery of consumer goods. Task allocation is an important problem to solve in such multi-robot settings. Given a mission that can be decomposed into discrete tasks, the Multi-Robot Task Allocation (MRTA) problem looks for an assignment of tasks to robots that ultimately results in efficient execution of the mission. There is a range of approaches to this optimisation problem, from centralised solvers to fully distributed methods that involve no explicit coordination between team members. Somewhere in the middle of this range lie market-based approaches, where tasks can be treated as goods, robots as "buyers" who can compute and express their own preferences for tasks in a virtual marketplace, and some clearing mechanism exists to match tasks to robots according to these preferences. The most common type of market-based mechanism for multi-robot task allocation is an auction, in which tasks are announced to the team, robots compute and place bids that encode some measure of cost or utility of performing the tasks, and tasks are awarded to robots over a number of rounds, according to the particular rules of the mechanism. Many different auction mechanisms exist, and they vary in the trade-offs that they make between computation time and space on the one hand, and performance of the execution of the mission on the other. In addition, the performance that results from a mechanism's allocation can be greatly affected by properties of task environments---the spatial and temporal arrangements of tasks, as well as other properties like precedence constraints, whether tasks require the simultaneous cooperation of multiple robots, and so on---in which it is employed. A simple mechanism that is inexpensive to compute and scales well may perform well in some environments, but not in others. The work presented in this thesis focuses on this relationship between auction-based task allocation mechanisms and properties of task environments, with the goal of developing a method of selecting, from a portfolio, a mechanism that is appropriate for a given task environment. The first part of this work is an empirical performance evaluation of a range of mechanisms employed in a series of environments of increasing complexity. The second part of this work uses results from this evaluation to develop and train a data-driven method of mechanism selection using properties of environments that can be measured at the start of a mission. The results show that, under certain conditions, this method of mechanism selection can lead to significant performance improvements compared to using a single mechanism alone.

Item Type:	Thesis (Doctor of Philosophy)
Divisions:	Faculty of Science and Engineering > School of Electrical Engineering, Electronics and Computer Science
Depositing User:	Symplectic Admin
Date Deposited:	20 Aug 2018 08:00
Last Modified:	19 Jan 2023 06:39
DOI:	10.17638/03018369
Supervisors:	Sklar, Elizabeth Parsons, Simon Tuyls, Karl
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3018369