Verteilte KI

Verteilte Künstliche Intelligenz - Uni Ulm WS95/96

5 "Theories of Agency"

Viele Formalismen beschäftigen sich nur mit einem Aspekt der Agentenmodellierung: "Belief", "Goals and Desires", "Introspection", für eine umfassendere theoretische Erarbeitung von Agenten ist es jedoch notwendig, die verschiedenen Ansätze innerhalb eines logischen Rahmen einzubetten.

* Motivation

* Moore, Cohen und Levesque, Singh, Werner

* Rao & Georgeff

* und andere

* Zusammenfassung

Literatur: M.J. Wooldridge: The Logical Modelling of computational Multi-Agent Systems. PhD Thesis, University of Manchester, Department of Computation, Technical Report MMU-DOC-94-01, 1992.

5.1 Motivation

Nicht nur die Kombination von Beliefs, Goals und Desire sondern auch die dynamischen Aspekte müssen logisch beschreibbar sein.

* wie sind Information (Beliefs) und Ziele und Wünsche miteinander verbunden?

* Wie verändert sich der kognitive Zustand eines Agenten über die Zeit?

* Wie beeinflußt die Umgebung den kognitiven Zustand eines Agenten?

* Wie beeinflussen Informationen und Einstellungen die Handlungen eines Agenten?

5.2 Ansatz von Cohen und Levesque

"rationale Balanz" zwischen Glauben, Ziele, Aktionen und Intentionen im Mittelpunkt, basierend auf einer "possible world" Semantik. es handelt sich um eine mehr-sorten, multi-modale Logik. Mit 4 modalen Operatoren:

* (BEL x p) Agent x glaubt p

* (GOAL x p) Agent x hat das Ziel p

* (HAPPENS a) Aktion a wird als Nächste durchgeführt werden

* (DONE a) Aktion a ist gerade ausgeführt worden

Diese Arbeit beeinflußte:

* Analyse und Kooperation im Multi-Agentendialog

* Theorie der kooperativen Problemlösungen

Literatur: Cohen P.R. & Levesque H.J., 1990: Intention is Choice with Commitment. Artificial Intelligence, 42: 213-261.

Intentionen stehen im Mittelpunkt (vgl. Bratman):

* Intentionen stehen am Anfang der Aktivität von Agenten, Agenten auf der Suche nach Problemlösungen für die aus ihrer Intention sich ergebenden Problemstellungen

* Intentionen filtern und adaptieren andere Intentionen

* Agenten verfolgen ihre Intentionen hartnäckig

* Agenten halten ihre Intentionen für möglich und unter bestimmten Umständen für realisierbar

* Agenten glauben nicht, daß sie ihre Intentionen nicht realisieren können.

* Agenten intendieren nicht alle "Seiteneffekte" die mit dem Erreichen ihrer Intention verbunden sind.

"a logic of rational agency" - Auf zwei Ebenen

* atomaren

"being careful to sort out the relationships among the basic modal operators. "

* molekularen

"new concepts defined out of the primitives ..., properties of communicateive acts can be derived form the embedding logic of rational interaction, whose properties are themselves grounded in rational action."

Dynamik

Neben den Operatoren DONE und HAPPENS werden weitere Operatoren genutzt, um die Struktur von Ereignissequenzen zu beschreiben, z.B.

* a;a' Ereignis a' folgt auf Ereignis a

* a? Testaktion (tritt auf, wenn a vorliegt, und löst ein leeres Ereignis aus)

Benutzt werden modalen Zeitoperatoren, z.B.:

* p := exists x: (HAPPENS x;p?)

* p := ¬¬p

* (LATER p) := ¬p & p

Auf der atomaren Ebene - Aktionen HAPPENS und DONE

Einige Eigenschaften komplexer Aktionen

(HAPPENS a;b) := (HAPPENS a; (HAPPENS b)?)

(DONE a) := (DONE (HAPPENS a)?;a)

p == (DONE p?)

Definitionen

(DONE x a) := (DONE a) & (AGT x a)

(HAPPENS x a) := (HAPPENS a) & (AGT x a)

AGT ordnet jedem Event einen Agenten zu, der als Initiator für diesen Event verantwortlich zeichnet.

Auf der atomaren Ebene - Belief

Axiome (Weak S5)

