Übersicht Wissensbasierte Agentenki.informatik.uni-wuerzburg.de/teach/documents/KI/skript/Kap07.6.pdf · 1 Künstliche Intelligenz: 7. Logische Agenten Frank Puppe 1 Übersicht I

1

Künstliche Intelligenz: 7. Logische Agenten Frank Puppe 1

Übersicht

I Künstliche IntelligenzII ProblemlösenIII Wissen und Schlussfolgern

7. Logische Agenten8. Prädikatenlogik 1. Stufe9. Schließen in der Prädikatenlogik 1. Stufe10. Wissensrepräsentation

IV Logisch HandelnV Unsicheres Wissen und SchließenVI LernenVII Kommunizieren, Wahrnehmen und Handeln


Vorteile wissensbasierter Agenten:• Eleganter Umgang mit nur teilweise beobachtbaren Umgebun-

gen: Aus Wahrnehmungen und Wissen kann der Weltzustand präzisiert werden (Bsp.: Med. Diagnose, Sprachverstehen)

• Neue Aufgaben als explizit beschriebene Ziele• Schneller Kompetenzerwerb durch Mitteilung oder Lernen• Adaption an Umweltänderungen durch WissensadaptionenGrundstruktur wissensbasierter Agenten:In jedem Zeittakt:1. Speichere Wahrnehmung in Wissensbasis (Tell) 2. Leite eine Aktion aus Wissensbasis her (Ask) 3. Führe die Aktion aus4. Speichere Aktion in Wissensbasis (Tell)

Wissen lässt sich gut in Logik formulieren!

Wissensbasierte Agenten


Wissensbasis (knowledge base): Enthält Repräsentationen von Fakten über die Welt.

Satz (sentence): Eine individuelle Repräsentation.

Wissensrepräsentation(ssprache) (knowledge representationlanguage): Sprache, in der die Sätze formuliert werden.

Tell und Ask: Hinzufügen neuer Sätze und Abfragen von Sätzen, die aus dem vorhandenen Wissen folgen.

Inferenz(mechanismus) (inference): Mechanismus, mit dem neue Sätze aus den bekannten Sätzen hergeleitet werden.

Hintergrundwissen (background knowledge): Apriorivorhandenes Wissen in der Wissensbasis

Allgemeiner Entwurf eines Agenten (1)


3 Ebenen, auf denen ein Wissensbasierter Agent beschrieben werden kann:

1. Wissensebene (Epistemologische Ebene): Ein Agent weiß etwas, z.B. daß die Friedensbrücke den Ostteil und den Westteil von Würzburg verbindet.

2. Logische Ebene: Ebene, in der das Wissen in Sätzen beschrieben ist, z.B. "verbindet (Friedensbrücke, Ostwürzburg, Westwürzburg)".

3. Implementationsebene: Implementierung der logischen Ebene, z.B. als Array, verzeigerte Liste, Prädikat, ...Deklarative Systementwicklung: Wissensbasis wird aufge-baut, indem dem System ein Satz nach dem anderen mitgeteilt wird (oder es Sätze aufgrund von Wahrnehmungen lernt).Prozedurale Systementwicklung: Direkte Programmierung des Verhaltens als Programmcode

Allgemeiner Entwurf eines Agenten (2)


WUMPUS-Welt

Die WUMPUS-Welt ist ein Höhlensystem mit durch Gänge verbundenen Höhlen. Darin gibt es Gold, aber auch einen drachenähnlichen WUMPUS sowie Löcher (pits), aus denen man sich nicht befreien kann. Von benachbarten Feldern kann man den WUMPUS riechen, die Löcher durch einen Windzug (breeze) spüren. Den WUMPUS kann man mit einem Pfeil töten.


PEAS-Beschreibung der WUMPUS-Welt• Performance Measure: 1000 Punkte für das Gold, -1000

Punkte, wenn man in ein Loch fällt oder vom WUMPUS gefressen wird, -1 Punkt für jeden Schritt und -10 Punkte für das Verschießen des Pfeils.

• Environment: 4*4 Matrix von Höhlen. Der Agent startet im Feld [1,1]. Der Ort des WUMPUS und des Goldes werden per Zufall gewählt. Jedes Feld kann ein Loch mit der Wahrscheinlichkeit von 20% sein.

• Aktuatoren: Sich um 90o drehen, einen Schritt vorwärts gehen (hat keinen Effekt bei Wand), Sterben in Löchern und beim WUMPUS, Das Gold grabschen, Schießen (nur einmal).

• Sensoren: Der Agent hat 5 boolsche Sensoren: Riechen (stench), Luftzug spüren (breeze), Glitzern sehen (glitter), sich an einer Wand stoßen (bump), den Todesschrei des WUMPUS hören (scream), die als 5-Tupel repräsentiert sind.

2


