Das Gebiet der Multi-Agent Systems gibt es seit ca. 1985. Entsprechend umfangreich ist die Literatur dazu bereits.
Pursuit Domain
Bereits 1986 wurde eine Aufgabe für simulierte Agenten vorgeschlagen, die dem Wolf und Schafe Spiel ähnlich ist: Auf einem schachbrettartigen Feld befinden sich vier Verfolger und ein Opfer (darum auch „predator/prey domain“). Alle können sich frei in die vier Haupthimmelsrichtungen bewegen. Die Aufgabe der Verfolger ist es, das Opfer so einzukreisen, dass es sich nicht mehr bewegen kann. In Rahmen dieses Paradigmas sind etliche Untersuchungen mit ganz unterschiedlichen Charakteristika der Verfolger und der Opfer publiziert worden. Diese erlauben es einmal, Wolf und Schafe bezüglich verschiedener Dimensionen etwas einzuordnen.
Untersuchte Fragen
Im Zusammenhang mit MAS sind in den letzten Jahren ganz unterschiedliche Fragen untersucht worden. Diese reichen von der Frage, ob Kooperation bzw. Kommunikation überhaupt notwendig ist bis hin zu verschiedenen Details einer Kooperation. Auch hier erlaubt es ein Überblick, die mit Wolf und Schafe verfolgten Fragen etwas einzuordnen.
Anregungen
Aus der Lektüre haben sich bisher folgende, spezifische Anregungen ergeben, die im Rahmen von Wolf und Schafe hilfreich sein könnten bzw. weiter verfolgt werden sollen.
Arbeitsdefinition „Agent“
Ein Agent lebt in einer Umwelt und verfügt über:
- Ziele
- Aktionsmöglichkeiten in der Umwelt
- Wissen über die Umwelt
Ein Agent nimmt etwas in der Umwelt als anderen Agenten war, wenn er dieses etwas mit diesen Bestimmungsstücken modelliert. (Stone & Veloso)
Strategien der Schafe
Koordination nach Bedarf
Koordination kann locker sein, wenn alles „normal“ läuft. Bei Problemen sollte sie verstärkt werden. Eskalationsstufen (Stone & Veloso):
- Autonomie (jedes Schaf spult seinen Taktik ab)
- Kommunikation (im Sinn von Informieren)
- Verhandeln
- (zentrale) Kontrolle
Zwei Ebenen Architektur
Die Steuerung der Schafe auf zwei Ebenen:
- Reaktor: Auf einer unteren Ebene wird das Vorgehen „real time“ durch relativ einfache Reaktionsmuster gesteuert (s.u.).
- Antizipator: Darüber läuft ein Prozess, der in Kenntnis dieser Reaktionsmuster vorausberechnet, was geschehen wird (sofern dazu genügend Zeit ist). Bei zu erwartenden Problemen (z.B. eine Lücke tut sich auf, die der Wolf nutzen könnte) greift er ein, indem er die Reaktionsmuster modifiziert. (Davidsson)
Reaktionsmuster
Aus den verschiedenen Arbeiten zur „pursuit domain“ ergibt sich eine bunte Sammlung von möglichen Reaktionsmustern:
Ecken blockieren
Jedes Schaf peilt das Nachbarfeld zum Wolf an, das am nächsten liegt. Nicht sehr effizient, da gegenseitige Behinderung. (Stone & Veloso)
Zum Wolf, weg vom Schaf
Jedes Schaf versucht so nahe zum Wolf und so weit weg von den anderen Schafen zu sein, wie möglich. Ist im offenen Feld (nur diagonale Bewegungen, hexagonales Feld) offenbar sehr effizient (sofern der Wolf sich zufällig bewegt, folgt er einer geraden Linie, gibt es Probleme). (Stone & Veloso)
Fälle als negative Beispiele
Zum einfachen Reaktionsmuster hinzu Fälle als negative Beispiele, wann vom Muster abwichen werden sollte. (Ho & Kamel)
Fallfenster
Informationen zu den einzelnen Fällen (die Situation) in folgendem Ausschnitt aus der ganzen Welt speichern (Ho & Kamel):
Kommunikationsanlässe
Vorverhandeln
Absprachen können vor dem Spiel stattfinden, so dass während dem Spiel weniger Kommunikation notwendig ist. (Stone & Veloso)
Informieren
(Als Ergänzung zum „Ecken blockieren“:) Das Schaf, das am weitesten weg ist, kündet die Ecke an, die es anpeilt. Dann wählt das nächste Schaf aus den verbleibenden die nächste und kündet an, etc. Klappt schon besser. (Stone & Veloso)
Hidden States als Kommunikationsanlass
Wenn für ein Teammitglied der Weltzustand durch die Wahrnehmung nicht eindeutig gegeben ist, können andere Zusatzinfos liefern (Friedrich, Kaiser, Rogalla & Dillmann)
Probleme übergeben
Zwei Möglichkeiten von der Fallbasis eines anderen zu profitieren
- Das Problem übergeben und die Lösung entgegen nehmen (distributed CBR)
- Das Problem und die Lösungsmethode übergeben, so dass nur von der Fallbasis des anderen profitiert wird (collective CBR) (Plaza, Arcos & MartÃn)
Kommunikationsprobleme
Problemtyp und Komplexität der Sprache
Um eine Beute zu verfolgen, die sich zufällig bewegt, genügt eine einfachere Sprache, als wenn sich die Beute auf einer geraden Linie bewegt. (Jim & Giles)
Kommunikationsprobleme bei Verteiltem Arbeiten
- Teammitglied muss mitteilen können, ob es Aufforderung versteht oder nicht, und ob es gewünschtes ausführen kann.
- Teammitglied muss mitteilen können, ob es Aufgabe gelöst hat oder nicht lösen konnte (Friedrich, Rogalla & Dillmann)
Kommunikationsprobleme zwischen Lehrer und Lerner wenn nur einer lernt
- Supervised learning: Lehrer muss richtiges Verhalten so beschreiben, dass es Lerner direkt versteht oder inferieren kann
- Reinforcement learning: Lehrer muss wissen, was für Lerner verstärkend bzw. bestrafend ist bzw. Lerner muss wissen, wie Lehrer das gemeint hat.
- Lehrer muss wissen, wo die Grenzen (z.B. in Sachen Präzision) des Lerners sind bzw. die beiden müssen darüber reden können (Friedrich, Kaiser, Rogalla & Dillmann)
Kommunikationsprobleme, wenn mehrere lernen als Team zu handeln
- Supervised learning: Wenn Teamzustand und Teamaktion problemlos auf Zustände und Aktionen einzelner Mitglieder aufgeteilt werden können, dann ist die derselbe Fall wie oben.
- Verstärkungslernen: Wenn nur ein Feedback für das gesamt Team gegeben wird, stellt sich das Problem des strukturellen credit assignments. Die Mitglieder können sich darüber unterhalten
- Damit das Lernen funktionieren kann, müssen auf jeden Fall die Teammitglied aus dem Teamziel ein Subziel für sich machen können, bzw. der Lehrer muss es ihnen erklären können. (Friedrich, Kaiser, Rogalla & Dillmann)
„Wahrheit“
Zwei Agenten mit grundsätzlich unterschiedlicher „Wahrheitsdefinition“:
- Etwas ist wahr, wenn es etwas in der Welt richtig beschreibt
- Etwas ist wahr, wenn es mit den restlichen Ãœberzeugungen konsistent ist.
Beispiel: Beide lernen, dass in einem Ofen die Temperatur hoch ist, wenn ein bestimmtes Ventil geschlossen ist. Neue Info: Ventil geschlossen, Temperatur aber tief. 1) bildet neue Überzeugung, dass dies auch möglich ist. 2) kommt zum Schluss, dass Sensor defekt ist. (Lacey, Nakata & Lee)
Lernmechanismen
Genetische Algorithmen
Relativ viele Projekte arbeiten mit genetischen Algorithmen. Dies dürfte für Wolf und Schafe eher ungeeignet sein, da psychologisch unplausibel. (Jim & Giles)
Generelles Algorithmusgerüst für Verstärkungslernen
Algorithm LearnMAP()
repeat
state <- UPDATE-STATE(state, percept)
action <- CHOOSE-ACTION(state, map)
update-val <- GET-FEEDBACK()
UPDATE-MAP(update-val. map)
until TERMINATION-CONDITION(map)
return(map)
Modulares Verstärkungslernen
Da der Zustandsraum mit allen anderen Jägern im Blickfeld (7*7) zu gross wird, je ein Zustandsraum mit der Beute und einem Jäger. Q-Learning in diesem Raum. Ein Kombinationsmodul trifft dann aus den drei Vorschlägen eine Auswahl. Es lässt sich folgendes Verhalten beobachten:
- Wenn Kollege in Sicht aber noch keine Beute: Dem Kollegen folgen (Herdenbildung)
- Wenn sichtbarer Kollege sichtbare Beute noch nicht sehen kann, dann so bewegen, dass Kollege den Anschluss nicht verliert. (altruistisches Verhalten) (Ono & Fukumoto)
Lernen der Sprache
Sprache wachsen lassen
Optimales Verhalten mit einer einfachen Sprache lernen (einfach: wenig Zeichen), dann Sprache vergrössern (mehr Zeichen) und weiterentwickeln lassen. (Jim & Giles)
Gelegenheiten zur Spracherweiterung
- Ein Zustand wird erreicht, der bedeutungsvoll ist und auf den man in Zukunft verweisen möchte (z.B. als Subziel)
- Ein neues Subziel wird generiert, für das es noch keinen Begriff gibt.
- Eine neue „Technik“ wird entwickelt. (Friedrich, Kaiser, Rogalla & Dillmann)
Neue Sprachelemente erklären
- Direkt, wenn sowohl Sprachelement wie „Bedeutung“ (z.B. Beschreibung des Weltzustandes) kommuniziert werden können.
- Indirekt, durch Vormachen/spielen des Zustandes, der Technik. (Friedrich, Kaiser, Rogalla & Dillmann)