Verteilte Künstliche Intelligenz - Uni Ulm WS95/96

6 Kooperation mit Kommunikation

"By definition an agent in a DAI system is social, it exists in an environment containing other agents, with which it will generally be expected to interact in some way."

Wooldridge, 1992

 

* Information und Kommunikation

* Speech Acts - Kommunikation als Aktion

* Eine planbasierte Theorie von Sprechakten

* Rationale Interaktion und Kommunikation

* Nicht monotones Schließen, Belief Revision, und Sprechakte: Ein paar Ideen

* Das Projekt DARPA - KIF

* Verhandlungen

* Contractnet Protocol

Literatur: Weingarten R., 1990: Information ohne Kommunikation? Fischer Sachbuch, Frankfurt. Cohen P.R., Morgan J. and Pollack M.E. (eds.), 1990: Intentions in Communication. MIT Press, Cambridge.


6.1 Motivation

 

Ein Ziel

* Koordination - Sicherstellen, daß die Aktionen von verschiedenen Agenten nicht in Konflikt zu einander stehen.

* Kohärenz - das Verhalten des Gesamtsystems ist befriedigend

Problem

* Agenten besitzen nur partielles Wissen

Idee

* Weitere Information durch Kommunikation

"informatio" in der antiken Philosophie:

* die Tätigkeit des Erkenntnissubjektes (Formung, Abbildung: Subjekt-Objekt)

* die äußere Informationsquelle (Lehre und Unterweisung als Diskurs: Subjekt-Subjekt)

* die in der Nachricht verobjektivierte Erkenntnis (Bericht, Kundschaft: Information unabhängig von einem handelnden Subjekt)

 

Probleme der Kommunikation oder der Umgang mit Zeichen (Semiotik)

 

Kratylos Dialog bei Platon:

"wenn ich dieses Wort ausspreche und dabei jenes denke, wie ist es dann überhaupt möglich, daß du erkennst, daß ich jenes denke"

 

Till Eulenspiegel:

"Was Ihr denkt, das weiß ich nicht, wie kann einer des anderen Gedanken erraten! Aber was Ihr mir gesagt habt, das weiß ich"

 

Ludwig Wittgenstein:

"Wenn man aber sagt, wie soll ich wissen, was er meint, ich sehe ja nur seine Zeichen, so sage ich, wie soll er wissen, was er meint, er hat ja nur seine Zeichen"

 

Die "einfache" Variante:

Kommunikation ist wie der Transport von Gütern (Conduit Metapher)

 

"zunächst impliziert sie, daß sich Gedanken, Gefühle und Bedeutungen fertig vorfabriziert in unserem Personen-Behälter befinden, die wir nur noch in Worte fassen und absenden müssen. Nicht ins Blickfeld tritt, was Kleist die allmähliche verfertigung der Gedanken beim Reden genannt hat (...). In der Conduit Methapher werden Gedanken, Bedeutungen usw. zu Objekten reifiziert. Worte und Sätze haben dann Bedeutungen, die unabhängig von Kontexten, von Wissen und Interessen der Interaktanten sind. Die Aufgabe des Höreres besteht daher lediglich darin, aus den Wort-Behältern die Bedeutungen wieder herauszunehmen, die der Sprecher in sie hineingelegt hat (...). Die Conduit Metapher legt einen Verständigungserfolg ohne Anstrengung nahe und begünstigt die vorschnelle Überzeugung, verstanden zu haben bzw. verstanden worden zu sein (....). "

 

Brünner, 1987 (Metaphern für Sprache und Kommunikation im Alltag und Wissenschaft. Diskussion Deutsch 94, 18. Jahrgang, 100-119.)

 

Die Conduitmetapher paßt nach Johnson und Lakoff (Metaphor and Communication, Trier: L.A.U.T. Series A, Paper No. 97, 1982) auf folgende Situationen:

 

1) The participants are equally competent speakers of the same dialect of the same language, and the individual variation is insignificant.

2) Relevant to the subject matter and the context, the participants share

* the same cultural assumptions

* the same relevant knowledge of the world

* the same relevant background assumptions about the context of the utterance

* the same understanding of what the conversation is about and