Schließen & Handeln in der WUMPUS - Welt (1)


Schließen & Handeln in der WUMPUS - Welt (2)


(Gegen-) Beispiel für logisches Schließen


Syntax und Semantik

Wenn eine Wissensbasis in der realen Welt wahr ist, dann sind auch alle daraus mit einer wahrheitserhaltenden (sound) Inferenzprozedurhergeleiteten Sätze in der Welt wahr!


• Syntax der Repräsentationssprache: spezifiziert wohlgeformte Sätze z.B. x+y=4 ist wohlgeformt, xy4+= ist nicht wohlgeformt.

• Semantik der Repräsentationssprache: definiert die Wahrheit von Sätzen hinsichtlich möglicher Welten (Modellen), z.B. x+y=4 ist wahr im Modell mit x=2 & y=2, aber falsch im Modell mit x=1 & y=1.

• Entailment (logische Implikation): α |= β bedeutet, dass in jedem Modell, in dem α wahr ist, auch β wahr ist, z.B. (x+y=4) |= (4=y+x)

• Inferenzprozedur i: WB |-i α bedeutet, dass aus der Wissensbasis WB die Inferenzprozedur den Satz α herleitet

- wahrheitserhaltend (sound): WB |-i α nur dann, wenn WB |= α- vollständig (complete): i kann alle Sätze herleiten, die logisch

folgern• Model Checking: Eine Inferenzprozedur, die alle Modelle aufzählt

und darin die Schlussfolgerung überprüft (sound & complete).• Beweis: Folge von Inferenzschritten zur Herleitung eines Satzes• Grounding: Verbindung zwischen Logik und realer Welt des

Agenten; teils über Sensoren (Fakten), teils über Lernen (Regeln)

Grundlegende Konzepte der Logik


Metapher für Entailment und Inferenz

"Nadel im Heuhaufen"•Heuhaufen: Alle Konsequenzen, die aus einer Wissensbasis

logisch folgern.•Nadel: Eine bestimmter Satz α• Entailment: Die Nadel α ist im Heuhaufen • Inferenzprozedur: Verfahren, die Nadel zu finden.• Wahrheitserhaltende Inferenzprozedur: findet nur Nadeln,

die wirklich im Heuhaufen sind• Vollständige Inferenzprozedur: findet alle Nadeln im

Heuhaufen (bei endlichen Heuhaufen ist model checkingvollständig).

3


Bsp. für Model Checking in WUMPUS-Welt


Eine Logik besteht aus einem formalen System mit Syntax und Semantik sowie einer Beweistheorie.

Zwei wichtige Logiken sind die Aussagenlogik und die Prädikatenlogik:

• Aussagenlogik: Fakten und Konnektoren• Prädikatenlogik 1. Stufe: Objekte, Prädikate, Konnektoren,

Quantoren

Ontologische Annahmen: beziehen sich auf die RealitätEpistemologische Annahmen: beziehen sich auf Wissen von Agenten

Logiken


Ontologische und epistemologische Annahmen


• Syntax (nächste Folie [nF])

• Semantik (nF + 1)

• Test auf Tautologien (nF + 2)

• Inferenzregeln (nF + 3/4)

• Komplexität von Inferenzen in Aussagenlogik (NP-vollständig)

• Monotonie: if KB1 |= a then KB1 ∪ KB2 |= a

• Hornklausel: P1 ∧ P2 ∧ ... ∧ Pn ⇒ Q

• Lineare Komplexität von Inferenzen mit Hornklauseln

Aussagenlogik


Syntax der Aussagenlogik

Konvention: Man kann die Klammern auch weglassen, wenn die Bedeutung eindeutig ist; dann gelten Präzedenzregeln für die Konnektoren in obiger Reihenfolge (¬ ∧ ∨ ⇒ ⇔);


Semantik der Aussagenlogik

Wahrheitstabelle für die fünf Konnektoren

4


Beweis von Tautologien• Tautologien: gültige (valid) Sätze, die immer gelten (d.h. in

allen Modellen)• unerfüllbare (unsatisfiable) Sätze, die nie gelten (d.h. in

keinem Modell)• erfüllbare (satisfiable) Sätze, die in manchen Modellen gelten

Tautologien können einfach mittels Wahrheitstabellen überprüft werden:


Logische ÄquivalenzenKönnen leicht über die Wahrheitstabelle bewiesen werden!(α, β und γ stehen für beliebige logische Sätze)


Inferenzregeln der Aussagenlogik

Modus Ponens: Wenn α ⇒ β und α gelten, dann kann β hergeleitet werden:

Und-Eliminierung: Von einer Konjunktion können Teile entfernt werden:

Unit-Resolution: Wenn in einer Disjunktionein Teil falsch ist, muss der restliche Teil wahr sein:

Weiterhin sind alle logischen Äquivalenzen (s. letzte Folie) als Inferenzregeln geeignet.


