Go to page
 

Bibliographic Metadata

Title
Local 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]
AuthorPodlipyan, Pavel
ParticipantsMeyer auf der Heide, Friedhelm ; Scheideler, Christian
PublishedPaderborn, 2017
Edition
Elektronische Ressource
Description1 Online-Ressource (xii, 100 Seiten) : Diagramme
Institutional NoteUniversität Paderborn, Dissertation, 2017
Annotation
Tag der Verteidigung: 08.11.2017
Defended on2017-11-08
LanguageEnglish
Document TypesDissertation (PhD)
URNurn:nbn:de:hbz:466:2-29792 
DOI10.17619/UNIPB/1-230 
Files
Local algorithms for the continuous gathering problem [1.36 mb]
Links
Reference
Classification
Abstract (German)

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 (English)

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