IKI 30320: Sistem Cerdas Kuliah 10: Logical Agents

IKI30320 Kuliah 10 10 Okt 2007 Ruli Manurung Knowledgebased agent Contoh: Wumpus World Logic Propositional logic Metode pembuktian

IKI 30320: Sistem Cerdas Kuliah 10: Logical Agents Ruli Manurung Fakultas Ilmu Komputer Universitas Indonesia

Ringkasan

10 Oktober 2007

Outline IKI30320 Kuliah 10 10 Okt 2007 Ruli Manurung

1

Knowledge-based agent

Knowledgebased agent

2

Contoh: Wumpus World

3

Logic

4

Propositional logic

5

Metode pembuktian

6

Ringkasan

Contoh: Wumpus World Logic Propositional logic Metode pembuktian Ringkasan


1



2


3

Logic

4

Propositional logic

5

Metode pembuktian

6

Ringkasan


Pentingnya pengetahuan IKI30320 Kuliah 10 10 Okt 2007 Ruli Manurung Knowledgebased agent Contoh: Wumpus World Logic Propositional logic Metode pembuktian

Problem solving agent: memilih solusi di antara kemungkinan yang ada. Apa yang ia “ketahui” tentang dunia tidak berkembang → problem solution (initial state, successor function, goal test) Knowledge-based agent: lebih “pintar”. Ia “mengetahui” hal-hal tentang dunia dan dapat melakukan reasoning (berpikir, bernalar) mengenai: Hal-hal yang tidak diketahui sebelumnya (imperfect/partial information) Tindakan yang paling baik untuk diambil

Ringkasan

Inference engine

domain−independent algorithms

Knowledge base

domain−specific content

Knowledge-based agent IKI30320 Kuliah 10 10 Okt 2007 Ruli Manurung

Knowledge Base: apa yang “diketahui” oleh si agent


Pendekatan deklaratif membangun agent: “beritahu” informasi yang relevan, simpan dalam KB → (T ELL).


Agen dapat ditanya (atau bertanya diri sendiri) apa yang sebaiknya dilakukan berdasarkan KB → (A SK). Sebuah knowledge-based agent harus bisa: Merepresentasikan world, state, action, dst. Menerima informasi baru (dan meng-update representasinya) Menyimpulkan pengetahuan lain yang tidak eksplisit (hidden property) Menyimpulkan action apa yang perlu diambil

Knowledge Base IKI30320 Kuliah 10 10 Okt 2007 Ruli Manurung

Knowledge Base: Knowledgebased agent Contoh: Wumpus World Logic Propositional logic Metode pembuktian Ringkasan

Himpunan representasi fakta yang diketahui tentang lingkungannya Tiap fakta disebut sentence. Dinyatakan dalam bahasa formal → bisa diolah T ELL: menambahkan sentence baru ke KB.

Inference Engine: Menentukan fakta baru yang dapat diturunkan dari pengetahuan yang sudah ada dalam KB. Menjawab pertanyaan (A SK) berdasarkan KB yang sudah.

Representasi IKI30320 Kuliah 10 10 Okt 2007 Ruli Manurung Knowledgebased agent Contoh: Wumpus World Logic Propositional logic Metode pembuktian Ringkasan

Agent dapat dipandang dari knowledge level: informasi apa yang diketahuinya? Mis: sebuah robot “mengetahui” bahwa gedung B ada di antara gedung A dan gedung C. Agent dapat dipandang dari implementation level: bagaimana representasi informasi yang diketahuinya? Logical sentence: di_antara(gdB,gdA,gdC) Natural language: “Gedung B ada di antara gedung A dan gedung C” Tabel posisi koordinat gedung-gedung Gambar diagram peta Fasilkom (bitmap? vector?)

Pilihan representasi berpengaruh thd. apa yang bisa dilakukan oleh inference engine.

Pendekatan deklaratif vs. prosedural IKI30320 Kuliah 10 10 Okt 2007 Ruli Manurung Knowledgebased agent Contoh: Wumpus World Logic Propositional logic Metode pembuktian Ringkasan

