Gemeinsam denken

Manche Probleme lassen sich mit mehreren, unabhängig denkenden und agierenden Einheiten schneller lösen. Dabei spielen unterschiedliche, sich ergänzende Perspektiven eine wichtige Rolle.Phoenixpix – Fotolia.com

Arbeiten unterschiedliche Akteure, die relativ unabhängig voneinander sind, an der Lösung einer Aufgabe, spricht man von sogenannten Multi-Agenten-Systemen. Agenten in diesem Sinne können sowohl Menschen als auch Computerprogramme oder Maschinen sein. Wichtig ist nur, dass jeder Agent eine gewisse Selbständigkeit besitzt und basierend auf den Wahrnehmungen seiner Umwelt Entscheidungen treffen kann, um diese dann in Aktionen umzusetzen. Diese Entscheidungsfindung ist eine Schlüsselstelle für derartige Systeme. Der Spezialfall der Multi-Roboter-Systeme wirft zusätzlich spezifische Probleme bei der Koordination der Pfadplanung auf: Die einzelnen Roboter müssen sich also einigen, wer wann wohin fährt, ohne dass es zu Staus kommt. Letztlich ist das eine zusätzliche Aufgabe, die die Künstliche Intelligenz der Fahrzeuge lösen muss.

Künstlich intelligente Entscheidungen treffen

Das Lehrbuch ‚Artificial Intelligence: A Modern Approach‘ von Stuart J. Russel und Peter Norvig machte die Sichtweise, intelligente Systeme als rationale Agenten aufzufassen, populär. Rational bedeutet in diesem Kontext, dass der Agent, entsprechend seiner Kenntnis der Welt, die Aktionen auswählt, die geeignet sind, ihn einem Ziel näher zu bringen. Oft genug reicht ein Agent allerdings nicht aus, um eine Aufgabe zu lösen. Das kann der Fall sein, weil es verschiedene Agenten mit verschiedenen Fähigkeiten gibt, weil diese jeweils nur begrenzte Informationen haben oder weil sie verschiedene Interessen verfolgen.

Eine sehr eingeschränkte Form von Multi-Agenten-Systemen sind die Distributed Constraint Satisfaction Problems – kurz DisCSP –, bei denen das Wissen über ein bestimmtes Problem über die Agenten verteilt ist und diese zu einer gemeinsamen Lösung kommen müssen, zum Beispiel zu einem gemeinsamen Ablaufplan, um ein Produkt zu erstellen. Für solche DisCSPs existieren verschiedene Methoden, um diese möglichst schnell zu lösen. Allgemein charakterisiert Katia Sycara Multi-Agenten-Systeme in ihrem gleichnamigen Aufsatz durch vier Merkmale: Jeder Agent hat unvollständige Information oder bestimmte Fähig­keiten, das Problem zu lösen, es gibt keine globale Steuerungs­instanz. Außerdem sind die  Daten verteilt und die Berechnung erfolgt asynchron.

All diese Eigenschaften bestehen bei den DisCSPs. Hinzu kommt, dass die Agenten sich koordinieren müssen, wofür allgemein verschiedene Mechanismen in Betracht kommen – je nach Art und Weise, wie diese Interaktion erfolgen soll. In einem kooperativen Setting, in dem alle Agenten daran interessiert sind, auf ein gemeinsames Ziel hinzuarbeiten, geht es vor allem darum, die Aufgabe in verschiedene Teile zu zerlegen und an die einzelnen Agenten weiterzugeben. Ein dafür geeignetes Verfahren ist das Kontraktnetz-Protokoll, das eine Aufgabe Stück für Stück an andere Agenten delegiert. Ein Manager verteilt dabei die Aufgaben an den Kontraktor, der jeweils die besten Bedingungen zur Erledigung dieser Aufgabe bietet.

