Zur Seitenansicht
 

Titelaufnahme

Titel
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]
AutorPodlipyan, Pavel
BeteiligteMeyer auf der Heide, Friedhelm In der Gemeinsamen Normdatei der DNB nachschlagen ; Scheideler, Christian In der Gemeinsamen Normdatei der DNB nachschlagen
ErschienenPaderborn, 2017
Ausgabe
Elektronische Ressource
Umfang1 Online-Ressource (xii, 100 Seiten) : Diagramme
HochschulschriftUniversität Paderborn, Dissertation, 2017
Anmerkung
Tag der Verteidigung: 08.11.2017
Verteidigung2017-11-08
SpracheEnglisch
DokumenttypDissertation
URNurn:nbn:de:hbz:466:2-29792 Persistent Identifier (URN)
DOI10.17619/UNIPB/1-230 
Dateien
Local algorithms for the continuous gathering problem [1.36 mb]
Links
Nachweis
Klassifikation
Zusammenfassung (Deutsch)

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.

Zusammenfassung (Englisch)

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