forall x (BEL x p) & (BEL x (p =>q)) => (BEL x q)

forall x (BEL x p) => (BEL x (BEL x p))

forall x ¬(BEL x p) => (BEL x ¬(BEL x p))

forall x (BEL x p) => ¬(BEL x p)

Inferenzregel

f then (BEL x f)

Wissen und Glauben

(KNOW x p) := p & (BEL x p)

Kompetenz

(COMPETENT x p) := (BEL x p) => (KNOW x p)

Kompetentes Wissen über die eigene Tat

forall x,e (AGT x e) => [(DONE e) == (BEL x (DONE e))]

Auf der atomaren Ebene - Achievement Goal

Konsistenz

forall x (GOAL x p) => ¬(GOAL x ¬p)

Achievement Goals

(A-GOAL x p) := (GOAL x (LATER p)) & (BEL x ¬p)

Keine Persistenz von Zielen - Jedes Ziel wird irgendwann aufgegeben

¬(GOAL x (LATER p))

Auf der molekularen Ebene - "Persistent Goal"

p ist ein "persistent goal" - ein andauerndes Ziel genau dann wenn:

* der Agent hat das Ziel, daß p irgendwann in der Zukunft erreicht wird, und er glaubt daß p zur Zeit noch nicht realisiert ist.

* der Agent gibt das Ziel p nur auf, falls p erreicht wurde oder falls er zu der Ansicht gekommen ist, daß p generell nicht erreichbar ist.

(P-GOAL x p) := (GOAL x (LATER p)) & (BEL x ¬p) & [BEFORE ((BEL x p) | (BEL x ¬p)) ¬(GOAL x (LATER p))]

mit (LATER p) := ¬p & p und
(BEFORE p q) := forall c (HAPPENS c;q?) => exists a: (a «= c) & (HAPPENS a;p?)

Auf der molekularen Ebene - Intention

Intention als eine bestimmte Art des persistent goal

(INTENTION x a) := (P-GOAL x [DONE x (BEL x (HAPPENS a))?; a])

Die Intention, eine Aktion a auszuführen, ist eine Art von Verpflichtung (Persistent-Goal) a ausgeführt zu haben. Es ist nicht nur eine Verpflichtung etwas zu tun, sondern die Handlung bewußt zu tun, d.h. zunächst daran zu glauben, daß er sie gleich ausführen wird und es dann auch zu tun.

Ein Modell dieses Ansatzes ist beschrieben durch:

<U,P,E,Agt,T,B,G,Pr>

* U eine Menge von Dingen (Universum)

* P ist eine Menge von Agenten

* E ist eine Menge primitiver Aktionen

* Agt: E -> P ordnet Ereignisse die verantworlichen Agenten zu

* T subset-of World ist eine Menge von Welten

* B subset-of T x P x Z x T st die Verbindungsrelation zwischen den Welten bzgl. Glauben (K45D), schwach S5

* G subset-of T x P x Z x T ist die Verbindungsrelation zwischen den Welten bzgl. der Ziele (D seriell) und G subset-of B

* Pr interpretiert die Prädikate

Die Semantik der Sprache wird über die Erfülltheitsrelation zwischen Strukturen der Form <M,sigma,v,n> und Formeln der Sprache definiert (M ist ein Modell, sigma eine Sequenz von Ereignissen, v bezeichnet die Variablenzuordnungsfunktion und n den zeitlichen Index ).

<M,sigma,v,n> (HAPPENS a) iff exists m in Z (m »= n) & <M,sigma,v,m[a]n>

<M,sigma,v,n> (DONE a) iff exists m in Z (m «= n) & <M,sigma,v,m[a]n>

<M,sigma,v,n> (BEL x a) iff forall sigma' in World <sigma, v(x),n,sigma'> in B => <M,sigma',v,n> a

<M,sigma,v,n> (GOAL x a) iff forall sigma' in World <sigma,v(x),n,sigma'> in G => <M,sigma',v,n> a

mit m[a]n bedeutet, daß a zwischen den Zeitpunkten n und m auftritt.

5.3 Ansatz von Werner

Werner definiert den kognitiven Zustand eines Agenten als Trippel:

<I,S,V>