Programmer memberitahu (T ELL) agent informasi tentang environment. Kalau informasi kurang, agent bisa melengkapinya sendiri. Bandingkan dengan pendekatan prosedural: programmer secara eksplisit memrogram agent untuk bertindak. Kalau program tidak benar ... ? (error?) Ini adalah masalah knowledge representation: bagaimana representasi yang tepat? Expressive: bisa menyatakan fakta tentang environment Tractable: bisa diolah/diproses inference engine (dg. cepat?)

Knowledge is power Representation + Reasoning = Intelligence!


1



2


3

Logic

4

Propositional logic

5

Metode pembuktian

6

Ringkasan


Aturan Main Wumpus World IKI30320 Kuliah 10 10 Okt 2007 Ruli Manurung Knowledgebased agent Contoh: Wumpus World Logic Propositional logic Metode pembuktian Ringkasan

Performance measure: emas +1000, mati -1000, gerak -1, panah -10 Environment: Matriks 4x4 kamar. Initial state [1,1]. Ada gold, wumpus dan pit yang lokasinya dipilih secara acak. Percept: Breeze: kamar di samping lubang jebakan ada hembusan angin Glitter: kamar di mana ada emas ada kilauan/sinar Smell: kamar di samping Wumpus berbau busuk Action: maju, belok kiri 90◦ , kanan 90◦ , tembak panah (hanya 1!), ambil benda

4

Breeze

Stench

Breeze

3

Stench

PIT

Breeze

PIT

Gold

2

Breeze

Stench

Breeze

1

Breeze

PIT START

1

2

3

4

Sifat Wumpus World IKI30320 Kuliah 10 10 Okt 2007 Ruli Manurung Knowledgebased agent Contoh: Wumpus World Logic Propositional logic Metode pembuktian Ringkasan

(Fully) observable? Tidak, hanya bisa persepsi lokal Deterministic? Ya, hasil tindakan jelas & pasti Episodic? Tidak, tergantung action sequence Static? Ya, gold, wumpus, pit tidak bergerak Discrete? Ya Single agent? Tidak

Menjelajahi Wumpus World IKI30320 Kuliah 10 10 Okt 2007 Ruli Manurung Knowledgebased agent Contoh: Wumpus World Logic Propositional logic

OK

Metode pembuktian Ringkasan

OK

OK A

Menjelajahi Wumpus World IKI30320 Kuliah 10 10 Okt 2007 Ruli Manurung Knowledgebased agent Contoh: Wumpus World Logic Propositional logic Metode pembuktian

B

OK A

Ringkasan

OK A

OK

Menjelajahi Wumpus World IKI30320 Kuliah 10 10 Okt 2007 Ruli Manurung Knowledgebased agent

P?

Contoh: Wumpus World Logic Propositional logic Metode pembuktian

B

OK

P?

OK

OK

A

Ringkasan

A

Menjelajahi Wumpus World IKI30320 Kuliah 10 10 Okt 2007 Ruli Manurung Knowledgebased agent

P?

Contoh: Wumpus World Logic Propositional logic Metode pembuktian

B

OK

P?

OK S

OK

A

Ringkasan

A

A


P?

P B

OK

P? OK

OK S

OK

A

Ringkasan

A

A

W


P?

P B

OK A

P? OK A

Ringkasan

OK S A

OK A

W


P?

OK

OK

P? OK

P B A

OK

A

Ringkasan

OK S A

OK A

W


P?

OK

P B

OK A

P? BGS OK OK A A

Ringkasan

OK S A

OK A

W


1



2


3

Logic

4

Propositional logic

5

Metode pembuktian

6

Ringkasan


Knowledge representation language IKI30320 Kuliah 10 10 Okt 2007 Ruli Manurung Knowledgebased agent Contoh: Wumpus World Logic Propositional logic Metode pembuktian Ringkasan

Knowledge representation language (KRL): bahasa yang digunakan untuk menyatakan fakta tentang “dunia”. Syntax: aturan yang mendefinisikan sentence yang sah dalam bahasa Semantics: aturan yang mendefinisikan “arti” sebuah sentence, mis: kebenaran sentence di dalam dunia

