Hauptseminar
RoboCup

Thema
Kooperative, mobile Roboter

Zusammenfassung
Schnell, billig und außer Kontrolle.
Das ist das Motto von Rodney Brooks, der sich mit seinem Team am MIT mit kooperativen Robotern befasst.
Ein Überblick über diese und andere Vorteile der Kooperation und Gründe zur Forschung auf dem Gebiet
wird in dieser Ausarbeitung zusammengestellt.

Sommersemester 2000

Universität Stuttgart
Fakultät Informatik
IPVR

Name
Uwe-Philipp Käppeler
Betreuer
Dipl.-Inf. M. Schulé
Prof. Dr. P. Levi

1  Einleitung

Um ferne Planeten zu erkunden benötigt man autonome Roboter. Ferngesteuerte Roboter würden auf dem Mars erst 45 Minuten nachdem sie das Bild eines Hindernisses zur Erde geschickt haben eine Reaktion von der Erde empfangen. Um 2019 für einen bemannten Flug zum Mars gewappnet zu sein, baut die NASA in den 80er Jahren den Ambler. Er kostete 2 Millionen Dollar, wog mehrere Tonnen, war fast 6 Meter hoch und schwer zu transportieren. Rodney Brooks vom Massachusetts Institute of Technology (MIT) war der Meinung, daß Unternehmen, die nur einen einzigen Roboter einsetzen, zur Unproduktivität verurteilt sind. Er schlug vor eine Horde kleiner Roboter zu verwenden. Die überschaubaren Verhaltensweisen jedes einzelnen Roboters sollten dazu beitragen ein gemeinsames Ziel zu erreichen - auch dann noch, wenn einzelne Roboter der Gruppe ausgefallen sind. [5]
Im Juli 1997 schickt die NASA Sojourner, einen einzelnen Roboter, zur Erkundung der Oberfläche auf den Mars. Trotz mehrerer technischer Schwierigkeiten konnte Sojourner eingesetzt werden. Geplant war ein Einsatz von bis zu einem Jahr, der Roboter fiel aber schon nach 30 Tagen wegen eines Softwarefehlers aus. [6]

An kooperativen Robotern wird immer mehr geforscht, doch bisher gibt es nur wenige Anwendungen und die Forschung steckt noch in den Startlöchern.

Diese Ausarbeitung zum Seminar beruht auf dem Text Cooperative Mobile Robotics: Antecedents and Directions [1]. Erkenntnisse und Teilprobleme dieses großen Forschungsgebietes wurden in diesem Artikel zusammengefasst. Im Hinblick auf unser Studienprojekt, den RoboCup, sollen hier Hintergrundinformationen vermittelt werden.


Bild des Boadicea: Ein Roboter, der von Rodney Brooks am MIT gebaut wurde

2  Forschung, ein Überblick

2.1  Definitionen

Kooperierende Roboter unterscheiden sich von anderen verteilten Systemen wie PC-Netzwerken hauptsächlich durch die reale Welt, die Umgebung, in der die Roboter interagieren und mit der sie zurecht kommen sollen.
Die Kooperation der Roboter wird in der Literatur nur knapp definiert: Diese unterschiedlichen Definitionen beschreiben auch die unterschiedlichen Forschungsrichtungen, mit denen man sich beschäftigen muss, um an kooperativen Robotern zu arbeiten: VKI - Verteilte künstliche Intelligenz, Kommunikation mit Fehlerkorrektur und -Toleranz und Kooperation selbst.

2.2  Motivation

Es gibt mehrere Gründe für die Forschung an kooperierenden Robotern:

2.3  Vom ersten kooperativen Roboter bis zum RoboCup

In den 40er Jahren baute Walter Grey schildkrötenähnliche Roboter, die mit Licht und Berührungssensoren ausgestattet waren. Dies hatte zur Folge, daß sie auf Bewegungen gegenseitig reagierten. In weiteren Versuchen wurden Roboter mit Lampen ausgestattet, die dann von anderen verfolgt wurden.


Die Shildkröten von Grey sahen dieser
LOGO-Schildkröte sehr ähnlich

Dann wurde auf dem Gebiet der verteilten, künstlichen Intelligenz (VKI) geforscht. Bis in die 90er Jahre wurden Roboter dazu hauptsächlich simuliert um ganze Schwärme zu beobachten und zu programmieren. Oft wurden dann hinterher noch Roboter gebaut um die Theorien aus den Simulationen zu überprüfen. Dazu wurden aber selten mehr als 3 Roboter angefertigt. Die größte Gruppe, die bis 1995 zu Forschungszwecken realisiert wurde bestand aus 20 Robotern [1].