* I als Informationszustand
eine Menge von partiellen Historien, die epistemischen Alternativen entsprechen, jede dieser Historien repräsentiert eine Art wie die Welt sich entwickelt haben kann, ausgehend davon was der Agent weiß

* S als intentionaler Zustand
eine Menge von Strategien, jede Strategie repräsentiert eine Reihenfolge von Aktionen, denen der Agent folgen kann, eine Strategie ist eine Funktion die einen Informationszustand in die Menge von Informationszuständen überführt, die aus einer Befolgung der Strategie resultieren würde

* V als Evaluierungszustand
eine Bewertungsfunktion, die Historien bestimmte utility Werte zumißt.

Literatur: Werner E., 1989: Cooperating Agents a Unified Theory of Communication and Social Structure. In: L.Gasser, and M. Huhns (eds.): Distributed Artificial Intelligence Vol. II, 3-36, San Mateo, CA.

Ein paar Bemerkungen zu CANPLAN.

* P,P1.... Eigenschaften

* Rn, Rn n-stellige Relationen für

* O eine Menge von Indiviuen.

* T eine Menge von Zeitpunkten geordnet durch die Relation <.

* TP eine Menge von Zeitperioden.

Eine Situation s ist eine Menge von Objekten in O, welche bestimmte Eigenschaften P haben und in der Relation Rn zueinander stehen, z.B.

S = {Pa;yes. Qa;no. R(a,b);yes}

CANPLAN - eine Multimodale Logik mit 8 Modaloperatoren

Pµ	µ galt irgendwann in der Vergangenheit
Fµ	µ gilt rgendwann einmal
Aµ	es ist notwendig für Agenten A, daß µ gilt
Aµ	Agent A plant, µ zu erreichen
Gµ	Gruppe G plant, µ zu erreichen
CANµ	Agent A kann µ erreichen
COCANµ	Agent A kann mit anderen kooperieren, um µ zu erreichen
COPCANµ	Gruppe G kann µ kooperativ erreichen

5.4 Rao & Georgeff - BDI Architekturen

Es existieren keine klaren Vorstellungen, welche Kombination von Vorinformation und Pro-Attitüden geeignet sind, einen Agenten zu charakterisieren:

* Konolige - Beliefs

* Cohen und Levesque - Beliefs und Goals

* Werner - Glauben (Information), Intention (Strategien) und Nützlichkeit

* Rao & Georgeff: Beliefs, Desire (oder Goals) und Intentions.

Basierend auf einer Theorie von sich verzweigenden zeitlichen Entwicklungen, in welcher die Belief-, Desire- und Intention-acessible Welten in Form von sich verzweigenden Zeitstrukturen interpretiert werden.

Insbesondere wird der Frage nachgegangen, wie die Antizipation von zukünftigen Zuständen, die Handlungen von Agenten beeinflußt.

Literatur: Rao A. Georgeff M.P., 1991: Modeling Rational Agents within a BDI Architecture. In: Principles of Knowledge Representation and Reasoning. Proceedings of the Second International Conference. Cambridge Massachusetts.

Branching Time

Im Gegensatz zu dem Ansatz von Cohen und Levesque, die jede mögliche Welt als eine Sequenz von Ereignissen entlang einer unendlichen Zeitachse interpretieren, repräsentieren Rao und Georgeff jede Welt als einen Zeitbaum.

Die aktuelle Welt ist eine von den über die Belief-Relation erreichbaren Welten, z.B. b1.

Dann wären die Ziele beschrieben durch die zu b1 korrespondierende Welt, die über die Goal-Relation erreichbar ist. Ziele und Intentionen bilden "Submengen" der Glaubensinhalte.

Intentionen bilden "first-class" Objekte vgl. Cohen/Levesque.

Intentionen in Anlehnung an Bratman bilden partielle Pläne, die angewendet werden können, um die Ziele zu erreichen, ähnlich den Strategien von Werner.

Es wird unterschieden zwischen:

* Entscheidungsfreiheit des Agenten

* Entwicklungen der Welt, die aus der Dynamik der Umwelt resultiert und nicht direkt auf die Handlungen des Agenten zurückgeführt werden können.

Beispiel

Ereignisse: d1 - gehe zu Zahnärztin Ohneschmerz
d2 - gehe zu Zahnarzt Mahlzahn
b - gehe schwimmen

Fakten: p - Schmerz
f - Zahnfüllung

