Logikbasierte Agenten

Überblick

• Wissensbasierte Agenten• Bsp.: Wumpus-Welt• Logik im Allgemeinen, Modelle und Logische

Konsequenz• Aussagenlogik• Inferenzregelen und Theorembeweise• Resolution• Vorwärtsverkettung, Rückwärtsverkettung

•

Wissensbasen

• Wissensbasis = Menge von Sätzen in einer formalen Sprache (Wissensrepräsentationsprache)

• Deklarativer Ansatz für den Bau eines Agenten:– Teile der Wissensbasis (WB) des Agenten das erforderliche Wissen mit

(Tell)– Dann kann der Agent alle Fragen durch Anfrage bei der WB

beantworten (Ask)

• Zwei mögliche Ebenen zur Beschreibung von Agenten:– Wissensebene, d.h. Wissen des Agenten unabhängig von der

Implementation– Implementationsebene, d.h. Datenstrukturen in WB + Algorithmen zu

deren Verarbeitung

–

–

Ein einfacher wissensbasierter Agent

Fähigkeiten des Agenten:– Repräsentation von Zuständen, Aktionen, etc.– Verarbeitung neuer Perzepte– Interne Repräsentation der Welt aktualisieren– Versteckte Eigenschaften der Welt logisch erschließen– Sinnvolle Aktionen erschließen

––––

–

•

Wumpus-WeltPeas-Beschreibung (Percepts, Environment, Actions, Sensors):

• Aktuatoren: Linksdrehung, Rechtsdrehung, Vorwärts, Greifen, Loslassen, Schießen

• Wahrnehmungen: Gesank, Luftzug, Glitzern, Bumms, Schrei

• Leistungsmaß:– Gold: +1000, Tod: (durch Wumpus oder Falltür) -1000– -1 pro Schritt, -10 für Gebrauch des Pfeils

• Umgebung– Raster von Quadraten– Gestank in Quadraten neben Wumpus– Luftzug in Quadraten neben Falltür– Glitzern falls Gold im selben Quadrat– Schießen in richtiger Richtung tötet Wumpus– Nur ein Pfeil verfügbar– Greifen sackt Gold ein (im aktuellen Quadrat)– Loslassen läßt Gold im aktuellen Quadrat fallen

–––––––

–

Charakterisierung der Wumpus-Welt

• Vollständig beobachtbar: Nein – nur lokale Perzeption

• Deterministisch: Ja – Ergebnis von Aktionen exakt spezifiziert

• Episodisch: Nein – sequenziell auf Ebene der Aktionen

• Statisch Ja – Wumpus und Falltüren bewegen sich nicht

• Diskret Ja

• Single-Agent? Ja – Wumpus wird hier nicht als Gegenspieler definiert

•

Explorieren der Wumpus-Welt

Explorieren der Wumpus-Welt

Explorieren der Wumpus-Welt

Explorieren der Wumpus-Welt

Explorieren der Wumpus-Welt

Explorieren der Wumpus-Welt

Explorieren der Wumpus-Welt

Explorieren der Wumpus-Welt

Agent für Wumpus-Welt

• Zwei Vorgehensweisen:1. Programmiere spezielle Lösung für Wumpus-Welt

• Führt wahrscheinlich schnell zum Ziel• Aber nicht verallgemeinerbar

2. Entwickle System, das• Notwendiges Wissen repräsentieren• Schlüsse ziehen und danach handeln kann

• Weg 2 verspricht langfristig mehr Erfolg!

Logik (allgemein)

• Logiken sind formale Sprachen zur Repräsentation von Information, die das Ziehen von Schlüssen erlauben.

• Syntax definiert die Sätze der Sprache.

• Semantik definiert die “Bedeutung" der Sätze:– D.h. definiert die Wahrheit eines Satz mit Bezug auf die Welt

• Bsp.: Sprache der Arithmetik:– x+2 ≥ y ist ein Satz; x2+y > {} ist kein Satz– x+2 ≥ y ist wahr, wenn die Zahl x+2 nicht kleiner ist als y– x+2 ≥ y ist wahr in einer Welt wo x = 7, y = 1– x+2 ≥ y ist falsch in einer Welt wo x = 0, y = 6