Contoh KRL: bahasa aritmetika IKI30320 Kuliah 10 10 Okt 2007 Ruli Manurung Knowledgebased agent Contoh: Wumpus World Logic Propositional logic Metode pembuktian Ringkasan

Syntax: x + 2 ≥ y adalah kalimat sah. x2 + y ≥ bukan kalimat sah.

Semantics: x + 2 ≥ y benar jhj bilangan x + 2 tidak lebih kecil dari bilangan y : x + 2 ≥ y benar dalam “dunia” di mana x = 7, y = 1 x + 2 ≥ y salah dalam “dunia” di mana x = 0, y = 6

Contoh KRL: bahasa Indonesia IKI30320 Kuliah 10 10 Okt 2007 Ruli Manurung Knowledgebased agent Contoh: Wumpus World Logic Propositional logic Metode pembuktian Ringkasan

Syntax: “Jakarta adalah ibukota Indonesia” adalah kalimat sah. “Ibu Indonesia kota Jakarta adalah” bukan kalimat sah.

Semantics: “X adalah ibukota Y ” benar jhj X adalah pusat pemerintahan negara Y . “Jakarta adalah ibukota Indonesia” benar dalam “dunia” kita sekarang. “Jakarta adalah ibukota Indonesia” salah dalam “dunia” th. 1948 (Yogya? Bukittinggi?).

Logika sebagai KRL IKI30320 Kuliah 10 10 Okt 2007 Ruli Manurung Knowledgebased agent Contoh: Wumpus World Logic Propositional logic Metode pembuktian Ringkasan

Logics: bahasa formal untuk merepresentasikan fakta sedemikian shg. kesimpulan (fakta baru, jawaban) dapat ditarik. Ada banyak metode inference yang diketahui. Kita bisa membangun agent Wumpus World dengan logika: memanfaatkan perkembangan logika oleh ahli matematika, filsafat selama ratusan tahun!

Entailment IKI30320 Kuliah 10 10 Okt 2007 Ruli Manurung Knowledgebased agent Contoh: Wumpus World Logic Propositional logic Metode pembuktian Ringkasan

Entailment berarti sesuatu fakta bisa disimpulkan dari (kumpulan) fakta lain. KB |= α: KB entails sentence α jhj α true dalam semua “dunia” di mana KB true. Contoh: KB mengandung sentence “Anto ganteng” dan “Ani cantik”. KB |= α1 : “Anto ganteng dan Ani cantik” KB 2 α2 : “Anto pintar” x + y = 4 |= 4 = x + y

Inference/reasoning IKI30320 Kuliah 10 10 Okt 2007 Ruli Manurung Knowledgebased agent Contoh: Wumpus World Logic

Inference, atau reasoning: pembentukan fakta (sentence) baru yang meng-entail fakta-fakta lama. Reasoning bukan dilakukan pada fakta di dunia (semantics), melainkan representasi fakta dalam KRL si agent (syntax). Otak manusia melakukan proses reasoning dalam suatu bentuk syntax!

Propositional logic

Sentences

World

Aspects of the real world

Sentence Entails

Follows

Semantics

Representation

Ringkasan

Semantics

Metode pembuktian

Aspect of the real world

Model IKI30320 Kuliah 10 10 Okt 2007 Ruli Manurung Knowledgebased agent Contoh: Wumpus World Logic

Model: sebuah “dunia” di mana kebenaran suatu sentence bisa diuji. m adalah model α jika α true di “dalam” m. M(α) adalah himpunan semua model dari α KB |= α jhj M(KB) ⊆ M(α) Mis: KB= Anto ganteng dan Ani cantik. α = Anto ganteng.

Propositional logic Metode pembuktian

x

x

x

x

x

M(

x

x

)

x

Ringkasan

x

x x

x

x

x xx x x x

x

x

x x

x

x x

xx x

x

x x

M(KB) x

x x

x

x

x

x x

x

x x

x

x

x x

Entailment dalam Wumpus World IKI30320 Kuliah 10 10 Okt 2007

Setelah melihat [1,1] OK, [2,1] Breeze:

