Multiagentensysteme

Deductive Reasoning Agents

Volkan Aksu & Sebastian Ptock

Überblick

Einleitung

Deductive Reasoning Agents

Der Staubsauger-Roboter

Agentenorientierte Programmierung (AOP)

Concurrent MetateM (CMM)

Zusammenfassung

EinleitungVorher ein bisschen Logik

Argument : ist eine Aussage oder eine Folge von Aussagen, die zur Begründung oder zur Widerlegung einer Behauptung (These) angeführt wird.

(http://de.wikipedia.org/wiki/Argument)

Argumente bestehen aus einer Schlussfolgerung oder Konklusion und einer oder mehreren Prämissen.

EinleitungVorher ein bisschen Logik

Überlegen Sie, ob das folgende Beispiel nach unserer Definition ein gültigesArgument ist!

Hubschrauber sind Vögel.Alle Vögel sind Lebewesen.——————————————Hubschrauber sind Lebewesen

EinleitungDeduktive Gültigkeit

Deduktive Gültigkeit: Wenn alle Prämissen wahr sind, dann muss die Konklusionwahr sein.

Es ist Benzin im Tank oder der Motor läuft nicht.Der Motor läuft.——————————————————————Benzin ist im Tank.

EinleitungDeduktion

Die Deduktion (v. lat.: deducere = herabführen) (…) ist in (…) der Logik eineSchlussfolgerungsweise vom Allgemeinen auf das Besondere.Genauer gesagt werden mithilfe der Deduktion spezielle Einzelerkenntnisse ausallgemeinen Theorien gewonnen. Sie bezeichnet das Verfahren, aus gegebenenPrämissen (...) Schlussfolgerungen abzuleiten.http://de.wikipedia.org/wiki/Deduktion

Beispiel:Alle Menschen sind sterblich. Sokrates ist ein Mensch. Sokrates ist sterblich.

EinleitungDeduktion & Induktion

Im Gegensatz zur Induktion: Die Induktion geht vom Einzelnen zum Allgemeinen.

Beispiel: Platon war ein Mensch. Aristoteles war ein Mensch. Epikur war ein Mensch. Platon ist gestorben. Aristoteles ist gestorben. Epikur ist gestorben. ------------------------------------------------------------ Alle Menschen sind sterblich.

Deductive Reasoning Agents

Agenten lassen sich in deliberative Agenten und reaktive Agenten unterscheiden.

Deliberative Agenten : denken gewissermaßen nach, bevor sie handeln.

Reaktive Agenten : reagieren sofort auf Signale. Die logische Schlussfolgerung ist dabei nicht möglich.

Deductive Reasoning AgentsRALPH

Aufbau von RALPH:

Kamera: sieht Tür Interpretation : übersetzt Wissensbas is : kennt Tür Plan : stoppen Aktion : anhalten

Deductive Reasoning AgentsProbleme

Schwierigkeiten bei den deduktiv schließenden Agenten:

The transduction problem: Übersetzen der Informationen über die Umgebung in eine adäquate symbolische Repräsentation.

The representation/reasoning problem: adäquate, zeitnahe Manipulation / Schlussfolgerung symbolisch repräsentierter Informationen.

Deductive Reasoning AgentsFormale Definition

Wie kann man den Aufbau und Funktionsweise eines solchen Agenten formal beschreiben?

>>>Agent als Theorembeweiser

Der Agent hat einen internen Zustand Δ.Beispiele für prädikatenlogische Formeln:

Offen(ventil221)Temperatur(reaktor4726, 321)Druck(tank7776, 28)

Deductive Reasoning AgentsFormale Definition

L: Menge von Sätzen in PL-1

D: Menge von Datenbanken (L) / Menge von Mengen von PL-1 FormelnD=℘(L)

∆iD: Zustand des Agenten

ρ: Menge von Deduktionsregeln

∆├ ρφ heißt:Die Formel φ kann aus ∆ mit den Deduktionsregeln ρ bewiesen werden.

Ac: Menge von ausführbaren Aktionenα: Aktion αAc

see: S -> Per // Objekt als Symbol wahrnehmennext: D x Per -> D // Wahrnehmung in interne Repräsentation aufnehmenaction: D -> Ac // Passende Aktion wählen

Deductive Reasoning AgentsFormale Defintion

Beispiel für Funktion action

Der Staubsauger-Roboter

Funktionen: vorwärts saugen drehen (nur eine Richtung 90°)

Sensor: Dreck Null

Blickrichtung: Nord Ost Süd West

Der Staubsauger-RoboterNext-Funktion

Drei Domänen-Prädikate:In(x,y): Agent ist auf Block(x,y)Dreck(x,y): Dreck auf Block(x,y)Blick(d): Blickrichtung des Agenten

Wir möchten eine Funktion “next” entwerfen, die die aktuelle, wahrgenommene Information der Datenbank hinzufügt und alte, nicht mehr benötigte Informationen löscht. So werden Domänen-Prädikate aktualisiert.

Der Staubsauger-RoboterNext-Funktion

old(∆) = {P(t1...tn) | P ∈ {In, Dreck, Blick} & P(t1…tn) ∈ ∆}Zustand als Prädikat aus Domäne

new: D x Per -> DDatenbank aktualisieren

next(∆,p) = (∆ \ old(∆)) ∪ new(∆,p)

Der Staubsauger-RoboterDeduktionsregeln

Deduktionsregeln haben die Form:φ(...) → ψ(...)

Ziel: Wenn Dreck vorhanden, dann saugen!In(x,y) Λ Dreck(x,y) → Do(saugen)

Wie kommt dieser Agent vorwärts?In(0,0) Λ Blick(Nord) Λ ¬Dreck(0,0) → Do(vorwärts)In(0,1) Λ Blick(Nord) Λ ¬Dreck(0,1) → Do(vorwärts)In(0,2) Λ Blick(Nord) Λ ¬Dreck(0,2) → Do(drehen)In(0,2) Λ Blick(Ost) → Do(vorwärts)

Agentenorientierte Programmierung

entwickelt von Yoav Shoham Idee: Agenten mit mentalen Eigenschaften zu programmieren (Wünsche, Glauben,Bedürfnisse, Intention etc.)

Mentale Eigenschaften – die Eigenschaften zu zweifeln, einzusehen, zu bejahen, zuverneinen, zu wollen, nicht zu wollen, bildlich vorzustellen und zu empfinden – sindEigenschaften der Seele, nicht des Körpers.(Ansgar Beckermann, Mentale Eigenschaften und mentale Substanzen– Antworten der Analytischen Philosophie auf das 'Leib-Seele-Problem' (2002))

Agentenorientierte Programmierung

Programmiersprache Agent0

Erste Programmiersprache für agentenorientiertes Programmieren

Ein Agent wird spezifiziert durch:

Überzeugungen (beliefs) Verpflichtungen (commitments) Fähigkeiten (capabilities) Verpflichtungsregeln (commitment rules)

Agentenorientierte Programmierung

commitment rules bestimmen, wie der Agent agiert.Jede Regel enthält: Nachrichtenzustand (message condition) geistigen Zustand (mental condition) Aktion

Beispiel einer Verpflichtungsregel (commitment rules):

COMMIT(( agent, REQUEST, DO(time, action)), ;;; msg conditon( B,[now, Friend agent] ANDCAN (self, action) ANDNOT [time, CMT(self, anyaction)]), ;;; mental conditionself,DO(time, action) )

Agentenorientierte Programmierung

Concurrent MetateM (CMM)

Entwickelt von Michael Fisher Basiert auf direkter Ausführung logischer Formeln Mehrere, konkurrierende Agenten, die über „Broadcast“-Nachrichten

kommunizieren Agenten haben zwei Komponenten:

Schnittstelle „Computational Engine“

Concurrent MetateM (CMM)Schnittstelle

Interaktion mit der Umwelt & anderen Agenten

„agent identifier“: Jeder Agent hat eine eigene ID „environment propositions“: Menge von Symbolen, die definiert, welche

Nachrichten empfangen werden können „component propositions“: Menge von Symbolen, die definiert, welche Nachrichten

gesendet werden können

Beispiel:

stack(pop, push)[popped, full]

agent identifier: stackenvironment propositions: pop, pushcomponent propositions: popped, full

Concurrent MetateM (CMM)Computational Engine

History: Zustände des Agenten & empfangene Nachrichten Deduktionsregeln:

Vorbedingung (Vergangenheit) -> Konsequenz (Zukunft) Aktionsauswahl: Nachricht verschicken

Concurrent MetateM (CMM)Regeln

Propostional MetateM Logic (PML) basiert auf temporaler Logik:

Concurrent MetateM (CMM)Zyklus

1. History aktualisieren, wenn Nachrichten empfangen wurden

2. Regeln auswählen (Vergangenheit der Regeln mit History vergleichen)

3. Den Regeln entsprechend agieren/Nachrichten verschicken:a. Vorher zurückgestellte Aktionen aufgreifenb. Nicht erfüllbare Aktionen für nächsten Durchlauf „merken“

4. GOTO 1

Concurrent MetateM (CMM)Beispiel

Zusammenfassung & FragenWas sind die zwei Grundprobleme beim deduktiven Schließen?

Worin unterscheiden sich reaktive und deliberative Agenten?

Was wäre, wenn man den Staubsauger-Roboter auf ein 10x10 Feld setzt? Wie „elegant“ wäre die Implementierung mit logischen Formeln?

(Beispiel: Niki der Roboter)

Was ist das Grundkonzept der agentenorientierten Programmierung(AOP)? Was versteht man unter “commitment rules”?

Aus welchen Komponenten besteht die Schnittstelle eines Agenten in einemConcurrent MetateM System?