* the same relevant conceptual metaphors and folk theories

 

Konzeptualisierung von Kommunikation

* Kommunikation als zweckrationaler Austausch von Informationen mittels Zeichen

* Kommunikation als gemeinsame Konstruktion und Aushandlung von Sachverhalten und sozialer Wirklichkeit

* Kommunikation als Konstitution und Regulation sozialer Beziehungen

* Kommunikation als sprachliches Handeln

* Kommunikation als verbale Verständigung

* Kommunikation als geglückte Verständigung

 

im folgenden primär: Kommunikation

* als zweckrationaler Austausch von Information: Pläne, Ergebnisse, Synchronisationssignalen ......

* Conduit Metapher

* als Aktion

 

Arten von Kommunikation zwischen künstlichen Agenten:
nach Werner 1990

* Keine (direkte) Kommunikation - Entscheidungstheorie, oder jeder weiß um des anderen Plans, oder Blackboardarchitektur, d.h. keine direkte Kommunikation.

* Signale - z.B. in Form von Semaphoren (vgl. verteilte Systeme)

* Berechnung als Senden von Nachrichten - ACTOR Modell

* Austausch von Plänen - Partielle, globale Planung

* Speech Acts - Kommunikation als Aktion

 


6.2 Speech Acts

Austin 1962 - How to Do Things with Words.

* Pragmatische linguistische Theorie, im Kern des Interesses der Gebrauch von Sprache nicht das Wesen von Sprache

* Kommunikation als Aktion, d.h. Aktion mit Intention, Verändern den Zustand der Welt,

* Äußerungen sind nur in einem bestimmten Kontext erlaubt und verändern diesen Kontext

Sei L die Menge an möglichen Äußerungen in einer Sprache und sei C die Menge der möglichen Kontexte:

Pragmatische Theorie: L x C -> C

Als Kontexte werden im allgemeinen der mentale Zustand des Agenten angenommen, d.h. Glauben, Wünsche, Intentionen.

 

Sätze drücken nicht nur ein Faktum aus, sondern führen eine Aktion aus. (performatives nach Austin)

 

Unterscheidung in:

* Lokutionäre Sprechakt : Syntaktisch Akzeptierbare Sätze (im Hinblick auf Artikulation, Konstruktion der Aussage)

* Illokutionäre Sprechakt : Request, Inform, Insist, State, Demand, and Argue (im Hinblick auf kommunikative Funktion)

* Perlokutionärer Sprechakt : Direkter Effekt auf den Empfänger (im Hinblick auf die Konsequenzen der Sprechhandlung)

Kommunikation kann genauso wie eine Aktion fehlschlagen.

 

Weiterentwicklung durch Searle

Speech Acts by John Searle 1969

* Konversation in einer Sprache ist eine regel-geleitetes Verhalten

* Definition von notwendigen und hinreichenden Bedingungen für eine geglückte Kommunikation

z.B. die Bedingungen für eine erfolgreiche Durchführung einer Request Aktion. Ein Sprecher äußert einen Satz, der eine Aufforderung an den Hörer enthält, eine bestimmte Aktion auszuführen.

* Normal I/O Conditions: d.h. der Hörer ist physisch in der Lage die Aufforderung wahrzunehmen, sie findet in einer normalen Umgebung statt (d.h. nicht im Film, Show etc.)

* Preparatory Conditions - Bedingungen an die Welt, um eine bestimmte Aktion auszuwählen, z.B. muß der Sprecher glauben, daß der Hörer in der Lage ist, der Aufforderung nachzukommen

* Sincerity Conditions - unehrlich wäre es, wenn der Sprecher die Aufforderung nicht ernst meint

* Essential Conditions - die Aktion des Sprechers war darauf gerichtet, den Hörer dazu zu bringen, eine bestimmte Aktion auszuführen.

 

Eine Strukturierung der illokutionären Sprechakte nach Searle:

* Representatives - Ein solcher Sprechakt verpflichtet den Sprecher an die Wahrheit einer Aussage - z.B. Assert ,

* Directives - Ein direkter Versuch den Hörer zu einer Aktion zu veranlassen, z.B. Request ,

* Commissives - Verpflichtet den Sprecher zu einer Reihe von Handlungen, z.B. Promising ,