Jeder Zeitbaum, zeigt die Entscheidungsfreiheiten eines Agenten auf, ein Agent A glaubt X zu einem Zeitpunkt t, wenn X zum Zeitpunkt t in allen über die Belief-Relation erreichbaren Welten wahr ist.

Formale Theorie

Erweiterung der CTL Logik (Temporale Aussagenlogik mit verzweigenden Zeiten) von Emerson durch:

* Prädikatenlogik erster Ordnung

* Einführung modaler Operatoren für Belief, Goals und Intentions

Unterscheidung in

* state-formula (evaluiert zu einem bestimmten Zeitpunkt)

* path-formula (evaluiert über einen bestimmten Pfad)

Syntax:

* jede Prädikatenformel ist eine state formula.

* wenn p1 und p2 state formula sind und x ist ein Individuum oder eine Ereignisvariable, dann sind ¬p1, p1 | p2 und exists x.p1(x) auch state formulas.

* wenn e ein Ereignis, dann sind auch succeeds(e), fails(e), does (e), succeeded(e), failed(e) und done(e) state formula.

* wenn eine p state formula ist dann ist auch BEL(p), GOAL(p), und INTEND(p) state formula.

* wenn q eine path formula ist, dann ist auch optional(q) eine state formula.

* jede state formula ist auch eine path formula

* wenn q1 und q2 path formulas sind, dann sind auch &#&172;q1, q1 | q2, q1 U q2, exists x.q1(x), q1 und q1 path formulas.

( U until, next, sometimes)

Auszüge aus der Semantik

Interpretation:

M = <W, E, T, , U, B, G, I, Pr>

W Menge von Welten, E Menge von primitiven Ereignistypen, T Menge von Zeitpunkten, binäre Relation auf den Zeitpunkten, U das Universum, Pr ist eine Abbildung von Entities erster Ordnung nach U bei gegebener Welt w und Zeitpunkt t, eine Situtation wt ist eine Welt zu einem bestimmten Zeitpunkt t , die Relationen B, G, I, bilden die aktuelle Situation eines Agenten ab auf die über die Belief usw. Relationen erreichbaren Welten. Jede Welt wird repräsentiert durch die möglichen Entwicklungsmöglichkeiten einer Welt über die Zeit.

W = <Tw, Aw , Sw, Fw >

Tw subset-of T eine Menge von Zeitpunkten der Welt w und Aw entspricht begrenzt auf Zeitpunkte aus Tw. Ein vollständiger Pfad ist eine unendliche Menge von Zeitpunkten (t0, t1, ... tn), so daß forall i: (ti, ti+1) in Aw,Fw,, Sw:Tw xTw -> E, mit Sw,(ti, tk) dann i=k.

M,v,(wt0,wt1,...) p iff M, v, wt0 p

M,v,(wt0,wt1, ...) q iff M,v,(wt1, ...) q

M,v,(wt0,wt1,...) q iff exists k: k »= 0 , so daß M,V,(wtk,...) q

M,v,(wt0,wt1, ...) q1 U q2 iff

(a) exists k, k»=0, so daß M, v, (wtk, ...) q2

forall 0 «= j < k: M,v,(wtj,...) q1

oder

(b) forall k »= 0, M,v,(wtk, ...) q1

Ereignisse:

M, v, wt1

succeeded(e) iff t0 existiert, so daß Sw (t0, t1) = e

M, v, wt1 failed(e) iff t0 existiert, so daß Fw (t0, t1) = e

done(e) := succeeded(e) | failed(e)

suceeds(e) = inevitable (e)((suceeded(e)))

inevitable(y) := ¬optional(¬q) ......

Beliefs, Goals and Intentions:

M, v, wt BEL(p) iff forall w' in Œ Bw,t : M, v, w't p

M, v, wt GOAL(p) iff forall w' in Œ Gw,t : M, v, w't p

M, v, wt INTEND(p) iff forall w' in Œ Iw,t : M, v, w't p

Axiome

A1 GOAL(p) implies BEL(p)

A2 INTEND(p) implies GOAL(p)

A3 INTEND(does(p)) implies does(p)

A4 INTEND(p) IMPLIES BEL(INTEND(p))

A5 GOAL(p) implies BEL(GOAL(p))

