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.
