Unerforschtes Gelände auf dem Meeresboden, auf fremden Planeten oder gefährliche Bereiche in Krisengebieten – Situationen fern jeder gewohnten menschlichen Umgebung. Hier wird der Mensch in Zukunft Aufgaben bewältigen müssen, die er nach heutigen technischen Möglichkeiten nicht oder nur unter großen Gefahren lösen kann. Bei vergleichbaren Problemen in uns bekannten Gebieten setzen wir heute häufig Roboter ein. Doch was, wenn der Mensch nicht in der Nähe sein kann, um Roboter zu steuern, wenn es keinerlei Infrastruktur gibt und keine externen Energiequellen, dafür aber unkalkulierbare Hindernisse zu erwarten sind?
In solchen Situationen müssen eingesetzte Roboter prinzipiell allein und völlig autonom agieren. Kommen sie als Gruppe zum Einsatz – was in unsicheren Gebieten häufig der Fall sein wird – müssen sie ihr Verhalten ständig aufeinander abstimmen. Bevor die Roboter jedoch weitergehende Aufgaben lösen können, muss ihr Bewegungsverhalten und ihre Kommunikation miteinander gewährleistet sein – auch dann noch, wenn es sich um unbekanntes und möglicherweise gefährliches Gelände handelt. Um als Gruppe zu agieren, ist es sinnvoll, wenn sich die Roboter zuvor formieren.
Um den Bedingungen in unsicheren Gebieten gerecht zu werden, müssen die Roboter adäquaten Strategien folgen. Voraussetzung ist, dass sie sich bewegen können und möglichst schnell ihr Ziel erreichen. Die Wege müssen dabei ähnlich lang sein, damit alle gleichmäßig viel Energie verbrauchen und nicht einzelne Roboter auf der Strecke bleiben. Letzteres würde die Auflösung einer Formation bedeuten.
Dr. Barbara Kempkes, vor kurzem promoviert und Mitarbeiterin in der Fachgruppe Algorithmen und Komplexität von Prof. Dr. Friedhelm Meyer auf der Heide, arbeitet an entsprechenden Fragestellungen zur Roboter-Formation. In ihrer Grundlagenforschung erstellt sie Theorien zum modellhaften Einsatz der Roboter. Ziel ihrer Arbeit war es, dass Roboter lokales Wissen nutzen, um zu einer global guten Lösung zu kommen: Mittels Algorithmen konnte sie sicherstellen, dass eine Gruppe von Robotern ohne zentrale Steuerung autonom in der Ebene verteilt agiert und in der Lage ist, eine Formation zu bilden.
Zwei verschiedene Formationsvarianten sind hierbei möglich und an jeweils unterschiedliche Bedingungen geknüpft: Beim Gathering-Problem sollen sich die Roboter an einem bestimmten Punkt zusammenfinden. Dafür kennt jeder Roboter alle anderen Roboter, die sich in seinem Kommunikationsradius befinden. Bei der Robot-Chain-Formation ordnen sich mehrere Roboter zwischen zwei festen Punkten linear an. Trotz der geringen Informationen, die sie ausschließlich durch ihre beiden Nachbarn erhalten, sind die Roboter in der Lage, eine Kette zu bilden.
Für beide Formationsvarianten besteht eine generelle Herausforderung: Jeder Roboter kennt nur einen festen Umkreis seiner Umgebung. Nur in diesem eingeschränkten Radius kann er Signale anderer Roboter empfangen und somit auch nur mit diesen kommunizieren. Dass die Roboter anfangs zusammenhängend versammelt sind, ist daher unerlässliche Voraussetzung für eine Formation. Mit den begrenzten Informationen aus seinem Umkreis muss ein Roboter dann entscheiden, was lokal machbar ist, wie er agiert und wie er mit den anderen Robotern eine Formation bilden kann – bei hoher Effizienz und gleichzeitig geringem Energieverbrauch. Dr. Kempkes hat hierfür entsprechende Algorithmen entworfen. Durch diskrete wie auch kontinuierliche Laufzeitanalysen konnte sie klären, wie lange die Roboter für eine bestimmte Formation benötigen. Damit hat sie die Effektivität der beiden Roboter-Formationen mathematisch bewiesen.
Die Robot-Chain-Formation wurde bereits in einer Bachelorarbeit auf sogenannten BeBots – kleinen Miniaturrobotern – implementiert und getestet.
Autorin: Jana Neuhaus
Kontakt:
Prof. Dr. Friedhelm Meyer auf der Heide
Algorithmen und Komplexität
Tel.: 05251-60-6480
Dieser Text steht auch als <link fileadmin aktuelles pressefotos maerz forschunginsight_februar2012.pdf _blank>PDF-Datei zur Verfügung.
