Kommunikation zwischen autonomen Agenten

Auch im Bereich der Kommunikation zwischen autonomen Agenten existiert unterdessen bereits eine umfangreiche Literatur als Folge diverser Workshops die zu diesem Thema durchgeführt wurden. Allerdings ist das Feld noch ziemlich im Aufbruch: „There seems to be little consensus on the basics of agent communication. There is no clear understanding of the semantics of individual speech acts … Even less is known about the semantics of conversation and the relation between speech acts and the conversation of which they form a part.“ (Dignum & Greaves, 2000)

Da dabei meist die spezifische Situation autonomer Softwareagenten diskutiert wird, ist vieles davon nicht speziell für das W.U.S. Projekt relevant. Darunter fallen z.B. Themen wie:

  • Zuteilung knapper Ressourcen bei mehreren gleichzeitig aktiven Agenten (Wagner et al., 2000)
  • Dialogpartner die plötzlich verschwinden oder sonst irgendwie inaktiv werden (Nodine & Unruh, 2000)
  • Finden und verpflichten geeigneter anderer Agenten als Partner (Dignum, Dunin-Keplicz & Verbrugge, 2000)
  • Interaktion zwischen Agenten sehr unterschiedlicher „Intelligenz“ Greaves, et al. 2000)
  • Standardisierte Sprachen, so dass beliebige neue Agenten eingefügt werden können (KQML und FIPA ACL)

Anregend scheinen mir aus der ganzen Diskussion einerseits ein genereller Ãœberblick über die Themen des Feldes (Dignum & Greaves) und einige Ãœberlegungen zum Thema „Conversation Policies“.

Zentrale Themen des Gebiets

(Dignum, F. & Greaves, M. (2000). Issues in Agent Communication: An Introduction)

Agententheorien

Es wird eine explizite Theorie benötigt, die beschreibt, wie Agenten „denken“. Ein beliebtes Modell ist das BDI (Belief, Desire, Intention). Oft werden allerdings nur vereinfachte Speech Acts angenommen: Kommunikation ist Aktion wie jede andere auch, Hauptziel ist die Veränderung der Meinungen (beliefs) andere Agenten.

Semantik

Was bedeutet/ was will ein Speech Act (Vorbedingungen, Folgen)? Dies ist eine schwieriges Thema unter anderem darum, da die einzelnen Agenten autonom sind, sich also gegenseitig nicht zu etwas zwingen können. Die Folgen eines Speech Acts können also nicht gleich beschreiben werden, wenn etwa die Folge der Aktion „X auf einen Tisch stellen“ (Þ „X steht auf dem Tisch“).

Ontologie

Es muss in der Sprache, in der die Kommunikation abläuft, möglich sein, auf Gegenstände etc. im Umfeld Bezug zu nehmen. Dies ist eine besondere Herausforderung für standardisierte Fragen, die solche Verweise für beliebige Anwendungsbereiche flexibel zulassen müssen.

Vollständigkeit der Nachrichtentypen

Welche Typen von Nachrichten braucht es überhaupt?

Conversation Policies

Wie hängen die einzelnen Äusserungen als Konversation zusammen? Was ist die semantische Basiseinheit, die Konversation oder der Speech Act? CP braucht es, weil es auf der Ebene isolierter Äusserungen viel zu viele Interpretationsmöglichkeiten gibt (z.B. ist eine Feststellung nun wirklich eine Feststellung oder eher eine Frage?) und damit die Agenten bei der Interpretation schnell überfordert sind..

Taskmodell und Dialogmodell

Elio et al. (2000) und Nodine & Unruh (2000) gehen beide davon aus, dass Sinn macht, den ganzen Ablauf eines Kooperation mehrerer Agenten durch zwei „Modelle“ zu steuern: Das Taskmodell und das Dialogmodell. Diese Modelle sind Vorgaben, wie die Interaktion und Kommunikation abzulaufen hat. Das Taskmodell steuert übergreifend das Vorgehen zum Lösen eines bestimmten Aufgabentyps. Einzelne Dialogmodelle kommen zum Zug, wenn im Verlauf der Bearbeitung der Aufgabe Kommunikation zur Koordination, zum Austausch von Informationen etc. notwendig wird. (In der Sprache von Problemlösen zu zweit wäre des Taskmodell durch die Kooperationsregeln gegeben, die Dialogmodelle durch die einzelnen Zirkel).

