Prof. Dr. Wilhelm Schäfer

»Today, software is required to be a commercial product. It must meet high quality demands and its production has to be cost-efficient. We work on methods and tools which support the improvement of software quality and especially target embedded systems. Many of the achieved results are turned into commercial products in close collaboration with small and large enterprises.«

Montag, 05. März 2012 05.03.12 16:31 Alter: 6 Jahre

Strukturen im Chaos
Formationen autonomer Roboter in unsicheren Gebieten

Foto (Jana Neuhaus): Autonome Roboter formieren sich in unbekanntem Gelände zu einer Linie – Dr. Barbara Kempkes vor einem Modellaufbau

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 Miniatur-robotern – implementiert und getestet.


Kontakt:
Prof. Dr. Friedhelm Meyer auf der Heide
Algorithmen und Komplexität
05251 60-6480
fmadh(at)uni-paderborn.de
Kontakt: Patrizia Höfer, Institut für Informatik, 05251 60-3341, hoefer[at]upb.de