Ruli Manurung Knowledgebased agent Contoh: Wumpus World Logic Propositional logic

? ?

Metode pembuktian Ringkasan

B A

A

?

Model jebakan di [2,1],[2,2],[3,1]: 3 pilihan boolean → 8 kemungkinan model.

Model (sebagian) Wumpus World IKI30320 Kuliah 10 10 Okt 2007

PIT

2 2

Ruli Manurung

Breeze

1

Breeze

PIT

1

1

Knowledgebased agent Contoh: Wumpus World

1

2

2

3

3

2

PIT

PIT

2

2 Breeze

PIT

1

Breeze

1

Breeze

1

Logic

1

2

1 1

2

2

PIT

PIT

PIT

2

Breeze

1

Breeze

PIT

1

2

PIT

PIT 1

Ringkasan

3

3


2

3

1

2

3 Breeze

PIT

1

1

2

3

2

3


PIT

2 2

Ruli Manurung

Breeze

1

Breeze

PIT

1


1 1

KB

2

2

3

3

2

PIT

PIT

2

2 Breeze

PIT

1

Breeze

1

Breeze

1

Logic

1

2

1 1

2

2

PIT

PIT

PIT

2

Breeze

1

Breeze

PIT

1

2

PIT

PIT 1

Ringkasan

3

3


2

3

1

2

2

3

3 Breeze

PIT

1

1

2

3

KB = pengamatan (percept) + aturan main Wumpus World


PIT

2 2

Ruli Manurung

Breeze

1

Breeze

PIT

1


1 1

KB

2

2

3

3

1 2

PIT

PIT

2

2 Breeze

PIT

1

Breeze

1

Breeze

1

Logic

1

2

1 1

2

2

PIT

PIT

PIT

2

Breeze

1

Breeze

PIT

1

2

PIT

PIT 1

Ringkasan

3

3


2

3

1

2

2

3

3 Breeze

PIT

1

1

2

3

α1 = “Kamar [1,2] aman”, KB |= α1 , dibuktikan dengan model checking: periksa semua kemungkinan M(KB), M(α1 )


PIT

2 2

Ruli Manurung

Breeze

1

Breeze

2

PIT

1

1


1

KB

2

2

3

3

2

PIT

PIT

2

2 Breeze

PIT

1

Breeze

1

Breeze

1

Logic Propositional logic Metode pembuktian

1

2

2

3

3 1

2

3

2

PIT

PIT

PIT

2

Breeze

1

Breeze

PIT

1

2

PIT

PIT 1

1

Ringkasan

1

2

3 Breeze

PIT

1

1

α2 = “Kamar [2,2] aman”, KB 2 α2

2

3

2

3

Inference IKI30320 Kuliah 10 10 Okt 2007 Ruli Manurung Knowledgebased agent Contoh: Wumpus World Logic Propositional logic Metode pembuktian Ringkasan

Inference adalah proses/algoritma yang “menurunkan” fakta baru dari fakta-fakta lama. KB ì α: sentence α bisa diturunkan dari KB oleh prosedur i Soundness: i dikatakan sound jika untuk semua KB ì α, KB |= α benar Completeness: i dikatakan sound jika untuk semua KB |= α, KB ì α benar Preview! Kita akan melihat sebuah logic, first-order logic, yang cukup ekspresif untuk menyatakan fakta-fakta, dan memiliki prosedur inference yang sound dan complete! Prosedur ini bisa menjawab semua pertanyaan yang jawabannya “terkandung” dalam KB.


1



2


3

Logic

4

Propositional logic

5

Metode pembuktian

6

Ringkasan


Propositional logic IKI30320 Kuliah 10 10 Okt 2007 Ruli Manurung Knowledgebased agent Contoh: Wumpus World Logic Propositional logic Metode pembuktian Ringkasan

