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]. Paderborn, 2018
Inhalt
- Vorwort
- Zusammenfassung
- Abstract
- Introduction
- Time Model and Robot Model
- Related Work
- Gathering Anonymous, Oblivious Robots on a Grid
- Introduction
- Our Local Model
- The Algorithm
- Measuring the Gathering Progress
- Correctness & Running Time
- Progress measure Boundary
- Impact of Inhibit patterns: Collisions
- Progress measure Convex
- Progress measure Area
- Total running time
- Proof of Lemma 4.3
- Outline of the proof
- Preparing for the proofs
- Bridges
- Area progress for swarms without bridges (Lemma 4.7).
- Area progress for swarms with bridges (Lemma 4.8).
- Proof of Lemma 4.5
- Simulation Results
- Simulation Results – Progress Analysis
- Asymptotically Optimal Gathering on a Grid
- Introduction
- The Algorithm
- Why the Strategy Produces Progress in Gathering
- Correctness and Running Time
- Run Passing Operation in Detail
- Gathering a Closed Chain of Robots on a Grid
- Introduction
- Basic Idea of the Algorithm
- Merges
- Reshapement of the chain, done by runners
- Parallelizing runs: Pipelining
- Stopping runs
- Correctness and running time
- Algorithm in Detail
- Correctness and Running Time
- Conclusions & Outlook
- Bibliography