English

We consider a group of autonomous robots that is deployed to an unknown terrain. There is no central control and the robots have to organize themselves. The central challenge is that each robot senses only its direct neighborhood and is only able to communicate with robots in its direct neighborhood. This leads to many algorithmic challenges. In this thesis we study, how task assignment problems can be solved in such a scenario, such that despite the locality constraints provable globally good solution are computed. In the first part of the thesis robots are assigned to treasures that are found in the terrain. In the second part of the thesis, roles within the robot team are dynamically assigned to robots. Those assignments have to be changed over time, since the robots move. In both parts, lower bounds are shown, as well as local approximation algorithms are described and analyzed.

Deutsch

Wir betrachten eine Gruppe von autonomen Robotern, die in einem unbekannten Gelände ausgesetzt werden. Es gibt keine zentrale Steuerung und die Roboter müssen sich selbst koordinieren. Zentrale Herausforderung dabei ist, dass jeder Roboter nur seine unmittelbare Nachbarschaft sieht und auch nur mit Robotern in seiner unmittelbaren Nachbarschaft kommunizieren kann. Daraus ergeben sich viele algorithmische Fragestellungen. In dieser Arbeit wird untersucht, wie in einem solchen Szenario Zuweisungsaufgaben gelöst werden können, so dass sich trotz der lokalen Einschränkungen global beweisbar gute Lösungen ergeben. Dabei werden im ersten Teil der Arbeit Roboter zu Schätzen zugewiesen, die im Gelände gefunden wurden. Im zweiten Teil der Arbeit werden dynamische Rollenzuweisungen innerhalb des Roboterteams vorgenommen. Dabei müssen die Zuweisungen mit der Zeit geändert werden, da die Roboter sich bewegen. Es werden jeweils untere Schranken gezeigt, sowie lokale Approximationsalgorithmen beschrieben und analysiert.