Startseite > Fachgruppen > Algorithmen und Komplexität > Forschung > Lokale Strategien für autonome Roboterschwärme

Lokale Strategien für autonome Roboterschwärme

Wir betrachten Schwärme von autonomen Robotern, die ein Gebiet ohne Infrastruktur erkunden sollen. Ohne vorhandene Infrastruktur sind bereits einfache Formationsaufgaben, wie das Bilden einer Linie, nicht trivial. Wir entwerfen effiziente Algorithmen für solche Formationsprobleme und analysieren ihre Laufzeit.

Verteiltes Rechnen trifft Dynamische Systeme

Mit dem Lehrstuhl „Angewandte Mathematik“ der Universität Paderborn, unter der Leitung von Professor Michael Dellnitz, vereinigen wir in einem von der DFG geförderten Projekt zwei Sichten auf Formationsalgorithmen. Der Forschungsbereich des Verteilten Rechnens beschäftigt sich damit, beweisbar korrekteund Worst Case-effiziente Algorithmen für Formationsprobleme zu entwickeln. Aus der Sicht der dynamischen Systeme ist ein feingranularerer Blick von Interesse: Wie müssen die Roboter initial angeordnet sein, damit der Algorithmus besonders schnell oder langsam ist? Wie verändert sich das Verhalten, wenn wir die Positionen der Roboter leicht verändern? Üblicherweise sind solche Fragestellungen so komplex, dass diese nicht mehr analytisch, sondern durch aufwändige Simulationen für eine feste (kleine) Anzahl an Robotern beantwortet werden. Durch die Kombination von beiden Sichten erwarten wir ein umfassenderes Verständnis, welches wir nutzen wollen, um Algorithmen für neue Formationsprobleme, z. B. Dispersionsprobleme, zu entwickeln.

Das Max-Chain-Formation-Problem (links) und das Max-Line-Formation Problem (rechts).

Dispersionsprobleme

Ziel von Dispersionsproblemen ist es, Roboter mit lokaler Sicht möglichst weit zu verteilen ohne dabei den Zusammenhang aufzugeben. Ein Beispiel sind Linienbildungsprobleme, wie das Max-Chain-Formation Problem und das Max-Line-Formation-Problem. Beim Max-Chain-Formation-Problem sind die Roboter in einer Kette angeordnet und das Ziel ist es, die Distanz der Endroboter dieser Kette zu maximieren und gleichzeitig dafür zu sorgen, dass die Kette zusammenhängend bleibt. Das Max-Line-Formation-Problem hat ein ähnliches Ziel: Die Roboter sollen auf einer Linie mit maximaler Länge angeordnet werden. Hierbei sind die Roboter initial nicht in einer Kette angeordnet, sondern können alle anderen Roboter in konstanter Distanz wahrnehmen. Für beide Probleme konnten wir effiziente Algorithmen in verschiedenen Zeitmodellen entwerfen.

Aktuell arbeiten wir an allgemeineren Dispersionsproblemen, wie das Ausfüllen einer geschlossenen Form. Man nimmt an, dass sich alle Roboter in einer geschlossenen Form, z. B. einem Rechteck befinden. Als Ziel möchte man erreichen, dass die Roboter die Form möglichst gut ausfüllen. Hierbei sind verschiedene Definitionen denkbar. Aktuell schauen wir uns speziell Rechtecke an und entwerfen Algorithmen, um die Roboter in einer Gitterformation aufzustellen.

In Zukunft wollen wir untersuchen, welche Fähigkeiten die Roboter benötigen, um solche Probleme zu lösen und um unsere Ergebnisse auf allgemeinere Formen zu verallgemeinern, z. B. konvexe Polygone.

Die Roboter im Quadrat sollen eine regelmäßige Gitterstruktur bilden.

Gefördert durch:

  • Deutsche Forschungsgemeinschaft (DFG), Projektpartner: Prof. Dr. Michael Dellnitz (Universität Paderborn)