Go to page
 

Bibliographic Metadata

Title
Local strategies for robot formation problems / by Barbara Kempkes
AuthorKempkes, Barbara
ExaminerMeyer auf der Heide, Friedhelm ; Kleine Büning, Hans
Published2012
Institutional NotePaderborn, Univ., Diss., 2012
Annotation
Tag der Verteidigung: 17.02.2012
LanguageEnglish
Document TypesDissertation (PhD)
URNurn:nbn:de:hbz:466:2-8599 
Files
Local strategies for robot formation problems [3.83 mb]
Links
Reference
Classification
Abstract (German)

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 (English)

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.