TY  - THES
AB  - 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.
AU  - Podlipyan, Pavel
CY  - Paderborn
DA  - 2017
DO  - 10.17619/UNIPB/1-230
DP  - Universität Paderborn
LA  - eng
N1  - Tag der Verteidigung: 08.11.2017
N1  - Universität Paderborn, Dissertation, 2017
PB  - Veröffentlichungen der Universität
PY  - 2017
SP  - 1 Online-Ressource (xii, 100 Seiten)
T2  - Institut für Informatik
TI  - Local algorithms for the continuous gathering problem
UR  - https://nbn-resolving.org/urn:nbn:de:hbz:466:2-29792
Y2  - 2025-04-20T01:21:48
ER  -