Startseite > Publikationen > Publikationen

Publikationen

Jung, Daniel:

Local Strategies for Swarm Formations on a Grid.

Dissertation, Fakultät für Elektrotechnik, Informatik und Mathematik, Universität Paderborn, Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn, Band 380, Feb. 2018, ISBN 978-3-942647-99-1

Abstract

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.

Weblink

http://digital.ub.uni-paderborn.de/ubpb/urn/urn:nbn:de:hbz:466:2-30212

Bibtex

@phdthesis{hniid=9711,
author = {Jung, Daniel},
title = {Local Strategies for Swarm Formations on a Grid},
type = {Dissertation},
school = {Fakult{\"a}t f{\"u}r Elektrotechnik, Informatik und Mathematik, Universit{\"a}t Paderborn},
volume = {380},
series = {Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn},
month = feb,
year = {2018},
note = {ISBN 978-3-942647-99-1},
}

BibTeX in die Zwischenablage kopieren

Permalink

https://www.hni.uni-paderborn.de/pub/9711