Titelaufnahme
Titelaufnahme
- TitelForming Large Patterns from Widespread Swarms of Oblivious Robots with Limited Visibility / Jonas Harbig ; Reviewers Prof. Dr. Friedhelm Meyer auf der Heide, (Paderborn University), Prof. Dr. Christian Scheideler, (Paderborn University)
- Autor
- Gutachter
- Erschienen
- Umfang1 Online-Ressource (117 Seiten) : Diagramme
- HochschulschriftUniversität Paderborn, Dissertation, 2025
- AnmerkungTag der Verteidigung: 31.07.2025
- Verteidigung2025-07-31
- SpracheDeutsch
- DokumenttypDissertation
- Schlagwörter (GND)
- URN
- DOI
Links
- Social MediaShare
- Nachweis
- IIIF
Dateien
Klassifikation
Zusammenfassung
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.
Abstract
Within the last years, exploration of hazardous environment (e.g. the Mars) by robot swarms became more and more relevant and theoretical research on robot swarms with restricted abilities increased. However, fundamental problems such as Arbitrary-Pattern-Formation, where the swarm should self-organize to a predefined geometric pattern, remained difficult under strong restrictions. Therefore, this thesis considers disoriented robots with limited visibility and presents a novel solution to the Arbitrary-Pattern-Formation problem. The well established OBLOT model is assumed; robots are all identical, compute their decisions locally, and cannot communicate or store persistent information (oblivious). They act according to the FSYNC scheduler, where robots execute fully-synchronously Look-Compute-Move cycles. Disoriented means that each robot observes its surrounding in a self-centered, arbitrarily rotated coordinate-system. With limited visibility, only robots within a constant radius can be observed. Arbitrary-Pattern-Formation (APF) considers a swarm, where all n robots know a pattern in advance and must obtain it in arbitrary rotation and translation. The problem is already solved for oblivious robots with global visibility [Yamashita, 2010]. The possibility of forming a pattern depends on its symmetricity, a measurement of the rotational symmetries that counts how often a pattern matches itself while rotating it around itself. The symmetricity of the pattern must be an integer multiple of the swarms symmetricity, otherwise APF is not solvable in general; this is called symmetry condition in the following. [Yamauchi, 2013] presents a solution of APF for robots with (arbitrary large) memory and limited visibility, but the swarm can only form a pattern with diameter ≤ 1:First, the swarm is contracted to a diameter ≤ 1 (this is called Near-Gathering) without changing its symmetricity, and then the formation of the pattern from [Yamashita, 2010] is applied to form a small pattern that satisfies the symmetry condition. Note that limited visibility naturally restricts the results to connected swarms, i.e. where the unit-disc-graph is connected. None of the mentioned results holds for oblivious robots with limited visibility. This thesis extents the results from [Yamashita, 2010] and [Yamauchi, 2013] to oblivious robots with limited visibility. First, a class called λ-contracting Near-Gathering protocols is presented, which are to our knowledge the first Near-Gathering protocols under this model. A Near-Gathering protocol transforms a widespread swarm (diameter can be much larger than 1) into a contracted swarm (diameter ≤ 1). Secondly, as far as we know the first method for analyzing the symmetricity change induced by a protocol is presented, and two concrete symmetricity preserving protocols are given. One protocol always preserves symmetricity, but leads only for certain swarms to Near-Gathering. The other one preserves symmetricity only when the Connectivity-Boundary (the set of robots surrounding the swarm) is convex and the swarm does not contain a 1-hole (circle of diameter 1 without a robot) but always leads to a Near-Gathering. Thirdly, to the best knowledge the first APF protocol for oblivious robots with limited visibility is presented that forms any large connected pattern (diameter can be much larger than 1) from any contracted initial configuration that fulfills the symmetry condition above. To round up the results, they are generalized for APF with widespread patterns -- a significantly more difficult problem as robots have to coordinate themselves outside their viewing range. The three results above do not require memory. However, it is shown in this thesis that the formation of a large pattern is not in general possible for oblivious robots with limited visibility if the swarm is widespread (even though both are connected and the symmetry condition is fulfilled). But by introducing just one single bit of memory it is possible to combine the results such that a large connected pattern can be formed from a widespread swarm. The combined result only holds for swarms that fulfill the symmetry condition and where Near-Gathering preserves symmetricity, i.e. that have a convex Connectivity-Boundary and contain no 1-hole.
Inhalt
Lizenz-/Rechtehinweis
