| |
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 show how the same theory can be used in the synthesis
of new approaches.
|