Wissensbasis der AgentenSei S1,2: Geruch (Stench) auf Feld [1,2];

B2,1: Luftzug (Breeze) auf [2,1].Dann ist die Wissensbasis nach diesen beiden Wahrnehmungen:¬S1,1 , ¬S2,1 , S1,2 , ¬B1,1 , B2,1 , ¬B1,2


Finden des WUMPUSR1: ¬S1,1 ⇒ ¬W1,1∧¬W2,1∧ ¬W1,2 ;R2: ¬S2,1 ⇒ ¬W1,1∧¬W2,1∧¬W2,2∧¬W3,1

R3:¬S1,2⇒¬W1,1∧¬W1,2∧¬W2,2∧¬W1,3; R4: S1,2⇒W1,3∨ W1,2∨ W2,2∨ W1,1


Resolution• Die bisherigen Inferenzregeln sind zwar wahrheitserhaltend,

aber ihre Vollständigkeit haben wir nicht analysiert.• Sie können durch eine einzige Inferenzregel ersetzt werden, die

wahrheitserhaltend und vollständig ist: Resolution

• Resolutionsregel mit 2 Klauseln:

• allgemeine Resolutionsregel (li und mi sind komplementäre Literale):

• Resolution kann zwar nicht alle wahren Sätze aufzählen, aber entscheiden, ob ein Satz wahr oder falsch ist →Widerspruchsbeweis: um zu zeigen, dass (WB |= α), zeige dass (WB ∧ ¬α) unerfüllbar ist.

5


Konjunktive Normalform (KNF)

• Die Resolutionsregel erfordert eine Disjunktion von Literalen.• Jeder Satz kann in eine Konjunktion von Disjunktionen von

Literalen umgeformt werden (d.h. in konjunktive Normalform), d.h. in (l1,1 ∨ … l1,k) ∧ … ∧ (ln,1 ∨ … ln,m)

• Umwandlungsprozedur:1. Ersetze alle ⇔, indem (a ⇔ b) durch (a ⇒ b) ∧ (b ⇒ a)

ersetzt wird2. Ersetze alle ⇒, indem (a ⇒ b) durch (¬a ∨ b) ersetzt wird3. Ersetze alle ¬, die nicht vor Literalen stehen, mit 3 Regeln:

¬(¬a) ≡ a; ¬(a ∨ b) ≡ (¬a ∧ ¬b); ¬(a ∧ b) ≡ (¬a ∨ ¬b);4. Bewege ∨ mit Distributivgesetzen nach innen.


Beispiel für Umformung in KNF

Ausgangssatz:

1. Ersetze ⇔:

2. Ersetze ⇒:

3. Ersetze äußere ¬:

4. Bewege ∨:


Beispiel für Ableitung mittels ResolutionUm in der Startkonfiguration der WUMPUS-Welt zu zeigen, dass kein Loch (Pit) im Feld (1,2) ist, weil kein Luftzug (breeze) auf (1,1) ist (¬B1,1), wird zunächst die Regel B1,1 ⇔ P1,2 ∨ P2,1 in Klau-selnormalform (konjunktive Normalform) umgewandelt (s. letzte Folie) und dann ¬P1,2 durch Widerspruchsbeweis gezeigt, d.h. die Frage wird negiert (¬ ¬ P1,2 = P1,2), der Klauselmenge hinzugefügt und eine leere Klauselmenge hergeleitet (ganz rechts).


Vorwärts- und Rückwärtsverkettung• Vereinfachung der Resolution: Statt Klauseln Hornklauseln• Hornklausel als Regel: (l1 ∧ l2 ∧ … ∧ ln ⇒ l), d.h. eine Klausel mit

höchstens einem nicht-negierten Literal: (¬l1 ∨ ¬l2 ∨ … ∨ ¬ln ∨ l)• Hornklausel ohne nicht-negiertes Literals heißt auch Fakt.• Inferenzen mit Hornklauseln erfordern nur lineare Zeit (zur

Größe der Wissensbasis).• Zwei Algorithmen:

– Vorwärtsverkettung: Prüfe bei allen Regeln, ob deren Vor-bedingung erfüllt ist, und füge dann Nachbedingung zu (Ein-zel)Fakten hinzu, bis keine neuen Fakten mehr herleitbar sind

– Rückwärtsverkettung: Ausgehend von einer Anfrage (Einzelfakt) werden die Regeln überprüft, die das Fakt herleiten können. Wenn bei deren Vorbedingungen Fakten unbekannt sind, wiederhole Prozedur rekursiv.


Vorwärtsverkettungs-Algorithmus PL-FC-Entails?• Noch nicht verarbeitete wahre Symbole werden auf Agenda notiert

und nach ihrer Herleitung genau einmal bearbeitet.• Regeln haben Zähler für Anzahl unerfüllter Vorbedingungen, die bei