Elio et al. (2000) bezeichnen gehen vom Bild aus, dass sie die Agenten in zwei „Problemräumen“ bewegen, dem Problemraum des Task und darin eingebettet jeweils dem Problemraum eines bestimmten Dialogs. Stockungen im Ablauf am einen oder anderen Ort führt zu einem Wechsel. An einer bestimmten Stelle im Task kann es notwendig sein, den Dialog anzuwerfen (z.B. Fragen stelle). An bestimmten Stellen im Dialog (z.B. wenn Frage nicht beantwortet werden kann) wird es notwendig, am Task weiterzuarbeiten. (Entspricht beim Problemlösen zu zweit dem über Frage/Antwort-Verbindungen zusammengehängte Suchbaum.) Ihr Ziel: „It is possible to define conversation policies, such as communication or dialogue protocols, that are based strictly on what messages and, respectively, what performatives may follow each other. While such an approach has many practical applications, such protocols support only „local coherence“ in a conversation. In a mixed-initiative dialogue between two agents cooperating on some joint task, there must be a ‚global coherence‘ in both the conversation and in the task they are trying to accomplish. Recognition of agent intentions about the joint task is essential for this global coherence, but there are further mechanisms needed to ensure that both local and global coherence are jointly maintained.“

Als Konsequenz davon sind die Dialogmodelle relativ kompakt und auf spezifische Gegebenheiten zugeschnitten und bilden einen modularen Baukasten.

Nodine & Unruh (2000) beschreiben einen möglichen Baukasten im Detail. Jedes Element ist ein kleines ATN. Als fundamentale Grundeinheiten, die auch für W.U.S. wichtig sind, sehen sie:

  1. a > tell > b
  2. a > tell > b > reply > a
  3. a > ask > b > reply > a
  4. a > * > (b, c, d, …) („multicast“, gleichzeitig mehrere gezielt ansprechen)
  5. a > * > * („broadcast“, Alle ansprechen, die es hören)
  6. a > ask > b > ask > c > reply > b > reply > a („forwarding“, Frage weiterleiten)
  7. a > ask > b > propose(c) > a > ask > c („delegation“, anderen Gesprächspartner vorschlagen)

(3 entspricht dem Frage-Antwort-Zyklus aus Problemlösen zu zweit; der Frage-Gegenfrage-Zyklus wäre ein zweites 3 an ein 3 angehängt, nachdem ein paar Schritte im Taskmodell absolviert wurden)

Man kann diese Abläufe mehr oder weniger robust gegenüber Fehler machen. Wird z.B. ein „ask“ von b an eine c weitergeleitet, ist es hilfreich, wenn sowohl a wie c darüber informierte werden, dass b nur Zwischenträger spielt. Fällt etwa b aus, können dann a und c direkt miteinander in Kontakt treten. Treten bei einem dieser Abläufe Probleme auf, wird die entsprechende Grundeinheiten adhoc durch bestimmte vordefinierte Erweiterungsmöglichkeiten ergänzt:

  1. discard: Aussteigen und sich abmelden ab beliebigem Knoten
  2. error: Fehlermeldung an alle Beteiligten ab beliebigem Knoten

(b kommt dem Frage-Verständnisgegenfrage-Zyklus aus Problemlösen zu zweit nahe)

Als weitere Elemente führen sie noch:

  • subscribe
  • periodic

Soweit sich das aus den graphischen Darstellungen der ATNs ablesen lässt, geht es dabei um den Wunsch von a an b, kontinuierlich über etwas auf dem Laufenden gehalten zu werden.

