16. Februar 2018

Wir gratulieren Daniel Jung zu seiner Promotion

Erfolgreich hat Daniel Jung seine Promotionsprüfung abgelegt. Er promovierte zu dem Thema „Local Strategies for Swarm Formations on a Grid“ bei Prof. Dr. Friedhelm Meyer auf der Heide.

Die 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 einem zuvor 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 und beweisen 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.

Wir gratulieren herzlichst.

zurück zur Übersicht