Erfüllung erniedrigt werden → wenn Zähler = 0 kann die Regel feuern.


Beispiel für Vorwärtsverkettung

• Als Und-Oder-Graph dargestellte Wissensbasis für Vorwärtsverkettung

6


Ein vollständiger Backtracking Algorithmus• DPLL: Davis-Putnam-Logemann-Loveland Algorithmus• Eine rekursive, tiefensuch-basierte Aufzählung aller möglichen

Modelle für den Satz der Anfrage• 3 Verbesserungen zur vollständigen Aufzählung

– Frühe Terminierung:• Eine (disjunktive) Klausel ist wahr, wenn irgendein Literal wahr ist.• Eine (konjunktiver) Satz ist wahr, wenn alle Klauseln wahr sind z.B.

(A v C) ∧ (A v B) ist wahr, wenn A wahr ist. • Ein Satz ist falsch, wenn irgendeine Klausel falsch ist.

– Pure Symbol Heuristic: Ein Symbol ist "pure", wenn es nur mit einem Vorzeichen (d.h. nur negiert oder nur nicht-negiert) vorkommt. Wenn ein Satz ein Modell hat, dann nur dann, wenn das negierte Symbol auf "falsch" bzw. das nicht-negierte auf "wahr" gesetzt wird.

– Unit Clause Heuristic: Eine Unit Clause enthält nur ein Literal. Bevor andere Literale ausprobiert werden, werden erst alle Unit Clauses auf wahr bzw. falsch gesetzt und deren Werte propagiert.


Hill-Climbing Algorithmus für Erfüllbarkeit • Grundidee: Wähle zufällig komplette Belegung aller Variablen

(ein Modell) und ändere den Wert einzelner Variablen so lange, bis alle Klauseln erfüllt sind (oder ein Schwellwert erreicht ist).

• Kriterien zur Auswahl der zu ändernden Variable:1. Sie soll in einer bisher nicht erfüllten Klausel vorkommen.2. Sie soll die Anzahl der bisher nicht erfüllten Klauseln

möglichst stark reduzieren (vgl. Min-Conflicts-Heuristik).3. Sie soll auch ein gewisses Zufallselement enthalten (wie bei

Simulated Annealing, zur Vermeidung lokaler Minima)• Umsetzung der Kriterien in WalkSAT-Algorithmus:

– Wähle unerfüllte Klausel (Kriterium 1)– Wähle mit gewisser Wahrscheinlichkeit p zufällig ein

Symbol (Kriterium 3) oder wähle das Symbol, das die Anzahl erfüllter Klauseln maximiert (Kriterium 2)


Bewertung von WalkSAT• Nicht vollständig• Aber in der Praxis sehr

erfolgreich• Wenn nach gewisser Zeit

keine Lösung für ein Erfüllbarkeitsproblem gefunden wurde, kann man die Heuristik verwenden, dass es keine Lösung gibt.

• Vergleich WalkSAT und DPLL bei 100 zufällig generierten erfülbaren 3-KNF-Problemen (d.h. KNF mit jeweils 3 Litera-len pro Klausel): s. rechts

Praxis: Problemlöser wie CHAFF kön-nen Tausende von Symbolen & Millionen von Klauseln routinemäßig bearbeiten


Anwendung auf WUMPUS-Welt• Schließen: In jeder Situation schließt der Agent aufgrund seiner

Wahrnehmungen und seinen Regeln für jedes Feld, ob es sicher, tödlich oder unsicher (d.h. weder sicher noch tödlich) ist.

• Planen: Wenn der Agent eine Glitzern sieht, nimmt er das Gold, sonst geht er auf ein sicheres Feld oder falls es keines gibt, auf ein unsicheres Feld.

• Handeln: Den kürzesten Weg von seiner aktuellen Position zum anvisierten Feld findet der Agent durch eine A*-Suche, wobei nur bekannte Felder besucht werden.

• Probleme:– Für jedes Feld müssen gesonderte Regeln existieren, obwohl

diese gleichartig sind (aber durch Schema generierbar).– Der Übergang von einer Situation zur nächsten erfolgt

außerhalb der Logik-Welt in einem Verwaltungsprogramm.


Vermeiden von nicht-logischen Elementen

• Indexieren aller Regeln mit Situationen sowie Formulierung der Situationsübergänge mit Zusatzregeln: sehr aufwändig

• Schaltkreis-basierte Agenten (circuit-based agents) • Benutzung einer aussagekräftigeren Logik: Prädikatenlogik

1. Stufe.

Documents

Übersicht Wissensbasierte Agentenki.informatik.uni-wuerzburg.de/teach/documents/KI/skript/Kap07.6.pdf · 1 Künstliche Intelligenz: 7. Logische Agenten Frank Puppe 1 Übersicht I