| 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. |
