Bibliographic Metadata
Bibliographic Metadata
- TitleLocal algorithms for the continuous gathering problem : / vorgelegt von Pavel Podlipyan ; [Betreuer: Prof. Dr. Friedhelm Meyer auf der Heide, Universität Paderborn, Gutachter: Prof. Dr. Friedhelm Meyer auf der Heide, Universität Paderborn, Prof. Dr. Christian Scheideler, Universität Paderborn]
- Author
- Participants
- Published
- EditionElektronische Ressource
- Description1 Online-Ressource (xii, 100 Seiten) : Diagramme
- Institutional NoteUniversität Paderborn, Dissertation, 2017
- AnnotationTag der Verteidigung: 08.11.2017
- Defended on2017-11-08
- LanguageEnglish
- Document TypesDissertation (PhD)
- URN
- DOI
Links
- Social MediaShare
- Reference
- IIIF
Files
Classification
Zusammenfassung
Im Zentrum unserer Betrachtung steht eine Gruppe von mobilen Robotern auf euklidischer Ebene. Roboter haben begrenzte Sicht und keine zentrale Steuerung. Sie agieren ausschließlich auf Grundlage lokaler Informationen. In diesem Rahmen ergeben sich viele algorithmische Probleme. In der vorliegenden Arbeit widmen wir uns dem Problem der kontinuierlichen Versammlung. Wir wollen herausfinden, wie schnell sich Roboter innerhalb eines kontinuierlichen Zeitmodells, an einem zuvor nicht definierten Punkt, sammeln können. In einem solchen Modell beobachtet ein Roboter seine unmittelbare Nachbarschaft kontinuierlich, während er gleichzeitig Geschwindigkeit und Richtung nach lokalen Vorgaben anpasst. Diesbezüglich legen wir eine Klasse von Algorithmen vor, die wir kontrahierende Algorithmen nennen. Algorithmen dieser Klasse veranlassen Roboter sich in der Zeit von $O(nd)$ zu sammeln, wobei $n$ die Anzahl der Roboter und $d$ den Durchmesser der Anfangskonfiguration beschreiben. Ferner zeigen wir einige konkrete kontrahierende Algorithmen, die wir auf ihre Effizienz hin untersuchen. Wir setzen Obere und Untere Schranken hinsichtlich der benötigten Zeit für die Versammlung von allen Robotern in einem zuvor nicht definierten Punkt. Daneben untersuchen wir, inwiefern sog. Proximity Untergraphen des Sichtbarkeitsgraph den Sammlungsprozess beeinflussen. Simulationen zeigen einen deutlichen Unterschied im Verhalten von solchen Robotern, die den Gabriel- oder Relativen Nachbarschaftsgraph als Sichtbarkeitsgraph nutzen. Während viele der Zusammenstöße während des Sammlungsprozesses auftreten, lässt sich bei der Verwendung von Proximity Graphen typischerweise nur ein Zusammenstoß (endgültig) ausmachen. In dieser Arbeit präsentieren wir eine kontrahierende Strategie, welche einen kollisionsfreien Sammlungsprozess gewährleistet.
Abstract
We consider a group of mobile robots in the Euclidean plane. Robots have a limited vision range and do not have a central control. Each robot acts by depending solely on local information. Many algorithmic problems arise in such a setting. In this work, we explore the continuous gathering problem. The goal is to know how fast the robots can gather in one not-predefined point in the continuous time model. In this model, each robot continuously observes its local neighborhood and adapts its speed and direction following a local rule. We present a class of algorithms, which we call the \emph
Content
Stats
- The PDF-Document has been downloaded 104 times.
License/Rightsstatement
