[Diese Seite ist derzeit noch in Bearbeitung und wird nach und nach ergänzt.]
SpaceAnts ist ein Forschungsprojekt zur Untersuchung algorithmischer Grundlagen für die Konstruktion und Rekonfiguration großskaliger Strukturen durch einfache, autonome Roboter. Das Projekt wird unter der Federführung der Technischen Universität Braunschweig und in Kooperation mit der Hochschule Bochum, der University of Houston, der Stony Brook University, dem MIT und der NASA durchgeführt. SpaceAnts wird seit dem 1. September 2024 von der Deutschen Forschungsgemeinschaft (DFG) gefördert und läuft voraussichtlich bis zum 31. August 2027.
Im Mittelpunkt von SpaceAnts steht die zentrale Herausforderung, eine Menge einfacher Roboter in die Lage zu versetzen, komplexe Bauaufgaben zu bewältigen. Dabei geht es insbesondere um Konstruktionen, die aus einer großen Anzahl modularer, gitterbasierter Komponenten bestehen. SpaceAnts zielt darauf ab, die algorithmischen Grundlagen für die Koordination großer Schwärme einfacher Roboter zu entwickeln, ohne auf einzelne Roboter mit enormen Fähigkeiten angewiesen zu sein. Dabei werden Methoden zur Optimierung und Koordination entwickelt, die verschiedene geometrische Aspekte berücksichtigen und für Anwendungen von ultraleichten modularen Strukturen im Weltraum bis hin zu mikroskopischen Dimensionen relevant sein können.
Zusätzliche Informationen über das Projekt können auf der Projektseite bei L3S und der Projektseite der Hochschule Bochum entnommen werden.
Da sich SpaceAnts noch in der laufenden Förderphase befindet, können zum jetzigen Zeitpunkt noch keine abschließenden Forschungsergebnisse präsentiert werden. Das Projekt befasst sich mit einer Vielzahl von Fragestellungen aus verschiedenen Forschungsrichtungen. Im Folgenden werden exemplarisch zwei dieser Forschungsrichtungen näher vorgestellt.
Ein Forschungsschwerpunkt in SpaceAnts ist die koordinierte Bewegungsplanung für viele autonome Roboter. Dabei wird untersucht, wie eine Menge von Robotern, die sich gleichzeitig in einer gemeinsamen Umgebung bewegt, ihre jeweilige Zielpositionen erreichen kann, ohne dass sie dabei miteinander kollidieren.
Aus dieser Problemstellung ergeben sich verschiedene Optimierungsziele. Beispielsweise kann untersucht werden, wie die Bewegungen der Roboter so geplant werden können, dass alle Roboter ihre Zielposition möglichst schnell erreichen. In diesem Fall wird die Gesamtzeit betrachtet, bis der letzte Roboter sein Ziel erreicht hat, was auch als Makespan bezeichnet wird. Eine andere Fragestellung besteht darin, die von allen Robotern insgesamt zurückgelegte Weglänge zu minimieren.
Aufbauend auf den bisherigen Ergebnissen untersucht SpaceAnts, wie koordinierte Bewegungspläne für große Roboterschwärme weiterentwickelt werden können. Dabei liegt ein Schwerpunkt auf der Erweiterung der bisherigen zweidimensionalen Ansätze auf dreidimensionale Szenarien, um die Anwendbarkeit in realen Umgebungen zu ermöglichen. Ein weiteres Ziel ist die Analyse und Verbesserung des sogenannten Stretch Factors, der das Verhältnis der benötigten Zeit eines parallelen Bewegungsplans zur theoretischen Minimalzeit beschreibt. Die Größe des Strech Factors ist jedoch eng gebunden an die Anordnung der Roboter im Raum. SpaceAnts setzt sich daher zum Ziel, das Zusammenspiel zwischen der Trennung einzelner Roboter und der Effizienz paralleler Bewegungspläne besser zu verstehen, die entsprechenden Zusammenhänge zwischen den relevanten Parametern zu formalisieren und die entwickelten Algorithmen in praktikable Steuerungsprotokolle zu überführen.
Ein zentraler Engpass bei der effizienten Planung von Bewegungs- und Rekonfigurationsprozessen von Robotern kann die zugrunde liegende Struktur, auf der diese Prozesse stattfinden sein. Beispielsweise für Kommunikationsnetzwerke, Logistik oder Verkehrssteuerung bestimmt diese Struktur maßgeblich, wie effizient sich Informationen, Materialien oder Roboter bewegen lassen. Daher reicht es nicht aus, nur die Bewegungen auf einer festen Struktur zu optimieren. Ebenso sollte auch die Struktur selbst für eine höhere Effizienz angepasst und rekonfiguriert werden. Ein wichtiges Modell für solche zugrunde liegenden Strukturen sind Triangulationen, also planare Verbindungsstrukturen, die eine Menge von Punkten in Dreiecke zerlegen und dadurch kollisionsfreie Verbindungen gewährleisten.
Allerdings sind nicht alle Triangulationen gleichermaßen gut geeignet. Abhängig davon, wie die Kanten zwischen den Punkten gewählt werden, können sich erhebliche Unterschiede in der Qualität der resultierenden Struktur ergeben. Ein zentrales Kriterium ist dabei, wie effizient Wege entlang der Struktur im Vergleich zu direkten euklidischen Verbindungen sind.
Ein weiterer Schwerpunkt in SpaceAnts liegt auf der Rekonfiguration von Strukturen durch Roboter mit eingeschränkten Fähigkeiten. Ziel ist es, ausgehend von einer gegebenen Startkonfiguration eine gewünschte Endkonfiguration der Struktur zu erreichen, indem einzelne Roboter lokale Aktionen ausführen. Die Herausforderung besteht darin, dass die Roboter ihre Aktionen nur auf Basis lokaler Informationen planen können. In diese Problemkategorie zählt beispielsweise das Tile Reconfiguration Problem, in dem ein einzelner Roboter mit den (eingeschränkten) Fähigkeiten, beispielsweise die eines DFA, eine Startkonfiguration von Kacheln in eine Zielkonfiguration übertragen muss.
Für SpaceAnts liegt der Schwerpunkt auf der parallelen Rekonfiguration von Triangulationen, insbesondere von Delaunay-Triangulationen und Minimum-Weight-Triangulationen. Dabei wird untersucht, wie sich lokale Strukturänderungen parallel durchführen lassen, um die Rekonfigurationszeit zu verkürzen, und wie sich dabei die Qualität der resultierenden Struktur verändert.
Darüber hinaus werden dynamisch veränderliche Rekonfigurationsstrukturen betrachtet, bei denen sich die zugrunde liegende Struktur während ihrer Nutzung weiter verändert. In solchen Szenarien bewegen sich Roboter entlang einer Struktur, die gleichzeitig rekonfiguriert wird. Dies erfordert neue algorithmische Methoden, die Rekonfiguration und Bewegung gleichzeitig berücksichtigen und effiziente Wege in sich dynamisch verändernden Strukturen ermöglichen.
Neben den oben beschriebenen Themenfeldern umfasst das Arbeitsprogramm von SpaceAnts weitere Forschungsbereiche, die sich mit verschiedenen algorithmischen und geometrischen Grundlagen für Robotersysteme und rekonfigurierbare Strukturen beschäftigen. Dazu gehören unter anderem die folgenden Themen:
In Zusammenarbeit mit der Technischen Universität Braunschweig wurden für SpaceAnts zwei Videos produziert, die die behandelten Forschungsthemen visualisieren.
Prof. Dr. Sándor P. Fekete
Abteilung Algorithmik
Technische Universität Braunschweig
Mühlenpfordtstraße 23
38106 Braunschweig
Telefon: +49 (0)531 391 311 1
Telefax: +49 (0)531 391 310 9
E-Mail: s.fekete@tu-bs.de
Internet: Webseite Prof. Dr. Fekete bei der TU Braunschweig