2 Koordination zwischen Agenten

2.1 Verschiedene Arten der Koordination

Im letzten Kapitel wurde Koordination als zur Konfliktvermeidung und für das gemeinsame Erreichen von Zielen notwendig beschrieben. Das weist auf zwei unterschiedliche Arten von Koordination hin:

1. Kooperation (Cooperation), d.h. Zusammenarbeit, gemeinsames Verfolgen von Zielen und

2. Konkurrenz (Competition), also Verfolgen von unterschiedlichen, sich teilweise widersprechenden Zielen.

Abbildung 1: Arten der Koordination (nach [7])

Bei konkurrierenden Zielen ist ein wesentlicher Teil der Koordination die Verhandlung zwischen den Agenten und das Finden von Kompromissen (Negotiation).

2.2 Organisationsformen für die Kooperation in natürlichen Betrieben

Um für die Kooperation in künstlichen Agentengesellschaften zu lernen, lohnt es sich, natürliche Agentengesellschaften in Form von Tiergemeinschaften oder menschliche Organisationsformen zu betrachten. Die Kooperation in Gemeinschaften von reaktiv aufgebauten Agenten⁴ läßt sich am besten als emergentes Verhalten beschreiben und dazu werden Gesellschaften von Lebewesen betrachtet, die nach einfachen Mustern handeln, wie z.B. Ameisenstaaten. Als Vorbild für die Kooperation unter deliberativen Agenten⁵ werden nun vier verschiedene Organisationsformen in menschlichen Betrieben betrachtet:

Abbildung 2: Einliniensystem

Nachteilhaft sind die durch die meist große Tiefe des Baumes bedingen langen und schwerfälligen Instanzen- und Befehlswege. Außerdem ist es schwer möglich, auf besondere Aufgaben spezialisierte Instanzen einzurichten, da diese dann entweder mehrfach vorkommen müssen oder nur von wenigen Oberinstanzen genutzt werden können. Ein weiterer Nachteil dieses Systems ist, daß die obersten Instanzen alles kontrollieren müssen und somit leicht überlastet sind.

Abbildung 3: Mehrliniensystem

Die Tatsache, daß mehrere Vorgesetzte einer Instanz weisungsbefugt sind, beinhaltet aber ein hohes Konfliktpotential. Es entstehen große Probleme, wenn eine Instanz zwei sich wiedersprechende Aufträge von verschiedenen Oberinstanzen bekommt. Es ist dann schwierig zu bestimmen, welcher Auftrag vorrang hat. Das wird noch dadurch erschwert, daß bei dieser Struktur die Abgrenzung der Kompetenzen der Instanzen für Aufgabenbereiche schwierig ist.

Abbildung 4: Stabliniensystem

Allerdings können durch die Zweiteilung der Stellen in Wissen (Expertenstab) und Entscheiden (Linieninstanz) wiederum leicht Konflikte zwischen diesen beiden Teilen entstehen.

Abbildung 5: Matrixorganisation

Da hier aber wie beim einfachen Mehrliniensystem wieder mehrere Vorgesetzte weisungsbefugt sind, ist wiederum die Gefahr von Konflikten gegeben. Allerdings sind die Kompetenzen hier eindeutiger verteilt, was die Gefahr etwas verringert.

2.3 Koordination in künstlichen Agentengesellschaften

Natürlich kann man die Organisationsformen aus natürlichen Agentengesellschaften nicht einfach auf die Konstruktion von künstlichen Agentengesellschaften übertragen. Aber sicherlich kann man durch ihre Betrachtung einiges für die Organisation von Multiagentensystemen lernen. Dies Kapitel soll nun wichtige Teilaspekte der Koordination in künstlichen Multiagentensystemen vorstellen.

2.3.1 Objekte der Koordination

Zunächst muß man sich überlegen, was überhaupt koordiniert werden muß. Man kann diese Objekte der Koordination mit [6] wohl unter vier Schlagworten zusammenfassen:

