Verteilte Künstliche Intelligenz - Uni Ulm WS95/96
4 Intention - Zur Theorie deliberativer Agenten
Janine took her umbrella
because she believed it was going to rain.
Startpunkt ist die Interpretation eines Agenten als einer Entität, deren Wahrnehmungen, Denken und Handlungen von Glauben, Wünsche etc. beeinflußt werden. Dennet bezeichnet solche Systeme als intentionale Systeme.
* Ein Anthromorphismus
* Possible World Semanik + Modale Logik
* Alternativen
Literatur: Fitting M.: Basic Modal Logic. In Handbook of Logic in AI, Genesereth M.R., Nilsson N.J.: Logical Foundations of Artificial Intelligence. Morgan Kaufman, Los Altos, 1987. Konolige K.: A Deduction Model of Belief. Research Notes in Artificial Intelligence, Morgan Kaufman, Los Altos, 1986.
4.1 Ein Anthropomorphismus
"A first order intentional system has beliefs and desires (etc.) but no beliefs and desires about beliefs and desires. .. A second-order intentional system is more sophisticated; it has beliefs and desires (..) about beliefs and desires (and other intentional states) - both those of others and its own"
Dennet 1987
"To ascribe beliefs, free will, intentions, consciousness, abilities, or wants to a machine is legitimate when such an ascription expresses the same information about the machine that it expresses about a person. It is useful when the ascription helps us understand the structure of the machine, its past or future behavior, or how to repair or improve it.
It is perhaps never logically required even for humans.."
McCarthy 1978
"it is perfectly coherent to treat a light switch as a (very cooperative) agent with the capability of transmitting current at will, who invariably transmits current when it believes that we want it transmitted and not otherwise; flicking the switch is simply our way of communicating our desires"
".... it does not buy us anything, since we essentially understand the mechanism sufficiently to have a simpler, mechanistic description of its behavior"
Shoham 1990
4.2 Repräsentation von Intention
Janine believes Cronos is the father of Zeus.
Genesereth/Nilsson 1987
Versuch einer Übersetzung in Prädikatenlogik erster Ordnung (FOP)
* Bel (Janine, Father(Zeus, Cronos))
Problem 1 (Syntaktisch): Father(Zeus, Cronos) ist eine FOP Formel und ist daher kein Term, d.h. der Ausdruck ist keine "well formed formula" der klassischen Prädikatenlogik erster Ordnung
Problem2 (Semantisch): Zeus und Jupiter sind zwei Namen für die gleiche Gottheit, es gilt also
* Zeus = Jupiter
aber gilt auch:
* Bel (Janine, Father(Jupiter, Cronos))
Problem von opaken Kontexten, die die Standardsubstitution der FOP nicht erlaubt.
* Janine believes p
Die Wahrheit obiger Aussage hängt nicht nur vom Wahrheitswert p ab.
Repräsentation von Glauben und Wissen beinhaltet
Wahl der Sprache:
* modale Sprachen, welche modale Operatoren vom Typ "non-truth-functional" beinhalten, welche auf Formeln angewendet werden.
* eine Metasprache: eine many-sorted Sprache erster Ordnung, welche Formeln einer anderen Objektsprache denotiert.
Wahl des semantischen Modells:
* possible-world Semantik
Glauben, Wissen etc. werden als Mengen von möglichen Welten repräsentiert mit einer Erreichbarkeitsrelation zwischen ihnen
* sentential oder interpreted symbolic structures
Glauben, Wissen etc. werden als symbolische Formeln explizit in einer Datenstruktur repräsentiert, die mit dem Agenten assoziiert ist.
4.3 Possible World Semantik
Basierend auf der Arbeit von Hintikka, 1962 und Kripke, 1963.
Scenario Kartenspiel
(nach Halpern 1987)Wir spielen Pocker, je mehr ein Spieler über die Karten der anderen weiß, desto besser wird er spielen. Vollständiges Wissen über die Karten der anderen ist jedoch ausgeschlossen (falls alle Spieler ehrlich spielen). Nehmen wir an, ein Spieler besitzt 4 Asse und überlegt nun, welche Karten möglicherweise seine Mitspieler besitzen. Dazu berechnet er alle möglichen Kombinationen, in welcher die Karten unter den Spielern verteilt werden. Jede Konfiguration wird getrennt auf einem Blatt notiert. Nun kann unser Spieler anfangen, diejenigen Konfigurationen, die nicht möglich sind (basierend auf dem aktuellen Wissen, hier all diejenigen in denen er nicht 4 Asse hat), auszusortieren. Jedes dieser Blätter repräsentiert eine Welt. Epistemische Alternativen (Hintikka 62) sind die Welten, die basierend auf dem aktuellen Wissen des Agenten möglich sind. Das, was in allen Welten wahr ist, wird vom Agenten geglaubt.
Vorteile dieses Ansatzes:
* die "possible world semantik" ist unabhängig von der kognitiven Struktur des Agenten
* mit der Formalisierung von möglichen Welten ist eine ausgereifte mathematische Theorie verbunden
Wie lassen sich diese möglichen Welten in eine Logik integrieren?
Epistemische Logiken (vgl. Vorlesung Nicht Standard Logiken) bauen im allgemeinen auf der Kripkesemantik auf und bilden eine Erweiterung der Aussagenlogik durch die Operatoren 
(box, notwendig)
(diamond, möglich).
Syntax:
Sei Prop = {p, q, ...} eine Menge abzählbarer atomarer Aussagen, dann ist die Syntax einer normalen propositionalen Modallogik gegeben durch:
* falls p
* wenn p und q Formeln sind dann sind auch ¬p und p & q Formeln
* wenn p eine Formel ist, so sind auch
p Formeln
Semantik
Ein Modell für eine normale propositionale Modalle Logik ist ein Triple: <W,R,µ> , wobei W eine nichtleere Menge von Welten bezeichnet und R eine Erreichbarkeitsrelation zwischen den Welten beschreibt ( R Teilmenge von W x W) und µ als Auswertungsfunktion (µ: W -> 2^Prop) angibt, welche atomaren Aussagen in der Welt wahr sind.
Die Semantik der modalen Operatoren wird über die Erreichbarkeitsrelation R
zwischen den Welten definiert, eine Formel p ist dann wahr, wenn p in jeder Welt, die von der aktuellen Welt
aus erreicht werden kann, wahr ist. Eine Formel
<M,w> 
p iff forall w' in W
: if (w,w') in R then <M,w'> p
<M,w> p iff exists w' in W: if (w,w') in R then <M,w'> p
Es gilt:
p <=> ¬p und p <=> ¬¬p
Eigenschaften der standard Modallogik:
(p => q) => (p => q)
Axiom K nach Krippke
Ausserdem gilt die Notwendigkeitsregel, die besagt, daß wenn
j gültig ist, dann auch j gültig ist. if
j
A weiß P ist sich jedoch über Q nicht im Klaren.
Axiome reflektieren bestimmte Eigenschaften der Erreichbarkeitsrelation R, die zwischen den Welten definiert ist, z.B.:
|
reflexive Erreichbarkeitsrelation (T) |
|
serielle Erreichbarkeitsrelation (D) |
|
transitive Erreichbarkeitsrelation 4 |
|
Euklidische Erreichbarkeitsrelation 5 |
(einige Systeme haben spezielle Namen erhalten: KT4 entspricht "S4", KT5 "S5" und KD45 "schwachem S5")
Wie lassen sich die Axiome D, T, 4 und 5 aus Sicht der Agenten interpretieren?
|
Ki p => p |
das was i weiß ist wahr. (unterscheidet Wissen vom Glauben: Wissensaxiom) |
|
Ki p => ¬Ki¬ p |
wenn i p glaubt, dann glaubt i nicht ¬p |
|
Ki p => Ki Ki p |
i weiß, was es weiß. (positive Introspektion, weniger fordernd als:) |
|
¬ Ki ¬p => Ki¬Ki¬ p |
i weiß, was es nicht weiß. (negative Introspektion) |
"KTD45" wird häufig als eine Logik des (idealisierten) Wissens und "KD45" als eine Logik des (idealisierten) Glaubens eingesetzt.
Ausserdem gilt die Notwendigkeitsregel, die besagt, daß wenn
p gültig ist, dann auch p gültig ist.
Mehrere Agenten
Die bisher entwickelte Logik bezieht sich auf nur einen Agenten, um das Wissen mehrerer Agenten abzubilden, werden indizierte Relationen eingeführt, eine (R
i) für jeden Agenten i :<W,R1,R2,...Rn,µ>. Der modale Operator wird ersetzt durch die Operatoren Ki , deren
Bedeutung analog zu definiert wird.
Ki p heißt: Agent i weiß, daß p
gilt.
<M,w>
p
Agent B weiß, daß Agent A P weiß.
Bsp.: Puzzle der weisen Männer (Frauen????)
* A weiß, daß wenn A keinen weißen Fleck hat, B es weiß.
* A weiß, daß B weiß, daß wenigstens einer einen weißen Fleck hat.
* A weiß, daß B nicht weiß, ob B einen weißen Fleck hat.
1) KA(¬White(A) => KB(¬White(A)))
2) KA(KB(¬White(A) => White(B)))
3) KA(¬KB(White(B)))
4) ¬White(A) => KB(¬White(A)) (1 und Wissensaxiom)
5) KB(¬White(A) => White(B)) (2 und Wissensaxiom)
6) KB(¬White(A)) => KB(White(B)) (5 und Kripke)
7) ¬White(A) => KB(White(B)) (4 und 6)
8) ¬ KB(White(B)) => White(A) (Kontraposition von 7)
9) KA(¬ KB(White(B)) => White(A)) (Notwendigkeitsregel, 8)
10) KA(¬ KB(White(B))) => KA(White(A)) (Kripke, 9)
11) KA(White(A)) (3 und 10, MP)
Wie gut eignet sich nun eine solche Logik das Wissen und den Glauben von Agenten darzustellen?
* if
Ki p
Die "necessitation rule" sagt uns, daß ein Agent alle gültigen Formeln kennen sollte, dies würde auch alle Tautologien der Aussagenlogik beinhalten
*Ki(p => q) => (Ki p => Ki q)
gemeinsam mit der Notwendigkeitsregel führt zu folgender Inferenzregel:
p => q then Ki p => Ki q
d.h. Agenten wissen alle Aussagenlogischen Konsequenzen, die sich aus seinem Wissen ergeben,
+ beides ist kontraintuitiv zur Modellierung von Agenten, deren Ressourcen endlich sind, Problem der "logischen Allwissenheit" (logical omniscience)
Weitere Probleme
* Konsistenz und Inkonsistenz
Menschliche Agenten arbeiten häufig mit inkonsistentem Wissen: Sie glauben
¬q, für künstliche Agenten (nach obiger Formel gilt), sie können nur inkonsistenten Glauben haben, wenn sie an alles glauben, was in der Sprache ausgedrückt werden kann.
* Äquivalenz von Glauben, Wissen und Aussagen
ein Agent X glaubt
"Any one of these problems might cause one to reject a possilble world formalization as unintuitive at best and completely unrealistic at worst. "
Levesque 84
Offensichtlichen Probleme der "possible world semantik" für Agentensysteme führt zu einer Reihe von alternativen Logikentwürfen, die eine Veränderung oder eine Abwendung von der "possible world semantik" bedeuten.
Einschub: Gemeinsames und verteiltes Wissen in der "Possible World Semantik"
p: es regnet in Tucson.
(M, w1) p & ¬ K1 p & K2 p &
K(K2 p | K2 ¬ p) & ¬K2(¬K1 p)
Gemeinsames Wissen
(M, w)
Ki p
für alle i in G
Verteiltes Wissen
(M, w)
p
für alle wi mit (w,wi ) in 
Ki
4.4 Alternativen zur logischen Allwissenheit?
Die logische Allwissenheit drückt sich aus:
* Wissen der gültigen Formeln: falls
* Geschlossen unter logischer Implikation: wenn Agent i
p weiß und p impliziert q dann weiß auch Agent i q* Geschlossen unter logischer Äquivalence, wenn Agent i
p weiß und wenn p und q logisch äquivalent sind, dann weiß Agent i auch q
Erste Alternative: Explizite Repräsentation von Wissen
Die Definition von Wissen als Wahrheit in allen für einen Agenten erreichbaren und damit möglichen Welten wird aufgegeben. Es ändert sich die Definition von Wissen. Das Wissen jedes Agenten wird in einer lokalen Datenbasis gespeichert.
Ein syntaktischer Ansatz:
Die Wahrheitsbelegung µ wird durch eine syntaktische Zuordnung sigma ersetzt, die einzelnen Formeln oder True und False zuordnet.
(M, s) p iff sigma(s)(p) = true.
Folgen, z.B.
* Ein Agent muß nicht mehr alle gültigen Formeln wissen, da es keine Notwendigkeit gibt, daß die syntaktische Zuordnung den Wert true Formeln der Form Ki (p) - mit p als allgemeingültiger Formel - zuweist.
* Ein Agent kann Widersprüchliches wissen, da ohne weitere Einschränkungen (z.B. um gewissen logische Standards zu garantieren), die Zuordnung true zu Ki(p) und Ki(¬p) möglich ist.
"in fact knowledge in syntactiv structures
does not have any interesting properties"
Um Wissen anstelle von Glauben zu modellieren, muß folgendes gefordert werden:
Ki p => p, sigma(s)(p)=true immer wenn sigma(s)(KI p) = true
Syntaktische Strukturen können zur Modellierung von realistischen Situationen genutzt werden:
Für jeden Agenten i gibt es eine Menge von Inferenzregeln Ri und für jeden Zustand s gibt es seine Menge von Fakten Bi(s), die Basismenge von Formeln, so daß sigma(s)(Kip) = true iff p kann von Bi(s) abgeleitet werden.
z.B. kann ein Schüler wissen, daß x + a = b aber anhand des Wissens, x = b - a nicht ableiten, da die Regel des Ableitens gleicher Quantitäten von beiden Seiten ihm nicht bekannt ist, in diesem Fall, wäre sigma(s)(Ki (x + a = b)) = true und sigma(s)(Ki (x = b - a)) = false
Bsp. Deduktionsmodell von Konolige.
Andere Möglichkeiten:
* nicht standard Aussagenlogik, p & ¬p => everything
(Idee p und ¬p haben unabhängige Wahrheitswerte, zwei Basen eine für wahre und eine für falsche Aussagen.
* Veränderung des Wesens von Welten, z.B. durch unmögliche Welten, in denen die üblichen Logikregeln nicht gelten. z.B. p und q sind wahr in einer Welt aber p Ÿ q ist nicht wahr in der Welt. Unmögliche Welten werden betrachtet, wenn ein Agent sein Wissen bestimmen will, die Implikationen basieren jedoch nur auf den möglichen Welten.
* Explizites (X) und Implizites Wissen (K) - über eine Bewußtseinsdefinition, die syntaktischer Art ist (A), z.B. Xi(p) <=> Ki(p) & Ai(p); von p schließe Ai(p) => Xi(p)
* Frames of Mind: unterschiedliche Welten sind möglich je nachdem, in welcher "Gemütslage" sich der Agent befindet, inkonsistentes Wissen wird möglich.
4.5 Zusammenfassend
Die Semantik von Wissen in Form der Kripke Semantik ist für viele Bereiche adequat und nützlich, ein Problem: die logische Allwissenheit und die geforderte Konsistenz des Wissens
Unterschiedliche Ansätze, die sich diesem Problem widmen, unter Beibehaltung der Welten oder der Definition von Wissen:
* Der Ansatz, der eine nicht Standard Aussagenlogik zugrundelegt, -> Agenten wissen alle logischen Konsequenzen
* Der Ansatz der unmöglichen Welten, Wir, die Konstrukteure des Schlußfolgerungssystems wissen um die logischen Gesetzmäßigkeiten der Welten, nur der Agent zeigt unlogische Einschätzungen.
* Der Bewußtseins Ansatz, kann ein Agent etwas Wissen, ohne sich diesem Etwas bewußt zu sein?
* Eine Gesellschaft von Agenten, die jeder eine andere Sicht der Dinge repräsentieren
Eine Kombination unterschiedlicher Ansätze, z.B. Bewußtsein, Gesellschaft von Agenten und zuzüglich Zeit kann zu folgendem Axiom führen:
(¬(Xi(p) & Xi
(¬p)))