Logical Agents. Chastine Fatichah. Teknik Informatika Institut Teknologi Sepuluh Nopember November 2012

Kecerdasan Buatan (KI092301)

Logical Agents Chastine Fatichah Teknik Informatika Institut Teknologi Sepuluh Nopember November 2012

12/10/2012

Logical Agents @ Kecerdasan Buatan (KI092301)

1 / 62

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

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

Knowledge bases

• •

Knowledge base (pengetahuan) = sekumpulan kalimat pada sebuah bahasa formal Pendekatan deklaratif membangun agent :

• •

Agen dapat ditanya (bertanya pd diri sendiri) apa yang sebaiknya dilakukan berdasarkan KB  (Ask) Agen dapat ditunjukkan level pengetahuan

• •

Beritahu informasi yg relevan, simpan dalam KB  (Tell)

Contoh: apa yg mereka ketahui, bagaimana implementasinya Atau level implementasi • Contoh: struktur data pada KB dan algoritma-algoritma yang memanipulasi 12/10/2012


4

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

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

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

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

Exploring a wumpus world

12/10/2012


9


12/10/2012


10


12/10/2012


11


12/10/2012


12


12/10/2012


13


12/10/2012


14


12/10/2012


15


12/10/2012


16

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

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

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

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

Wumpus models

12/10/2012


21

Wumpus models

• KB = wumpus-world rules + observations • 12/10/2012


22

Wumpus models

• • • •

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

12/10/2012


23

Wumpus models

• KB = wumpus-world rules + observations 12/10/2012


24

Wumpus models

• KB = wumpus-world rules + observations • α2 = "[2,2] is safe", KB ╞ α2 • 12/10/2012


25

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

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

Logika Propositional: Semantics Tiap model menspesifikasikan true/false untuk setiap simbol proposisi Misal:P1,2 false

P2,2 true

P3,1 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 S1S2 is true andS2S1 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

Tabel kebenaran untuk konektifitas

12/10/2012


29

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  B2,1 

12/10/2012

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


30

Tabel Kebenararan untuk inference

12/10/2012


31

Inference dengan enumeration

• •

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

12/10/2012


32

Logical equivalence •

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

12/10/2012


33

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: AA

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

12/10/2012


34

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

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

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 doublenegation: (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

Algortima Resolution

12/10/2012


38

Resolution example

• KB = (B1,1  (P1,2 P2,1))  B1,1 α = P1,2 •

12/10/2012


39

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

Forward chaining •

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

•

Tambahkan kesimpulan ke KB, sampai query ditemukan

12/10/2012


41

Algortima Forward chaining

12/10/2012


42

Contoh Forward chaining

12/10/2012


43


12/10/2012


44


12/10/2012


45


12/10/2012


46

Forward chaining example

12/10/2012


47


12/10/2012


48


12/10/2012


49


12/10/2012


50

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

Contoh Backward chaining

12/10/2012


52


12/10/2012


53


12/10/2012


54


12/10/2012


55


12/10/2012


56


12/10/2012


57


12/10/2012


58


12/10/2012


59


12/10/2012


60


12/10/2012


61

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

12/10/2012


62

Logical Agents. Chastine Fatichah. Teknik Informatika Institut Teknologi Sepuluh Nopember November 2012

Recommend Documents