Local strategies for robot formation problems / by Barbara Kempkes

Bibliographic Metadata

Links

Files

Classification

Zusammenfassung

Wir betrachten eine Gruppe von mobilen, autonomen Robotern in einem ebenen Gelände. 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, unter welchen Voraussetzungen die Roboter sich auf einem Punkt versammeln bzw. eine Linie zwischen zwei festen Stationen bilden können. Dafür werden mehrere Roboter-Strategien in verschiedenen Bewegungsmodellen vorgestellt. Diese Strategien werden auf ihre Effizienz hin untersucht. Es werden obere und untere Schranken für die benötigte Anzahl Runden und die Bewegungsdistanz gezeigt. In einigen Fällen wird außerdem die benötigte Bewegungsdistanz mit derjenigen Bewegungsdistanz verglichen, die eine optimale globale Strategie auf der gleichen Instanz benötigen würde. So werden kompetititve Faktoren hergeleitet.

Abstract

We consider a team of autonomous mobile robots in the Euclidean plane. There is no central control and the robots have to coordinate themselves. The key challenge is that each robot can only see its immediate neighbors and can also communicate only with robots in this neighborhood. This results in many algorithmic problems. This dissertation examines the conditions under which the robots can gather in one point respectively form a line between two fixed stations. For both problems, several robot strategies are presented in various models. These strategies are examined for their efficiency; Upper and lower bounds for the required number of rounds as well as the travelled distance are shown. In some cases, we also compare the distance traveled when using our strategies to the distance needed by an optimal global algorithm. Like this, competitive factors are derived.

Stats

License/Rightsstatement