––

–•

–

•

Logische Konsequenz (Entailment)

• Logische Konsequenz heißt dass ein Satz logisch aus einem Satz α folgt:

α ╞

• α ╞ gilt genau dann, wenn in jedem Modell, in dem α wahr ist, auch wahr ist.– Bsp.: x+y = 4 folgt aus 4 = x+y

• D.h. falls α wahr ist, ist auch wahr.

• WB ╞ α bedeutet: Satz α folgt aus Wissensbasis WB dann und nur dann,

wenn α in allen Welten wahr ist, in denen WB wahr ist.

– Bsp.: Aus der WB, die die Sätze “Schalke hat gewonnen” und “HSV hat gewonnen” enthält, folgt:

“Schalke hat gewonnen oder HSV hat gewonnen”.

• Logische Konsequenz ist eine Beziehung zwischen Sätzen, die auf Semantik basiert.

–

Sprache als Beschreibung der Welt

• Sätze der formalen Sprache sollten Aspekten der Welt entsprechen und sollten so beschaffen sein dass …

• … auch gefolgerte neue Sätze Aspekten der Welt entsprechen !

• Problem: Was heißt hier „Welt“ ?• Wie kann Beziehung zwischen Welt und Sprache formalisiert

werden?• Antwort: „Modell“ statt „Welt“

Modelle• Bisher: Semantik wurde über Wahrheit eines Satzes

in einer Welt definiert. Problem: Begriff „Welt“ ist unpräzise.

• Besser: „Modell“ statt „Welt“.

• Modelle sind formale „Welten“, in denen die Wahrheit von Sätzen eindeutig festgestellt werden kann.

– Z.B. wird die Frage, ob Wumpus medizinisch tot ist oder nur unschädlich, in die Abstraktion von der Welt zum Modell „verlagert“.

– Damit ist die lebendig/tot auf Ebene der Modelle eindeutig geklärt.

• m ist ein Modell von Satz α, wenn α in m wahr ist.

• M(α) ist die Menge aller Modelle von α.

• D.h. WB ╞ α falls M(WB) M(α)– Z.B. WB = Schalke hat gewonnen und HSV hat

gewonnenα = HSV hat gewonnen

–••

Logische Konsequenz in der Wumpus-Welt

• Vereinfachte Wumpus-Welt: Nur Falltüren

• Situation nach folgender Perzeptions-Aktions Folge:

– Keine Wahrnehmung in [1,1]– Gehe rechts– Luftzug in [2,1]

• Betrachte mögliche Modelle für WB :3 Boolesche Entscheidungen 8 mögliche Modelle

•

Wumpus Modelle

Wumpus Modelle

• WB = Regeln der Wumpus-Welt + Beobachtungen

Wumpus Modelle

• WB = Regeln der Wumpus-Welt + Beobachtungen• Aussage α1 = "[1,2] ist sicher“• WB ╞ α1, Beweis durch Model-Checking

•

Wumpus Modelle

• WB = Regeln der Wumpus-Welt + Beobachtungen

Wumpus Modelle

• WB = Regeln der Wumpus-Welt + Beobachtungen• Aussage α2 = "[2,2] ist sicher" • WB ╞ α2