* Expressives - Drücken den phsychologischen Zustand des Sprechers aus, z.B. Thanking,

* Declarations - beeinflußen die institutionellen Beziehungen der Gesprächspartner, z.B. Declare War.


6.3 A Plan-Based Theory of Speech Acts

Literatur: Cohen P.R., and Perrault C.R., 1979: Elements of a Plan Based Theory of Speech Act. Cognitive Science, 3:177-212.

 

Sprechakte als Operatoren in Plänen:

"By modelling them in a planning system as operators defined .. in terms of speakers' and hearers' beliefs and goals. Thus, speech acts are treated in the same way as physical actions".

 

Kontext der Sprechakte: Mentale Zustand der Teilnehmer (in Form von Beliefs, Desires, Intentions ....)

 

 

Request (S, H, a)

Preconditions Cando.pr (S Believe (H CANDO a))
(S Believe (H BELIEVE (H CANDO
a))

Want.pr (S Believe (S WANT request-instance))
Effect (H Believe (S BELIEVE (S WANT
a))

Cause-to-Want (A1, A2, a)

Preconditions Cando.pr (A1 BELIEVE (A2 BELIEVE (A2 WANT a))
Want.pr
-
Effect (A1 BELIEVE (A1 WANT a))

 

Inform (S, H, f)

Preconditions Cando.pr (S BELIEVE f)
Want.pr (S BELIEVE (S WANT inform-instance
))
Effect (H BELIEVE (S BELIEVE f))

 

Convince (A1, A2, f)

Preconditions Cando.pr (A1 BELIEVE (A2 BELIEVE f))
Want.pr
-
Effect (A1 BELIEVE f)

 


Einige der Sprechakte lassen sich ersetzen:

* Inform (SPEAKER, HEARER, (SPEAKER WANT ACTION))

Unterscheidung in illokutionäre und perlokutionäre Sprechakte.

Kritik: Es ist sehr unwahrscheinlich, daß Menschen, bevor sie eine Aussage verstehen, sie zunächst nach ihrem illokutionären Aspekt klassifizieren.


6.4 Rationale Interaktion und Kommunikation

Literatur: Cohen P.R. and Levesque H.J., 1990: Rational Interaction as the Basis for Communication. In: Cohen P.R., Morgan J. and Pollack M.E. (eds): Intentions in Communication. MIT Press, Cambridge, 221-256.

 

* die Identifikation der illokutionären Aspekte ist unnötig

"What speakers and hearers have to do is only recognize each others intentions (based on mutual beliefs). We do not require that those intentions include intentions that the hearer recognize precisely what illocutionary acts were being performed"

* Illokutionäre Sprechakte sind komplexe Aktionen keine Basisaktionen

* Eigenschaften illokutionärer Sprechakte können durch Rationälität erklärt werden

Problem der Identifikation von Aktionen, eine Aktion oder mehrere ?

z.B. das Gavrilo Prinzip 1914 (nach Searle), "simultaneously pulling a trigger, firing a gun, killing Archduke Ferdinand and starting World War I."

Idee: Unterscheidung zwischen Ereignissen und der Beschreibung, Kommunikation von Ereignissen

 

 

Bsp.: Die Definition von einer Anforderung (Request).

Alternating belief (alternierender Glaube):

(ABEL n x y p) = (BEL x (BEL y (BEL x ... (BEL x p) ...)))

Mutual belief (gegenseitiger Glaube):

(BMB x y p) = " n (ABEL n x y p)

Attempt (Versuch, Bemühung):

Ein Versuch ist eine komplexe Aktion, die ein Agent ausführt, wenn sie etwas (e) tut, mit dem Wunsch einen bestimmten Effekt (p) zu erwirken oder wenigstens (q) als Nebeneffekt zu erreichen.

 

(HELPFUL x y):= [( (BEL x (GOAL y (DONE x e))) &
¬(GOAL x ¬(DONE x e)) )
]
=> (GOAL x (DONE x e))

Ein Agent ist hilfreich gegenüber einem anderen Agenten, wenn er solange es nicht seinen eigenen Zielsetzungen widerspricht, die Ziele des anderen soweit sie seine eigenen Aktivitäten betreffen adaptiert.

 

{REQUEST x y e a } :=

{ATTEMPT x e f
(BMB y x (GOAL x f))}

   
 

mit f definiert als

(DONE y a) Ÿ (INTEND y a

 

   
 

((GOAL x (DONE y a)) Ÿ
(HELPFUL y x)

)

   

Eine Aufforderung ist ein Versuch seitens des Agenten (x), in dem er das Ereignis e ausführt, folgende Effekte zu erzielen nämlich daß der andere Agent (y) a intendiert (vor dem Hintergrund, daß Agent (x) es als Ziel hat, daß y a tut und y auch x gegenüber hilfreich eingestellt ist.) und auch irgendwann einmal ausführt, falls dem nicht so ist sollte wenigstens als Seiteneffekt der Wunsch der Ausführung von a durch y seitens x klar geworden sein.


6.5 Nicht-Monotones Schließen, Belief Revision und Sprechakte - Ein paar Ideen

Defaulttheorie nach Perrault

Literatur: Perrault C.R., An Application of Default logic to speech acts theory. In: P.R. Cohen, J. Morgan and M.E.Pollack (eds.): Intentions in Communication. MIT Press, 161-186.

Ein Szenario mit Kommunikationsteilnehmern kann als default Theorie repräsentiert werden (vgl. Reiter und Grundlagen der KI).

Annahme: das Wissen eines Beobachters bevor eine bestimmte Äußerung erfolgt.

Defaultregeln: Annahmen über das Szenario.

z.B.: falls Agent A glaubt, daß B f glaubt und f ist konsistent mit dem Wissen von A, dann glaubt A auch f. (A glaubt, daß f gilt, wenn B f äußert.)

Erweiterung der Default Theorie durch

* die Aussage, daß eine Äußerung getätigt wurde,

* Aussagen, die beschreiben, wer wen beobachtet

 

Jede Extension der default Theorie beschreibt eine konsistente Sicht des Beobachters über die Welt vor und nach einer bestimmten Äußerung.

 

Mit der Defaulttheorie können Lügen modelliert werden, Agent B äußert etwas woran er nicht glaubt, Agent A ist jedoch nicht in der Lage diese Lüge zu entdecken.

 

Kritik an der Defaulttheorie:

 

* durch Äußerung von bel. Fakten kommt ein Agent dazu, jede beliebige Aussage zu glauben.

* Probleme der Belief-Revision werden nicht adequat behandelt.

* Probleme bei der Integrierung in Aktionstheorien

 

HAEL (Hierarchic Autoepistemic Logic)

Literatur: D. Appelt, K. Konolige, 1988: A Nonmonotonic Logic for Reasoning about Speech Acts and Belief Revision. M.Reinfrank, J.de Kleer, M.L. Ginsberg E. Sandewall (eds.): NonMonotonic Reasoning. LNAI Volume 346, Springer Verlag, 164-175.

Idee: Aufbauend auf einer auto-epistemischen Logik (L p , d.h. ich glaube p; default: solange ich nicht ¬p glaube ...) werden Prioritäten zwischen Default Theorien angegeben. Indizierte Operatoren Li Anlegen von Evidenzräumen, mit einer irreflexiven, partiellen Ordnung. Jede Theorie erbt von der vorhergehenden Theorie.

* wenn p ein normaler Satz in ist und , dann ist p auch in

* wenn p ein normaler Satz in ist und , dann ist Li p auch in

* wenn pein normaler Satz nicht in ist und , dann ist ¬ Li p in

z.B. F(x): x fliegt, B(x): x ist ein Vogel und P(x): x ist ein Pinguin.

 

Es ergibt sich eine Hierarchie von Defaults , wobei die Defaults mit mehr Gewicht weiter unten in der Hierarchie angesiedelt werden.

 

HAEL kann für Speechacts in der folgenden Weise genutzt werden:

"assume that there is a hierarchy of autoepistiemic subtheories. The lowest subtheory t0 contains the strongest evidence about the speaker's and hearer's mental states. "(Wissen)" In the subtheorie t1 defaults are collected about the effects of the speech act on the beliefs of both speaker and hearer. These defaults can be overridden by the particular evidence of t0. At level 2, the beliefs of the speaker and hearer that can be deduced in t1 are used as evidence to guide defaults about nested beliefs..."

 

Präferenzordnung Kognitiver Zustände nach Galliers

Literatur: J.R. Galliers: A Strategic Framework for Multi-Agent Cooperative Dialogue. In: Proc. 8th ECAI, München, 1988, 415-420.

Dialogue concerns the generation and interpretation of utterances; utterances are speech actions planned to convey the information that the speaker is in a particular mental state which relates to the fact that the speaker has a goal to induce a particular mental state in the hearer.

Basierend auf dem Ansatz von Cohen und Levesque werden Präferenzen definiert, Präferenzen bilden Beziehungen zwischen Beliefs und Goals:

(Prefer x p q) := (BEL x [(BEL x (p | q)) => (GOAL x (LATER p))])

"Revision of another's cognitive state ... is the motivating force for communicative behavior. .. Strategic interaction acknowledges all participants sharing control over the effects of a communication. ... Strategic planning to achieve a desired change in another's belief states is therefore a matter of setting the goal state based upon a prediction of the context of that other agent, such that the general rulnal autonomous belief revision would then dictate the desired change anyway."

Bsp.: Für Revision

Neue Erkenntnis:


6.6 Wenn Agenten nicht die gleiche Sprache sprechen..... KIF - A Knowledge Interchange Format

Kommunikation wird von vornherein als gelingende Verständigung interpretiert, der Sprecher meint,was er sagt und der Hörer versteht, was der Sprecher zu sagen beabsichtigt. Vorraussetzung: Parallelschaltung zwischen den Akteuren

KIF - Ein DARPA Projekt (Defence Advance Research Project) hatte zum Ziel, das Wissen von wissensbasierten Systemen für andere Systeme nutzbar zu machen, Wiederverwendung von Information, ein Problem, die "Parallelschaltung" zwischen den wissensbasierten Systemen ist nicht mehr gegeben.

Das Problem der unterschiedlichen Sprachen:

Idee: Entwicklung einer Zwischensprache zur Kommunikation von Wissen

* eine formal definierte deklarative Semantik

* genügende Ausdrucksstärke

* eine Struktur, die semiautomatische Übersetzung gewährleistet

 

KIF ist eine erweiterte Prädikatenlogik erster Ordnung und ist charakterisiert u.a. durch folgende Merkmale:

 

* eine einfache listenbasierte Syntax

* Eigenschaften von Funktionen und Relationen sind ausdrückbar (z.B. transitivität, etc.)

* einer Untersprache um Domainontologien zu definieren

* Wissen über Wissen oder Glauben über Glauben ist ausdrückbar:

(=> (believes john '(material ,?x ,?y))
(beieves lisa '(material ,?x ,?y)))

* eine Subsprache zum Ausdrücken von monotonen und nicht monotonen Inferenzregeln

(<<= (flies ?x) (bird ?x) (consis (flies ?x)))

 

Weiterentwicklung und Spezialisierung von KIF: KQML
(A Knowledge Query and Manipulation Language)

ein Nachrichtenformat und eine Protokoll zum Austausch von Nachrichten zwischen Agenten:

 

Eine Menge von Features werden angeboten, die entsprechend erweitert werden können: Sie definieren die Operationen, mit denen die Agenten den Glauben und die Ziele anderer Agenten beeinflußen können.


6.7 Kommunikation und Verhandlungen

* Kommunikation nicht nur zum Informationsaustausch

Ziel von Multiagentensystemen die Bearbeitung von Problemen.

* Kommunikation als Arbeitsteilung: Illokutionär: REQUEST...., Kommunikation als Mittel zur Verhandlung über Kooperationen

Kooperation Ohne Kommunikation

* Basierend auf Spieltheorie, Payoff Matrix

* Selbstorganisation (Game of Life)

Kooperation mit Kommunikation

* Shared Memory

* Message Passing

 

Phasen eines Kooperativen Problemlöseprozesses

* Problemdekomposition
(nach Problembereich oder Agenten)

* Verteilung
(Verhandlungen, Direkte Deligierung)

* Lösung der Teilprobleme
(Konflikterkennung, Kooperation in Form von Task-Sharing, Resultsharing)

Beim Aufgabensharing wird davon ausgegangen, daß sich die Teillösungen unabhängig voneinander erstellen lassen, beim Ergebnissharing, hat die Verteilung schon stattgefunden und es geht darum den Interdependenzen Rechnung zu tragen.

* Synthese zur Gesamtlösung (Wer und wie)

 

Kooperation und Koordination als Verhandeln

 

* Multidirektionaler Informationsaustausch zwischen den Agenten

* Interpretation der Information aus der lokalen Perspektive und Abschätzen des Nutzens einer kooperativen Haltung (Hier Spieltheorie, Entscheidungstheorie, auch bezgl. zeitlicher Aspekte usw.)

* Übereinkunft nach gegenseitiger Absprache

* Dynamische Auftraggeber- und Auftragnehmerrollen der Agenten

 

 


6.8 Contract-Net Protocoll

* Dynamische Auftraggeber- und Auftragnehmerrollen der Agenten

R. Davis, R.G. Smith

 

* Speicherung des Problemspezifischen Wissens in der Datenbasis

Nebenläufig arbeiten:

* Kommunikationsprozessor: für die Kommunikation mit anderen Agenten

* der Vertragsprozessor: für die Verhandlungen mit anderen und für die Verwaltung des Zustands und der Resourcen des Agenten

* Aufgabenprozessor: für die Abwicklung der Teilaufgaben.

Contract Net

To: *

From: Willy

Type: Task Announcement

Contract-ID: 22-03-1

Task Abstraction:

Task Type Signal

Position Lat 47N Long 17E

Eligibility Specification:

Have Sensors

Must Have Position Area A

Bid Specification:

Position Lat Long

Every Sensor Name Type

Expiration Time:

28 17:30 Februar 1979

Ausschreibungsnachricht

To: Willy

From: Anton

Type: Bid

Contract-ID: 22-03-1

Node Abstraction:

Position Lat 62N Long 9W

Sensor Name: S1 Type S

Sensor Name: S2 Type S

Sensor Name: T1 Type T

Bewerbungsnachricht

To: Anton

From: Willy

Type: Award

Contract-ID: 22-03-1

Node Abstraction:

Sensor Name: S1 Type S

Sensor Name: S2 Type S

Vertragsnachricht

Verhandlungen:

* Generierung neuer Aufgaben, die an alle andern Agenten als Ausschreibungsnachricht gesendet werden,

* der generierende Agent schlüpft in die Rolle des Managers.

* Falls ein Agent den Minimalanforderungen genügt und und der Agent für die Ausführung der Arbeit geeignet ist (Task Evaluation Procedures) bewirbt er sich um den Auftrag mit einer Bewerbungsnachricht.

* Der Manager vergibt entsprechend der Klassifikation der Bewerber den Auftrag an einen Agenten und sendet ihm die Vertragsnachricht, die der Agent durch einen Bestätigungsnachricht beantwortet.

* Der ausgewählte Agent kann nun das Problem weiter zerlegen und an andere Agenten verteilen.

 

 

Zusammenfassung

* Was ist Kommunikation - Probleme des Verstehens und der Unwahrscheinlichkeit des Gelingens zwischenmenschlicher Kommunikation

* Kommunikation in künstlichen Agenten - Die Conduitmetapher - Kommunikation als Sprechakte

* Formale Ansätze zu Sprechakten Basierend auf der Logik von Cohen und Levesque , Sprechakte als den kognitiven Zustand der Agenten verändernde Aktionen (Belief, Goals ...), die mit einer bestimmten Intention ausgeführt werden

* Veränderung von kognitiven Zuständen durch Sprechakte: Frage der Revision von Wissen, Defaults und Präferenzen

* Unterschiedliche Sprachen als Kommunikationsbarieren, KIF und KQML...

* Wozu eigentlich Kommunikation? Gemeinsames Problemlösen, Kooperation, Koordination und Kommunikation: Verhandlungen zwischen künstlichen Agenten

* Contract Net motiviert von Wirtschaftstheorien - Ein Verhandlungsprotokoll

 


UP