|
|
|
Informatik-Lexikon
Refactoring
Remote Database Access
Roboter, Web-
Roboter-Fußball
Erläuterung
Software, die benutzt wird, muß laufend den sich ändernden
Anforderungen angepaßt werden, d.h. sie muß gewartet werden.
Leider führt Software-Wartung in der Regel zur Degeneration der Struktur
der Software. Das macht weitere Änderungen immer schwieriger, bis
schließlich nur noch eine Neuimplementierung sinnvoll ist. Lehman
[5] hat diese Entwicklung beobachtet und festgestellt,
daß es sich bei diesem Phänomen um eine Art Naturgesetz handelt.
Eine Möglichkeit, dieser „natürlichen" Degeneration
der Software-Struktur entgegenzuwirken, ist die kontinuierliche Software-Restrukturierung,
die dafür sorgt, daß die Software jederzeit verständlich
und änderbar bleibt. Bei objektorientierter Software spricht man
anstelle von Restrukturierung auch von Refactoring. Fowler [4]
definiert den Begriff Refactoring folgendermaßen:
„Refactoring is a change made to the internal structure of a software
component to make it easier to understand and cheaper to modify, without
changing the observable behavior of that software component."
Das Refactoring umfaßt also konstruktive Maßnahmen, die dazu
dienen, eine vorhandene Software oder Teile davon verständlicher
und leichter änderbar zu machen, ohne dabei das beobachtbare Verhalten
zu verändern. Die Verständlichkeit einer Software ist hoch,
wenn ihre Struktur ihrem Verhalten angemessen ist, es also eine enge Verbindung
zwischen Struktur und Funktion gibt. Dann können zu ändernde
Teile leichter identifiziert und geändert werden. Eine geeignete
Aufteilung der Zuständigkeiten zwischen den Komponenten der Struktur
bewirkt, daß notwendige Änderungen sich nur lokal auswirken.
Durch Änderungen der Funktion können allerdings die vorhandenen
Strukturen ungeeignet werden, weshalb es dann angebracht ist, sie mittels
Refactoring in neue, bessere Strukturen zu überführen.
Einige typische Beispiele für Refactorings sind:
- Definition einer neuen abstrakten Oberklasse zu mehreren bestehenden
Klassen, um deren Gemeinsamkeiten aufzunehmen und eine einheitliche
Schnittstelle zu schaffen. Die Gemeinsamkeiten können so in der
Oberklasse definiert und auf die Unterklassen vererbt werden.
- Verschieben einer Klasse in und zwischen Vererbungshierarchien, um
semantisch falsche oder ungeschickte Spezialisierungen zu korrigieren
und Vererbung effektiver zu nutzen.
- Verschieben von Attributen und Methoden zwischen Klassen, um unnötige
Parameter beim Methodenaufruf und unnötige Assoziationen zwischen
Klassen zu vermeiden.
- Verbergen direkt sichtbarer Attribute und Definition geeigneter Zugriffsmethoden,
um eine bessere Datenkapselung zu erreichen.
- Ersetzen eines Code-Abschnitts durch einen Methodenaufruf, um lange
Methoden zu zerschlagen und duplizierte Code-Abschnitte zusammenzuführen.
- Ändern des Namens von Klassen, Attributen, Methoden und Parametern,
um deren Bedeutung klarer zu dokumentieren.
Die genannten Änderungen ziehen natürlich Änderungen
bei den Verwendern der betroffenen Teile nach sich, falls die Schnittstellen
verändert werden. Man sieht anhand der genannten Beispiele, daß
sich Refactoring auf den weiten Bereich von detaillierten Code-Strukturen,
z.B. einzelnen Code-Abschnitten einer Methode, bis hin zu Entwurfsstrukturen,
z.B. den Vererbungshierarchien, auswirkt. Ein umfassender Katalog von
Refactorings mit Anwendungsbeispielen in Java findet sich in [4].
Beck [2] gibt ein kleineres Beispiel für
Refactoring in Smalltalk.
Gerade im Bereich der evolutionären (d.h. iterativen und inkrementellen)
Software-Entwicklung wird Refactoring eine hohe Bedeutung zugeschrieben.
Bedingt durch die Vorgehensweise haben frühe Versionen der Software
in der Regel eine schlechte Struktur, da laufend bestehende Teile geändert
und neue Teile hinzugefügt werden. Wird nicht durch Refactoring gegengesteuert,
entsteht schnell ein unwartbares Monstrum.
Aber auch das Vorgehensmodell, bei dem erst implementiert wird, wenn
das System vollständig entworfen wurde, kommt nicht ohne Refactoring
aus. Die in der Entwurfsphase entwickelte Struktur wird sich in der Implementierungsphase
als unvollkommen herausstellen, weil es unmöglich ist, alle Aspekte
im voraus zu überschauen. Während der Implementierung erkennt
man auch, welche Strukturen besser geeignet sind, die gewünschte
Funktionalität zu tragen.
Neben den genannten Wirkungen auf Verständlichkeit und Änderbarkeit
hat Refactoring noch andere positive Effekte. Zum Beispiel kann duplizierter
Code, der durch Kopieren und Einfügen entstanden ist, durch geeignetes
Refactoring wieder zusammengeführt (vgl. das Copy-and-Paste Programming
AntiPattern in [3]) und damit Redundanz entfernt
werden.
Auch als Technik, an unbekannten Code heranzugehen, kann man Refactoring
einsetzen. Man bringt die bereits verstandenen Programmteile in eine besser
verständliche Struktur und kann dadurch das eigene Verständnis
sofort im Code reflektieren. Interessanterweise ist es oft so, daß
man während des Refactorings auf Fehler im Code aufmerksam wird.
Eine große Gefahr beim Refactoring ist es, durch die Änderungen
an der Struktur neue Fehler in die Software hineinzubringen. Daher wird
empfohlen, für alle betroffenen Software-Komponenten vorher umfangreiche
Tests (sowohl auf Klassen- als auch auf Systemebene) bereitzustellen,
die das korrekte Funktionieren der Software prüfen. Während
des Refactorings werden nach jedem größeren Schritt die Tests
erneut ausgeführt, um zu prüfen, ob durch Unachtsamkeit die
Funktion der Software verändert wurde. Tritt beim Test ein Fehler
zutage, kann seine Ursache so leichter eingegrenzt werden: Es muß
an den zuletzt vorgenommenen Änderungen liegen. Dieses Vorgehen ist
aber nur eine Kontrolle, die keinerlei Sicherheit bietet, daß wirklich
nichts verändert wurde.
Daher hat Opdyke in seiner Dissertation [6]
semantikerhaltende Refactorings (für C++) untersucht, die beweisbar
das Programmverhalten nicht verändern, sofern ihre Vorbedingungen
erfüllt sind. Werden nur solche semantikerhaltenden Transformationen
durchgeführt, können keine neuen Fehler in die Software hineingetragen
werden. Die von Opdyke angegebenen Refactorings können, da sie formal
spezifiziert sind, durch ein Werkzeug auf ihre Zulässigkeit geprüft
und gegebenenfalls auch durchgeführt werden.
Werkzeugunterstützung beim Refactoring ist sehr wichtig, da alle
Änderungen an der Struktur, die sich auf die öffentliche Schnittstelle
einer Komponente auswirken, weitreichende Folgen für alle Verwender
dieser Komponente haben. Diese müssen an die neue Schnittstelle angepaßt
werden, was bei der Durchführung von Hand sehr mühsam werden
kann. Werden die zu ändernden Stellen dagegen von einem Werkzeug
identifiziert und die Anpassungen automatisch vorgenommen, ist die Hemmschwelle
zu einer weitreichenden Änderung, die einen positiven Effekt auf
die Software-Struktur hat, viel niedriger.
Für verschiedene Smalltalk-Dialekte gibt es bereits den Refactoring
Browser von Roberts und Brant ([7]; siehe auch
http://st-www.cs.uiuc.edu/users/brant/Refactory/).
Der Refactoring Browser ist in die normale Entwicklungsumgebung integriert
und kann Opdykes Refactorings (angepaßt an Smalltalk) und andere
Refactorings (unter anderem inspiriert von [1])
automatisch durchführen. Für Programmiersprachen wie C++ oder
Java scheint es noch keine Refactoring-Werkzeuge zu geben, was wohl auch
an der komplizierten Grammatik und Sprachsemantik liegt.
Ein großes Hindernis beim Refactoring ist allerdings kein technisches:
Ein Software-Projekt-Manager muß davon überzeugt sein (oder
werden), daß es sinnvoll und notwendig ist, wenn seine Entwickler
keinen neuen Code schaffen, sondern an bereits vorhandenem Code Refactorings
durchführen. Das wirkt zunächst sehr unproduktiv, schließlich
arbeitet der vorhandene Code ja zufriedenstellend. Wozu dann Aufwand investieren,
ihn zu ändern? Wie bei den meisten präventiven Maßnahmen
im Software Engineering ist es auch beim Refactoring so, daß es
sich um eine Investition in die Zukunft handelt, die die zu erwartenden
Wartungskosten verringert und die Produktivität in der Wartung erhöht.
Ob sich die Investition tatsächlich lohnt, ist schwer vorhersagbar.
Die bisher dokumentierten Erfahrungen mit Refactoring in der Praxis sind
allerdings recht positiv.
Artikelanfang Seitenanfang
|
|
Literatur
- Beck, K.: Smalltalk Best Practice Patterns.
Prentice Hall 1996. Auch auf deutsch erschienen: Beck, K.: Smalltalk:
Praxisnahe Gebrauchsmuster. Prentice Hall 1997
- Beck, K.: Make it Run, Make it Right: Design
Through Refactoring Smalltalk Report, 6(4), 19–24, 1997
- Brown, W.; Malveau, R.; McCormick, H.; Mowbray,
T.: AntiPatterns: Refactoring Software, Architectures, and Projects
in Crisis. Wiley 1998
- Fowler, M.: Refactoring: Improving the Design
of Existing Code. Addison-Wesley 1999 (noch nicht erschienen; siehe
auch
http://www.awl.com/cseng/titles/0-201-89542-0/refactor/index.html)
- Lehman, M.: Programs, Life Cycles and Laws
of Software Evolution. Proceedings of the IEEE, 68(9), 1060–1076,
1980
- Opdyke, W.: Refactoring Object-Oriented Frameworks.
Ph.D. thesis, University of Illinois at Urbana-Champaign, 1992
- Roberts, D.; Brant, J.; Johnson, R.: A Refactoring
Tool for Smalltalk. Theory and Practice of Object Systems, 3, 253–263,
1997
Artikelanfang Seitenanfang
|
Erläuterung
Die Größe des World Wide Webs macht die Suche nach Informationen
zu einem bestimmten Thema sehr schwer. Allein durch manuelles Durchsuchen
von Web-Seiten mit einem Browser ist eine umfassende Informationssuche
nicht möglich. Man hat eine bessere Chance die gewünschte Information
zu finden, wenn man die Dienste von Suchmaschinen wie Altavista
in Anspruch nimmt. Diese verwalten in der Regel einen Index, der Stichwörter
mit Web-Seiten verbindet. Eine Anfragesprache ermöglicht eine gezielte
Suche in diesem Index.
Die Indizes werden meistens automatisch aufgebaut. Programme, die diese
Aufgabe übernehmen, gehören zur Gruppe der Web-Roboter.
Web-Roboter kommunizieren automatisch, d.h. ohne menschliche Steuerung,
mit Web-Servern. Sie können Web-Seiten laden, diese analysieren und
aufgrund dieser Analyse über das weitere Vorgehen entscheiden. Web-Roboter
automatisieren den manuellen Umgang eines Menschen mit einem Web-Browser.
Im Gegensatz zu klassischen Robotern arbeiten sie nicht in einer physikalischen
Welt, sondern ihre Umgebung ist das Internet. Die wichtigsten Anwendungsfelder
sind:
- Aufbau von Indizes für Suchdienste,
- Überwachung von Änderungen von Web-Seiten,
- intelligente Informationsbeschaffung.
Web-Roboter werden auch Web Crawler oder Web Wanderer genannt. Sie gehören
zur Kategorie der intelligenten Agenten, auch Softbots (software robots)
genannt. Dies sind autonom agierende Softwareeinheiten, die Informationen
aufnehmen und verarbeiten, wobei sie standardisiert mit ihrer Umgebung
einschließlich anderer Agenten interagieren [3].
Je nach Ausprägung treffen Web-Roboter autonom Entscheidungen basierend
auf ihren Wahrnehmungen, den Antworten der Web-Server. Die Kommunikation
mit ihrer Umgebung basiert auf dem Protokoll HTTP. Zur Repräsentation
des wichtigsten Objektes der Kommunikation, den Web-Seiten, wird die Sprache
HTML verwendet. Web-Roboter arbeiten in einer unbekannten, sich ständig
ändernden Umgebung: Web-Server können temporär nicht erreichbar
sein, Web-Seiten ändern sich schnell, instabile Verbindungen.
Aus diesem Grund müssen Web-Roboter robuste Systeme sein und unter
diesen Randbedingungen korrekt arbeiten. Die Grundlage für das Auffinden
neuer Dokumente bildet die Hypertextstruktur des Webs. Diese macht das
Web zu einem gerichteten Graphen, wobei die Verweise die Kanten bilden.
Um bei der Suche nach neuen Dokumenten systematisch vorzugehen, werden
die aus der Graphentheorie bekannten Suchverfahren wie Breiten- oder beschränkte
Tiefensuche verwendet. Häufig werden von einer Web-Seite aus startend,
rekursiv alle Verweise verfolgt. Dies setzt voraus, daß der Roboter
alle relevanten URLs aus dem HTML-Quelltext isolieren kann. Zur Analyse
von Web-Seiten werden HTML-Parser eingesetzt, die je nach Aufgabenstellung
den Quelltext mehr oder weniger detailliert analysieren.
Web-Roboter zum Aufbau von Indizes für Suchdienste verwenden häufig
die Breitensuche. Ausgehend von einer oder mehreren URLs durchsuchen sie
das Web und extrahieren nach verschiedenen Verfahren Wörter, welche
in die Indizes eingefügt werden. Dabei werden sowohl statistische
Methoden wie Worthäufigkeiten und inverse Dokumentenhäufigkeiten
als auch probabilistische Methoden eingesetzt [4].
Viele Roboter untersuchen die Dokumente vollständig, andere nur Titel
und Überschriften. Zur Unterstützung komplexer Anfragen werden
neben Indizes auch die Anfänge der Dokumente (z.B. die ersten 100
Wörter) abgespeichert.
Da das Laden und Analysieren von Seiten aufwendig ist, wird nicht jede
gefundene URL weiter verfolgt. Statt dessen verwenden Web-Roboter Heuristiken,
um URLs von informationsreichen Web-Seiten herauszufiltern. Der Web-Roboter
des Suchdienstes Lycos bevorzugt z.B. URLs mit kurzen Pfadangaben, da
die zugehörigen Dokumente häufig Home-Pages sind und viele aussagekräftige
Verweise auf andere Seiten haben. Eine Übersicht über die in
den verschiedenen Suchdiensten verwendeten Algorithmen und Indizierungsverfahren
findet man in [4].
Web-Roboter können auch für sehr komplexe Aufgaben eingesetzt
werden und haben sich zu einem interessanten Anwendungsgebiet der KI entwickelt.
Es gibt mittlerweile viele Anwendungen im Web, welche automatisiert werden
können:
- Preisvergleiche von Produkten verschiedener Händler,
- Überwachung von dynamischen Datenquellen,
- gezielte Informationsbeschaffung.
Diese Aufgaben bilden eine größere Herausforderung für
Web-Roboter als Suchdienste und es gibt bisher nur wenige Prototypen.
Die Analyse von Dokumenten kann sich nicht allein auf die von HTML vorgegebenen
Auszeichnungselemente stützen. Bei den bisher realisierten intelligenten
Web-Robotern kommen folgende Techniken zum Einsatz:
- Einschränkung der Menge potentiell relevanter Seiten durch Verwendung
verschiedener Informationsquellen: Email-Server, Archive von News-Gruppen,
Datenbanken von Bibliotheken und Suchdienste.
- Heuristiken zur Erzeugung von URLs von Home-Pages (z.B. wird turau@informatik.fh-wiesbaden.de
zu
www.informatik.fh-wiesbaden.de/~turau) .
- Analyse von kleinen Bereichen von HTML-Dokumenten unter Verwendung
einfacher Grammatiken.
Der Roboter Ahoy! [10] bestimmt die URLs
von Home-Pages von Personen aufgrund von Namen. Mit Hilfe externer Quellen
wird versucht, die E-mail-Adresse zu bestimmen, um daraus mittels Heuristiken
Rückschlüsse auf Kandidaten für URLs zu ziehen. Durch eine Analyse des
Titels dieser Dokumente werden dann potentielle Home-Pages herausgefiltert.
Der eigentliche Inhalt der Seiten wird nicht analysiert.
Webfind versucht die URLs wissenschaftlicher Arbeiten aufgrund
von Wörtern aus dem Titel herauszufinden [9].
Als primäre Informationsquelle dienen Bibliotheksdatenbanken. Aus
ihnen werden Angaben über Autoren und deren Institutionen extrahiert.
Ausgehend von Home-Pages der Autoren oder Institutionen wird rekursiv
nach dem Dokument gesucht. Analysiert werden dabei nur kleine Ausschnitte
der HTML-Dokumente: zwei Zeilen vor und nach Hyperlinks.
Einige Roboter beschränken sich auf die Analyse von Dokumenten
mit einer einfachen logischen Struktur. Dazu werden Grammatiken von Dokumenttypen
erstellt und mit Hilfe von Mustervergleichen einzelne sinntragende Elemente
identifiziert. FAQ-Miner [5] und FAQ-Finder
[1] sind Web-Roboter zur Informationsbeschaffung
aus FAQ-Dokumenten. Durch einen Vergleich mit einer einfachen Grammatik
dieser Dokumente werden Frage-Antwort Paare extrahiert. Mit Hilfe von
statistischen Verfahren und semantischen Netzen werden dann zur Benutzeranfrage
ähnliche Fragen in FAQ-Dokumenten bestimmt.
Der Web-Roboter ShopBot arbeitet ebenfalls mit einer Grammatik
für Dokumententeile [2]. Er nimmt Preisvergleiche
unter Verkaufsangeboten im Web vor. Dabei wird die homogene Gestaltung
von Web-Seiten von Online-Händlern ausgenutzt. Diese bieten oft Suchformulare
zur Anforderung artikelspezifischer Daten. ShopBot analysiert nur <FORM>
Tags. Das Besondere an ShopBot ist die Verwendung eines Lernalgorithmus
zur Analyse dieser Formulare. Nach Abschluß der Lernphase werden
Preisanfragen durch parallele Auswertung der bestimmten Suchformulare
durchgeführt. Die URLs von Händlern werden ShopBot vorgegeben.
Die beschriebenen Web-Roboter sind noch sehr spezialisierte Systeme.
Einen Ansatz für eine Architektur von Web-Robotern bietet [11].
Die Entwicklung praktisch verwendbarer Web-Roboter ist eine große
Chance, KI-Technologien im größeren Umfang einzusetzen. Das
Web ist eine enorme Informationsquelle, welche im Gegensatz zu vielen
anderen Quellen elektronisch vorliegt, eine schwache Strukturierung trägt
und permanent erweitert und aktualisiert wird.
Die bisher beschriebenen Web-Roboter sind nicht mobil. Sie kommunizieren
zwar mit Web-Servern, welche geographisch verteilt sind, das eigentliche
Programm läuft jedoch auf einem Rechner ab. Mobile Agenten haben
die Fähigkeit, unter Bewahrung eines internen Zustandes auf andere
Rechner zu migrieren. Um in einer heterogenen Umgebung zu operieren, muß
ihr Code plattformunabhängig sein. Hierzu werden häufig Scriptsprachen
wie Telescript oder auch Java verwendet. Dies erfordert einen entsprechenden
Interpreter auf jedem Rechner, der besucht werden soll. Es gibt bisher
nur wenige Probleme, welche wirklich die Mobilität von Agenten erfordern.
J. Ousterhout, der Autor von Tcl, nannte mobile Agenten „a solution
in search of a problem" [6]. Viele der
diskutierten Anwendungen, wie z.B. Online-Auktionen, werfen zudem auch
noch viele ungelöste Sicherheitsfragen auf: Wie kann ein Agent vor
Manipulationen durch einen Hostrechner und umgekehrt geschützt werden.
Web-Roboter sind nicht auf jedem Server willkommen. Sie belasten das
Netzwerk, behindern richtige Besucher und verfälschen Zugriffshäufigkeiten.
So möchten die Betreiber von Suchdiensten sogenannte Metasuch-Roboter
von ihren Web-Servern fernhalten. Unvorsichtig erstellte Web-Roboter können
versehentlich komplexe CGI-Skripte starten. Sich täglich ändernde
Web-Seiten sollten nicht indiziert werden. Der Robot Exclusion Standard
gibt Administratoren von Web-Servern eine Möglichkeit, die Bereiche
anzuzeigen, welche von Robotern gemieden werden sollten. Eine einfach
strukturierte Textdatei mit dem Namen robots.txt im Wurzelverzeichnis
des Servers gibt Auskunft, welche Seiten für welche Web-Roboter nicht
zugänglich sind. Es gehört zum guten Stil des Internets, diese
Konvention einzuhalten. Der Standard hat seit seiner Einführung 1994
breite Anerkennung gefunden und es ist ein Internet Draft der IETF in
Arbeit [7]. Bei einer 1997 durchgeführten
Untersuchung wurde auf 2.4% aller Web-Server eine solche Datei vorgefunden
[11].
Es gibt Bibliotheken zum Erstellen von Web-Robotern. Die Bibliothek
LWP ist in Perl 5 geschrieben und basiert auf der Bibliothek libwww von
R. Fielding [12]. LWP enthält Klassen zum
Parsen von HTML-Dokumenten und zur Handhabung von URLs, mit deren Hilfe
Web-Roboter erstellt werden können. Eine gute Quelle für Information
über Web-Roboter sind die Web Robot Pages von M. Koster [8].
|
|
Literatur
- Burke, R., Hammond, K., Kulyukin, V., Lytinen,
S., Tomuro, N. and Schoenberg, S., Question Answering from Frequently
Asked Question Files: Experiences with the FAQ Finder System, TR-97-05,
Univ. of Chicago, 1997.
- Doorenbos, R., Etzioni, 0., and Weld, D., A
Scalable Comparison-Shopping Agent for the World-Wide Web, Proc. ACM
Conf. Autonomous Agents, 1997.
- Etzioni, 0., Moving Up the Information Food
Chain: Deploying Softbots on the World Wide Web, Proc. 14th Nat. Conf.
On AI,1996.
- Gudivada, V., Raghavan, V., Grosky, W., and
Kasanagottu, R., Information Retrieval on the World Wide Web",
IEEE Internet Computing, Vol. 1, No. 5, 58-68, 1997.
- Hsu, J. and Yih, W.,„Template-Based Information
Mining from HTML Documents, 14th Nat. Conf. on AI, 256262, 1997.
- Kiniry, J. and Zimmerman, A., A Hands-on look
at Java Mobile Agents, IEEE Internet Computing, Vol. 1, 21-30, 1997.
- Koster, M., A Method for Web Robots Control,
Network Working Group Internet Draft,
http://info.webcrawler.com/mak/projects/robots/norobots-rfc.html,
1996.
- Koster, M., The Web Robots Pages,
http://info.webcrawler.com/mak/projects/robots/robots.html
- Monge, A. and Elkan, C., WebFind: Automatic
Retrieval of Scientific Papers over the World Wide Web, AAAI Fall Symp.
On AI Applications in Knowledge Navigation and Retrieval, 1995.
- Shakes, J., Langheinrich, M. and Etzioni O.,
Dynamic Reference Sifting: A Case Study In The Homepage Domain, Proc.
of the 6th Int. WWW Conf., 189-200,1997.
- Turau, V., Eine empirische Analyse von HTML-Dokumenten
im WWW, Technischer Report 0198, FH Wiesbaden,1998
http://www.informatik.fh-wiesbaden.de/~turau/ewa/ewa.html.
- Wong, C., Web Client Programming with Perl,
O'Reilly, 1997.
Eingegangen am 02.04.1998
Artikelanfang Seitenanfang
|
|
Autor & Copyright
Volker Turau
Fachbereich Informatik
FH Wiesbaden
Kurt-Schumacher-Ring 18
65197 Wiesbaden
turau@informatik.fh-wiesbaden.de
© 1998 Informatik Spektrum, Springer-Verlag Berlin Heidelberg
Artikelanfang Seitenanfang
|
Roboter-Fußball
Kurzinfo Warum
beschäftigen sich weltweit über 300 Forscherteams mit insgesamt mehreren
1000 Forschern mit der Aufgabe, fußballspielende Roboter zu konstruieren
oder zu simulieren? Die Antwort liegt nicht alleine in der Faszination
des Fußballspiels, obwohl diese sicher hilft. Der Grund ist, daß sich
fußballspielende Roboter sehr gut dafür eignen, die Forschung im Bereich
der Robotik und der Künstlichen Intelligenz voranzutreiben.
|
Erläuterung
Bisherige mobile Roboter, die überwiegend in der industriellen Produktion
und zum Materialtransport eingesetzt wurden, waren langsam, groß,
teuer und nur für eine überwiegend statische Umgebung geeignet.
Künftige Serviceroboter sollen kleiner, leichter und schneller
sein und sollten sich in einer dynamischen Umgebung (Büroumgebung
oder Haushaltsumgebung) zurechtfinden, mit Personen, anderen Robotern
und Haustieren zurechtkommen und mit diesen geeignet interagieren können.
Hierbei sind sicher nicht alle Interaktionspartner kooperativ, daher sollten
künftige Roboter einerseits kooperationsfähig sein, andererseits
auch Strategien für Konkurrenz um Wege oder Ressourcen besitzen.
Ein schnelles dynamisches Spiel mit relativ einfachen Spielregeln, wie
das Fußballspiel, eignet sich hier ideal als Benchmark-Szenario:
die Gesamtleistung von Roboter-Teams kann durch Vergleichsspiele und Wettkämpfe
trotz Zufallseinflüssen relativ objektiv gemessen werden.
Anfänge, Organisationen und Spielklassen
Die Geschichte des Roboterfußballs begann nach Vorbereitungen,
die in den frühen 90er Jahren stattfanden, mit dem ersten offiziellen
RoboCup-Turnier 1997 während der IJCAI-97-Konferenz in Nagoya/Japan.
Bereits 1998 gab es allerdings dann zwei konkurrierende Organisationen,
die beide den Anspruch erhoben, Roboter-Fußball zu organisierren.
Der von Japan (Dr. Hiroaki Kitano, Sony) organisierte RoboCup [1]
und die von Korea (Prof. Jong-Hwan Kim, KAIST) geleitete FIRA [2].
Beide unterscheiden sich in den Größen der Roboter und in den
Spielregeln. Der Autor dieses Beitrags war vor allem im RoboCup aktiv,
daher bezieht sich dieser Beitrag überwiegend auf diese Organisation.
Im RoboCup gibt es derzeit 7 verschiedene Ligen, die sich durch die Größe
und Art ihrer Roboter unterscheiden:
In der Simulation league treten nur „virtuelle Roboter",
jeweils 11 pro Team, gegeneinander an. Es gibt einen zentralen RoboCup-Server,
der die Aktionen aller simulierten Spieler ausführt, d.h. die jeweiligen
Spielzüge der 22 Programme, welche die Aktionen der Spieler berechnen.
In der Middle-size league treten jeweils 4 reale Roboter von ca.
50 cm Durchmesser auf einem Spielfeld von ca. 5 x 9 m 2 gegeneinander
an. Die Roboter müssen ihre komplette Sensorik selbst tragen. Sie
können allerdings per Funk miteinander und mit einer Basisstation
kommunizieren. Der Ball, ein Lederfußball normaler Größe,
die Tore und die Roboter haben spezielle Farben, so daß sie per
Farb-Bildverarbeitung leicht detektiert werden können. Bei der Small-size
league spielen jeweils 5 kleinere Roboter von ca. 15 cm Durchmesser
auf einer Tischtennis-Platte um einen Golfball. Hier darf eine zentrale
Deckenkamera verwendet werden, was die Positionsbestimmung des Balls und
der Roboter viel einfacher macht, dafür ist die Regelung der im Verhältnis
zur Spielfeldgröße sehr schnellen Roboter schwieriger. In der
Sony four-legged league treten jeweils 3 leicht modifizierte AIBO-Roboter
[3] von Sony gegeneinander an, auf einem Spielfeld
der Größe 2 x 3 m 2 . Hier gibt es wegen der ein geschränkten
Bildverarbeitung der Roboter„hunde" noch eine spezielle Farbcodierung
am Spielfeldrand. Bisher agierten diese Roboter völlig autonom. Im RoboCup
Junior sollen Schüler für die Robotik begeistert werden, hier hat
z.B. Lego mit den Lego Mindstorms Roboterbaukästen geeignete Hardware
und Software entwickelt. Auf die beiden neuesten Klassen, Humanoid
Robots und RoboCup Rescue, wird später noch eingegangen.
Spielregeln des RoboCup
Im folgenden sollen kurz die wichtigsten Regeln der Middle-size league
des RoboCup etwas ausführlicher erläutert werden, da aus Platzgründen
nicht alle Wettbewerbstypen konkretisiert werden können. Diese gilt derzeit
noch, mangels leistungsfähiger humanoider Roboter, als die „Königsklasse"
der fußballspielenden Roboter. Das Gewicht der Roboter ist auf 80kg beschränkt,
ebenso ihre Maximalhöhe auf 80cm. Um die Aufgabe der Erkennung von Ball,
Robotern, Toren etc. möglichst einfach zu halten, ist der Ball als einziges
Objekt orangerot, ein Tor ganz gelb, das andere ganz blau, der Fußboden
grün, die Banden weiß, die Roboter sind schwarz mit genormten Farbmarkierungen.
Dies dient dazu, die Aufgabe der Bildverarbeitung so einfach zu halten,
daß sie mit onboard-PCs durchführbar ist.
Um die Form der Roboter gab und gibt es lang andauernde Diskussionen,
speziell, was an Kick-und Führungsmechanismen für den Ball erlaubt ist
oder nicht. So muß sichergestellt sein, daß nicht ein Roboter den Ball
umschließt oder festklemmt und diesen bis ins gegnerische Tor schiebt,
ohne daß ein anderer intervenieren könnte. Es gibt daher eine Regel, die
sicherstellt, daß der Ball jederzeit von Gegnern abgenommen werden kann.
Um die genaue Formulierung dieser Regeln wird hart gerungen, weil für
Unbeteiligte eher geringfügige Regeländerungen starke Auswirkungen auf
die Fähigkeiten der Roboter haben können. Würde beispielsweise die Farbe
des Balls von orange auf weiß geändert, könnte er nicht mehr farblich
erkannt werden, und alle Teams müßten neue, formbasierte Ballerkennungsalgorithmen
entwickeln, die derzeit noch zu zeitaufwendig und unsicher sind. Würden
die Torfarben entfernt, müßten die meisten Teams zusätzliche Sensorik
(z.B. digitale Kompasse) einbauen. Insofern sind die derzeitigen Roboter
noch längst nicht ausreichend robust, um etwa mit einem 3-jährigen Kind
verglichen werden zu können.
Technik der Fußball-Roboter
Basisplattform vieler Fußball-Roboter sind kommerzielle Kleinroboter,
wie etwa der ActivMedia Pioneer oder der Nomad SuperScout. Diese bringen
bereits einen ausreichend guten Antrieb mit, oft auch einen eingebauten
PC mit kleinem Formfaktor. In den letzten Jahren sah man auch verstärkt
Eigenkonstruktionen, etwa von der GMD, der Uni Ulm, Padua, Sharif University
und anderen.
Zumeist besitzen die käuflichen Roboter auch Ultraschall-Sensoren,
die aber für eine gute Lokalisation nicht ausreichen und höchstens
als Abstandssensor zur Hindernisvermeidung eingesetzt werden. Einige Teams
setzen zusätzlich Infrarot-Sensoren als Abstandssensoren ein, speziell
für den Nahbereich.
Die wichtigsten Sensoren der Fußball-Roboter sind Farbkameras
mit Bildverarbeitung. Inzwischen setzen relativ viele Teams selbstgebaute
360°-Kameras ein, bei denen eine Kamera von unten auf einen konischen
oder paraboloiden Spiegel schaut, so daß die Kamera einen (stark
verzerrten) Rundumblick um den Roboter liefert. Andere verwenden mehrere
Kameras, mit denen der frontale Bereich besser abgedeckt wird, der Rückraum
dagegen weniger. Bei den Tübinger Robotern wird sowohl eine 360°-Kamera
als auch eine Frontkamera verwendet. Mit digitalen Kameras nach IEEE 1394
könnte die Bildaufnahme verbessert werden, die meisten Teams nutzen
aus Kostengründen noch analoge CCD-Kameras.
Der mit Abstand präziseste Sensor der Fußballroboter ist
ein 2D-Laserentfernungsmesser der Freiburger Firma Sick AG, den mehrere
deutsche Teams (Freiburg, Stuttgart und Tübingen) verwenden. Leider
ist dieser mit 4.5 kg recht schwer und relativ teuer. Jedoch ist die Geschwindigkeit
und Genauigkeit (ca. 30 Scans/s mit Winkelauflösung von 1° und
Entfernungsauflösung von 10 mm) so hoch, daß diese Sensoren
in Verbindung mit sehr guter Auswerte- und Pfadplanungssoftware Garanten
für die mehrfachen Titelgewinne des Freiburger Teams waren.
Die Kommunikation der Roboter untereinander und mit einer Basisstation
am Spielfeldrand, in der die Roboter sich gegenseitig ihre Position sowie
ggf. die Position des Balles und der gegnerischen Spieler mitteilen, spielt
eine wichtige Rolle. Trotz mehrjähriger Erfahrungen mit Funk-Ethernet-Sy-stemen
im IEEE 802.11b-Standard bereitet die Störung der Kommunikation,
die durch die vielen gleichzeitig funkenden Teams bei jedem größeren
Turnier erneut auftritt (und nie zu Hause beim Training!) immer noch große
Schwierigkeiten.
Viele Roboter verwenden einen Kick-Mechanismus, der entweder durch Preßluft,
durch Federkraft oder durch starke Elektromagnete arbeitet. Diese Kick-Mechanismen
sind vergleichbar mit dem Kicken eines 3-Jährigen. Allerdings können
die Roboter bisher ebensowenig mit dem Ball um Hindernisse dribbeln wie
dieser, weil dazu nötige Führungsmechanismen wegen obiger Regeln
verboten sind. Die Technik aller Roboter der verwendeten Teams und besonders
interessante Forschungsberichte der besten Teams sind in den jährlichen
Konferenzbänden über den RoboCup (z.B. in [4])
nachzulesen.
Software der fußballspielenden Roboter
Für KI-Forscher bietet sich das Gebiet als eines an, bei dem viele
ihrer Methoden, wie heuristische Suchverfahren, KI-Planungsverfahren,
Wissensrepräsentationsformalismen und Umweltmodellierung, Sensorfusion
etc. eingesetzt werden können und gegen andere Ansätze (neuronale
Modelle, statistische Verfahren) verglichen werden können. Tatsächlich
spielen die auf symbolischer KI basierenden Verfahren bisher in der middle-size
league des RoboCup aber nur eine geringe Rolle, möglicherweise
deshalb, weil trotz aller Anstrengungen die Probleme der niedrigeren Schichten,
speziell der Sensorik (schnelle, robuste Echtzeit-Farbbildverarbeitung)
und Regelung bisher noch dominierten.
Die beste KI-Planung nützt wenig, wenn der Roboter den Ball nicht
zuverlässig detektieren kann. Es läßt sich bei einem Überblick
über die verschiedenen Teams derzeit auch kein einheitliches Software-Architekturmodell
identifizieren. Viele Teams haben in ihrer Software-Architektur sowohl
Prinzipien hierarchischer Organisation, etwa angelehnt an das Perzeptionsmodell
der Robotik (sense, model, perceive, plan, act) als auch Prinzipien eines
Behavior-basierten Ansatzes nach der Subsumption-Architektur von Brooks.
Schnelle, farbbasierte Bildverarbeitung und Varianten von Kalman-Filtern
für die Trajektorienberechnung von Ball und Gegenspielern spielen
in den meisten Teams eine wichtige Rolle, das Freiburger Team verwendet
erfolgreich auch Echtzeit-Pfadplanungsalgorithmen. In vielen Teams verhindern
aber noch Fehler in niedrigeren Ebenen der insgesamt recht komplexen,
meist von vielen Studenten geschriebenen und schwer zu testenden Software
und eine unzureichende Sensorik und Aktorik zur genauen Ballannahme die
erfolgreiche Demonstration höherer Fähigkeiten, wie etwa ein
Doppelpaßspiel.
Außerdem hat jedes Middle-size-Team eigene Robotik-Forschungsschwerpunkte,
eigene Hardware und Software, und es gibt, bedingt durch die unterschiedliche
Hardware und Sensorik, bisher in dieser Liga nur wenig Austausch von Software.
Eine stärkere Kooperation ist jedoch in dem vor kurzem begonnenen
DFG-Schwerpunktprogramm Robo-Cup geplant und sie findet in der Simulation
league und der Sony legged league bereits erfolgreich statt.
Informationen zur Deutschen Robocup-Szene finden sich in [5].
Aktuelle und künftige Entwicklungen
Was sind die aktuellen Entwicklungen des Roboterfußballs? Obwohl
die Spielstärke realer Roboterteams immer noch relativ schwach ist,
arbeitet die RoboCup-Community daran, die anfangs bewußt sehr roboterfreundlich
gehaltene Spielumgebung langsam zu „normalisieren". Dies ist
allerdings viel schwieriger als vermutet. Nachdem erst vor kurzem für
den RoboCup 2002 in Fukuoka [6] die Entfernung
der Banden beschlossen wurde, müssen alle Teams, die ihre Position
durch Entfernungsmessung zu den Wänden bestimmten, ihre Roboter-Selbstlokalisation
neu entwickeln. Weiterhin ist künftig eine Reduktion der großen
Abhängigkeit von Farben zur Objekterkennung geplant.
RoboCup Rescue ist das neueste Szenario, das ebenfalls auf H.
Kitano zurückgeht: Als Folge des Erdbebens von Kobe in Japan schlug
er vor, ebenso einen Wettkampf von Rettungsrobotern zu veranstalten. Diese
Idee fiel auch bei der American Association for Artificial Intelligence
(AAAI) auf fruchtbaren Boden, und das amerikanische National Institute
for Standards and Technology (NIST) erstellte umgehend ein transportables
zweistöckiges Katastrophen-Szenario, in dem Roboter teilweise ferngesteuert,
teilweise autonom in verschiedenen Räumen mit wachsendem Schwierigkeitsgrad
nach Verschütteten suchen sollten. Dieses Szenario hat durch den
Terroranschlag auf das World Trade Center schlagartig eine sehr hohe Relevanz
bekommen. In der Suche nach Überlebenden wurden dabei zum ersten
Mal Suchroboter eingesetzt. Auch hier gibt es eine Simulationsliga und
eine Liga mit echten Robotern, die 2001 in Seattle ihr Debut feierte.
In der Humanoid league, die 2000 in Melbourne zum ersten Mal
demonstriert wurde, treten zweibeinige Roboter gegeneinander an. Prototypen
solcher Roboter sind etwa der Honda Asimo, der Sony SDR-3X, der Fujitso HOAP-1 oder der Roboter PINO [8]
von Kitano, sowie weitere. Honda hat in die Entwicklung humanoider Roboter
bisher über 100 Millionen Dollar investiert. Auch in Deutschland
werden inzwischen humanoide Roboter erforscht, etwa an der TU München
und der Uni Karlsruhe. Allerdings sind alle derartigen Roboter derzeit
noch weniger als ihre rollenden Geschwister in der Lage, Fußball
zu spielen. Für laufende Roboter ist das Problem der Bildverarbeitung
wegen der stärkeren und weniger gut vorhersagbaren Eigenbewegung
der Kamera viel schwieriger, die derzeitige Akku-Technik erlaubt zudem
nur sehr kurze Zeiten autonomen Gehens. Die Stabilität der humanoiden
Roboter bei Kontakt mit einem Gegenspieler ist auch noch ungelöst.
Hier gibt es also noch sehr viel Forschungs-und Entwicklungsbedarf,
bevor die Vision des RoboCup-Gründers Kitano, daß ein Roboterteam
im Jahre 2050 das menschliche Fußball-Weltmeisterteam schlagen könnte,
in den Bereich der Möglichkeit rückt.
Artikelanfang Seitenanfang
|
|
Autor & Copyright
Andreas Zell
Universität Tübingen
© 2002 Informatik Spektrum, Springer-Verlag Berlin Heidelberg
Artikelanfang Seitenanfang
|
|
|
|
|