Eine andere Möglichkeit ist das sogenannte Blackboard-System. Zur Erläuterung dient hier die Metapher von Experten, die um eine Tafel herum stehen und versuchen zur Lösung beizutragen, indem sie ihre Lösungsansätze auf die Tafel schreiben. Sie können dabei von Lösungen Gebrauch machen, die bereits auf der Tafel stehen. Bei all diesen Ansätzen müssen die Agenten gegebenenfalls mehrere Schritte voraus planen, um eine konfliktfreie Ausführung zu garantieren. Beispiele für kooperative Szenarien sind das gemeinsame Finden eines Ablaufplans, um eine Menge von Treffen abzuwickeln, die Organisation von größeren Arbeitsabläufen oder auch das Zusammenspiel innerhalb eines Sportteams.

Im Gegensatz zu solch kooperativen Szenarien stehen wettbewerbsartige Situationen, bei denen alle Agenten individuelle Ziele verfolgen, die durchaus miteinander in Konflikt stehen können. Typische Bespiele sind hier elektronische Märkte oder auch Datennetzwerke mit verschiedenen Providern. Die Koordination kann hier nicht durch Absprache erfolgen, da es kein gemeinsames Ziel gibt, sondern eine übergeordnete Instanz muss durch geeignete Protokolle und Spielregeln dafür sorgen, dass die Agenten ihre individuellen Ziele verfolgen können. In solchen Fällen bietet die Spieltheorie verschiedene Werkzeuge. Wissenschaftler haben beispielsweise Auktionen in all ihren Spielarten untersucht und entwickeln diese stetig weiter. So beruhen zum Beispiel die Online-Auktionsverfahren von Google auf solchen Techniken. Ein weiteres wichtiges Verfahren ist das sogenannte Mechanismus Design. Dabei geht es darum, Spielregeln so zu entwerfen, dass sie Mitspieler anregen, ihre wahren Präferenzen zu äußern, um darauf aufbauend eine gemeinsame Entscheidung zu fällen. Ein solcher Mechanismus kommt beispielsweise bei der Zuweisung von Mitfahrern an Autofahrer zum Tragen.

Simulationsumgebung Robocup-Rescue: So sieht das Spielfeld für den Wettbewerb um die beste Koordinationsstrategie aus.Universität Freiburg

Simulierte Szenarien testen Problem­lösungsstrategien

Bei den bisher genannten Beispielen ging es immer darum, eine bestimmte Aufgabe zu lösen, bei der verschiedene Agenten kooperieren oder miteinander im Wettbewerb stehen. Oft simulieren Forscher ein vorhandenes System von Agenten (meist Menschen oder von Menschen gesteuerte Fahrzeuge), um beispielsweise Kapazitätsaussagen treffen zu können oder verschiedene Strategien zu untersuchen. Auch dazu eignen sich Multi-Agenten-Systeme, wobei hier das Ziel ist, das Verhalten einzelner Agenten möglichst genau nachzuempfinden. Solche mikroskopischen Simulationen können unter Umständen genauere Aussagen als makroskopische machen, die es zum Beispiel ermöglichen, die Bewegung von Menschenmengen durch physikalische Gesetze, wie der Dynamik von Flüssigkeiten, zu beschreiben. Sie können aber auch dazu dienen, bestimmte Problemlösungsstrategien zu evaluieren und zu vergleichen. Auch auf dem internationalen Wettbewerb Robocup-Rescue beispielsweise treten verschiedene Koordinationsstrategien für den Einsatz von Rettungskräften bei Naturkatastrophen miteinander in Wettstreit.

Roboter kooperieren

Multi-Roboter-Systeme sind ein Spezialfall von Multi-Agenten-Systemen. Hier sind Roboter die Agenten. Jene können sich in ihrer physikalischen Umwelt bewegen und diese manipulieren. Außerdem können die Roboter in den meisten Fällen miteinander kooperieren. Dadurch können Gruppen von Robotern einige Probleme in der Robotik einfacher und effizienter lösen. So kann beispielsweise eine Gruppe von Explorationsrobotern schneller einen vorgegebenen Raum nach Opfern absuchen, als das ein einzelner Roboter könnte. Auch können mehrere Roboter das Lokalisationsproblem – also fest stellen, wo sie sich befinden – gemeinsam zuverlässiger lösen. Allerdings werden manche Dinge auch schwieriger. So ist das Pfadplanungsproblem für einen einzelnen Roboter erheblich einfacher lösbar als für eine Gruppe von Robotern. Auch ist der Aufwand, Aufgaben zu verteilen und zu überwachen, natürlich größer.

