logical agentsnurul_nusyirwan.staff.gunadarma.ac.id/downloads/files/...logical agents @ kecerdasan...

62
Logical Agents Chastine Fatichah Teknik Informatika Institut Teknologi Sepuluh Nopember November 2012 12/10/2012 1 / 62 Logical Agents @ Kecerdasan Buatan (KI092301) Kecerdasan Buatan (KI092301)

Upload: others

Post on 20-Oct-2020

11 views

Category:

Documents


0 download

TRANSCRIPT

  • Logical Agents

    Chastine Fatichah

    Teknik Informatika

    Institut Teknologi Sepuluh Nopember

    November 2012

    12/10/2012 1 / 62 Logical Agents @ Kecerdasan Buatan (KI092301)

    Kecerdasan Buatan (KI092301)

  • Pokok Bahasan

    • Knowledge-based agents • Contoh: Wumpus world • Logic • Propositional logic • Equivalence, validity, satisfiability • Inference rules dan metode pembuktian

    • forward chaining • backward chaining • resolution

    12/10/2012 2/ 62 Logical Agents @ Kecerdasan Buatan (KI092301)

  • Outline

    • Knowledge-based agents • Contoh: Wumpus world • Logic • Propositional logic • Equivalence, validity, satisfiability • Inference rules dan metode pembuktian

    • forward chaining • backward chaining • resolution

    12/10/2012 3 / 62

    Logical Agents @ Kecerdasan Buatan (KI092301)

  • Knowledge bases

    • Knowledge base (pengetahuan) = sekumpulan kalimat pada sebuah bahasa formal

    • Pendekatan deklaratif membangun agent : • Beritahu informasi yg relevan, simpan dalam KB (Tell) •

    • Agen dapat ditanya (bertanya pd diri sendiri) apa yang sebaiknya dilakukan berdasarkan KB (Ask)

    • Agen dapat ditunjukkan level pengetahuan Contoh: apa yg mereka ketahui, bagaimana implementasinya

    Atau level implementasi • Contoh: struktur data pada KB dan algoritma-algoritma yang

    memanipulasi

    12/10/2012 4 Logical Agents @ Kecerdasan Buatan (KI092301)

  • Knowledge-based Agent

    • Agen harus dapat: • Merepresentasikan state, action, dll. • Menerima informasi baru • Mengupdate representasi • Menyimpulkan pengetahuan lain yang tidak eksplisit (hidden

    property)

    • Menyimpulkan action apa yang perlu diambil 12/10/2012 5 Logical Agents @ Kecerdasan Buatan (KI092301)

  • Outline

    • Knowledge-based agents • Contoh: Wumpus world • Logic • Propositional logic • Equivalence, validity, satisfiability • Inference rules dan metode pembuktian

    • forward chaining • backward chaining • resolution

    12/10/2012 6 Logical Agents @ Kecerdasan Buatan (KI092301)

  • Wumpus World Performance measure

    emas +1000, mati -1000

    gerak -1 , panah -10

    Environment

    Squares adjacent to wumpus are smelly

    Squares adjacent to pit are breezy

    Glitter iff gold is in the same square

    Shooting kills wumpus if you are facing it

    Shooting uses up the only arrow

    Grabbing picks up gold if in same square

    Releasing drops the gold in same square

    Sensors: Stench, Breeze, Glitter, Bump, Scream

    Actuators: Left turn, Right turn, Forward, Grab, Release, Shoot

    12/10/2012 7 Logical Agents @ Kecerdasan Buatan (KI092301)

  • Karakteristik Wumpus world

    • Fully Observable No – hanya local persepsi • Deterministic Yes – keluaran yg bisa

    dispesifikasikan secara tepat

    • Episodic No – sequential pada level aksi • Static Yes – Wumpus dan Pits tidak bergerak • Discrete Yes • Single-agent? Yes – Wumpus mmepunyai fitur

    alami

    12/10/2012 8 Logical Agents @ Kecerdasan Buatan (KI092301)

  • Exploring a wumpus world

    12/10/2012 9 Logical Agents @ Kecerdasan Buatan (KI092301)

  • Exploring a wumpus world

    12/10/2012 10 Logical Agents @ Kecerdasan Buatan (KI092301)

  • Exploring a wumpus world

    12/10/2012 11 Logical Agents @ Kecerdasan Buatan (KI092301)

  • Exploring a wumpus world

    12/10/2012 12 Logical Agents @ Kecerdasan Buatan (KI092301)

  • Exploring a wumpus world

    12/10/2012 13 Logical Agents @ Kecerdasan Buatan (KI092301)

  • Exploring a wumpus world

    12/10/2012 14 Logical Agents @ Kecerdasan Buatan (KI092301)

  • Exploring a wumpus world

    12/10/2012 15 Logical Agents @ Kecerdasan Buatan (KI092301)

  • Exploring a wumpus world

    12/10/2012 16 Logical Agents @ Kecerdasan Buatan (KI092301)

  • Logic

    • Logic adalah bahasa formal untuk merepresentasikan informasi sedemikian hingga kesimpulan dapat dibuat

    • Syntax mendefinisikan kalimat-kalimat pada bahasa • Semantics mendefinisikan arti kalimat;

    misal, mendefinisikan kebenaran sebuah kalimat

    • Contoh, bahasa aritmatika • x+2 ≥ y is a sentence; x2+y > is not a sentence • x+2 ≥ y is true iff the number x+2 is no less than the number y • x+2 ≥ y is true in a world where x = 7, y = 1 • x+2 ≥ y is false in a world where x = 0, y = 6 •

    12/10/2012 17 Logical Agents @ Kecerdasan Buatan (KI092301)

  • Entailment

    • Entailment artinya bahwa sesuatu mengikuti dari yang lain

    KB ╞

    • • Knowledge base KB entails kalimat α jika dan

    hanya jika α adalah true pada semua dunia dimana KB bernilai true

    • Misal, KB “the Giants won” dan “the Reds won” entails “Either the Giants won or the Reds won”

    • Misal, x+y = 4 entails 4 = x+y • Entailment adalah sebuah hubungan antar kalimat (

    syntax) yang didasarkan pada semantics 12/10/2012 18 Logical Agents @ Kecerdasan Buatan (KI092301)

  • Models

    • m adalah sebuah model pada sebuah kalimat α jika α bernilai true pada m

    • M(α) adalah kumpulan semua model pada α •

    • KB ╞ α iff M(KB) M(α) • Misal:

    • KB = Giants won and Reds won

    • α = Giants won •

    12/10/2012 19 Logical Agents @ Kecerdasan Buatan (KI092301)

  • Entailment pada wumpus world

    Situasi setelah deteksi

    nothing in [1,1], moving

    right, breeze in [2,1]

    Kemungkinan semua model

    pada KB yang

    mengasumsikan hanya

    ada pits

    3 Boolean terpilih 8

    possible models

    12/10/2012 20 Logical Agents @ Kecerdasan Buatan (KI092301)

  • Wumpus models

    12/10/2012 21 Logical Agents @ Kecerdasan Buatan (KI092301)

  • Wumpus models

    • KB = wumpus-world rules + observations • 12/10/2012 22 Logical Agents @ Kecerdasan Buatan (KI092301)

  • Wumpus models

    • KB = wumpus-world rules + observations • α1 = "[1,2] is safe", KB ╞ α1, proved by model checking • •

    12/10/2012 23 Logical Agents @ Kecerdasan Buatan (KI092301)

  • Wumpus models

    • KB = wumpus-world rules + observations

    12/10/2012 24 Logical Agents @ Kecerdasan Buatan (KI092301)

  • Wumpus models

    • KB = wumpus-world rules + observations • α2 = "[2,2] is safe", KB ╞ α2 • 12/10/2012 25 Logical Agents @ Kecerdasan Buatan (KI092301)

  • Inference

    • KB ├i α = kalimat α dapat diderivasi dari KB dengan prosedur I

    • Soundness: i adalah sound jika KB ├i α, bernilai juga benar pada KB╞ α

    • Completeness: i adalah complete jika KB╞ α, bernilai juga benar pada KB ├i α

    12/10/2012 26 Logical Agents @ Kecerdasan Buatan (KI092301)

  • Propositional logic: Syntax

    • Propositional logic adalah logika paling sederhana – menggambarkan ide dasar

    • Simbol proposisi P1, P2 dll adalah sebuah kalimat

    • If S is a sentence, S is a sentence (negation) • • If S1 and S2 are sentences, S1 S2 is a sentence (conjunction) • • If S1 and S2 are sentences, S1 S2 is a sentence (disjunction) • • If S1 and S2 are sentences, S1 S2 is a sentence (implication) • • If S1 and S2 are sentences, S1 S2 is a sentence (biconditional) • 12/10/2012 27 Logical Agents @ Kecerdasan Buatan (KI092301)

  • Logika Propositional: Semantics

    Tiap model menspesifikasikan true/false untuk setiap simbol proposisi

    Misal:P1,2 P2,2 P3,1 false true false

    Dengan simbol ini, 8 possible models, dapat digenerate secara otomatis

    Rule untuk mengevaluasi nilai kebenaran dengan model m:

    S is true iff S is false

    S1 S2 is true iff S1 is true and S2 is true

    S1 S2 is true iff S1is true or S2 is true

    S1 S2 is true iff S1 is false or S2 is true

    i.e., is false iff S1 is true and S2 is false

    S1 S2 is true iff S1S2 is true andS2S1 is true

    Proses recursif sederhana mengevaluasi sebuah kalimat, misal

    P1,2 (P2,2 P3,1) = true (true false) = true true = true

    12/10/2012 28 Logical Agents @ Kecerdasan Buatan (KI092301)

  • Tabel kebenaran untuk

    konektifitas

    12/10/2012 29 Logical Agents @ Kecerdasan Buatan (KI092301)

  • Kalimat pada Wumpus world

    Let Pi,j be true if there is a pit in [i, j].

    Let Bi,j be true if there is a breeze in [i, j].

    P1,1 B1,1 B2,1

    • "Pits cause breezes in adjacent squares” B1,1 (P1,2 P2,1)

    B2,1 (P1,1 P2,2 P3,1)

    12/10/2012 30 Logical Agents @ Kecerdasan Buatan (KI092301)

  • Tabel Kebenararan untuk

    inference

    12/10/2012 31 Logical Agents @ Kecerdasan Buatan (KI092301)

  • Inference dengan enumeration

    • Untuk n symbol, waktu kompleksitas adalah O(2n), space kompleksitas adalah O(n)

    • 12/10/2012 32 Logical Agents @ Kecerdasan Buatan (KI092301)

  • Logical equivalence

    • Dua kalimat adalah logically equivalent iff bernilai true pada model yang sama: α ≡ ß iff α╞ β and β╞ α

    12/10/2012 33 Logical Agents @ Kecerdasan Buatan (KI092301)

  • Validity dan satisfiability

    Sebuah kalimat adalah valid jika bernilai true pada semua model,

    Misal, True, A A, A A, (A (A B)) B

    Validity dihubungkan ke inference melalui Deduction Theorem:

    KB ╞ α if and only if (KB α) is valid

    Sebuah kalimat adalah satisfiable jika bernilai true pada beberapa model Misal: A B, C

    Sebuah kalimat adalah unsatisfiable jika bernilai salah pada semua model Misal: AA

    Satisfiability dihubungkan ke inference melalui : KB ╞ α if and only if (KB α) is unsatisfiable

    12/10/2012 34 Logical Agents @ Kecerdasan Buatan (KI092301)

  • Resolution Conjunctive Normal Form (CNF)

    conjunction of disjunctions of literals

    clauses

    E.g., (A B) (B C D)

    • Resolution inference rule (for CNF): •

    li … lk, m1 … mn

    li … li-1 li+1 … lk m1 … mj-1 mj+1 ... mn

    dimana li dan mj adalah complementary literals.

    Misal: P1,3 P2,2, P2,2

    P1,3

    12/10/2012 35 Logical Agents @ Kecerdasan Buatan (KI092301)

  • Resolution

    Soundness of resolution inference rule:

    (li … li-1 li+1 … lk) li

    mj (m1 … mj-1 mj+1 ... mn)

    (li … li-1 li+1 … lk) (m1 … mj-1 mj+1 ... mn)

    12/10/2012 36 Logical Agents @ Kecerdasan Buatan (KI092301)

  • Konversi ke CNF

    B1,1 (P1,2 P2,1)β

    1. Eliminate , replacing α β with (α β)(β α). (B1,1 (P1,2 P2,1)) ((P1,2 P2,1) B1,1)

    2. Eliminate , replacing α β with α β. (B1,1 P1,2 P2,1) ((P1,2 P2,1) B1,1)

    3. Move inwards using de Morgan's rules and double-negation: (B1,1 P1,2 P2,1) ((P1,2 P2,1) B1,1)

    4. Apply distributivity law ( over ) and flatten: (B1,1 P1,2 P2,1) (P1,2 B1,1) (P2,1 B1,1)

    12/10/2012 37 Logical Agents @ Kecerdasan Buatan (KI092301)

  • Algortima Resolution

    12/10/2012 38 Logical Agents @ Kecerdasan Buatan (KI092301)

  • Resolution example

    • KB = (B1,1 (P1,2 P2,1)) B1,1 α = P1,2 •

    12/10/2012 39 Logical Agents @ Kecerdasan Buatan (KI092301)

  • Forward and backward chaining

    • Horn Form (restricted) KB = conjunction of Horn clauses

    • Horn clause = • proposition symbol; or • (conjunction of symbols) symbol

    • E.g., C (B A) (C D B) •

    • Modus Ponens (for Horn Form): complete for Horn KBs •

    α1, … ,αn, α1 … αn β

    β

    • Can be used with forward chaining or backward chaining. • These algorithms are very natural and run in linear time • 12/10/2012 40 Logical Agents @ Kecerdasan Buatan (KI092301)

  • Forward chaining

    • Ide: sembarang rule yang memiliki premise yang satisfy dalam KB,

    • Tambahkan kesimpulan ke KB, sampai query ditemukan

    12/10/2012 41 Logical Agents @ Kecerdasan Buatan (KI092301)

  • Algortima Forward chaining

    12/10/2012 42 Logical Agents @ Kecerdasan Buatan (KI092301)

  • Contoh Forward chaining

    12/10/2012 43 Logical Agents @ Kecerdasan Buatan (KI092301)

  • Contoh Forward chaining

    12/10/2012 44 Logical Agents @ Kecerdasan Buatan (KI092301)

  • Contoh Forward chaining

    12/10/2012 45 Logical Agents @ Kecerdasan Buatan (KI092301)

  • Contoh Forward chaining

    12/10/2012 46 Logical Agents @ Kecerdasan Buatan (KI092301)

  • Forward chaining example

    12/10/2012 47 Logical Agents @ Kecerdasan Buatan (KI092301)

  • Contoh Forward chaining

    12/10/2012 48 Logical Agents @ Kecerdasan Buatan (KI092301)

  • Contoh Forward chaining

    12/10/2012 49 Logical Agents @ Kecerdasan Buatan (KI092301)

  • Contoh Forward chaining

    12/10/2012 50 Logical Agents @ Kecerdasan Buatan (KI092301)

  • Backward chaining

    Ide: bekerja backwards dari query q:

    membuktikan q dengan BC, cek jika q sudah diketahui, atau

    buktikan dengan BC semua premise pada beberapa rule concluding q

    Avoid loops: chek jika subgoal baru sudah siap pada stack tujuan

    Avoid repeated work: check if new subgoal

    telah terbukti benar, atau

    telah gagal

    12/10/2012 51 Logical Agents @ Kecerdasan Buatan (KI092301)

  • Contoh Backward chaining

    12/10/2012 52 Logical Agents @ Kecerdasan Buatan (KI092301)

  • Contoh Backward chaining

    12/10/2012 53 Logical Agents @ Kecerdasan Buatan (KI092301)

  • Contoh Backward chaining

    12/10/2012 54 Logical Agents @ Kecerdasan Buatan (KI092301)

  • Contoh Backward chaining

    12/10/2012 55 Logical Agents @ Kecerdasan Buatan (KI092301)

  • Contoh Backward chaining

    12/10/2012 56 Logical Agents @ Kecerdasan Buatan (KI092301)

  • Contoh Backward chaining

    12/10/2012 57 Logical Agents @ Kecerdasan Buatan (KI092301)

  • Contoh Backward chaining

    12/10/2012 58 Logical Agents @ Kecerdasan Buatan (KI092301)

  • Contoh Backward chaining

    12/10/2012 59 Logical Agents @ Kecerdasan Buatan (KI092301)

  • Contoh Backward chaining

    12/10/2012 60 Logical Agents @ Kecerdasan Buatan (KI092301)

  • Contoh Backward chaining

    12/10/2012 61 Logical Agents @ Kecerdasan Buatan (KI092301)

  • 12/10/2012 Logical Agents @ Kecerdasan Buatan (KI092301) 62

    Sumber :

    1.Slide perkuliahan Stuart Russell's (Berkeley) http://aima.cs.berkeley.edu/

    http://aima.cs.berkeley.edu/