Grafik einer Polyworld-Simulation

Seit den 80ern macht die Forschung an mobilen, kooperativen Robotern große Fortschritte. Das geschah hauptsächlich indem man bestimmte Aufgaben spezifizierte und diese dann zu lösen versuchte. Ein paar dieser Aufgaben werden im nächsten Kapitel vorgestellt. Auch der RoboCup ist eine dieser gestellten Aufgaben, die im Moment weltweit bearbeitet wird und sich zu einem anerkannten Testfeld etabliert [17] . Werden diese Aufgaben sehr genau spezifiziert, so ist es hinterher im direkten Vergleich einfach feststellbar, welches die bessere Lösung zu einer Aufgabe war. Dazu gibt es beim RoboCup die verschiedenen Meisterschaften, die immer wieder neu ausgetragen werden.

2.4  Aufgaben und Anwendungen

Dieses Kapitel soll einen kleinen Überblick der Aufgaben verschaffen, die neben dem RoboCup dazu dienen sollen die Forschung auf dem Gebiet der kooperativen mobilen Roboter voranzutreiben.
Geplante Anwendungen kooperativer Roboter sind unter anderem die Minensuche, die Landkartenerstellung oder der Zusammenbau von Objekten. Zur Durchführung aller Anwendungen werden die folgenden Grundaufgabentypen benötigt.

2.4.1  Verkehrskontrolle

Agieren mehrere Roboter in einer gemeinsamen Umgebung, so müssen sie Kollisionen vermeiden. Verkehrsregelung und Kollisionsvermeidung kann als eine Art Ressourcenkonflikt betrachtet werden. Dieses Problem kann durch Verkehrsregeln oder Kommunikation gelöst werden. Auch die Wegplanung zählt zu diesem Bereich. Es handelt sich um geometrische Probleme. Ein Roboter muss dazu seine gesamte Umgebung beachten.

2.4.2  Kistenschieben

Auch als Sofaschieben bekannt. Hier geht es um Aufgabenbestimmung, Fehlertoleranz und Lernen beim schieben von Objekten. Kooperation kann hier sehr wichtig sein, wenn zum Beispiel ein Objekt geschoben werden muss, das so schwer ist, daß es ein einzelner Roboter mit seiner Kraft nicht bewegen kann. Diese Aufgaben sind auch dadurch interessant, daß es sehr verschiedene Lösungsansätze gibt. Die Roboter können dabei zum Beispiel kommunizieren. Das Gegenteil dazu ist ein Ansatz, bei dem sich die Roboter überhaupt nicht bewusst sind, daß sie gerade mit anderen zusammen am gleichen Problem arbeiten.


http://www.dfki.de/pas/dmass/forks.gif
Deutsches Forschungszentrum
für Künstliche Intelligenz GmbH [16]

2.4.3  Fütterung

Eine Gruppe von Robotern sammelt Objekte ein, die in ihrer Umgebung verteilt sind. Anwendungen zu diesen Aufgaben sind das Aufräumen von giftigem Abfall, Suchen und Retten sowie die Ernte. Diese Aufgaben können von den Robotern auch einzeln gelöst werden. Die Frage ist, wie mehrere Roboter zusammen die Aufgaben besser lösen. Auch hier sind die Lösungsansätze sehr verschieden und reichen von zufälligem Absuchen und Sammeln bis hin zu Bewegungen in Formationen, die die zu sammelnden Objekte auf ein Ziel zuschieben.


MinDART Studie [12]

3  Teilgebiete der Forschung

3.1  Gruppenarchitektur

3.1.1  Zentral / Dezentral

Die grundlegendsten Architekturmerkmale einer Gruppe von Robotern werden durch die Wahl zwischen einer zentralen oder dezentralen Organisation festgelegt. Bei einer dezentralen Architektur wird außerdem entschieden, ob sie hierarchisch oder anarchisch organisiert ist.


Schematische Darstellung der Organisationsformen