Damit erhalten Nodine & Unruh (2000) einen recht flexiblen Baukasten. In ihren eigenen Worten: „In this paper, our basic conversation policies define only correct operation. We have implemented a mechanism for composing a conversation with an appropriate extension when deviant or unforeseen events happen that affect the conversation. Examples of extension include errors, discards, and delegation. We also support a notion of composing different basic conversations together into a more complex conversation using concatenation. This allows us, for instance, to do negotiated asks, achieves, tells, etc. It also allows us to do a standby with respect to some other conversation, such as an ask. Both extension and concatenation can be described formally, based on the underlying nite-state representation of the conversation.“

Greaves, Holmback, & Bradshaw (2000) gehen auch davon aus, dass die Dialoge von relativ modularen „conversation policies“ gesteuert werden. Ihre Elemente sind aber nicht in ein übergreifendes Taskmodell eingebettet und sehen dann auch entsprechend anders aus:

  • CP für Turn Taking
  • CP für „zum Ende kommen“
  • CP für „Empfangsbestätigungen“
  • CP für Problembehandlungen

Solche CPs können mehrere gleichzeitig aktiv sein und aus ihnen ergeben sich „computational models“ (Dialogmodelle ?), die den Ablauf steuern. Diese können in den einzelnen Agenten mit ganz unterschiedlichen Methoden implementiert sein, solange die nur miteinander interagieren können.

Den aktuellen Wissensstand kommunizieren

Eine etwas technischer, aber interessanter Vorschlag zur Frage, wie denn Agenten, die gemeinsam an einem Problem arbeiten, sich über den aktuellen Wissensstand informieren könnten, findet sich bei Davies & Edwards (1997). Sie gehen von Agenten aus, die mit Hilfe des Version Space Algorithmus (Mitchell) arbeiten. Anstelle bei Bedarf einem Partner die gerade wahrscheinlichste Hypothese mitzuteilen, könnte es nützlich sein, gerade den ganzen noch offenen Version Space darzustellen, d.h. je die Menge der spezifischsten und der allgemeinsten noch möglichen Hypothesen.

Literatur

  • Davies, W. & Edwards, P. (1997). The Communication of Inductive Inferences. In: Weiss, G.: Distributed Artificial Intelligence Meets Machine Learning: Learning in Multi-Agent Environments. Lecture Notes in Computer Science, Artificial Intelligence. Berlin, Springer. 1237: 221-241.
  • Dignum, F. & Greaves, M. (2000). Issues in Agent Communication: An Introduction. In: Dignum, F. & Greaves, M.: Issues in agent communication. Lecture Notes in Artifical Intelligence. 1916. Berlin, Springer: 1-16.
  • Dignum, F. & Greaves, M., Eds. (2000). Issues in agent communication. Lecture Notes in Artifical Intelligence. 1916. Berlin, Springer.
  • Dignum, F., Dunin-Keplicz, B. & Verbrugge, R. (2000). Dialogue in Team Formation. In: Dignum, F. & Greaves, M.: Issues in agent communication. Lecture Notes in Artifical Intelligence. Berlin, Springer: 264-280.
  • Elio, R., Haddadi, A. & Singh, A. (2000). Task Models, Intentions, and Agent Conversation Policies.: Proceedings of the Pacific Rim Conference on AI (PRICAI-2000). Lecture Notes in Artificial Intelligence. 1886. Berlin, Springer: 394-403.
  • Greaves, M., Holmback, H. & Bradshaw, J. (2000). What is a Conversation Policy? In: Dignum, F. & Greaves, M.: Issues in agent communication. Lecture Notes in Artifical Intelligence. Berlin, Springer: 118-131.
  • Nodine, M. H. & Unruh, A. (2000). Constructing Robust Conversation Policies in Dynamic Agent Communities. In: Dignum, F. & Greaves, M.: Agent Communication. Lecture Notes in Artifical Intelligence. 1916. Berlin, Springer: 205-219.
  • Wagner, T., Benyo, B., Lesser, V. & Xuan, P. (2000). Inverstigating Interactions between Agent Conversations and Agent Control Components. In: Dignum, F. & Greaves, M.: Agent Communication. Lecture Notes in Artifical Intelligence. 1916. Berlin, Springer: 314-330.