• Beachte: Aus WB folgt aber auch nicht α2 !(d.h. “Falltür in [2,2]" !

• (d.h. α2 folgt nicht aus WB)

Inferenz• WB ├i α bedeutet “Satz α kann aus WB mittels des

Inferenz-Algorithmus i abgeleitet werden”.

• Korrektheit: i ist korrekt, wenn aus der Wahrheit von WB ├i α folgt dass auch WB╞ α wahr ist.

• Vollständigkeit: i ist vollständig, wenn aus der Wahrheit von WB╞ α folgt dass auch WB ├i α wahr ist.

• Vorschau: Wir werden eine Logik definieren (Logik 1. Ordnung), in der eine Vielzahl relevanter Fakten repräsentiert werden kann und für die korrekte und vollständige Inferenzregeln bekannt sind.

• D.h. der Inferenz-Algorithmus kann jede Frage beantworten, deren Antwort aus den in der WB bekannten Fakten folgt.

Aussagenlogik: Syntax

• Aussagenlogik …– ist eine sehr einfache Logik,– zeigt Ideen der Logik.

• Syntax definiert erlaubte Sätze

• Aussagensymbole (Großbuchstaben) P1, P2 etc. sind Sätze

• Besondere Symbole: wahr, falsch

• Komplexe Sätze:– Wenn S ein Satz ist, ist auch S ein Satz (Negation)– Wenn S1 und S2 Sätze sind,

• ist auch S1 S2 ein Satz (Konjunktion)• ist auch S1 S2 ein Satz (Disjunktion)• ist auch S1 S2 ein Satz (Implikation)• ist auch S1 S2 ein Satz (Bikonditional)

•••

•

––

Syntax der Aussagenlogik: Formale Grammtik

Satz AtomarerSatz | KomplexerSatz

AtomarerSatz True | False | Symbol

Symbol P | Q | R . . .

KomplexerSatz Satz

| (Satz Satz)

| (Satz Satz)

| (Satz Satz)

| (Satz Satz)

Aussagenlogik: Semantik• Semantik definiert, wie Wahrheit eines Satzes in Bezug auf ein Modell bestimmt

wird.

• Jedes Modell legt die Wahrheitswerte wahr/falsch für jedes Aussagesymbol fest:Z.B. P1,2 P2,2 P3,1

falsch wahr falsch

• Für aus den drei Symbolen P1,2, P2,2, P3,1 gebildete Sätze sind 8 Modelle möglich.

• Folgende Regeln definieren, wie Wahrheitswert für Komplexe Sätze bezüglich eines Modells m ermittelt werden:

S ist wahr wenn S falsch ist S1 S2 ist wahr wenn S1 wahr ist und S2 wahr istS1 S2 ist wahr wenn S1 wahr ist oder S2 wahr istS1 S2 ist wahr wenn S1 falsch ist oder S2 wahr ist d.h. ist falsch wenn S1 wahr ist und S2 falsch istS1 S2 ist wahr wenn S1S2 wahr ist und S2S1 wahr ist

• Einfacher rekursiver Prozess zum Auswerten beliebiger Sätze, z.B.

P1,2 (P2,2 P3,1) = wahr (wahr falsch) = wahr wahr = wahr

•

•

Semantik: Wahrheitstabelle der Verknüpfungen

• Beachte: Implikation bedeutet nicht kausalen Zusammenhang zwischen P und Q.

Gültigkeit und Erfüllbarkeit

Ein Satz ist gültig, wenn er für alle Modelle wahr ist.Z.B. A A, A A, (A (A B)) B

Satz A (wobei A Literal) ist also nicht gültig (obwohl er wahr sein kann)

Gültigkeit und Inferenz hängen zusammen über das Deduktionstheorem:WB ╞ α dann und nur dann, wenn (WB α) gültig ist.

Ein Satz ist erfüllbar, wenn er in mindestens einem Modell wahr ist.Z.B. A B, C

Ein Satz ist unerfüllbar, wenn er in keinem Modell wahr ist.Z.B. AA

Erfüllbarkeit und Konsequenz hängen folgendermaßen zusammen:WB ╞ α dann und nur dann, wenn (WB α) unerfüllbar ist.

––

Logische Äquivalenz

• Zwei Sätze sind logisch äquivalent wenn sie für dieselben Modelle wahr sind:

α ≡ ß wenn α╞ β und β╞ α

••

Überblick: Konsequenz, Äquivalenz, Implikation, Bikonditional

• Logische Konsequenz: α ╞ – Begriff der Logik (nicht nur der Aussagenlogik)– Beziehung zwischen zwei Sätzen, basierend auf Semantik– Gilt, wenn in jedem Modell, in dem α wahr ist, auch wahr ist: M(α) M().– Achtung: Umgangssprachlich: „Aus α folgt “.

• Äquivalenz: α ≡ ß – Begriff der Logik– Beziehung zwischen zwei Sätzen– Gilt, wenn α und für dieselben Modelle wahr sind: α╞ β und β╞ α

• Implikation: A B– Begriff der Aussagenlogik– A B ist ein Satz, gebildet aus zwei anderen Sätzen– Wahrheit dieses Satzes ist definiert über Semantik (geg. durch Wahrheitstabelle).– A B ist wahr falls A falsch oder B wahr ist.

• Bikonditional: A B– Begriff der Aussagenlogik– Cf. Implikation, aber Implikation in beiden Richtungen– Achtung: Umgangssprachlich: „A äquivalent B“.

Wissensbasis• Wissensbasis ist Sammlung wahrer Sätze• Die Sätze können auch als ein wahrer Satz aufgefasst werden

(Konjunktion aller Einzelsätze)• Sätze beziehen sich sowohl auf

– Generell gültige Aussagen („Wumpus stinkt in 4er-Nachbarschaft“)– Aktuelle Perzepte („Gestank hier und jetzt“)

Beispiel:• Sei Pi,j wahr wenn eine Falltür (pit) bei [i, j] ist.• Sei Bi,j wahr wenn Luftzug (breeze) bei [i, j] ist.

WB:• Sätze aus Perzepten: „[1,1] ok, Breeze in [2,1]“

1. P1,1

2. B1,1

3. B2,1

• Generelles Weltwissen: „Falltüren verursachen Luftzug in angrenzenden Quadraten“:

4. B1,1 (P1,2 P2,1)5. B2,1 (P1,1 P2,2 P3,1)

1.

Inferenz durch Aufzählung (Model-Checking)

• Aufgabe: Feststellen, ob ein Satz Konsequenz der Wissensbasis ist: WB╞ ?

• Beispiel: Ist P2,2 Konsequenz der WB?

• Ansatz: „Beweis durch vollständiges Ausprobieren“ in der Wahrheitstabelle– Liste alle Modelle auf, d.h. alle möglichen Wahrheitswerte aller

beteiligten atomaren Sätze– Stelle fest, für welche Modelle WB wahr ist– WB╞ gilt, falls wahr ist für alle Modelle, für die WB wahr ist.

Inferenz durch Aufzählung: Beispiel

• Nur für 3 Zeilen ist WB wahr• P2,2 ist in einer dieser Zeilen nicht wahr• Also ist P2,2 nicht Konsequenz der WB (denn es könnte auch P3,1

wahr sein)• Es ist aber auch nicht P2,2 Konsequenz aus WB (P2,2 könnte wahr

sein)

Inferenz durch Aufzählung: Algorithmus

• Depth-first Aufzählung aller Modelle ist korrekt und vollständig.• Verwendet wie Backtracking partielle (d.h. nicht vollständige) Modelle• Für n Symbole ist Zeitkomplexität O(2n), Raumkomplexität O(n)• TT -- Truth Table, PL – Propositional Logik• PL-True(m) gibt wahr zurück, falls Satz für Modell m gilt.• Extend(P,w,m) gibt neues Modell m zurück, in dem P Wahrheitswert w hat.

Beweismethoden

Beweismethoden können grob in zwei Arten eingeteilt werden:

• Model-Checking– Wahrheitstabelle zählt alle Möglichkeiten auf (exponentiell in n)– Verbessertes Backtracking, z.B. Davis-Putnam-Logemann-Loveland

(DPLL)– Heuristische Suche im Modell-Raum (zulässig aber unvollständig)

z.B. Min-Conflicts-ähnliche Hill-Climbing Algorithmen

• Anwendung von Inferenzregeln– Zulässige Generierung neuer Sätze aus bekannten.– Beweis = Folge nacheinander angewandter Inferenzregeln, die als

Operatoren in Standard-Suche angesehen werden können.– Normalerweise Transformation der Sätze in Normalform nötig

(als „Eingabeformat“ für den Inferenzalgorithmus).

–

–

––

–»

Inferenzregeln

• Modus Ponens:

Heißt: Sind die Sätze und vorgegeben, so kann Satz geschlossen werden („Satz ist vorgegeben“ heißt „die Wahrheit des Satzes ist vorgegeben“).

• Und-Eliminierung:

• Bikonditional-Eliminierung:

,

)()(

Begriffe: Literal, Klausel

• Literal:Atomarer Satz oder dessen Negation

• Klausel:Disjunktion von Literalen

Inferenzregeln: Resolution

• Konjunktive Normalform (KNF): Konjunktion von Disjunktionen von Literalen

z.B. (A B) (B C D)

• Resolution: Inferenzregel (für KNF):

l1 … lk, m1 … mn

l1 … li-1 li+1 … lk m1 … ml-1 ml+1 ... mn

wobei li und ml komplementäre Literale sind.

Z.B. P1,3 P2,2, P2,2

P1,3

• Resolution ist korrekt und vollständig.•

»•

•

Resolution: Korrektheit

l1 … li-1 li+1 … lk ist entweder wahr oder falsch.

Falls wahr: Dann ist auch

l1 … li-1 li+1 … lk m1 … ml-1 ml+1 ... mn wahr

Falls falsch:Dann ist li wahr, folglich ist ml falsch und damit

m1 … ml-1 ml+1 ... mn wahr. Dann ist auch

l1 … li-1 li+1 … lk m1 … ml-1 ml+1 ... mn wahr.

Umwandlung in KNF

B1,1 (P1,2 P2,1)

1. Eliminiere : Ersetze α β mit (α β)(β α).(B1,1 (P1,2 P2,1)) ((P1,2 P2,1) B1,1)

2. Eliminiere : Ersetze α β mit α β.(B1,1 P1,2 P2,1) ((P1,2 P2,1) B1,1)

3. Ziehe in die Klammern mittels de Morgan's Regeln und ggf. Doppel-Negation:(B1,1 P1,2 P2,1) ((P1,2 P2,1) B1,1)

4. Wende Distributiv-Gesetz an:(B1,1 P1,2 P2,1) (P1,2 B1,1) (P2,1 B1,1)

KNF erreicht !

–•

–•

–•

–

•

Resolutionsalgorithmus: Beispiel

WB = (B1,1 (P1,2 P2,1)) B1,1

α = P1,2

Fehler: P2,1

Resolutionsalgorithmus

Idee: Beweis durch Widerspruch, d.h. zeige WBα unerfüllbar

•

Vorwärts- und Rückwärtsverkettung

• Praxis: WB enthält häufig nur Konjunktion von Horn-Klauseln, so dass Resolution durch einfachere Algorithmen ersetzt werden kann.

• Horn-Klausel:– Symbol (atomare Aussage); oder– (Konjunktion von Symbolen) Symbol– z.B. C (B A) (C D B)

• Modus Ponens (für Horn-Klauseln): Vollständig für Horn-WBα1, … ,αn, α1 … αn β

β

• Ermöglicht Verwendung einfacher Inferenzalgorithmen wie Vorwärtsverkettung und Rückwärtsverkettung.

• Diese Algorithmen sind intuitiv verständlich und linear in der Zeit.

••

–

Vorwärtsverkettung

• Idee: – Eliminiere jede Regel, deren Prämissen in der WB erfüllt sind, – füge ihre Konsequenz der WB hinzu,– bis die Anfrage gefunden wurde.

• Vorwärtsverkettung ist korrekt und vollständig für Horn-WB.

Vorwärtsverkettung: Algorithmus

• Count: Für jede Implikation die Zahl noch unbekannter Prämissen• Agenda: Als wahr bekannte, noch nicht verarbeitete Symbole

Vorwärtsverkettung: Beispiel

B

A

LBA

LPA

MLB

PML

QP

B

A

LBA

LPA

MLB

PML

QP

Vorwärtsverkettung: Beispiel

B

A

LBA

LPA

MLB

PML

QP

Vorwärtsverkettung: Beispiel

B

A

LBA

LPA

MLB

PML

QP

Vorwärtsverkettung: Beispiel

B

A

LBA

LPA

MLB

PML

QP

Vorwärtsverkettung: Beispiel

B

A

LBA

LPA

MLB

PML

QP

Vorwärtsverkettung: Beispiel

B

A

LBA

LPA

MLB

PML

QP

Vorwärtsverkettung: Beispiel

B

A

LBA

LPA

MLB

PML

QP

Vorwärtsverkettung: Beispiel

Rückwärtsverkettung

Idee: Von Anfrage q aus rückwärts arbeiten.

Beweise q durch Rückwärtsverkettung:Prüfe, ob q schon bekannt ist, oderbeweise durch Rückwärtsverkettung alle Pramissen einer Regel, aus

der q folgt.

Vermeide Schleifen: Prüfe, ob neues Teilziel bereits auf „Ziel Stack“ ist.

Vermeide unnötige Arbeit: Prüfe, ob neues Teilziel1. schon als wahr erkannt wurde, oder2. dieser Versuch fehlgeschlagen ist.

3.

–

•

•

Rückwärtsverkettung Beispiel

B

A

LBA

LPA

MLB

PML

QP

B

A

LBA

LPA

MLB

PML

QP

Rückwärtsverkettung Beispiel

B

A

LBA

LPA

MLB

PML

QP

Rückwärtsverkettung Beispiel

B

A

LBA

LPA

MLB

PML

QP

Rückwärtsverkettung Beispiel

B

A

LBA

LPA

MLB

PML

QP

Rückwärtsverkettung Beispiel

B

A

LBA

LPA

MLB

PML

QP

Rückwärtsverkettung Beispiel

B

A

LBA

LPA

MLB

PML

QP

Rückwärtsverkettung Beispiel

B

A

LBA

LPA

MLB

PML

QP

Rückwärtsverkettung Beispiel

B

A

LBA

LPA

MLB

PML

QP

Rückwärtsverkettung Beispiel

B

A

LBA

LPA

MLB

PML

QP

Rückwärtsverkettung Beispiel

Vergleich Vorwärts- / Rückwärtsverkettung

• Vorwärtsverkettung ist datengetrieben, automatisch, „unbewusste“ Verarbeitung,– Z.B. Objekterkennung, Routine-Enscheidungen

• Unter Umständen wird viel Aufwand in irrelevante Teilziele gesteckt.

• Rückwärtsverkettung ist zielorientiert, angemessen für Problemlösen,– Z.B. Wo sind meine Schlüssel? Wie krieg ich ein Diplom?

• Komplexität der Rückwärtsverkettung kann erheblich kleiner sein als linear in der Größe der WB.

•

»

–

Effiziente aussagenlogische Inferenz

Zwei Familien effizienter Algorithmen für aussagenlogische Inferenz:

• Vollständige Backtracking-Suche: – DPLL Algorithmus (Davis, Putnam, Logemann, Loveland)

• Unvollständige lokale Suche– WalkSAT Algorithmus

–

•

DPLL-Algorithmus

• DPLL überprüft, ob ein Eingabesatz (in KNF) erfüllbar ist.

• Prinzip: Rekursive Tiefensuche wie TT-Entails(), aber mit Verbesserungen gegenüber naiver vollständiger Aufzählung:

1. Frühe Terminierung• Eine Klausel ist wahr, wenn eins ihrer Literale wahr ist.• Ein Satz (in KNF) ist falsch, wenn eine der Klauseln falsch ist.

2. Reine-Symbol-Heuristik• „Reine“ Symbole: Haben gleiches „Vorzeichen“ in allen Klauseln.

– Z.B. In den drei Klauseln (A B), (B C), (C A) sind A, B rein, C unrein.

• Erfüllbarer Satz (in KNF) hat immer ein Modell, in dem die Literale der reinen Symbole wahr sind.

• Daher: Weise Literalen reiner Symbole wahr zu.

3. Einheitsklausel-Heuristik• Einheitsklausel: Klausel mit nur einem Literal• Das Literal einer Einheitsklausel muss wahr sein.

••

DPLL-Algorithmus (Überblick)

WalkSAT-Algorithmus

• Lokaler Such-Algorithmus• Unvollständig• Suchschritt: Verändere Wahrheitswert eines Symbols• Bewertungsfunktion: Min-Conflicts• Problem: Balance zwischen Gier und Zufälligkeit finden

• Prinzip WalkSAT:Repeat:– Wähle zufällig unerfüllte Klausel– Wähle Symbol aus Klausel nach einer von zwei Methoden:• Zufall• Wähle Symbol so, dass Flip Min-Conflicts (d.h. Zahl unerfüllter Klauseln) optimiert

– Flip

••

•

WalkSAT Algorithmus

Schwierige Erfüllbarkeitsprobleme

• Wann sind Probleme schwierig?• Hängt ab von m / n:

m = # Klauseln n = # Symbole

• Betrachte Zufallsklauseln:– m<<n: Einfach, da viele Lösungen– m>>n: Einfach, da meist unerfüllbar– m etwas größer als n: Schwierig

• Experiment: Zufällige 3-KNF Sätze, z.B.(D B C) (B A C) (C B E) (E D B) (B E C)– # Symbole n=50 fest– Variables m– Teste DPLL und WalkSat– Schwierige Probleme bei „kritischem Punkt“ für ca. m/n = 4.3

–•

Schwierige Erfüllbarkeitsprobleme

Wahrscheinlichkeit der Erfüllbarkeit:

Mittlere Laufzeit für 100 erfüllbare zufällige 3-KNF Sätze:

•

Schwierige Erfüllbarkeitsprobleme

• Probleme um kritischen Punkt schwieriger• WalkSAT wesentlich schneller (würde aber Unerfüllbarkeit nicht bemerken!)• DPLL ebenfalls sehr effektiv (< 2000 Schritte) statt 250 für Wahrheitstafel

Inferenz-basierte Agenten in der Wumpus-Welt

Wumpus-Welt Agent auf Basis von Aussagenlogik:

P1,1 (Start-Quadrat ok)W1,1 (Start-Quadrat ok)Bx,y (Px,y+1 Px,y-1 Px+1,y Px-1,y) (Breeze neben Pit)Sx,y (Wx,y+1 Wx,y-1 Wx+1,y Wx-1,y) (Stench neben Wumpus)W1,1 W1,2 … W4,4 (Wumpus ist irgendwo)W1,1 W1,2 (Nur ein Wumpus)W1,1 W1,3 ( ’’ )…

64 Symbole, 155 Sätze, davon einer mit 16 Symbolen

Problem: Aussagen müssen für jedes Quadrat wiederholt werden, Aussagenlogik kann Verallgemeinerung nicht darstellen!

•

Unzulässiger Trick: Variable für Ort, Orientierung, Aktion außerhalb der WB !

• WB enthält bislang nur „Physik“ der Wumpus-Welt

• Ort, Orientierung des Agenten fehlen

• Naiver Ansatz:

– „Agent auf Feld [i,j]“: Li,j

– Bewegung: Z.B. L1,1 Rechts Vorwärts L2,1

– Falsch, denn L1,1 und L2,1 können nicht gleichzeitig wahr sein !

– „“ bedeutet nicht zeitlichen Ablauf !

• Ausweg: Für jede Zeit t und jeden Ort [x,y],

Lx,yt FacingRight t Forward t Lx+1,y

t+1

Beachte: Je ein Satz für jede Zeit und jeden Ort !

• Problem: Ständige Vermehrung der Sätze !

•

Ort und Orientierung repräsentieren

Zusammenfassung• Logik-basierte Agenten wenden Inferenz auf eine Wissensbasis an

um neue Informationen zu erhalten und Entscheidungen zu treffen• Grundlegende Konzepte der Logik:

– Syntax: Legt Struktur von Sätzen formal fest.– Semantik: Definiert Wahrheit von Sätze bezgl. Modellen.– Konsequenz: Wahrheit eines Satz als Folge der Wahrheit eines anderen– Inferenz: Ableitung eines Satzes aus einem anderen Satz– Korrektheit: Nur Ableitung von Sätzen, die log. Konsequenzen sind– Vollständigkeit: Ableitung aller Sätze, die log. Konsequenzen sind

• Inferenzalgorithmen: – Resolution ist vollständig für Aussagenlogik– Vorwärts- / Rückwärtsverkettung sind linear in der Zeit, vollständig für

Hornklauseln

• Wumpus-Welt erfordert Fähigkeit, unvollständige Information zu repräsentieren und logisch zu schließen

• Aussagenlogik kann Wumpus-Welt im Prinzip repräsentieren, ist aber viel zu umständlich

•–––––

–•

•