Eine zentrale Organisation wird von einer einzigen Einheit gesteuert. Bei der Dezentralen Organisationen fehlt diese alles steuernde Einheit. Dabei sind in einer anarchischen Organisation alle Agenten gleichberechtigt. In einer hierarchischen Organisation sind Teile des ganzen Zentral gesteuert.
Es wird oft behauptet, daß eine dezentrale Organisation mehrere Vorteile, wie zum Beispiel ein hohes Maß an Robustheit und Ausfallsicherheit, gegenüber einer zentralen Organisation hat [16] . Es gibt aber bis heute keine empirischen oder theoretischen Beweise dafür. [7] Gesucht sind vor allem Vergleiche zwischen diesen Organisationen im Bereich von kleinen Gruppen wie zum Beispiel 2 Robotern, die eine Kiste verschieben.
In der Praxis wird häufiger die dezentrale Organisation eingesetzt. Aber selten lässt sich eine Organisation von Robotergruppen exakt der einen oder anderen Form zuordnen. Meist gibt es auch in der dezentralen Organisation die Möglichkeit, daß ein Roboter unter bestimmten Umständen die Führung übernehmen kann. [8]

3.1.2  Differenzierung

Man unterscheidet zwischen homogenen Gruppen von Robotern die völlig identisch sind und heterogenen Gruppen, die verschiedene Individuen enthalten. In der Literatur werden hauptsächlich die homogenen Gruppen behandelt.
Parker [9] führte das Konzept der Aufgabenüberdeckung ein. Damit wird beschrieben, wie gut ein bestimmtes Individuum der Gruppe für eine Aufgabe geeignet ist. In homogenen Gruppen hat die Aufgabenüberdeckung ihr Maximum. Je heterogener eine Gruppe ist, desto mehr nimmt die Aufgabenüberdeckung ab. Im Extremfall ist nur noch ein einziger Roboter einer Gruppe fähig eine bestimmte Aufgabe zu lösen.
In heterogenen Systemen kann eine Aufgabenteilung schon durch die Fähigkeiten der Gruppenmitglieder festgelegt sein. Beim RoboCup ist zum Beispiel der Torwart oft etwas anders aufgebaut als die Feldspieler um das Tor besser verteidigen zu können, indem er sich seitlich bewegen kann. In homogenen Systemen wie den Feldspielern unter sich dagegen gibt es Rollen, die zur Laufzeit dynamisch verteilt werden wie Torschütze und Rückendecker, sowie Rollen, die schon bei der Entwicklung des Systems festgelegt werden können wie Angreifer und Verteidiger.

3.1.3  Kommunikationstrukturen

In [1] sind über 20 Verweise zu anderen Ausarbeitungen zum Thema Kommunikation angegeben. Da fast alle Robo-Fußballer bereits mit einem Standard-Funknetz ausgerüstet sind, wird auch hier wieder nur ein grober Überblick über die verschiedenen Möglichkeiten aufgezeigt.

3.1.4  Modellbildung anderer Agenten

Modelle von Intentionen, Aktionen, Fähigkeiten und Zuständen anderer Roboter können zu einer Reduktion der Kommunikation führen. So können zum Beispiel bei der Wegplanung zukünftige Positionen anderer Roboter berechnet oder vermutet werden. Eine mögliche Kollision kann dann durch Kommunikation verhindert werden.

3.1.5  Repräsentative Architekturen

In diesem Abschnitt werden einige Standardarchitekturen vorgestellt.

3.2  Resourcenkonflikt

Ressourcenkonflikte treten auf, sobald sich Roboter einen gemeinsamen Raum, manipulierbare Objekte oder Kommunikationsmedien teilen. Wie bereits erwähnt werden zur Kommunikation meist Standardkomponenten und Protokolle verwendet, da diese bereits ausgereift sind. Bei der Wegplanung hat man es dagegen nicht so leicht. Mehrere Studien sind zu dem Schluss gekommen, dass eine Planung der Wege aller Roboter einer Gruppe im Voraus einfach nicht möglich ist. Auch bei fußballspielenden Robotern ist die Wegplanung eine wichtige Aufgabe.
Lösungen wurden in der Forschung vor allem für Verkehrssysteme gesucht. Um Kollisionen und gegenseitiges Blockieren, das zum Stillstand führt, zu vermeiden, reichen schon ein paar wenige einfache Verkehrsregeln wie [14] : Systeme, die sich nicht auf vorgegebenen Straßen fortbewegen, benötigen kompliziertere Algorithmen, die zum Beispiel mit einem globalen Raum-Zeit-Modell und einem iterativen Vorgehen der Roboter arbeiten. Im Raum-Zeit-Modell wird die aktuelle Umgebung nachgebildet und vermutet, wie sie in der näheren Zukunft aussehen wird. Jeder einzelne Roboter wiederholt die folgenden Schritte immer wieder [15] : Der modifizierte Weg wird meist ermittelt, indem der Roboter das erkannte Hindernis so umgeht, daß er den kleinsten Umweg antreten muss [18] . Werden die Iterationen schnell hintereinander durchgeführt, so kann auch einem sich bewegenden Hindernis effektiv ausgewichen werden.

