| |
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 ignored. To address part of
this negligence, this dissertation focuses 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 some objective grounding to this
important area of research, this dissertation presents 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. By casting
MRTA problems in the well-understood framework of optimization, a
half-century of work in operations research, game theory, economics,
and network flows can be adapted for use in robotic domains. This
dissertation demonstrates how such theory can be used for analysis and
greater understanding of existing approaches to task allocation, and
suggests how the same theory can be used in the synthesis of new
approaches. Although vital for the advancement of the field, analysis
is only one component of a comprehensive research
agenda. Sensor-actuator systems such as robots present a rich, complex
problem domain that can exhibit significant levels of noise and
uncertainty. One must implement and empirically validate proposed MRTA
algorithms. Thus this dissertation also presents experimental work
with an auction-based task allocation system, implemented on physical
robots. Optimization theory is used to explain how and why this
approach is successful. This kind of empirical work is a natural
complement to formal analysis, and can serve the crucial role of
suggesting modifications to the formal model that is analyzed. Such
experiments require substantial supporting software
infrastructure. This dissertation describes the underlying software
facilities that were developed for experimental use in the study of
MRTA, as well as for more general use. Specifically discussed is the
Player/Stage project, which produces high-quality Open Source software
to support robotics research, with the goal of providing a standard
platform for mobile robot experimentation and simulation.
|
