Local protocols for contracting and expanding robot formation problems
Creators: name: Castenow, Jannik
Publisher: name: Universität Paderborn
Year: 2023

description: Inspiriert von der Vision von Roboterschwärmen, die gemeinsam Gebiete wie die Oberfläche entfernter Planeten erkunden, untersuchen wir die theoretischen Grundlagen von mobilen Roboterschwärmen. Die Roboter werden als Punkte in einem d-dimensionalen euklidischen Raum modelliert. Jeder Roboter hat nur sehr begrenzte Fähigkeiten und lokale Informationen über seine Umgebung (er kann andere Roboter nur bis zu seiner Sichtweite wahrnehmen). In der Regel sind die Roboter orientierungslos, d. h., sie haben kein gemeinsames Koordinaten- oder Positionierungssystem. Aufgrund der begrenzten Fähigkeiten der Roboter werden bereits grundlegende Aufgaben für die Roboter zu einer algorithmischen Herausforderung.In dieser Arbeit untersuchen wir vier Formationsprobleme, bei denen sich die Roboter so bewegen sollen, dass ihre Positionen ein vorgegebenes Muster bilden.Unser Fokus liegt auf der folgenden Frage: Wie schnell können die Roboter ein bestimmtes Formationsproblem mit gegebenen Roboterfähigkeiten lösen? Die Formationsprobleme können in zwei Klassen eingeteilt werden: Kontrahierende und expandierende Formationsprobleme. Das Ziel von kontrahierenden Formationsproblemen ist es, die Roboter näher zusammenzubringen oder eine Zielstruktur zu minimieren.Auf der anderen Seite gibt es expandierende Formationsprobleme, bei denen sich die Roboter ausbreiten müssen, um eine möglichst große Fläche abzudecken oder eine Zielstruktur zu maximieren.Kontrahierende Formationsprobleme sind in der Literatur gut bekannt, aber über expandierende Formationsprobleme ist, insbesondere bei Robotern mit nur lokalen Informationen, noch viel Forschungsbedarf.Konkret untersuchen wir die kontrahierenden Formationsprobleme Gathering und Chain-Formation. Beim Gathering müssen sich die Roboter zu einem einzigen, nicht vordefinierten Punkt bewegen. [...]
description: Inspired by the vision of robot swarms collectively exploring hazardous areas such as the surface of distant planets, we study the theoretical foundations of mobile robot swarms. The robots are modeled as points in a d-dimensional Euclidean space. Each robot on its own has very limited capabilities and only local information about its environment (it can only observe other robots up to its viewing range). Mostly, the robots are disoriented, i.e., they do not agree on any common coordinate or positioning system. Due to the limited capabilities of the robots, even basic tasks for the robots become algorithmically challenging. In this thesis, we study four robot formation problems in which the robots are to move such that their positions fulfill a predefined pattern. Our focus lies on the following question: How fast can the robots solve a particular formation problem under given robot capabilities? The formation problems can be categorized into two classes: contracting and expanding formation problems. The goal of contracting formation problems is to move the robots closer together or to minimize a target structure. On the opposite side, we have expanding formation problems, where the robots have to spread out to cover as much area as possible or to maximize a target structure. Contracting formation problems are well-established in the literature, but much less is known about expanding formation problems, especially for robots with only local information. Concretely, we study the two contracting formation problems Gathering and Chain-Formation.Gathering demands to move the robots to a single, not predefined point. [...].