3.3  Ursprung der Kooperation

Bisher wurde die Kooperation von Robotern fast immer künstlich geschaffen. Interessanter wäre jedoch eine Kooperation, die zwischen egoistischen Robotern entsteht, sobald diese ohne menschliche Hilfe erkennen, daß sie ihre Aufgaben zusammen effektiver lösen können.
In der Natur gibt es dazu zwei unterschiedliche, beobachtbare Verhaltensstrukturen. Soziales Verhalten, wie es zum Beispiel bei Ameisen beobachtet werden kann, und kooperatives Verhalten. Beim Sozialen Verhalten ist die Kooperation der einzelnen schwachen Individuen genetisch festgelegt. Sie ist nötig zum Überleben der ganzen Gruppe.
Kooperatives Verhalten von höheren Tieren dagegen beruht auf dem intuitiven Wunsch der Interaktion, um daraus eigenen Nutzen zu ziehen.

3.4  Aufgabenteilung

Bisher gibt es nur wenige Arbeiten zur Aufgabenteilung unter kooperativen Robotern. Die meisten Anwendungen wie Fütterung und Kistenschieben sind zu einfach um hier nach komplexen Lösungen zu suchen.
Dazu kommt, daß die Aufgabenteilung auch stark von der zentral oder dezentral organisierten Gruppenarchitektur abhängt. Außerdem spielen geometrische Gegebenheiten bei der Aufgabenteilung eine große Rolle. Besonders beim Roboterfußball, bei dem die einzelnen Agenten je nach Spielsituation die Roboter der eigenen Mannschaft unterstützen oder die Gegnerischen behindern können.

3.5  Geometrische Probleme

Im Unterschied zu den anderen Teilproblemen geht es bei den geometrischen Problemen um die Einbindung der sich bewegenden Roboter in eine 2- oder 3-dimensionale, physische Umwelt. Auf die Probleme der Wegplanung wurde in dieser Ausarbeitung bereits eingegangen.
Weitere Schwerpunkte der geometrischen Probleme sind das Bilden von Formationen und das Marschieren in diesen. Lange Zeit gab es keinen Algorithmus für verteilte Architekturen, der die Agenten dazu bringt, zusammen einen Kreis zu formen. Uny Cao, Fukanaga und Kahng [1] machten erstmals einen Vorschlag, wie dieses Problem theoretisch gelöst werden kann.
Um Formationen während der Fortbewegung einer Gruppe einzuhalten werden meist Ansätze mit Führern und Verfolgern verwendet. Schwierig ist hierbei wieder die Hindernisvermeidung, die zentral vom Führer beachtet werden muss.
Auch im RoboCup gibt es Mannschaften, deren Roboter während dem Spiel Formationen bilden. Hat ein Spieler den Ball und ist im Angriff, so wird er oft von einem Mitspieler begleitet, der ihm Rückendeckung gibt.

4  Zukunft der Forschung

4.1  Technologische Einschränkungen

Die begrenzten technischen Möglichkeiten bremsen die Forschung an Robotern. Dadurch, daß die gängige Roboter-Hardware extrem unzuverlässig ist, ist es sehr schwierig, eine ganze Gruppe von Robotern funktionstüchtig zu halten.
Die Forschung anhand von Simulationen umgeht die technischen Schwierigkeiten gänzlich. Auf diesem Wege lassen sich mehr Experimente durchführen, als mit echten Robotern möglich wäre. Doch kann der rein theoretische Ansatz auch dazu führen, daß ein in einer Simulation erfolgreich getestetes System in der Realität unumgänglich zu einem Misserfolg führt.
Heute ist es kein Problem mehr, mit Multirobotersystemen aus 10 bis 20 Individuen zu arbeiten. Doch auch in der näheren Zukunft wird es unmöglich bleiben, kollektives Massenverhalten an Hunderten oder Tausenden von echten Robotern zu studieren. Um Schritte in diese Richtung unternehmen zu können, versucht man einzelne Roboter so klein wie nur möglich zu konstruieren.


