A Formal Analysis and Taxonomy of Task Allocation in Multi-Robot Systems

TLDR

Despite more than a decade of experimental work in multi‑robot systems, theoretical aspects of coordination mechanisms remain largely untreated, and MRTA research has largely been ad hoc and empirical with infrequent analysis. The study aims to bring objective grounding to multi‑robot task allocation by formally analyzing MRTA problems. The authors conduct a formal study of MRTA problems, applying operations‑research and combinatorial‑optimization theory to analyze existing approaches and guide the synthesis of new ones. They present a domain‑independent taxonomy of MRTA problems, showing that many can be cast as instances of well‑studied optimization problems, and illustrate how this theory can both analyze current methods and inspire new ones.

Abstract

Despite more than a decade of experimental work in multi-robot systems, important theoretical aspects of multi-robot coordination mechanisms have, to date, been largely untreated. To address this issue, we focus on the problem of multi-robot task allocation (MRTA). Most work on MRTA has been ad hoc and empirical, with many coordination architectures having been proposed and validated in a proof-of-concept fashion, but infrequently analyzed. With the goal of bringing objective grounding to this important area of research, we present a formal study of MRTA problems. A domain-independent taxonomy of MRTA problems is given, and it is shown how many such problems can be viewed as instances of other, well-studied, optimization problems. We demonstrate how relevant theory from operations research and combinatorial optimization can be used for analysis and greater understanding of existing approaches to task allocation, and to show how the same theory can be used in the synthesis of new approaches.