1. Ziele,

2. Aktivitäten,

3. Agenten,

4. Interaktionen.

Bei den Zielen ist die Auswahl und Aktivierung zu koordinieren. Ein aktiviertes Ziel ist eines aus den ausgewählten, das aktuell verfolgt wird.

Unter dem zweiten Punkt sind die Zerlegung von Zielen in Subziele und die Abbildung von Zielen auf Aktiviäten zusammengefaßt. Es geht also um die Zerlegung von globalen Zielen in von einzelnen Agenten ausführbare Aufgaben.

Der nächste Punkt ("Agenten“) bezeichnet die Verteilung der dadurch erhaltenen Aufgaben unter den Agenten.

Als Interaktionen sind die Zuteilung von Ressourcen, die Sequentialisierung des Zugriffs auf Ressourcen und die Synchronisation zu verstehen, also klassische Aufgaben in nebenläufigen Systemen.

Die ersten drei Punkte betreffen ausschließlich kooperierende Agenten, die hier auch im weiteren vorwiegend besprochen werden sollen. Die Interaktionen sind dem gegenüber sowohl bei kooperierenden als auch bei konkurrierenden Agenten zu koordinieren, zumindest soweit sie auf die gleichen Ressourcen zugreifen. Die Synchronisation ist in jedem Fall notwendig, um z.B. Verhandlungen (® Negotiation, siehe Kapitel 2.3.4.2) zu ermöglichen.

2.3.2 Koordinationsmechanismen

Es gibt verschiedene Mechanismen, mit denen man Koordination erreichen kann. Zum Beispiel könnte die Ausführung von allen Aktivitäten der Agenten genau mit Plänen festgelegt sein, die vorbestimmte Regeln zur Koordination beachten. Die Koordination würde damit auf eine standardisierte Basis gestellt.

Eine andere Möglichkeit ist die direkte Überwachung der Abhängigkeiten und des Zusammenspiels der Aktivitäten der Agenten durch einen der Agenten. Dieser wirkt dann also als Vorgesetzter, der die korrekte Zusammenarbeit der Mitarbeiter sicherzustellen hat. Oder er wirkt bei konkurrierenden Agenten als Richter, der in Konfliktfällen die Entscheidung trifft.

Eine sehr kommunikationsintensive aber gleichberechtigte Variante ist die Möglichkeit der wechselseitigen Abstimmung. Dabei stimmt jeder Agent sein Verhalten kontinuierlich in Abhängigkeit von den Interaktionen mit anderen Agenten ab. Wenn ein Agent also z.B. von einem anderen Hilfe bei der Bewältigung einer Aufgabe benötigt, oder wenn er auf die selbe Ressource zugreifen will, dann wird er den anderen Agenten direkt darauf ansprechen und sich mit ihm abstimmen.

2.3.3 Planung in Multiagentensystemen

2.3.3.1 Allgemeines

Agenten, die ein gemeinsames Ziel verfolgen und zur Erreichung dieses Ziels kooperieren wollen, müssen planen können. Dies Planen wird von Bernd Neumann definiert als:

"Planen ist das Entwerfen einer Aktionsfolge, mit der eine Startsituation in eine gewünschte Zielsituation überführt werden kann.“

Allerdings unterscheidet sich Planung in Multiagentensystemen recht stark von den traditionellen Planungsansätzen der Künstlichen Intelligenz. Der entscheidende Unterschied ist, daß in Multiagentensystemen mehrere autonome intelligente Agenten vorhanden sind, die theoretisch alle eigenständig planen können. Es geht also darum, Methoden zu entwickeln, die Aufgaben der klassischen Künstlichen Intelligenz verteilt lösen können. Darum ist ein Oberbegriff für Multiagentensysteme auch Verteilte Künstliche Intelligenz. Auf die Planung bezogen heißt das, daß Pläne von mehreren Agenten gemeinsam generiert und auch ausgeführt werden können. Um diese Zusammenarbeit zu ermöglichen, ist Kommunikation zwischen den Agenten notwendig.

Die Tatsache, daß es mehrere handelnde Einheiten gibt, bewirkt außerdem, daß die Aktionen nicht sequentiell ablaufen können, daß also ein nebenläufiger Plan erstellt werden muß. Oft ist in Multiagentensystemen überdies die Umgebung dynamisch. Sie kann sich also auch unabhängig vom Handeln eines Agenten verändern.

Grundsätzlich unterscheidet man beim Planen in Multiagentensystemen zwischen Zentralem Planen und Dezentralem Planen. Als eine zwischen den beiden Extremen stehende Lösung wird als drittes das Blackboard-Planen vorgestellt.

2.3.3.2 Zentrales Planen

Abbildung 6: Zentrales Planen (nach [6])

2.3.3.3 Dezentrales Planen

Abbildung 7: Dezentrales Planen (nach [6])

2.3.3.4 Blackboard-Planen

Abbildung 8: Blackboard-Planen (nach [6])

Beim Blackboard-Planen wird so erreicht, daß die Planung beim Vermittler (dem Blackboard) nur mäßig komplex ist, da die Agenten jeweils spezielle Teilplanungsaufgaben übernehmen. Außerdem wird dadurch eine Mitbestimmung der Agenten erreicht ohne besonders aufwendige Kommunikation zu benötigen. Die Planung in den Agenten kann je nach zu lösender Teilaufgabe recht einfach sein. Wenn man die Planungsaufgaben redundant verteilt, wenn also mehrere Agenten die gleichen Aufgaben lösen, dann wird auch dieses System recht fehlertolerant. Allerdings steigt dann auch wieder das Konfliktpotential, denn bei verschiedenen Lösungen für das gleiche Planungsproblem muß ja entschieden werden, welche auszuwählen ist.

2.3.4 Kommunikation zwischen Agenten

2.3.4.1 Allgemeines

Wie die letzten Kapitel gezeigt haben, ist Kommunikation ein wichtiger Teil von Multiagentensystemen. Man kann im Wesentlichen zwischen zwei verschiedenen Arten, die Kommunikation auszuführen, unterscheiden:

Zunächst gibt es die dem Blackboard-Prinzip entsprechende Möglichkeit, daß die Informationen über einen gemeinsamen Speicherbereich ausgetauscht werden können. Dabei sind die Informationen immer prinzipiell von allen Agenten lesbar und alle Agenten, denen sie wichtig erscheinen, können darauf zugreifen. Jeder Agent kann außerdem solche Informationen auf dem Blackboard veröffentlichen. Diese Methode der Kommunikation nennt man shared memory.

Die andere Möglichkeit ist, Nachrichten direkt an den oder die Empfänger zu senden, für die sie gedacht sind. Dazu muß der Sender der Nachricht natürlich wissen, für welche anderen Agenten die Nachricht interessant sein könnte und er muß sie entsprechend adressieren. Diese Methode wird message passing genannt.

Es genügt aber nicht, die Agenten einfach Nachrichten versenden zu lassen, damit sie sich untereinander verständigen können. Es kann ja sein, daß man es mit heterogenen Agenten zu tun hat, die ihr Wissen vollkommen unterschiedlich repräsentieren und eine unterschiedliche Sprache sprechen. Es müssen für eine erfolgreiche Kommunikation also auch noch einige andere Voraussetzungen erfüllt sein:

Zunächst müssen die Agenten, wie bereits angesprochen, eine gemeinsame Sprache benutzen. Auch wenn sie Wissen intern unterschiedlich repräsentieren, müssen sie sich auf eine Repräsentationsform einigen, mit der sie das Wissen transportieren wollen und die dann beide in ihre interne Repräsentationsform übersetzen können. Eine solche Sprache wird mit KIF (Knowledge Interchange Format) im Kapitel 2.3.4.3 vorgestellt und wird gemeinhin als Interlingua bezeichnet.

Des weiteren müssen die Agenten vergleichbare Vorstellungen von der Welt haben. Sie müssen die Wörter der Sprache, mit der sie sich verständigen, mit ähnlichen Vorstellungen verbinden können und deswegen ähnliche Objekte als existent kennen. Dies kann u.U. durch eine sogenannte Ontolingua sichergestellt werden, auf die hier aber nicht näher eingegangen werden soll.

Die Agenten müssen außerdem verschiedene Nachrichtentypen unterscheiden können. Es gibt in der mündlichen Kommunikation beispielsweise eine recht große Anzahl unterschiedlicher Sprechakt-Typen. Diese unterschiedlichen Typen haben unterschiedliche Zwecke. Zum Beispiel kann ein Sprechakt einen Befehl enthalten. Oder er kann einfach zur Information dienen. Er kann aber auch die Antwort auf einen Befehl sein oder eine Anfrage nach Information. Insgesamt wurden die englischen Verben z.B. in [8] in 21 Kategorien und weitere Unterkategorien eingeteilt. Für die Kommunikation zwischen künstlichen Agenten muß man üblicherweise nicht ebenso viele Nachrichtentypen unterscheiden, aber es gibt doch einige Typen, die man auch dort benötigt. Die möglichen Typen und das Nachrichtenformat, das unter anderem den Nachrichtentyp enthält, wird z.B. in KQML (Knowledge Query and Manipulation Language) spezifiziert, die im Kapitel 2.3.4.4 kurz vorgestellt wird.

Damit die Kommunikation gelingt, muß außerdem noch der Ablauf des Dialoges einheitlich geregelt sein. Dazu wird bei künstlichen Agenten ein Protokoll spezifiziert, das dann beide Agenten benutzen. KQML enthält auch ein solches Protokoll.

2.3.4.2 Verschiedene Konversationsmuster

Die meisten Nachrichtentypen in Multiagentensystemen haben den Zweck, sich über Aktiviäten zu verständigen. Für solche Verhandlungen haben drei typische Konversationsmuster herausgebildet:

Die miteinander kommunizierenden Agenten stehen oft in einer Master-Slave bzw. Client-Server-Beziehung zueinander. Das heißt, es besteht eine hierarchische Ordnung zwischen den beiden an der Kommunikation beteiligten Einheiten, wobei der Master bzw. der Client die Dienste des Slaves bzw. des Servers in Anspruch nimmt und diesem Befehle erteilt. Diese strenge Strukturierung der Konversation bewirkt, daß die Kommunikation sehr effizient ausgeführt werden kann, da zum Beispiel keine längeren Verhandlungen über strittige Punkte vonnöten sind. Voraussetzung dieser Art der Konversationstruktur ist aber, daß der Master die Fähigkeiten der Slaves kennt und auch ihre aktuelle Verfügbarkeit bestimmen kann.

Ein weiteres mögliches Konversationsmuster ist das sogenannte Contract Net. Dabei schließen Agenten, die Hilfe benötigen, mit anderen Agenten Verträge über die Erfüllung eines Auftrags ab. Zunächst schreibt ein beliebiger Agent, der gerade eine Aufgabe zu vergeben hat, diese unter allen anderen Agenten aus. Dieser Agent wird dann Auftraggeber oder manager genannt. Agenten, welche die notwendigen Fähigkeiten und freie Ressourcen zur Erledigung der Aufgabe haben, bewerten die Ausschreibung. Daraufhin gibt eine Teilmenge dieser Agenten Angebote (bids) an den manager ab. Diese Agenten werden auch bidder genannt. Der manager bewertet die eingegangenen Angebote, selektiert das beste und vergibt den Auftrag (contract) an den anbietenden Agenten (contractor). Der Auftragnehmer ist nun verpflichtet, den Auftrag auszuführen. Er meldet den Fortgang der Bearbeitung und den Vollzug an den manager. Bei einer Verzögerung der Bearbeitung kann der manager den contractor auch mahnen. Der Vorteil dieser Kommunikationsstruktur ist, daß sie nicht streng hierarchisch aufgebaut ist, sondern daß die Rollen dynamisch verteilt werden, je nachdem, ob ein Agent einen Auftrag zu vergeben hat oder meint, einen Auftrag von einem anderen Agenten übernehmen zu können. Der Auftragnehmer kann entsprechend Teilaufgaben wiederum als manager weitergeben.

Die dritte Möglichkeit, die Kommunikation zu strukturieren, ist die sogenannte Negotiation. Dabei ist die Konversation gerade nicht strukturiert, sondern eine flache, gleichberechtigte Verhandlung zwischen verschiedenen Agenten. Dieses Konversationsmuster kann natürlich eine sehr umfangreiche Kommunikation ergeben, wie man es aus Debatten und Diskussionen unter gleichberechtigten Partnern kennt. Deshalb wird die Negotiation vorwiegend zur Kompromissfindung zwischen Agenten mit gegensätzlichen Zielen eingesetzt, bei der die anderen beiden Kommunikationsstrukturen nicht anwendbar sind.

2.3.4.3 Knowledge Interchange Format (KIF)

KIF ist, wie bereits in Kapitel 2.3.4.1 angesprochen, eine Sprache, die dem Austausch von Wissen zwischen Systemen mit unterschiedlichen Wissensrepräsentationen dient. KIF ist also eine ausschließlich für diesen Wissenstransfer entwickelte Zwischensprache (Interlingua), in der das zu übertragende Wissen während der Übertragung repräsentiert wird. KIF ist also weder zur internen Wissensrepräsentation gedacht, noch zur Kommunikation mit dem Benutzer, noch ist es direkt für Reasoning, d.h. für das Erschließen von neuem Wissen aus dem bereits vorhandenen Wissen, zu gebrauchen. Allerdings bietet KIF sehr umfassende Ausdrucksmöglichkeiten, denn möglichst viele andere Wissensrepräsentationsformalismen sollen ja für den Wissenstransfer nach KIF übersetzbar und ohne Verlust an Information wieder in eine andere Wissensrepräsentationssprache zurück übersetzbar sein. KIF erlaubt beispielsweise beliebige Ausdrücke in Prädikatenlogik erster Stufe, die Repräsentation von Meta-Wissen, die Beschreibung von Regeln für nicht-monotones Schließen und die Definition von Objekten, Funktionen und Relationen. Außerdem hat KIF eine deklarative Semantik, das heißt es sind keine Bezüge zu einem Interpreter nötig, um Sätze der Sprache zu verstehen.

KIF ist nur eine von vielen möglichen Interlinguae. Sie hat zwar den Vorteil, daß sie in viele andere Wissensrepräsentationssprachen übersetzbar ist, aber je nach den von den Agenten tatsächlich verwendeten Repräsentationsformalismen kommen auch andere Sprachen zum Austausch des Wissens in Frage. Zum Beispiel könnten auch Prolog, Lisp oder sogar SQL als Interlinguae dienen. Wenn alle Agenten die gleiche interne Wissensrepräsentationssprache verwenden, benötigt man natürlich keine besondere Zwischensprache, sondern kann als Transfersprache direkt diese interne Sprache verwenden.

2.3.4.4 Knowledge Query and Manipulation Language (KQML)

KQML besteht im wesentlichen aus zwei Teilen: einer Sprache zur Formulierung verschiedener Nachrichtentypen zum Wissensaustausch und einem Protokoll zur Regelung des Dialogablaufs.

Abbildung 9: KQML Protokollstack

:content <eigentlicher Inhalt>
:type <Nachrichtentyp>
:language <für den Inhalt verwendete Sprache>
:ontology <Thema der Nachricht>
:sender <Sender der Nachricht>
:receiver <Empfänger der Nachricht>

Das Protokoll von KQML ist eine Erweiterung des ISO-7-Schichten Modells und setzt auf die oberste Schicht des ISO/OSI Protokollstacks drei weitere Schichten auf. Diese drei Schichten werden zusammengenommen SKTP (Simple Knowledge Transfer Protocol) genannt.

Direkt auf den application-layer des ISO/OSI-Modells setzt der communication-layer von SKTP auf. Dieser benutzt die Daten aus der KQML-Nachricht, die für die Nachrichtenübertragung wichtig sind, also die Adressen von Sender und Empfänger der Nachricht. Darüber ist der message-layer angeordnet. Dieser verwendet die Angaben zu dem Format der Nachricht, also den Nachrichtentyp, die für den Inhalt verwendete Wissensrepräsentationssprache und das Thema der Nachricht. Die oberste Schicht des SKTP-Protokolls, der content-layer, betrachtet nur den eigentlichen Inhalt der Nachricht, also das in den Wörtern der Interlingua ausgedrückte Wissen.

2.3.5 Lernen in Multiagentensystemen

2.3.5.1 Allgemeines

Sandip Sen und Gerhard Weiss definieren maschinelles Lernen als:

"The acquisition of new knowledge and motor and cognitive skills and the incorporation of the acquired knowledge and skills in future system activities, provided that this acquisition and incorporation is conducted by the system itself and leads to an improvement in its performance.“

Da Multiagentensysteme typischerweise sehr komplex sind und damit ein gutes Verhalten des Systems schwer analytisch konstruierbar ist, kann man oft bessere Ergebnisse durch maschinelles Lernen erreichen. Deswegen lohnt es sich, auch diesen Aspekt von Multiagentensystemen zu betrachten, obwohl er kein notwendiger Bestandteil dieser Systeme ist.

Wie beim Planen kann auch beim Lernen in Multiagentensystemen zwischen zentralem Lernen und dezentralem Lernen unterschieden. Dabei lernt beim zentralen Lernen ein Agent isoliert von den anderen und beim dezentralen Lernen lernen alle Agenten interaktiv.

2.3.5.2 Verschiedene Aspekte des Lernens

Das Gebiet des maschinellen Lernens in Multiagentensystemen ist noch sehr jung. Deswegen gibt es noch keinen Kanon an bewährten Lernmethoden für diese Systeme. Es gibt aber eine Fülle von Ansätzen, die entweder direkt aus der traditionellen KI übernommen wurden oder bereits Anpassungen für die verteilte KI erfahren haben. Um diese verschiedenen Ansätze einordnen und beurteilen zu können, gibt es verschiedene Merkmale, nach denen die verschiedenen Arten des maschinellen Lernens unterschieden werden können:

• Dezentralisierungsgrad (Verteiltheit und Parallelität),

• Art der Interaktion (Stärke, Dauer, Häufigkeit, Strukturierung, Veränderbarkeit),

• Einfluß der verschiedenen Agenten auf den Lernprozeß (Wichtigkeit und Rollen),

• Lernziel (individuelles oder Gruppenverhalten),

• Lern-Feedback:

  • supervised learning: Das gewünschte Lernergebnis wird als Feedback mit dem erreichten Ergebnis verglichen und es wird versucht, das zweite dem ersten anzunähern.

  • reinforcement learning: Die Nützlichkeit des gefundenen Lernergebnisses für das zu lösende Problem wird als Feedback geliefert, und es wird versucht, diese Nützlichkeit zu maximieren.

  • unsupervised learning: Es wird kein Feedback zurückgeliefert.

• Repräsentation des erlernten Wissens (z.B. in Prädikatenlogik oder neuronalen Netzen).