Ein extrem kleiner Roboter vom MIT ist diese Ameise

Ameisen-Roboter werden am MIT erfolgreich für Forschung an Fütterungsaufgaben verwendet. Doch selbst die Einzelteile einer dieser winzigen Roboter kosten 300$, Laborkosten nicht inbegriffen [19] .

4.2  Offene Forschungsgebiete

Es gibt viele Teilgebiete der Forschung an Robotern, die noch so gut wie unerforscht sind. Da diese Wissenschaft noch jung ist, war sie bisher hauptsächlich informell und konzeptorientiert. So fehlen bisher zum Beispiel formale Metriken um die Kooperation von Systemen zu messen.
Es gibt auch Teilprobleme, die theoretisch bereits gelöst sind, doch bei der Umsetzung in die Praxis auf Schwierigkeiten stoßen, wie das Problem des Bildens einer Formation. Dieses wurde geometrisch optimal gelöst, wobei Aspekte wie Fehlertoleranz und Führerwahl noch ungeklärt sind.
Wissenschaften, die das Wachstum der kooperativen Roboter noch beträchtlich beeinflussen können, sind:

5  Fazit

So lustig es aussehen mag Roboter fußballspielen zu lassen, es dient der Wissenschaft und soll die einzelnen Forschungsgebiete der kooperativen mobilen Roboter vorantreiben. Fast alle dieser Forschungsgebiete sind bei der Konstruktion einer Roboterfußballmannschaft im Einsatz. Ergebnisse von Mannschaftsspielen stellen eine der wenigen Metriken dar, die man heute auf dem Gebiet der Kooperation überhaupt hat.
Die ganze Forschung an mobilen kooperativen Robotern steckt noch in den Kinderschuhen. Ebenso wie die Technologie, die dazu zur Verfügung steht.

Referenzen

[1]
Y. Unycao, Alex S. Fukunaga, Andrew B. Kahng: Cooperative Mobile Robotics: Antecedents and Directions; Los Angeles, July 27, 1997
[2]
D. Barnes, J. Gray: Behaviour synthesis for co-operant mobile robot control pp 1135-1140; 1991 - Zitat aus [1]
[3]
M. Mataric Interaction and intelligent behaviour; MIT, 1994 - Zitat aus [1]
[4]
S. Premvuti, S. Yuta: Consideration on the cooperation of multiple autonomous mobile robots; 1990 - Zitat aus [1]
[5]
Steven Levy: Künstliches Leben aus dem Computer; 1992
[6]
Rhein-Zeitung: http://rhein-zeitung.de/old/97/07/08/topnews/marschem.html
[7]
L. Steels: Simulation of adaptive behaviour; 1994 - Zitat aus [1]
[8]
O. Causse and Pampagnin: Management of a multirobot system in a public environment; 1995 - Zitat aus [1]
[9]
L. E. Parker: Heterogeneous muti-robot cooperation; MIT, 1994
[10]
S. Ichikawa: Cooperative routesearching behaviour of multi-robot system using hello-call communication; 1993 - Zitat aus [1]
[11]
J. Wang, G. Beni: Distributed computing problems in cellular robotic systems; 1990 - Zitat aus [1]
[12]
http://www.cs.umn.edu/Research/airvl/mindart/
[13]
H. Asama, A. Matsumoto, Y. Ishida: Design of an autonomous and distributed robot system: ACTRESS; 1989 - Zitat aus [1]
[14]
S. Kato, S. Nishiyama, J. Takeno: Coordinating mobile robots by applying traffic rules; 1992 - Zitat aus [1]
[15]
M. Rude: Cooperation of mobile robots by event transforms into local space-time; 1994 - Zitat aus [1]
[16]
Deutsches Forschungszentrum für künstliche Intelligenz:

http://www.dfki.de/dfki/forschung.html
http://www.dfki.de/pas/f2w.cgi?dmass/forks-g
[17]
Thomas Christaller: Autonome intelligente Systeme; GMD, 1998

http://set.gmd.de/de/ais.html
[18]
D. Yeung, G. Bekey: A decentralized approach to the motion planning problem for multiple mobile robots. - Zitat aus [1]
[19]
Rodney Brooks: The Ants: A Community of Microrobots

http://www.ai.mit.edu/projects/ants/

Abbildungsverzeichnis

File translated from TEX by TTH, version 2.69.
On 12 Dec 2000, 00:49.