Algorithmen für Schwarmrobotik: Verteiltes Rechnen trifft Dynamische Systeme

Überblick

Das Ziel dieses Projekts ist es, die Fähigkeiten und Grenzen lokaler, verteilter Strategien für Schwärme mobiler Roboter zu untersuchen. Solche Strategien bestehen aus Protokollen, die von den einzelnen Robotern ausgeführt werden. Sie sollen die Bewegungen der Roboter so steuern, dass aus einer beliebigen Ausgangskonfiguration der Roboter global eine vorgegebene Formation wie Sammeln, Linienbildung oder andere Formen erreicht wird. Diese Forschungsrichtung ist im Verteilten Rechnen gut etabliert. Unser Ansatz besteht darin, Methoden und Techniken aus der Forschung über Verteiltes Rechnen und über Dynamische Systeme zu kombinieren, um das Verständnis von Protokollen für solche Formationsaufgaben zu erweitern. Zu diesem Zweck analysieren wir die Geschwindigkeit der Protokolle im Hinblick auf die Laufzeitkomplexität im Sinne des verteilten Rechnens, sowie Stabilitätseigenschaften der vorgegebenen Formation unter Verwendung von Ideen aus Dynamischen Systemen. Während im Verteilten Rechnens oft nur eine Worst-Case-Analyse in Betracht gezogen wird, erlauben die Werkzeuge Dynamischer Systeme eine feinkörnigere Analyse der Eingabekonfigurationen durch Untersuchung des Zustandsraums. Konkret beschreibt die State Space Foliation langfristige dynamische Verhalten von Eingabekonfigurationen detaillierter, d.h. sie erlaubt es Klassen von Konfigurationen zu identifizieren, die unterschiedlich schnell konvergieren, und sogar Klassen, die nicht zu der vorgeschriebenen Formation konvergieren. Die Kombination beider Sichten führt somit zu einem fundierteren Verständnis der Auswirkungen verteilter Strategien für Schwärme mobiler Roboter.

DFG-Verfahren Sachbeihilfen

Antragsteller Professor Dr. Michael Dellnitz; Professor Dr. Friedhelm Meyer auf der Heide

Key Facts

Laufzeit:
04/2021 - 08/2024
Gefördert durch:
DFG
Websites:
DFG-Datenbank gepris
Algorithms for Swarm Robotics: Distributed Computing meets Dynamical Systems

Detailinformationen

Projektleitung

contact-box image

Prof. Dr. Michael Dellnitz

Lehrstuhl für Angewandte Mathematik

Zur Person
contact-box image

Prof. Dr. Friedhelm Meyer auf der Heide

Algorithmen und Komplexität / Heinz Nixdorf Institut

Zur Person

Projektmitglieder

contact-box image

Dr. Raphael Gerlach

Institut für Industriemathematik

Zur Person
contact-box image

Jannik Castenow M.Sc.

Zur Person
contact-box image

Jonas Harbig

Algorithmen und Komplexität / Heinz Nixdorf Institut

Zur Person
contact-box image

Dr. Sören von der Gracht, (geb. Schwenker)

Lehrstuhl für Angewandte Mathematik

Zur Person

Kontakt

Wenn Sie Fragen zu diesem Projekt haben, kontaktieren Sie uns!

Jannik Castenow M.Sc.

contact-box image

Jonas Harbig

Algorithmen und Komplexität / Heinz Nixdorf Institut

Wissenschaftlicher Mitarbeiter - Mitglied - Forschung zu Schwarmalgorithmen

contact-box image
+49 5251 60-6427 F2.413

Publikationen

Gathering a Euclidean Closed Chain of Robots in Linear Time and Improved Algorithms for Chain-Formation
J. Castenow, J. Harbig, D. Jung, T. Knollmann, F. Meyer auf der Heide, Theoretical Computer Science 939 (2023) 261–291.
A Unifying Approach to Efficient (Near-)Gathering of Disoriented Robots with Limited Visibility
J. Castenow, J. Harbig, D. Jung, P. Kling, T. Knollmann, F. Meyer auf der Heide, in: E. Hillel, R. Palmieri, E. Riviére (Eds.), Proceedings of the 26th International Conference on Principles of Distributed Systems (OPODIS) , Schloss Dagstuhl – Leibniz Zentrum für Informatik, Brussels, 2023, p. 15:1–15:25.
Unifying Gathering Protocols for Swarms of Mobile Robots
J. Castenow, J. Harbig, F. Meyer auf der Heide, in: Lecture Notes in Computer Science, Springer International Publishing, Cham, 2023.
On the Dynamical Hierarchy in Gathering Protocols with Circulant Topologies
R. Gerlach, S. von der Gracht, M. Dellnitz, ArXiv:2305.06632 (n.d.).
A Discrete and Continuous Study of the Max-Chain-Formation Problem
J. Castenow, P. Kling, T. Knollmann, F. Meyer auf der Heide, Information and Computation (2022).
Alle Publikationen anzeigen