Informatik-Lexikon
R
Refactoring
Remote Database Access
Roboter, Web-
Roboter-Fußball
Refactoring |
ErläuterungSoftware, 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:
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:
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. |
|
|
Ralf Reißing © 1999 Informatik Spektrum, Springer-Verlag Berlin Heidelberg |
Web-Roboter |
ErläuterungDie 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:
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:
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:
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]. |
|
ErläuterungBisherige 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 SpielklassenDie 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 RoboCupIm 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-RoboterBasisplattform 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 RoboterFü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 EntwicklungenWas 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. |
Hinweis: Die URLs entsprechen dem Stand bei der Veröffentlichung des Artikels und werden nicht aktualisiert. |
|
Autor & Copyright © 2002 Informatik Spektrum, Springer-Verlag Berlin Heidelberg |