A6 INTEND(p) implies GOAL(INTEND(p))

A7 done(e) implies BEL(done(E))

A8 INTEND(p) implies inevitable(

Folgende Formeln sind erfüllbar:

* BEL(p) & ¬GOAL(p))

* inevitable(BEL(p)) & ¬GOAL(p)

* GOAL(p) & BEL(inevitable((p implies r))) & ¬GOAL(r)

Jedoch gilt die Geschlossenheit unter Implikation für Intention und Ziele, folgende Formeln sind gültig:

INTEND(p) & INTEND(p implies r) implies INTEND(r)

GOAL(p) & GOAL(p implies r) implies GOAL(r)

5.4 Situated Automaton

Der Ontologische Status von "possible worlds" und "epistemischen Alternativen" ist fragwürdig"

vs.

"possible worlds" sind eine sinnvolle Abstraktion, auch wenn sie nicht notwendigerweise "existieren" müssen.

Eine Alternative sind die "situated automaton" von Rosenschein. Hier wird die Information analysiert, die implizit im Zustand eines Automaten vorhanden ist.

Literatur: Rosenschein S.J., Kaelbling L.P., 1995: A situated view of representation and control. Artificial Intelligence 73 (1995) 149-173. Kaelbling L.P., Littman M.L., Cassandra A.R., 1995: Partially Obervable markov Decision Processes for Artificial Intelligence. Wachsmuth I., Rollinger C.-R., Brauer W. (eds.): KI-95: Advances in Artificial Intelligence. Springer, Heidelberg, 1-18.

"the key lies in understanding how a process can naturally mirror in its states subtle conditions in its environments and how this mirrowng states ripple out to overt actions that eventually achieve goals."

Allgemeine Definition eines Automaten

<S,Sigma,A,delta,lambda,s0>

* S ist ein Menge von Zuständen

* Sigma ist eine Menge von Inputs

* A ist eine Menge von Outputaktionen

* delta: S x Sigma -> S ist eine Zustandsfunktion, die gegeben einen Zustand und eine Inputfunktion den nächsten Zustand berechnet.

* lambda: S -> A ist die Ausgabefunktion

* s0 in S ist der initiale Zustand

Der Automat interagiert mit seiner Umwelt durch das Senden von Outputs, die Umgebung versorgt den Automaten wiederum mit einem Stimulus, der zu einem internen Zustandsübergang führt und wiederum einen Output auslösen wird usw..

Der Zustand einer Welt wird beschrieben durch den Zustand des Systems und den Zustand der Umgebung.

* Unterscheidung nach deterministischen und nicht deterministischen Welten

* Absolute oder nur teilweise Beobachtung dieser Welt durch den Agenten möglich

Kontrolle eines Markovprozesses mit partieller Beobachtbarkeit

SE (state estimator): in Abhängigkeit der letzten Aktion, der aktuellen Beobachtung und des früheren Glaubens über den Zustand der Welt manifestiert sich der Glauben über die derzeitige Welt (sie wird als Wahrscheinlichkeitsverteilung angegeben).

π (policy): Strategie wie sich ein Agent gegeben eine bestimmte Situation am besten verhält (Auswertung eines kontinuierlichen Belief Markov Entscheidungsprozesses)

"impractical for problems of reasonable size... the results are encouraging and have allowed us to get very good solutions ... in the order about 100 states...."

5.5 Zusammenfassung

Offene Probleme:

* Omniscience, Inkonsistenz

* Resource Bounded

* Beziehung zwischen Intention und Aktion

* Welche Kombination von Attitüden ist erforderlich, Agenten zu beschreiben, z.B. BDI (Rao & Georgeff) oder Notion of Choice (Shoham)

Welche Rolle soll eine entwickelte Agententheorie spielen?

* Spezifikation von Agenten (ähnliche Problemstellung, wie im Softwareengineering, welche Eigenschaften eines Agenten, seines Glauben usw. können abgeleitet werden), wie nützlich und ausdrucksstark ist eine spezielle Spezifikationssprache?

* Wissensrepräsentationsformalismus - es stellt sich dann die Frage nach der Wissensverarbeitung, Algorithmen gesucht, die mit solchen Theorien schliessen

* Anregung für die Kognitionswissenschaften und die Philosophie (dies war z.B. die Intention von Hintikka).