Strategien für Formationsbildung in Roboterschwärmen
Das Szenario
Wir betrachten ein Team von autonomen mobilen Robotern, die in einem unbekannten Gelände ausgesetzt werden. Dies kann beispielsweise ein bisher unerforschter Planet oder auch ein Ozean sein. Unsere Forschung verfolgt das Ziel, Strategien für die Roboter zu entwerfen, um verschiedenen Anforderungen einer solchen Mission eines Roboterteams gerecht zu werden. Eine typische Aufgabe ist die Erforschung des Geländes. Hierbei ist die Frage, wie sich das Roboterteam verhalten sollte, um ein Gelände mit verschiedenen Hindernissen zu erforschen. Das sollte möglichst schnell gehen, außerdem sollten die von den Robotern dabei zurücklegen Wege möglichst gleichverteilt sein, um die Energie der Roboter möglichst gleichmäßig zu verbrauchen. Außerdem ist in einer unbekannten Umgebung typischerweise keine Infrastruktur gegeben, die die Roboter nutzen könnten, um miteinander zu kommunizieren. Daher sind eigene Kommunikationsstrukturen erforderlich, bei denen die Roboter sich durch direkte Kommunikation miteinander austauschen. Das Ziel ist die Aufrechterhaltung eines Kommunikationsnetzwerks zwischen den Robotern und der Basisstation, um relevante Informationen schnell an die Basisstation weiterleiten zu können. Dafür können Relay-Roboter eingesetzt werden, die sich an guten Stellen positionieren sollen, damit ein möglichst kurzes Kommunikationsnetz zwischen den Robotern und der Basisstation entsteht. Bewegen sich die Roboter, dann müssen auch die Relay-Roboter ihre Positionen anpassen.
Algorithmische Herausforderung
Die große algorithmische Herausforderung besteht nun darin, dass jeder einzelne Roboter lediglich einen sehr eingeschränkten Bereich seiner Umgebung kennt und daher auch nur in der Lage ist, mit anderen Robotern in seiner unmittelbaren Umgebung zu kommunizieren. Obwohl jeder Roboter seine Entscheidungen lediglich auf der Grundlage dieser unvollständigen Informationen trifft, sollen die erreichten Lösungen, als Ganzes gesehen, beweisbar gut sein. Außerdem sollen diese Lösungen effizient, das heißt schnell oder mit möglichst wenig Energieverbrauch für die Roboter, erreicht werden.
Im letzten Jahr haben wir uns besonders der Fragestellung gewidmet, ob und unter welchen Voraussetzungen die Roboter mit ihrer lokalen Sicht auf die Umgebung Formationen bilden können. Dabei haben wir uns insbesondere damit beschäftigt, wie schnell es die Roboter schaffen können, sich auf einem Punkt zu versammeln oder eine Linie zwischen zwei vorgegebenen Punkten zu bilden. Auch die von den Robotern dabei zurückgelegte Distanz haben wir untersucht. Die Ergebnisse sind sehr stark von den Fähigkeiten der verwendeten Roboter abhängig. Wir haben uns auf die Untersuchung von Algorithmen konzentriert, bei denen die Fähigkeiten der Roboter möglichst gering gehalten werden.
Roboter bilden ein Kommunikationsnetzwerk (angedeutet in Rot) zwischen festen Stationen (schwarz)
Ein Beispiel
Wir haben zum Beispiel eine Strategie entwickelt, die es den mobilen Robotern, die jeweils nur Nachbarn innerhalb eines festen Kreises um ihre Position sehen können, erlauben, sich an einer (nicht vorgegebenen) Stelle in der Ebene zu treffen. Dazu benötigen sie O(n²) synchrone Runden und kein Roboter läuft eine längere Strecke als O(n²).
Strategie eines Roboters (schwarz) zum Versammeln auf einem Punkt, bauend auf relativen Positionen seiner Nachbarn (rot). Die grauen Roboter können von ihm nicht gesehen werden.
Ausblick
Für die Zukunft planen wir die Untersuchung von Roboterformationen unter Dynamik. Dabei soll es um die Fragestellung gehen, inwieweit Formationen aufrechterhalten können, wenn sich bestimmte Roboter nach einer vorgegebenen Trajektorie bewegen. Ein Beispiel ist ein Quadrat, in dem sich Roboter befinden. Wenn die Eckpunkte des Quadrats sich entlang der gleichen Trajektorie bewegen, so dass die Form des Quadrats aufrechterhalten wird, können die anderen Roboter innerhalb des Quadrats bleiben und dabei gewährleisten, dass das Roboternetzwerk zusammenhängend bleibt? Weiterhin wollen wir untersuchen, ob die Roboter lernen können, wie sie sich in bestimmten Situationen verhalten sollten. Dabei geht es uns um die Garantie von bestimmten Gütekriterien.
Kontakt:
Dipl.-Wirt.-Inf. Barbara Kempkes
E-Mail: barbaras@uni-paderborn.de
Telefon: +49 (0) 5251/60 64 69
