TY  - THES
AB  - In den letzten Jahren ist die Erkundung von gefahrenreichen Umgebungen (z.B. dem Mars) durch Roboterschwärme immer relevanter gewordern und die Forschung an Roboterschwärmen mit eingeschränkten Fähighkeiten hat zugenommen. Allerdings sind fundamentale Probleme wie Arbitrary-Pattern-Formation (zu deutsch: Beliebige-Muster-Bildung), in dem ein Schwarm selbst organisiert ein vorab definiertes geometrisches Muster bilden soll, nach wie vor schwer zu lösen für stark eingeschränkt Roboter. Daher betrachten diese Arbeit orientierungslose Roboter mit eingeschränkter Sichtweite  und präsentiert eine neue Lösung des Arbitrary-Pattern-Formation Problems. Das OBLOT Modell wird angenommen, in dem Roboter identisch sind, ihre Entscheidungen lokal treffen und weder miteinander kommunizieren noch Informationen dauerhaft speichern können (erinnerungslos). Roboter agieren in vollkommen synchronen Zyklen (FSYNC), in denen zunächst alle Roboter ihre Umgebung beobachten, dann eine Bewegung auf Basis der Beobachtung berechnen und diese schließlich ausführen. Orientierungslos heißt, dass jeder Roboter seine Umgebung in einem selbstzentrierten und beliebig gedrehtem Koordinatensystem wahrnimmt. Mit eingeschränkter Sichtweite können nur Roboter in einem konstanten Radius beobachtet werden. Das Arbitrary-Pattern-Formation (APF) Problem betrachtet einen Schwarm, in dem alle n Roboter ein Muster P ∈ R^2n kennen und dieses in beliebiger Rotation und Translation bilden müssen. Das Problem ist bereits für erinnerungslose Roboter mit globaler Sicht gelöst [Yamashita, 2010]. Es wurde gezeigt, dass es von der Symmetricity des Musters abhängt, ob dieses gebildet werden kann. Symmetricity ist eine Einheit für die Rotationssymmetrien einer Punktmenge; sie zählt, wie häufig die Menge mit sich selbst übereinstimmt, während sie einmal um sich selbst gedreht wird. Die Symmetricity des Musters muss ein ganzzahliges Vielfaches der Symmetricity des Schwarmes haben, damit das Muster gebildet werden kann; dies wird im Folgenden als Symmetriebedingung bezeichnet. [Yamauchi, 2013] präsentiert eine Lösung des APF Problems für Roboter mit (beliebig großem) Speicher und begrenzter Sichtweite, allerdings muss das Muster einen Durchmesser von ≤ 1 haben. Zunächst wird der Schwarm zusammengezogen zu einem Durchmesser ≤ 1 (das wird Near-Gathering genannt, zu deutsch: Nahes-Versammeln) ohne dass sich seine Symmetricity ändert. Dann wird das Protokoll aus [Yamashita, 2010] angewendet, um ein kleines Muster zu bilden, welches die Symmetriebedingung erfüllt. Die begrenzte Sichtweite schränkt die Ergebnisse auf Schwärme ein, deren Unit-Disc-Graph zusammenhängt. Keines der genannten Ergebnisse gilt für erinnerungslose Roboter mit eingeschränkter Sichtweite. Diese Dissertation erweitert die Ergebnisse von [Yamashita, 2010] und [Yamauchi, 2013] für orientierungslose OBLOT Roboter mit eingeschränkter Sichtweite. Erstens: Eine Klasse, genannt λ-kontrahierende Near-Gathering Protokolle, wird präsentiert, welche nach bestem Wissen die ersten bekannten Near-Gathering Protokolle für dieses Modell sind. Ein Near-Gathering Protokoll verwandelt einen weitverteilten Schwarm (der Durchmesser kann viel größer als 1 sein) in einen kontrahierten Schwarm (Durchmesser ≤ 1). Zweitens: Die, soweit wir wissen, erste Methode zur Untersuchung der Symmetricity-Änderung aufgrund eines Protokolls wird präsentiert. Außerdem werden zwei konkrete Symmetricity-erhaltende Protokolle angegeben. Das eine erhält in allen Fällen die Symmetricity, führt aber nur in einigen Fällen zu Near-Gathering. Das andere erhält die Symmetricity nur, wenn die Connectivity-Boundary (die Menge der Roboter, die den Schwarm umschließen) konvex ist und der Schwarm kein 1-Loch (ein Kreis mit Durchmesser 1 ohne Roboter) beinhaltet, führt aber in jedem Fall zu Near-Gathering. Drittens: Das, unseres Wissens nach, erste Arbitrary-Pattern-Formation Protokoll für dieses Modell wird präsentiert, welches jedes große und zusammenhängende Muster (der Durchesser kann viel größer als 1 sein) von jedem kontrahierten Schwarm bilden kann, wenn die Symmetriebedingung erfüllt ist. Um die Ergebnisse abzurunden werden sie generalisiert für APF mit weitverteilten Schwärmen -- ein signifikant schwereres Problem, da Roboter sich koordinieren müssen ohne sich gegenseitig sehen zu können. Die drei oben genannten Resultate benötigen keinen Speicher. Allerdings wird in dieser Arbeit gezeigt, dass das Bilden eines großen Musters nicht im Generellen für erinnerungslose Roboter mit eingeschränkter Sichtweite möglich ist, wenn der Schwarm weitverteilt ist (auch dann nicht, wenn beide zusammenhängend sind und die Symmetriebedingung erfüllt ist). Mit einem Bit Speicher ist es jedoch möglich, die Ergebnisse zu kombinieren, sodass ein großes zusammenhängendes Muster von einem weitverteiltem Schwarm gebildet werden kann. Das kombinierte Ergebnis gilt nur für Schwärme, welche die Symmetriebedingung erfüllen und in denen Near-Gathering die Symmetricity erhält, d.h. die eine konvexe Connectivity-Boundary haben und kein 1-Loch enthalten.
AU  - Harbig, Jonas
CY  - Paderborn
DO  - 10.17619/UNIPB/1-2493
DP  - Universität Paderborn
LA  - ger
N1  - Tag der Verteidigung: 31.07.2025
N1  - Universität Paderborn, Dissertation, 2025
PB  - Veröffentlichungen der Universität
PY  - 2025
SP  - 1 Online-Ressource (117 Seiten) : Diagramme
T2  - Institut für Informatik
TI  - Forming Large Patterns from Widespread Swarms of Oblivious Robots with Limited Visibility
UR  - https://nbn-resolving.org/urn:nbn:de:hbz:466:2-57171
Y2  - 2026-02-04T14:17:25
ER  -