Propositional logic adalah logic yang paling sederhana Sebuah sentence dinyatakan sebagai propositional symbol P1 , P2 , dst. Syntax Jika S adalah kalimat, ¬S adalah kalimat (negation) Jika S1 dan S2 adalah kalimat, S1 ∧ S2 adalah kalimat (conjunction) Jika S1 dan S2 adalah kalimat, S1 ∨ S2 adalah kalimat (disjunction) Jika S1 dan S2 adalah kalimat, S1 ⇒ S2 adalah kalimat (implication) Jika S1 dan S2 adalah kalimat, S1 ⇔ S2 adalah kalimat (biconditional)

Semantics dari propositional logic IKI30320 Kuliah 10 10 Okt 2007 Ruli Manurung Knowledgebased agent Contoh: Wumpus World Logic Propositional logic Metode pembuktian Ringkasan

Sebuah model memberi menilai true/false terhadap setiap proposition, mis: P1,2 P2,2 P3,1 true true false (Semua 8 model yang mungkin bisa dijabarkan) Aturan menentukan kebenaran sebuah kalimat terhadap m: ¬S S1 ∧ S2 S1 ∨ S2 S1 ⇒ S2 dkl. S1 ⇔ S2

true iff true iff true iff true iff false iff true iff

S S1 S1 S1 S1 S1 ⇒ S2

false true and true or false or true and true and

S2 S2 S2 S2 S2 ⇒ S1

true true true false true

Sebuah proses rekursif bisa mengevaluasi kalimat sembarang: ¬P1,2 ∧ (P2,2 ∨ P3,1 ) = true ∧ (false ∨ true) = true ∧ true = true

Kalimat representasi Wumpus World IKI30320 Kuliah 10 10 Okt 2007 Ruli Manurung Knowledgebased agent Contoh: Wumpus World Logic Propositional logic Metode pembuktian Ringkasan

Semantics: Pi,j = true kalau ada lubang jebakan (pit) di [i, j]. Bi,j = true kalau ada hembusan angin (breeze) di [i, j].

Aturan main: kamar di samping lubang jebakan ada hembusan angin B1,1 ⇔ (P1,2 ∨ P2,1 ) B2,1 ⇔ (P1,1 ∨ P2,2 ∨ P3,1 )

Hasil pengamatan (percept): ¬P1,1 ¬B1,1 B2,1

Inference dengan truth-table IKI30320 Kuliah 10 10 Okt 2007 Ruli Manurung Knowledgebased agent Contoh: Wumpus World Logic Propositional logic Metode pembuktian Ringkasan

Kita dapat membuktikan apakah KB |= α1 menggunakan truth table. Ini adalah sejenis model checking. B1,1 false false .. . false false false false false .. . true

B2,1 false false .. . true true true true true .. . true

P1,1 false false .. . false false false false false .. . true

P1,2 false false .. . false false false false false .. . true

P2,1 false false .. . false false false false true .. . true

P2,2 false false .. . false false true true false .. . true

P3,1 false true .. . false true false true false .. . true

KB false false .. . false true true true false .. . false

α1 true true .. . true true true true true .. . false

Prosedur inference dengan truth-table IKI30320 Kuliah 10 10 Okt 2007 Ruli Manurung Knowledgebased agent Contoh: Wumpus World Logic Propositional logic Metode pembuktian Ringkasan