Viele Augen sehen mehr als eins

Alle Messungen, die ein Roboter durchführt, sind naturgemäß mit einem Fehler behaftet. Durch verschiedene Messungen kann er diesen Fehler reduzieren. Eine Möglichkeit ist, Messungen und Schätzungen aller Roboter, die sich gegenseitig beobachten können, zu fusionieren, um so bessere Schätzungen zu erhalten. Speziell für das Lokalisationsproblem lassen sich so genauere Schätzungen erreichen. Eine andere Lösung für dieses Problem ist, Roboter als Landmarken zu definieren, um die Orientierung zu erleichtern. Dies lässt sich einfach durch RFID-Chips umsetzen, die es ermöglichen, besuchte Stellen wieder zu erkennen und Informationen lokal auszutauschen. Das verbessert auch Schätzungen über andere Objekte erheblich. Das Roboterfußballteam CS Freiburg, das mehrmals Weltmeister geworden ist, hat beispielsweise die Schätzung der Ballposition durch verschiedene Roboter fusioniert, um genauere Schätzungen zu erhalten. Ein wichtiger Punkt dabei war, dass ein Mehrheitsprinzip sogenannte Phantombälle, die durch Fehlwahrnehmungen der Kameras entstanden sind, ausgefiltert hat.

Um eine gegenseitige Blockade der Roboter an Engstellen zu verhindern, existieren verschiedene Ansätze.Universität Freiburg

Engstellen vermeiden

Wenn sich mehr als ein Roboter innerhalb eines vorgegebenen Raums bewegen soll, ergibt sich das Problem, dass sie sich gegenseitig in die Quere kommen können. Dadurch wird das Pfadplanungsproblem, das für einen Roboter in einer vorgegebenen Anzahl von Dimensionen effizient lösbar ist, zu einem sogenannten PSPACE-vollständigen Problem, das vermutlich nur in exponentieller Zeit vollständig zu lösen ist. Deshalb existieren verschiedene Koordinationsmechanismen, die das Problem approximativ lösen. Einer davon ist, dass die Roboter Prioritäten erhalten und die Pfadplanung iterativ erfolgt, wobei jeder jeweils die Pläne der höher priorisierten Roboter berücksichtigt, wenn er den eigenen Plan erstellt. Alternativ können sie auch alle Pläne unabhängig voneinander erstellen und dann lediglich die zeitliche Ausführung (wiederum basierend auf den Prioritäten) modifizieren. Das heißt, ein Roboter muss gegebenenfalls auf seinem Pfad anhalten und erst einen anderen Roboter passieren lassen. Eine andere Möglichkeit besteht darin, Konflikte nur dann zu lösen, wenn sie lokal auftreten und die Roboter direkt miteinander kommunizieren können. Dann ist keine zentrale Instanz für die Planung notwendig. Allerdings müssen Mechanismen vorhanden sein, die durch lokale Interaktion eine globale Blockade feststellen und auflösen können.

Bei den Roboterfußball-Weltmeisterschaften zeigt sich, welche Mannschaft die Rollen am sinnvollsten verteilt.Universität Freiburg

Aufgaben verteilen

Der wichtigste Punkt bei einem Multi-Roboter-Team ist das Verteilen der Aufgaben. Diese ist durch die verschiedenen Fähigkeiten der Roboter zumindest zum Teil vorgegeben. Bei zwei Gruppen von Robotern beispielsweise, von denen die eine schwere Lasten über weite Entfernungen schnell transportieren kann und die andere, wendig und klein, aber langsam ist und nur einen eingeschränkten Wirkungsradius besitzt, ist klar, welche Gruppe eine Exploration idealerweise übernimmt. Je nach globaler Aufgabe, kann die Zuweisung von Aufgaben unterschiedlich verlaufen. Beim oben erwähnten Roboterfußball hatte anfänglich jeder Roboter einen eigenen Kompetenzbereich auf dem Fußballfeld, den er möglichst nicht zu verlassen hatte. Dies stellte sich jedoch als zu unflexibel heraus. Ein besseres System war, vier Rollen zu definieren, die jeweils von einem Spieler eingenommen werden mussten: Torwart, Verteidiger, Libero und Angreifer.

