Go to page
 

Bibliographic Metadata

Title
Local strategies for swarm formations on a grid / Daniel Jung ; [Reviewers: Prof. Dr. Friedhelm Meyer auf der Heide, Paderborn University ; Prof. Dr. Christian Scheideler, Paderborn University]
AuthorJung, Daniel
ParticipantsMeyer auf der Heide, Friedhelm ; Scheideler, Christian
PublishedPaderborn, 2018
Edition
Elektronische Ressource
Description1 Online-Ressource (xiii, 129 Seiten) : Diagramme
Institutional NoteUniversität Paderborn, Dissertation, 2018
Annotation
Tag der Verteidigung: 13.02.2018
Defended on2018-02-13
LanguageEnglish
Document TypesDissertation (PhD)
URNurn:nbn:de:hbz:466:2-30212 
DOI10.17619/UNIPB/1-271 
Files
Local strategies for swarm formations on a grid [2.92 mb]
Links
Reference
Classification
Abstract (German)

Meine Dissertation beschäftigt sich mit dem Gathering Problem für Schwärme von n punktförmigen Robotern auf einem Gitter, bei dem sich alle Roboter des Schwarms auf einemzuvor nicht festgelegten Punkt versammeln sollen. Besonderes Augenmerk liegt auf der starken Einschränkung der Roboterfähigkeiten. Hierzu zählen insbesondere das Fehlen einer globalen Steuerung, eines globalen Kompasses, einer globalen Sichtweite und einer (globalen) Kommunikationsfähigkeit. Darüber hinaus sind alle Roboter identisch. Den Robotern sind nur lokale Fähigkeiten gegeben. Hierzu zählt etwa eine nur konstante Sichtweite. Die Roboter arbeiten alle vollständig synchron. Wir präsentieren und analysieren drei Gatheringstrategien unter verschiedenen Robotermodellen undbeweisen jeweils formal Korrektheit und Gesamtlaufzeit: In Kapitel 4 liegt der Fokus auf der Minimierung der zur Verfügung stehenden Roboterfähigkeiten. Die zugrundeliegende Strategie schließt das Gathering in Zeit O(n^2) ab. In den Kapiteln 5 und 6 ist das Ziel die Laufzeitoptimierung unter weiterhin nur lokalen Roboterfähigkeiten: Wir erlauben zusätzlich einen konstant großen Speicher und eine konstante Anzahl lokal sichtbarer Status (Lichter, Flaggen)und beweisen jeweils eine asymptotisch optimale Laufzeit O(n). Anders als in den Kapiteln 4 und 5, beschränken wir in Kapitel 6 Konnektivität und Sicht zusätzlich durch eine initial gegebene Kettenstruktur mit Kantenlänge 1.

Abstract (English)

My dissertation deals with the Gathering problem for swarms of n point-shaped robots on a grid, in which all robots of the swarm are supposed to gather at a previously undefined point. Special attention is paid to the strong limitation of robot capabilities. These include in particular the lack of global control, a global compass, global visibility and (global) communication skills. Furthermore, all robots are identical. The robots are given only local abilities. This includes a constant range of vision. The robots all work completely synchronously. In this work we present and analyze three different Gathering strategies in different robot models. We formally prove correctness and total running time: Chapter 4 focuses on minimizing the available robot capabilities. The underlying strategy completes the gathering in O(n^2) time. For the following Chapters 5 and 6, the aim is to optimize the total running time under using only local robot capabilities: We additionally allow a constant-sized memory and a constant number of locally visible statuses (lights, flags). For the strategies of both chapters we show an asymptotically optimal running time of O(n). Unlike in Chapters 4 and 5, we additionally restrict connectivity and vision to an initially given chain connectivity in Chapter 6, where two chain neighbors must have a distance of 1 from each other. A robot can only see and interact with a constant number of its direct chain neighbors.

License
CC-BY-License (4.0)Creative Commons Attribution 4.0 International License