function TT-E NTAILS ?(KB, α) returns true or false symbols ← a list of the proposition symbols in KB and α return TT-C HECK -A LL(KB, α, symbols, [ ]) function TT-C HECK -A LL(KB, α, symbols, model) returns true or false if E MPTY ?(symbols) then if PL-T RUE ?(KB, model) then return PL-T RUE ?(α, model) else return true else do P ← F IRST(symbols); rest ← R EST(symbols) return TT-C HECK -A LL(KB, α, rest, E XTEND(P, true, model) and TT-C HECK -A LL(KB, α, rest, E XTEND(P, false, model)

Inference dengan menjabarkan seluruh truth table adalah sound dan complete. Untuk n symbol → O(2n ). NP complete _ ¨

Logical equivalence IKI30320 Kuliah 10 10 Okt 2007 Ruli Manurung Knowledgebased agent Contoh: Wumpus World Logic Propositional logic Metode pembuktian Ringkasan

Dua kalimat logically equivalent jhj mereka benar dalam model yang sama: α ≡ β jhj α |= β dan β |= α (α ∧ β) (α ∨ β) ((α ∧ β) ∧ γ) ((α ∨ β) ∨ γ) ¬(¬α) (α ⇒ β) (α ⇒ β) (α ⇔ β) ¬(α ∧ β) ¬(α ∨ β) (α ∧ (β ∨ γ)) (α ∨ (β ∧ γ))

≡ ≡ ≡ ≡ ≡ ≡ ≡ ≡ ≡ ≡ ≡ ≡

(β ∧ α) (β ∨ α) (α ∧ (β ∧ γ)) (α ∨ (β ∨ γ)) α (¬β ⇒ ¬α) (¬α ∨ β) ((α ⇒ β) ∧ (β ⇒ α)) (¬α ∨ ¬β) (¬α ∧ ¬β) ((α ∧ β) ∨ (α ∧ γ)) ((α ∨ β) ∧ (α ∨ γ))

commutativity of ∧ commutativity of ∨ associativity of ∧ associativity of ∨ double-negation elimination contraposition implication elimination biconditional elimination de Morgan de Morgan distributivity of ∧ over ∨ distributivity of ∨ over ∧

Validity dan Satisfiability IKI30320 Kuliah 10 10 Okt 2007 Ruli Manurung Knowledgebased agent Contoh: Wumpus World Logic Propositional logic Metode pembuktian Ringkasan

Sebuah kalimat valid jika ia true dalam semua model Mis.: “Hari ini hujan atau hari ini tidak hujan”. Deduction Theorem KB |= α jika dan hanya jika (KB ⇒ α) valid Sebuah kalimat satisfiable jika ada model di mana ia true Mis.: “Hari ini hujan”. Sebuah kalimat unsatisfiable jika tidak ada model di mana ia true Mis.: “Hari ini hujan dan hari ini tidak hujan”. Reductio ad absurdum (proof by contradiction) KB |= α jika dan hanya jika (KB ∧ ¬α) unsatisfiable


1



2


3

Logic

4

Propositional logic

5

Metode pembuktian

6

Ringkasan


Rules of Inference IKI30320 Kuliah 10 10 Okt 2007 Ruli Manurung Knowledgebased agent Contoh: Wumpus World Logic Propositional logic Metode pembuktian Ringkasan

Sebuah inference rule adalah pola syntax yang dapat menurunkan sebuah kalimat baru yang sah (sound). Rule yang paling terkenal adalah modus ponens:

α⇒β

,

α

β Contoh rule lain: and elimination:

α∧β α

dan

α∧β β

Semua logical equivalence juga bisa dipakai sebagai inference rule. Untuk membuktikan KB |= α, kita bisa mencari serangkaian inference rule yang hasil akhirnya adalah α. Jika kita gunakan semua inference rule sebagai operator → algoritma search biasa! Seringkali bisa jauh lebih efisien dari penjabaran truth-table → tidak tergantung ukuran KB (monotonicity).

Jenis-jenis metode pembuktian IKI30320 Kuliah 10 10 Okt 2007 Ruli Manurung Knowledgebased agent Contoh: Wumpus World Logic Propositional logic Metode pembuktian Ringkasan

Secara umum, ada 2 jenis: Pengaplikasian inference rule Hasilkan kalimat baru yang sah (sound) dari yang lama Bukti (proof): serangkaian pengaplikasian inference rule Inference rule sebagai operator → algoritma search. Biasanya, kalimat harus diterjemahkan ke dalam sebuah normal form

Model checking Penjabaran truth table (eksponensial dalam n) Backtracking lebih efisien, mis: algoritma DPLL Heuristic search dalam model space (sound tapi incomplete), mis: min-conflicts hill-climbing

Horn Form IKI30320 Kuliah 10 10 Okt 2007 Ruli Manurung Knowledgebased agent Contoh: Wumpus World Logic Propositional logic Metode pembuktian Ringkasan

Horn Form: KB = conjunction of Horn Clauses Horn Clause: Proposition symbol (Conjunction of symbols) → symbol

Mis: C ∧ (B ⇒ A) ∧ (C ∧ D ⇒ B) Modus ponens pada Horn Form (complete pada Horn KB):

α1 ,...,αn

,

α1 ∧...∧αn ⇒β β

Bisa digunakan dengan algoritma forward chaining atau backward chaining.

Forward chaining IKI30320 Kuliah 10 10 Okt 2007 Ruli Manurung Knowledgebased agent Contoh: Wumpus World

Ide dasar

Q

Aplikasikan rule yang premise-nya diketahui benar dalam KB, tambah conclusion ke dalam KB, ulangi sampai query (Q) terbukti.

P

Logic Propositional logic Metode pembuktian Ringkasan

Mis: P⇒Q L∧M ⇒P B∧L⇒M A∧P ⇒L A∧B ⇒L A B

M L

A

B

Algoritma Forward Chaining IKI30320 Kuliah 10 10 Okt 2007 Ruli Manurung

Algorithm Forward Chaining Knowledgebased agent Contoh: Wumpus World Logic Propositional logic Metode pembuktian Ringkasan

function PL-FC-E NTAILS ?(KB, q) returns true or false local variables: count, a table, indexed by clause, initially the number of premises inferred, a table, indexed by symbol, each entry initially false agenda, a list of symbols, initially the symbols known to be true while agenda is not empty do p ← P OP(agenda) unless inferred[p] do inferred[p] ← true for each Horn clause c in whose premise p appears do decrement count[c] if count[c] = 0 then do if H EAD[c] = q then return true P USH(H EAD[c], agenda) return false

Forward chaining IKI30320 Kuliah 10 10 Okt 2007

Q

Ruli Manurung

1


P


2

Logic

M

Propositional logic

2

Metode pembuktian

L

Ringkasan

2

2 A

B


Q

Ruli Manurung

1


P


2

Logic

M

Propositional logic

2

Metode pembuktian

L

Ringkasan

1

1 A

B


Q

Ruli Manurung

1


P


2

Logic

M

Propositional logic

1

Metode pembuktian

L

Ringkasan

1

0 A

B


Q

Ruli Manurung

1


P


1

Logic

M

Propositional logic

0

Metode pembuktian

L

Ringkasan

1

0 A

B


Q

Ruli Manurung

1


P


0

Logic

M

Propositional logic

0

Metode pembuktian

L

Ringkasan

1

0 A

B


Q

Ruli Manurung

0


P


0

Logic

M

Propositional logic

0

Metode pembuktian

L

Ringkasan

0

0 A

B


Q

Ruli Manurung

0


P


0

Logic

M

Propositional logic

0

Metode pembuktian

L

Ringkasan

0

0 A

B


Q

Ruli Manurung

0


P


0

Logic

M

Propositional logic

0

Metode pembuktian

L

Ringkasan

0

0 A

B

Backward chaining IKI30320 Kuliah 10 10 Okt 2007 Ruli Manurung Knowledgebased agent Contoh: Wumpus World Logic Propositional logic Metode pembuktian Ringkasan

Ide dasar Untuk membuktikan query q: periksa jika q sudah diketahui, atau secara rekursif, buktikan semua premise rule yang conlusion-nya q. Hindari loop: periksa apakah subgoal yang baru sudah ada di goal stack Hindari mengulang pekerjaan: periksa apakah subgoal yang baru sudah dibuktikan benar, atau sudah dibuktikan salah.

Backward chaining IKI30320 Kuliah 10 10 Okt 2007

Q

Ruli Manurung Knowledgebased agent

P

Contoh: Wumpus World Logic

M


L

Ringkasan

A

B


Q


P


M


L

Ringkasan

A

B


Q


P


M


L

Ringkasan

A

B


Q


P


M


L

Ringkasan

A

B


Q


P


M


L

Ringkasan

A

B


Q


P


M


L

Ringkasan

A

B


Q


P


M


L

Ringkasan

A

B


Q


P


M


L

Ringkasan

A

B


Q


P


M


L

Ringkasan

A

B


Q


P


M


L

Ringkasan

A

B

Forward vs. Backward Chaining IKI30320 Kuliah 10 10 Okt 2007 Ruli Manurung Knowledgebased agent Contoh: Wumpus World Logic Propositional logic Metode pembuktian Ringkasan

Forward Chaining adalah pendekatan data-driven, bottom-up → pemrosesan informasi secara tak sadar (unconscious processing) Mis: mengenali obyek (indera penglihatan) Melakukan banyak usaha/kerja yang tidak relevan terhadap goal. Backward chaining adalah pendekatan goal-driven, top-down → pemrosesan informasi secara sadar (conscious processing) Mis: Bagaimana saya ke Bucharest? lulus kuliah cepat? Kompleksitas BC bisa jauh lebih kecil dari linear dalam ukuran KB.

Resolution IKI30320 Kuliah 10 10 Okt 2007 Ruli Manurung Knowledgebased agent Contoh: Wumpus World Logic Propositional logic Metode pembuktian Ringkasan

Conjunctive Normal Form (CNF): conjunction of disjunction of literals mis: (A ∨ ¬B) ∧ (B ∨ ¬C ∨ ¬D) Resolution inference rule (untuk CNF):

`1 ∨...∨`k , m1 ∨...∨mn `1 ∨...∨ì−1 ∨ì+1 ∨...∨`k ∨m1 ∨...∨mj−1 ∨mj+1 ∨...∨mn di mana ì dan mj adalah complementary literal (mis: P dan ¬P). Contoh:

P1,3 ∨P2,2 , P1,3

¬P2,2

Resolution adalah sound dan complete untuk propositional logic!

P?

P B

OK A

P? OK A

OK S A

OK A

W

Pembuktian dengan resolution IKI30320 Kuliah 10 10 Okt 2007

Untuk membuktikan apakah KB |= α:

Ruli Manurung

Terjemahkan KB dan α ke dalam CNF.


Lakukan proof by contradiction: buktikan (KB ∧ ¬α) adalah unsatisfiable


Algoritma Resolution function PL-R ESOLUTION(KB, α) returns true or false clauses ← the set of clauses in the CNF representation of KB ∧ ¬α new ← { } loop do for each Ci , Cj in clauses do resolvents ← PL-R ESOLVE(Ci , Cj ) if resolvents contains the empty clause then return true new ← new ∪ resolvents if new ⊆ clauses then return false clauses ← clauses ∪ new

Contoh Resolution IKI30320 Kuliah 10 10 Okt 2007 Ruli Manurung Knowledgebased agent

Contoh: KB = (B1,1 ⇔ (P1,2 ∨ P2,1 )) ∧ ¬B1,1 α = ¬P1,2


B1,1 P1,2 P2,1

P2,1 B1,1

B1,1

P1,2 B1,1

P2,1

P1,2

Propositional logic Metode pembuktian Ringkasan

B1,1 P1,2 B1,1

P1,2 P2,1

B1,1 P2,1 B1,1

P1,2

P1,2 P2,1

P2,1

P1,2


1



2


3

Logic

4

Propositional logic

5

Metode pembuktian

6

Ringkasan


Ringkasan IKI30320 Kuliah 10 10 Okt 2007 Ruli Manurung Knowledgebased agent Contoh: Wumpus World Logic Propositional logic Metode pembuktian Ringkasan

Knowledge-based agent menggunakan inference pada knowledge base untuk menghasilkan informasi baru atau mengambil keputusan. Konsep-konsep dasar logika sebagai knowedge representation language: Syntax: struktur kalimat bahasa formal Semantics: arti kalimat sebagai kebenaran terhadap model Entailment: menyimpulkan kalimat baru yang benar Inference: proses menurunkan kalimat baru dari kalimat-kalimat lama Soundness: proses menurunkan hanya kalimat yang di-entail Completeness: proses menurunkan SEMUA kalimat yang di-entail Forward, backward chaining: proses inference complete dan linear untuk Horn form Resolution: inference rule yang complete untuk propositional logic Baca bab 7 buku Russell & Norvig

IKI 30320: Sistem Cerdas Kuliah 10: Logical Agents

Recommend Documents