Hier ist die Bewertung der Positionen für den Libero beim Roboterfußball für das gesamte Spielfeld zu sehen. Rot symbolisiert eine ungünstige, gelb eine gute und weiß eine ideale Position.Universität Freiburg

Je nach Spielsituation gibt es einen idealen Punkt für jede Rolle auf dem Spielfeld. Für die Fußball spielenden Roboter gibt es abhängig von der Distanz zu diesem Punkt Kosten (in Form von aufzuwendender Energie und Zeit), die entstehen. Basierend auf dem Nutzen, einen Spieler auf dem Punkt stehen zu haben und den Kosten , die er benötigt, um dort hinzufahren, entsteht dann ein Optimierungsproblem: Die Spieler müssen die entsprechenden Rollen so zuordnen, dass der Nutzen maximiert und die Kosten minimiert werden. Dieses Optimierungsproblem können die Spieler dezentral lösen und so dynamisch ihre Rolle wechseln. Diese dynamische Rollenzuweisung hat sich im Team des CS-Freiburg bewährt, speziell da es auch mit Ausfällen einzelner Spieler umgehen konnte. Weniger wichtige Rollen bekommen dann eine niedrigere Priorität. In anderen Kontexten eignen sich natürlich andere Mechanismen. So ist bei der Aufgabe, große Flächen mit Robotern kooperativ zu reinigen, eine dezentrale Strategie erfolgversprechender, die nur auf lokaler Kommunikation beruht. Auch hier können einzelne Akteure ausfallen, ohne die Lösung der Aufgabe zu verhindern.

Mehr miteinander reden

Wie bereits angemerkt, sind die Art und die Struktur der Kommunikation von großer Bedeutung. Eine Punkt-zu-Punkt-Kommunikation beispielsweise besteht dann, wenn zwei Roboter mit nahezu beliebiger Bandbreite immer in Verbindung treten können – weil zum Beispiel ein zuverlässiges Wlan-Netzwerk vorhanden ist. Die zentrale Koordination kann dann auch eine zentrale Instanz übernehmen, die Aufgaben verteilt und die Pfadkoordination übernimmt. Diese Vorgehensweise hat auch der Teamchef des Roboterfußballteams des CS Freiburg gewählt. Ein Fallback-Mechanismus garantierte auch bei nicht funktionierendem Wlan noch die Koordination – wenn auch auf einem schlechteren Qualitätslevel. Die zentrale Instanz zur Koordination war hier allerdings nicht entscheidend, da jeder Roboter im Team die Koordination hätte durchführen können. Diese ist eigentlich nur dann notwendig, wenn diese zum Beispiel erheblich mehr Rechenaufwand als die einzelnen Roboter zu bewältigen hat, wenn die Aufträge über diese zentrale Instanz ins System kommen oder für zentrale Systemverbesserungen. Oft sind aber keine stabilen Kommunikationsverbindungen vorhanden. Über Bluetooth beispielsweise können Roboter nur auf kurze Distanzen miteinander kommunizieren. Der Austausch über Aufteilung und bereits erledigte Aufgaben findet dann nur statt, wenn die Roboter sich begegnen. In Umgebungen mit zerstörter Infrastruktur – weil eine Katastrophe stattgefunden hat – ist die Kommunikationsfähigkeit oft noch unsicherer. Hier können künstlich ausgebrachte Landmarken – RFID-Chips – die Topologie eines unbekannten Geländes zuverlässig kartographieren und Informationen über die bereits kartographierten Gebiete verteilen.

Insgesamt steigen die Anforderungen an zuverlässige Kommunikationsmechanismen mit der Anzahl der Roboter und der Anfälligkeit der Kommunikationsinfrastruktur. Dabei spielen ad-hoc-Netzwerke eine immer größere Rolle.

(dl)