Algorithms for Swarm Robotics: Distributed Computing meets Dynamical Systems

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